b*t
2 楼
给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
里。 怎么做比较快？
HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
好。
RADIX树也是集合稠密的时候没什么优势。
有什么想法没？
里。 怎么做比较快？
HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
好。
RADIX树也是集合稠密的时候没什么优势。
有什么想法没？
a*3
3 楼
是丁丁么。。。。
【在 b*s 的大作中提到】
: 这种格式画在纽约也不少……
【在 b*s 的大作中提到】
: 这种格式画在纽约也不少……
g*g
4 楼
通常都是先上简单的，性能不够再优化吧。比如java的integer hash就是返回integer
本身。
稠密不应该是问题。
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
本身。
稠密不应该是问题。
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
b*s
5 楼
对，还有那个船长……
是丁丁么。。。。
【在 a********3 的大作中提到】
: 是丁丁么。。。。
是丁丁么。。。。
【在 a********3 的大作中提到】
: 是丁丁么。。。。
l*t
6 楼
any mainstream language has built-in hash functions. Do you have to write
your own hash function?
your own hash function?
s*o
7 楼
没算狗
【在 b*s 的大作中提到】
: 对，还有那个船长……
:
: 是丁丁么。。。。
【在 b*s 的大作中提到】
: 对，还有那个船长……
:
: 是丁丁么。。。。
k*g
8 楼
S
How many (i.e. what is size of S) ?
Measured in powers of 1024, e.g. 1K, 1M, 1G, 1T, ...
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
b*s
9 楼
你还鸡兔同笼呢……
没算狗
【在 s*****o 的大作中提到】
: 没算狗
没算狗
【在 s*****o 的大作中提到】
: 没算狗
N*K
10 楼
哈哈 搞个p的哈希啊
开一块内存 比如 std::array A
首先清零数据
然后 对S立面的任意 x 设置 A[x]=1;
你要节省内存 可以 用 std::array A
A和S放一起
来一个新数字 y 直接查A[y]
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
开一块内存 比如 std::array
首先清零数据
然后 对S立面的任意 x 设置 A[x]=1;
你要节省内存 可以 用 std::array
A和S放一起
来一个新数字 y 直接查A[y]
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
z*i
11 楼
Brussels是个好城市。
【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗
【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗
N*K
12 楼
要是整数巨大无比 unsigned long long 存不下
S集合是稀疏的 那就把整数分成几段 每段用hash 这样可以防止hash碰撞
【在 N******K 的大作中提到】
: 哈哈 搞个p的哈希啊
: 开一块内存 比如 std::array A
: 首先清零数据
: 然后 对S立面的任意 x 设置 A[x]=1;
: 你要节省内存 可以 用 std::array A
: A和S放一起
: 来一个新数字 y 直接查A[y]
:
: S
S集合是稀疏的 那就把整数分成几段 每段用hash 这样可以防止hash碰撞
【在 N******K 的大作中提到】
: 哈哈 搞个p的哈希啊
: 开一块内存 比如 std::array
: 首先清零数据
: 然后 对S立面的任意 x 设置 A[x]=1;
: 你要节省内存 可以 用 std::array
: A和S放一起
: 来一个新数字 y 直接查A[y]
:
: S
M*N
13 楼
tintin是那里人？
【在 z*i 的大作中提到】
: Brussels是个好城市。
【在 z*i 的大作中提到】
: Brussels是个好城市。
b*t
14 楼
我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
处跳
integer
【在 g*****g 的大作中提到】
: 通常都是先上简单的，性能不够再优化吧。比如java的integer hash就是返回integer
: 本身。
: 稠密不应该是问题。
:
: S
表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
处跳
integer
【在 g*****g 的大作中提到】
: 通常都是先上简单的，性能不够再优化吧。比如java的integer hash就是返回integer
: 本身。
: 稠密不应该是问题。
:
: S
T*e
15 楼
你没数那只小白狗
【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗
【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗
b*s
16 楼
最简单的是先排序，以后都二分查找
这样不需要额外存储，速度也是logn级别的，和一般hash实现没大区别
另外如果很稠密，可以设计个好点的hash函数
比如发现数据有一半在 0-1000，其余的离散
就可以把这段做线性的array，其余的用前述方法
这样查到这一段内的是o(1)，其余的是o（logn）
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
这样不需要额外存储，速度也是logn级别的，和一般hash实现没大区别
另外如果很稠密，可以设计个好点的hash函数
比如发现数据有一半在 0-1000，其余的离散
就可以把这段做线性的array，其余的用前述方法
这样查到这一段内的是o(1)，其余的是o（logn）
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
p*s
17 楼
啊！！！
你击中了我的软肋
不过不稀奇，因为埃尔热就是比利时人嘛。
【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗
你击中了我的软肋
不过不稀奇，因为埃尔热就是比利时人嘛。
【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗
b*t
18 楼
集合里只有32位正整数，你要开数组至少要2^32/8=2^29 byte, 这不可行吧
【在 N******K 的大作中提到】
: 哈哈 搞个p的哈希啊
: 开一块内存 比如 std::array A
: 首先清零数据
: 然后 对S立面的任意 x 设置 A[x]=1;
: 你要节省内存 可以 用 std::array A
: A和S放一起
: 来一个新数字 y 直接查A[y]
:
: S
【在 N******K 的大作中提到】
: 哈哈 搞个p的哈希啊
: 开一块内存 比如 std::array
: 首先清零数据
: 然后 对S立面的任意 x 设置 A[x]=1;
: 你要节省内存 可以 用 std::array
: A和S放一起
: 来一个新数字 y 直接查A[y]
:
: S
s*o
19 楼
我每年都要去玩，一定要建设好Brussels
【在 z*i 的大作中提到】
: Brussels是个好城市。
【在 z*i 的大作中提到】
: Brussels是个好城市。
g*g
20 楼
不知道你的应用是不是内存受限。这年头内存白菜价，2^32也不过4G，如果你用bitmap
不过500M。
如果涵盖大部分正整数，反转不就没几个数了。
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
不过500M。
如果涵盖大部分正整数，反转不就没几个数了。
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
M*N
21 楼
为啥每年去啊
【在 s*****o 的大作中提到】
: 我每年都要去玩，一定要建设好Brussels
【在 s*****o 的大作中提到】
: 我每年都要去玩，一定要建设好Brussels
b*s
22 楼
呵呵
bitmap
【在 g*****g 的大作中提到】
: 不知道你的应用是不是内存受限。这年头内存白菜价，2^32也不过4G，如果你用bitmap
: 不过500M。
: 如果涵盖大部分正整数，反转不就没几个数了。
bitmap
【在 g*****g 的大作中提到】
: 不知道你的应用是不是内存受限。这年头内存白菜价，2^32也不过4G，如果你用bitmap
: 不过500M。
: 如果涵盖大部分正整数，反转不就没几个数了。
a*3
23 楼
下班了。。。
包大人周末不准灌哦。。。
人家这个周末有ｐａｒｔｙ．．．．
下周一再战～～～～
嘿嘿
【在 b*s 的大作中提到】
: 对，还有那个船长……
:
: 是丁丁么。。。。
包大人周末不准灌哦。。。
人家这个周末有ｐａｒｔｙ．．．．
下周一再战～～～～
嘿嘿
【在 b*s 的大作中提到】
: 对，还有那个船长……
:
: 是丁丁么。。。。
N*K
24 楼
最大数和最小数的差值多少？
【在 b*******t 的大作中提到】
: 集合里只有32位正整数，你要开数组至少要2^32/8=2^29 byte, 这不可行吧
【在 b*******t 的大作中提到】
: 集合里只有32位正整数，你要开数组至少要2^32/8=2^29 byte, 这不可行吧
s*o
25 楼
碰
【在 T****e 的大作中提到】
: 你没数那只小白狗
【在 T****e 的大作中提到】
: 你没数那只小白狗
b*t
26 楼
32位问题不大，64位就不行了吧
bitmap
【在 g*****g 的大作中提到】
: 不知道你的应用是不是内存受限。这年头内存白菜价，2^32也不过4G，如果你用bitmap
: 不过500M。
: 如果涵盖大部分正整数，反转不就没几个数了。
bitmap
【在 g*****g 的大作中提到】
: 不知道你的应用是不是内存受限。这年头内存白菜价，2^32也不过4G，如果你用bitmap
: 不过500M。
: 如果涵盖大部分正整数，反转不就没几个数了。
z*i
27 楼
没问题，比利时人务实，比法国人靠谱多了。
而且Brussels的 vision 是 capital of EU， 还是挺多元化的。
【在 s*****o 的大作中提到】
: 我每年都要去玩，一定要建设好Brussels
而且Brussels的 vision 是 capital of EU， 还是挺多元化的。
【在 s*****o 的大作中提到】
: 我每年都要去玩，一定要建设好Brussels
g*g
28 楼
64位你就只能老实哈希了。1v1也不过是哈希的一种。bucket多一些罢了。
总归是数字越少越好，bucket越多越好。
return (int)(value ^ (value >>> 32));
【在 b*******t 的大作中提到】
: 32位问题不大，64位就不行了吧
:
: bitmap
总归是数字越少越好，bucket越多越好。
return (int)(value ^ (value >>> 32));
【在 b*******t 的大作中提到】
: 32位问题不大，64位就不行了吧
:
: bitmap
w*r
29 楼
前两天我还谷歌地图上查了一下
221B Baker St., London， UK
结果。。。
221B Baker St., London， UK
结果。。。
n*t
30 楼
多级索引二叉树？先把集合分区，这样 search 的时候最终落到 cache
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
M*N
31 楼
这么早啊。。。
【在 a********3 的大作中提到】
: 下班了。。。
: 包大人周末不准灌哦。。。
: 人家这个周末有ｐａｒｔｙ．．．．
: 下周一再战～～～～
: 嘿嘿
【在 a********3 的大作中提到】
: 下班了。。。
: 包大人周末不准灌哦。。。
: 人家这个周末有ｐａｒｔｙ．．．．
: 下周一再战～～～～
: 嘿嘿
d*n
32 楼
纯性能的话用bitset就可以了。
big range+sparse要性能可以先用bloom filter加上hash。
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
big range+sparse要性能可以先用bloom filter加上hash。
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
s*o
33 楼
突然想到这句，就跟小茶想蓝妹妹一个道理。。。
【在 M****N 的大作中提到】
: 为啥每年去啊
【在 M****N 的大作中提到】
: 为啥每年去啊
g*e
34 楼
std::set
M*N
35 楼
@@
【在 s*****o 的大作中提到】
: 突然想到这句，就跟小茶想蓝妹妹一个道理。。。
【在 s*****o 的大作中提到】
: 突然想到这句，就跟小茶想蓝妹妹一个道理。。。
N*n
36 楼
Just grab a good template or generic implementation of hash table to
use. No need to code it yourself. A standard hash table should be
designed well enough to handle your use cases.
use. No need to code it yourself. A standard hash table should be
designed well enough to handle your use cases.
z*i
37 楼
？ 没问题啊。
street view上一堆人排队呢。
【在 w***r 的大作中提到】
: 前两天我还谷歌地图上查了一下
: 221B Baker St., London， UK
: 结果。。。
street view上一堆人排队呢。
【在 w***r 的大作中提到】
: 前两天我还谷歌地图上查了一下
: 221B Baker St., London， UK
: 结果。。。
b*s
38 楼
对数级他显然不满意
【在 g*********e 的大作中提到】
: std::set
【在 g*********e 的大作中提到】
: std::set
s*o
39 楼
成都是个好地方 我每年都要去玩 一定要建设好成都
--少将
【在 M****N 的大作中提到】
: @@
--少将
【在 M****N 的大作中提到】
: @@
b*t
40 楼
对数级是极限了吧。 除了复杂度这些硬指标，实现也很重要，比如哪种容易并行化，
有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
把这些放在一块儿比较能省我不少时间。
【在 b*******s 的大作中提到】
: 对数级他显然不满意
有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
把这些放在一块儿比较能省我不少时间。
【在 b*******s 的大作中提到】
: 对数级他显然不满意
M*N
41 楼
题字的那位？
【在 s*****o 的大作中提到】
: 成都是个好地方 我每年都要去玩 一定要建设好成都
: --少将
【在 s*****o 的大作中提到】
: 成都是个好地方 我每年都要去玩 一定要建设好成都
: --少将
w*w
42 楼
如果不需要实时加新数进去的话，总能offline找个相对均匀的bucket分布，然后
bucket内再建平衡树。
，
TRIE
【在 b*******t 的大作中提到】
: 对数级是极限了吧。 除了复杂度这些硬指标，实现也很重要，比如哪种容易并行化，
: 有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
: ，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
: 把这些放在一块儿比较能省我不少时间。
bucket内再建平衡树。
，
TRIE
【在 b*******t 的大作中提到】
: 对数级是极限了吧。 除了复杂度这些硬指标，实现也很重要，比如哪种容易并行化，
: 有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
: ，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
: 把这些放在一块儿比较能省我不少时间。
z*i
43 楼
你能忘了这个茬儿么。。。。
【在 s*****o 的大作中提到】
: 突然想到这句，就跟小茶想蓝妹妹一个道理。。。
【在 s*****o 的大作中提到】
: 突然想到这句，就跟小茶想蓝妹妹一个道理。。。
b*s
44 楼
你要是有这种总结性文章，也请给我一份，谢谢
，
TRIE
【在 b*******t 的大作中提到】
: 对数级是极限了吧。 除了复杂度这些硬指标，实现也很重要，比如哪种容易并行化，
: 有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
: ，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
: 把这些放在一块儿比较能省我不少时间。
，
TRIE
【在 b*******t 的大作中提到】
: 对数级是极限了吧。 除了复杂度这些硬指标，实现也很重要，比如哪种容易并行化，
: 有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
: ，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
: 把这些放在一块儿比较能省我不少时间。
s*o
45 楼
爷扑
【在 M****N 的大作中提到】
: 题字的那位？
【在 M****N 的大作中提到】
: 题字的那位？
y*a
46 楼
hehe..这个够不够一个MASTER THESIS？
【在 b*******s 的大作中提到】
: 你要是有这种总结性文章，也请给我一份，谢谢
:
: ，
: TRIE
【在 b*******s 的大作中提到】
: 你要是有这种总结性文章，也请给我一份，谢谢
:
: ，
: TRIE
s*o
47 楼
看心情吧。。。
【在 z*i 的大作中提到】
: 你能忘了这个茬儿么。。。。
【在 z*i 的大作中提到】
: 你能忘了这个茬儿么。。。。
w*g
48 楼
如果S是固定的不需要支持插入删除，并且S的取值范围确实很大，可以用perfect hash
，用大量离线计算时间换一点speedup。
你这个总得有一些约束才好优化。如果就一个generic的问题，std::set或者std::
unorderd_set基本上就是最好的了。
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
，用大量离线计算时间换一点speedup。
你这个总得有一些约束才好优化。如果就一个generic的问题，std::set或者std::
unorderd_set基本上就是最好的了。
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
M*N
49 楼
。。。
【在 s*****o 的大作中提到】
: 爷扑
【在 s*****o 的大作中提到】
: 爷扑
w*r
50 楼
对呀，还真能找到这个地方。街景看上去和电视剧里一样啊。
【在 z*i 的大作中提到】
: ？ 没问题啊。
: street view上一堆人排队呢。
【在 z*i 的大作中提到】
: ？ 没问题啊。
: street view上一堆人排队呢。
z*i
51 楼
那个剧下一季啥时候出来?
【在 w***r 的大作中提到】
: 对呀，还真能找到这个地方。街景看上去和电视剧里一样啊。
【在 w***r 的大作中提到】
: 对呀，还真能找到这个地方。街景看上去和电视剧里一样啊。
s*e
52 楼
羊羊原来这么可爱~~~~~~~~~哈哈
【在 s*****o 的大作中提到】
: 看心情吧。。。
【在 s*****o 的大作中提到】
: 看心情吧。。。
w*r
53 楼
不知道啊，Netflix 用户表示不赶趟。
【在 z*i 的大作中提到】
: 那个剧下一季啥时候出来?
【在 z*i 的大作中提到】
: 那个剧下一季啥时候出来?
L*s
54 楼
最近羊羊心情很好啊，草肥马壮么？
【在 s*****o 的大作中提到】
: 看心情吧。。。
【在 s*****o 的大作中提到】
: 看心情吧。。。
z*i
55 楼
草肥马壮， 这是气死羊的节奏啊。
【在 L**********s 的大作中提到】
: 最近羊羊心情很好啊，草肥马壮么？
【在 L**********s 的大作中提到】
: 最近羊羊心情很好啊，草肥马壮么？
L*s
56 楼
羊不是食草动物么？
【在 z*i 的大作中提到】
: 草肥马壮， 这是气死羊的节奏啊。
【在 z*i 的大作中提到】
: 草肥马壮， 这是气死羊的节奏啊。
b*s
57 楼
跟马竞争食物啊。马把草吃了，羊吃啥？
【在 L**********s 的大作中提到】
: 羊不是食草动物么？
【在 L**********s 的大作中提到】
: 羊不是食草动物么？
s*e
58 楼
敲你下头！对我家米妮温柔点~~~~~
【在 b*s 的大作中提到】
: 跟马竞争食物啊。马把草吃了，羊吃啥？
【在 b*s 的大作中提到】
: 跟马竞争食物啊。马把草吃了，羊吃啥？
O*a
59 楼
我滴爱
z*i
60 楼
赤裸裸？
【在 O*****a 的大作中提到】
: 我滴爱
【在 O*****a 的大作中提到】
: 我滴爱
b*s
61 楼
捂眼睛……
【在 z*i 的大作中提到】
: 赤裸裸？
【在 z*i 的大作中提到】
: 赤裸裸？
O*a
62 楼
从小看白雪长大的呀...
【在 z*i 的大作中提到】
: 赤裸裸？
【在 z*i 的大作中提到】
: 赤裸裸？
z*i
63 楼
what？ 你不是８５后啊。。。
【在 O*****a 的大作中提到】
: 从小看白雪长大的呀...
【在 O*****a 的大作中提到】
: 从小看白雪长大的呀...
b*s
64 楼
侬是eurocrat么？
我每年都要去玩，一定要建设好Brussels
【在 s*****o 的大作中提到】
: 我每年都要去玩，一定要建设好Brussels
我每年都要去玩，一定要建设好Brussels
【在 s*****o 的大作中提到】
: 我每年都要去玩，一定要建设好Brussels
b*s
65 楼
那主要还是新教荷兰人flemish的功劳。南方法语区的比利时人跟法国人一样懒散……
没问题，比利时人务实，比法国人靠谱多了。
而且Brussels的 vision 是 capital of EU， 还是挺多元化的。
【在 z*i 的大作中提到】
: 没问题，比利时人务实，比法国人靠谱多了。
: 而且Brussels的 vision 是 capital of EU， 还是挺多元化的。
没问题，比利时人务实，比法国人靠谱多了。
而且Brussels的 vision 是 capital of EU， 还是挺多元化的。
【在 z*i 的大作中提到】
: 没问题，比利时人务实，比法国人靠谱多了。
: 而且Brussels的 vision 是 capital of EU， 还是挺多元化的。
b*s
66 楼
米妮是谁？
敲你下头！对我家米妮温柔点~~~~~
【在 s*****e 的大作中提到】
: 敲你下头！对我家米妮温柔点~~~~~
敲你下头！对我家米妮温柔点~~~~~
【在 s*****e 的大作中提到】
: 敲你下头！对我家米妮温柔点~~~~~
z*i
67 楼
没王室存在早就分了。
【在 b*s 的大作中提到】
: 那主要还是新教荷兰人flemish的功劳。南方法语区的比利时人跟法国人一样懒散……
:
: 没问题，比利时人务实，比法国人靠谱多了。
: 而且Brussels的 vision 是 capital of EU， 还是挺多元化的。
【在 b*s 的大作中提到】
: 那主要还是新教荷兰人flemish的功劳。南方法语区的比利时人跟法国人一样懒散……
:
: 没问题，比利时人务实，比法国人靠谱多了。
: 而且Brussels的 vision 是 capital of EU， 还是挺多元化的。
b*s
68 楼
在Flemish地区，英语比法语管用。我住的地方，就有法语区来的人抱怨前台的不说法
语，只说荷兰语和英语……
【在 z*i 的大作中提到】
: 没王室存在早就分了。
语，只说荷兰语和英语……
【在 z*i 的大作中提到】
: 没王室存在早就分了。
L*s
69 楼
背后有靠山就是爽啊，哦耶～～～
【在 s*****e 的大作中提到】
: 敲你下头！对我家米妮温柔点~~~~~
【在 s*****e 的大作中提到】
: 敲你下头！对我家米妮温柔点~~~~~
O*a
70 楼
what... are you here to push my buttons? >_<
【在 z*i 的大作中提到】
: what？ 你不是８５后啊。。。
【在 z*i 的大作中提到】
: what？ 你不是８５后啊。。。
z*i
71 楼
遁～
【在 O*****a 的大作中提到】
: what... are you here to push my buttons? >_<
【在 O*****a 的大作中提到】
: what... are you here to push my buttons? >_<
O*a
72 楼
too late, damages done... T___T
【在 z*i 的大作中提到】
: 遁～
【在 z*i 的大作中提到】
: 遁～
b*s
73 楼
毛……
what... are you here to push my buttons? >_<
【在 O*****a 的大作中提到】
: what... are you here to push my buttons? >_<
what... are you here to push my buttons? >_<
【在 O*****a 的大作中提到】
: what... are you here to push my buttons? >_<
O*a
74 楼
Furby... ^^
【在 b*s 的大作中提到】
: 毛……
:
: what... are you here to push my buttons? >_<
【在 b*s 的大作中提到】
: 毛……
:
: what... are you here to push my buttons? >_<
z*i
75 楼
晕，一放狗才发现是这么个萌物啊。。。
【在 O*****a 的大作中提到】
: Furby... ^^
【在 O*****a 的大作中提到】
: Furby... ^^
M*N
76 楼
侬不用微信sticker?
【在 z*i 的大作中提到】
: 晕，一放狗才发现是这么个萌物啊。。。
【在 z*i 的大作中提到】
: 晕，一放狗才发现是这么个萌物啊。。。
g*r
77 楼
我以为那是为00后准备的呢
【在 M****N 的大作中提到】
: 侬不用微信sticker?
【在 M****N 的大作中提到】
: 侬不用微信sticker?
O*a
78 楼
they bite... ^^
【在 z*i 的大作中提到】
: 晕，一放狗才发现是这么个萌物啊。。。
【在 z*i 的大作中提到】
: 晕，一放狗才发现是这么个萌物啊。。。
相关阅读
Qt4 和 Visual C++ 2005 + Vista 不兼容？有IT民工用AI Planning嘛？[合集] 请问关于堆栈的问题[合集] Thinking in C++这本书怎么样啊？[合集] one simple question[合集] 也来一道面试题C++真的吗？“Google Facebook抢夺计算机毕业生 年薪涨至9.5万”[合集] Interview Question[合集] 用什么工具画程序的FLOW CHART?[合集] 软件工程的书有什么好的推荐一下？ (转载)[合集] 如何只用putchar来实现itoa?怎么非ASCII字符就过滤不了呢？[Perl]一个算法求助[合集] 又学了一招[合集] i++ * i++?[合集] 一个指针的小问题问一个很奇怪的LPDRAWITEMSTRUCT的问题 (MFC)[合集] Exception Handling in C请问如何对付error C2148问题：陣列的總大小不能超過 0x7fffffff 位元組class套class