@yangyuhan12138
其实这样做的目的就是不需要所有线程同时 take 啊，不发生冲突就不会有入 sync 的问题，我的原意只是让进入 sync 尽量少即可说明问题。

当然我想复杂了，因为 aqs 是两年前看的内容了，今天临时翻了下细节不熟悉，搞得我想成进入 sync 后就不会出来，忘记后面还有一个 await 会释放锁从而最终所有 node 都会出 sync 了。

@yangyuhan12138 哦，你说的这个也对，await 的时候会释放锁，从而不在 sync 队列里面了。从这个方面来说也是对的。

@yangyuhan12138 又想了下，直接 sleep 一次也是可以说明问题，因为上面没有活跃线程，那么在 unfair lock 的情况下，无论是加锁还是超时都应该一次抢到，因此不用进入 sync 队列, 这个逻辑说的通。

不过公平锁还是可以通过自己拷贝一份 Queue 然后换掉来测试，当然似乎没有这个必要了～

@yangyuhan12138 如果你指主线程再 poll 前只 sleep 一下我认为不能说明问题，这个只影响上面的线程是否执行完毕全部进入阻塞状态，而不影响进入 sync 队列的 node 数量。你这样对测试结果反而看起来更像线程太多影响调度导致而不是 node 太多导致。

如果指的是每次 submit 前 sleep 一下才有说服力是 node 太多导致的。

非公平锁也不能测试啊，你拷贝一份 queue 的代码把锁换了，而且可以测试更多自定义的操作。

@yangyuhan12138

关于 1，我的意思是线程本身没有执行完，不是说线程没有创建完。

其它部分又仔细看了下代码，你说的应该是对的。一开始看的不仔细。

要验证下应该也比较容易，只需要确保每一个 take 都直接执行到 await 那里，这样就不会因为 lock 进入 sync 队列了。

这个应该可以通过在 take 前面加一个 flag 用来告知主线程这里快执行到 take 了，然后再 sleep 一小会。之后再执行下一个 submit。

这种情况下进入 sync 队列的应该非常少或者没有，来对比下会不会出现误差大的情况。

但是多说一句，这么大线程数量的情况下，任何 poll 不可靠都是符合逻辑的，因为 os 调度总需要线程时间...虽然这个 case 里面让别的线程暂时 sleep 住了。实际场景中应该不需要考虑这种情况。

@yangyuhan12138 我在 mac 上试了下，由于 mac 线程数量的限制，我只能用 4000 个线程去试，没有能复现你说的现象。

另外我又看了下 aqs 的代码，
take 应该是一直放在 condition 队列里面，因为没有被唤醒或者超时，不会进入 sync。
poll （ 1000 ）则应该是一开始进入 condition，超时后进入 sync 队列。

那么在 sync 里面其实就只有一个元素，不会有很多 node 去争抢锁。而 condition queue 则和队列大小没有明显关系，超时是通过 park （ timeout ）+自旋来实现的，和其他节点无关。

有没有可能是你上面 submit 的循环在后台线程实际没有执行完，所以下面的 poll 等的时候实际上还有很多线程不停创建，由于线程太多，os 调度的时候不停切换，很多没有执行到 sleep 哪一步，所以导致 poll 误差太大？你在 poll 直接 sleep 一段时间看看呢

@yangyuhan12138 你这个几秒完全没有根据啊，你前面得有多少 node 才会有这么大误差？我觉得完全没有必要考虑这种不切实际的情况

会超过，但是 nanosecond 的精度很高了，差异很小，这就是为什么这个 api 要用纳秒做参数的原因，实际中应该可以忽略误差。

@dusu 原来是集群那你扩大分片不就行了，怎么会有 100g 呢？你说的集群是主从？

你这个限制比较多，又要省钱....要不自己搭建一个 mongo 集群，要不自己搭建 ssdb 集群（运维成本，改动小点），要不试试阿里云混合存储 redis ？

写入是指更新还是增加一个 key ？ hash 数量会变化吗？ latency 要求是啥

看样子，这个岗位是类似平台入口侧的？

@690690 能稍微说下嘛？比如说钱，这个 jd 上的薪资会用什么方式打折扣？

@690690 这个有啥坑？

你为啥要盯着重庆，趁年轻去北京或者别的一线见识见识多好，重庆 it 比成都都差远了

直观上的理解似乎是 a 个元素取 k 个数，但是这 k 个数又是可以重复的且存在全序关系，因此除了第一个数，再增加 k-1 个数，代表当每一个数需要选的和前一个数一样的那种可能？感觉不太严格，虽然结果肯定是对的

@keith1126 数学归纳法就更加靠猜测了，直接程度还不如我从杨辉三角联想到组合数的性质来推导，至少不太跳跃。

@ssynhtn 如果只做到我在一楼给出来的程度是完全可以的。
推了下这个公式，大概思路是联想到类似杨辉三角的性质，然后引入组合数的性质 c （ n，k ）= c （ n-1，k ）+ c （ n-1，k-1 ），类似于一楼 f 的递推公式，然后想办法把 n 和 i 凑到这个组合数上面来就得到了结果。但是整个思路有点类似于靠猜想和凑的思路，不知道正解推导的思路是啥（硬算？）

我给一个思路吧，不知是否可行：
1. 分解问题，令 f （ x，k ）代表从数字 x 进行变换 k 次之后的数列长度，k 从 0 开始

2. f 的动态规划方程可以这样：
f （ x，k ）= f （ 1，k - 1 ）+ f （ 2，k -1 ）+ ... f （ x - 1，k - 1 ）
f （ x-1，k ）= f （ 1，k-1 ）+ ... f （ x-1，k-1 ）
所以有 f （ x，k ）= f （ x-1，k ）+ f （ x，k-1 ）
计算出来的复杂度是 O （ xk ），这是预处理的过程。

3. 假设需要查询位置 p，令 g （ x，k，p ）为题目所求，即变化后的数列的第 p 项，这个时候遍历 f （ 1，k-1 ），f （ 2，k-1 ）... f （ x，k-1 ）并维护当前数列的长度（也就是 sum ）
找到 p 所在的位置 t，假设前面长度为 sum，则问题可以直接规约到 g （ t，k-1，p - sum ）
这一步的时间复杂度是 O （ x ）

4. 不断递降可以将 k 降低到 1，一共需要 k 次，因此总复杂度是 O （ xk ）

5. 对于 k 为 1 的情况，结果是显然的。

6. 第三步的复杂度可以进一步降低，通过预处理求出 f 数列前缀和，那么可以进行二分查找找到第一个大于 p 的一项，降低为 logx