p**r
发帖数: 5853 | 1 不是啥面试问题，
是俺，街头派遇到实际问题，请教各路学院大神指点算法：
大概情况如下：
N个List |
l*******m
发帖数: 1096 | 2 这么短，不用优化
【在 p**r 的大作中提到】
: 不是啥面试问题，
: 是俺，街头派遇到实际问题，请教各路学院大神指点算法：
: 大概情况如下：
: N个List
|
n*****t
发帖数: 22014 | 3 下室派不认为还有比两分更好的算法，唯一的改进也就是设法知道长度
【在 p**r 的大作中提到】
: 不是啥面试问题，
: 是俺，街头派遇到实际问题，请教各路学院大神指点算法：
: 大概情况如下：
: N个List
|
d******e
发帖数: 2265 | 4 经典面试题。
递归：
1, 2, 4,8 ...直到 2 ^n false
从2^n-1开始1, 2 ,4 ,8,知道 false
.....
【在 p**r 的大作中提到】
: 不是啥面试问题，
: 是俺，街头派遇到实际问题，请教各路学院大神指点算法：
: 大概情况如下：
: N个List
|
g*****g
发帖数: 34805 | 5 有当然是有的，比如并发检查可以做到 logN。只不过10000个没啥必要。
【在 n*****t 的大作中提到】
: 下室派不认为还有比两分更好的算法，唯一的改进也就是设法知道长度
|
d*******r
发帖数: 3299 | 6 到底是
case-1. List |
p**r
发帖数: 5853 | 7 只是举例而已，100，1000，1000，多打0多累。
【在 l*******m 的大作中提到】
: 这么短，不用优化
|
p**r
发帖数: 5853 | 8 多谢下作派，长度不但无法确定，而且一直在变。
【在 n*****t 的大作中提到】
: 下室派不认为还有比两分更好的算法，唯一的改进也就是设法知道长度
|
p**r
发帖数: 5853 | 9 没看懂，大神解释一下？
【在 d******e 的大作中提到】
: 经典面试题。
: 递归：
: 1, 2, 4,8 ...直到 2 ^n false
: 从2^n-1开始1, 2 ,4 ,8,知道 false
: .....
|
N********n
发帖数: 8363 | 10
二分法 is of logN and already very quick.
【在 p**r 的大作中提到】
: 没看懂，大神解释一下？
|
|
|
p*******n
发帖数: 2697 | 11 我替他解释下吧。他的做法是一种二分的优化，可以把复杂度从logN降到logK，N是总
长，K是出现false的那个长度，K
他的1， 2，4，8。。是开始指数级的增长一直找到出现false为止的，停，假设是第M
，K<＝M<＝N。然后在前M个数中二分。
【在 p**r 的大作中提到】
: 没看懂，大神解释一下？
|
p*******n
发帖数: 2697 | 12 这种做法对长度未知，或者K远小于N，会比普通二分好
M
【在 p*******n 的大作中提到】
: 我替他解释下吧。他的做法是一种二分的优化，可以把复杂度从logN降到logK，N是总
: 长，K是出现false的那个长度，K: 他的1， 2，4，8。。是开始指数级的增长一直找到出现false为止的，停，假设是第M
: ，K<＝M<＝N。然后在前M个数中二分。
|
i***h
发帖数: 12655 | 13 这个能不能描述的更清楚一点？
是多线程的？List长度求了以后还会变？分界点也会动态变化吗？
【在 p**r 的大作中提到】
: 多谢下作派，长度不但无法确定，而且一直在变。
|
n*****t
发帖数: 22014 | 14 N=1024, K= 27，两种算法都是 10 次啊。K = 48 还更慢。
【在 p*******n 的大作中提到】
: 我替他解释下吧。他的做法是一种二分的优化，可以把复杂度从logN降到logK，N是总
: 长，K是出现false的那个长度，K: 他的1， 2，4，8。。是开始指数级的增长一直找到出现false为止的，停，假设是第M
: ，K<＝M<＝N。然后在前M个数中二分。
|
p*******n
发帖数: 2697 | 15 是没多大用处。 2logK跟logN的区别，N远大于K有点加速
【在 n*****t 的大作中提到】
: N=1024, K= 27，两种算法都是 10 次啊。K = 48 还更慢。
|
p**r
发帖数: 5853 | 16 不说并发，单纯算法呢？
【在 g*****g 的大作中提到】
: 有当然是有的，比如并发检查可以做到 logN。只不过10000个没啥必要。
|
p**r
发帖数: 5853 | 17 懂了，多谢
【在 p*******n 的大作中提到】
: 这种做法对长度未知，或者K远小于N，会比普通二分好
:
: M
|
p**r
发帖数: 5853 | 18 多谢，是这样的list
【在 d*******r 的大作中提到】
: 到底是
: case-1. List
|
p**r
发帖数: 5853 | 19 如果多数情况N远大于K那，那就把N设置小一点，遇到N是true的时候，再double N反向
二分法是否更好点?
【在 p*******n 的大作中提到】
: 是没多大用处。 2logK跟logN的区别，N远大于K有点加速
|
p*******n
发帖数: 2697 | 20 没看懂你的话，N应该是个未知定值，根据你的情况
【在 p**r 的大作中提到】
: 如果多数情况N远大于K那，那就把N设置小一点，遇到N是true的时候，再double N反向
: 二分法是否更好点?
|
|
|
n*****t
发帖数: 22014 | 21 No, 他有已知上限 N，但是 K 的分布未知。如果 N 不确定倒可以反向。
【在 p*******n 的大作中提到】
: 没看懂你的话，N应该是个未知定值，根据你的情况
|
p**r
发帖数: 5853 | 22 对，N是未定值，但是有上限，
我的意思如果知道K远小于N，比如说5/10000
那何不把N从1万改到100来处理，
如果遇到N本身就是true的情况，再反向二分。
【在 p*******n 的大作中提到】
: 没看懂你的话，N应该是个未知定值，根据你的情况
|
p**r
发帖数: 5853 | 23 我个人感觉其实任何实战项目中遇到的都可以用已知上限来处理，
可能我书念得少，但是我觉得实战中不可能遇到上限无限大的情况。
其实我这个案例中的N上限，
也是我自己预估的，根据以往数据，确定一个大概上限，
然后再二分。
【在 n*****t 的大作中提到】
: No, 他有已知上限 N，但是 K 的分布未知。如果 N 不确定倒可以反向。
|
n*****t
发帖数: 22014 | 24 这个预估的 N 如果不精确，也可以先反向，但不从 1/2/4 开始，起跳是 1024、
1048576 等等。找到第一个 false 开始向下两分，没有 flase 直接 null 就从最后区
间两分。
至于第一个两分数列怎么选 。。。野拳派表示暂时没想明白
【在 p**r 的大作中提到】
: 我个人感觉其实任何实战项目中遇到的都可以用已知上限来处理，
: 可能我书念得少，但是我觉得实战中不可能遇到上限无限大的情况。
: 其实我这个案例中的N上限，
: 也是我自己预估的，根据以往数据，确定一个大概上限，
: 然后再二分。
|
p**r
发帖数: 5853 | 25 目前第一个两份数列的N就是取的以往出现过的最大K在稍微加点。
楼上有不少学院派的同学，觉得才1万数列，太小意思了，
其实我的每个并不表示直接拿到的，
是耗了不少电费得出的一个结果，所以哪怕是少1次check也是节约猫腻啊。
这就是想一会儿生个男孩，一会生个女孩，
学院派想的就是怎么搞才能男孩，
街头派想的就是如何在保持铁棒不磨成针的情况下生个男孩。
【在 n*****t 的大作中提到】
: 这个预估的 N 如果不精确，也可以先反向，但不从 1/2/4 开始，起跳是 1024、
: 1048576 等等。找到第一个 false 开始向下两分，没有 flase 直接 null 就从最后区
: 间两分。
: 至于第一个两分数列怎么选 。。。野拳派表示暂时没想明白
|
p*******n
发帖数: 2697 | 26 第一遍扫，就是为了能找到缩小的subset
第二遍扫，才是在subset里二分
为啥不能像你说的那样预估，是因为那样不准呀
至于是以2为底递增，还是10，还是1024，还是更大完全取决于你的实际情况。先预处
理扫一遍只是一个处理的思路。
【在 p**r 的大作中提到】
: 对，N是未定值，但是有上限，
: 我的意思如果知道K远小于N，比如说5/10000
: 那何不把N从1万改到100来处理，
: 如果遇到N本身就是true的情况，再反向二分。
|
z*****u
发帖数: 62 | 27 你这样一说就无解了，cost function 都不清楚。否则的话vectorize一下你的data
structure有可能有10-100x speed up.
【在 p**r 的大作中提到】
: 目前第一个两份数列的N就是取的以往出现过的最大K在稍微加点。
: 楼上有不少学院派的同学，觉得才1万数列，太小意思了，
: 其实我的每个并不表示直接拿到的，
: 是耗了不少电费得出的一个结果，所以哪怕是少1次check也是节约猫腻啊。
: 这就是想一会儿生个男孩，一会生个女孩，
: 学院派想的就是怎么搞才能男孩，
: 街头派想的就是如何在保持铁棒不磨成针的情况下生个男孩。
|
