b*******t
发帖数: 34 | 1 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
里。 怎么做比较快？
HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
好。
RADIX树也是集合稠密的时候没什么优势。
有什么想法没？ |
g*****g
发帖数: 34805 | 2 通常都是先上简单的，性能不够再优化吧。比如java的integer hash就是返回integer
本身。
稠密不应该是问题。
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
|
l********t
发帖数: 878 | 3 any mainstream language has built-in hash functions. Do you have to write
your own hash function? |
k**********g
发帖数: 989 | 4
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树也是集合稠密的时候没什么优势。
: 有什么想法没？
|
N******K
发帖数: 10202 | 5 哈哈 搞个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树也是集合稠密的时候没什么优势。
: 有什么想法没？
|
N******K
发帖数: 10202 | 6 要是整数巨大无比 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
|
b*******t
发帖数: 34 | 7 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
处跳
integer
【在 g*****g 的大作中提到】
: 通常都是先上简单的，性能不够再优化吧。比如java的integer hash就是返回integer
: 本身。
: 稠密不应该是问题。
:
: S
|
b*******s
发帖数: 5216 | 8 最简单的是先排序，以后都二分查找
这样不需要额外存储，速度也是logn级别的，和一般hash实现没大区别
另外如果很稠密，可以设计个好点的hash函数
比如发现数据有一半在 0-1000，其余的离散
就可以把这段做线性的array，其余的用前述方法
这样查到这一段内的是o(1)，其余的是o（logn）
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
|
b*******t
发帖数: 34 | 9 集合里只有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
|
g*****g
发帖数: 34805 | 10 不知道你的应用是不是内存受限。这年头内存白菜价，2^32也不过4G，如果你用bitmap
不过500M。
如果涵盖大部分正整数，反转不就没几个数了。
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
|
|
|
b*******s
发帖数: 5216 | 11 呵呵
bitmap
【在 g*****g 的大作中提到】
: 不知道你的应用是不是内存受限。这年头内存白菜价，2^32也不过4G，如果你用bitmap
: 不过500M。
: 如果涵盖大部分正整数，反转不就没几个数了。
|
N******K
发帖数: 10202 | 12 最大数和最小数的差值多少？
【在 b*******t 的大作中提到】
: 集合里只有32位正整数，你要开数组至少要2^32/8=2^29 byte, 这不可行吧
|
b*******t
发帖数: 34 | 13 32位问题不大，64位就不行了吧
bitmap
【在 g*****g 的大作中提到】
: 不知道你的应用是不是内存受限。这年头内存白菜价，2^32也不过4G，如果你用bitmap
: 不过500M。
: 如果涵盖大部分正整数，反转不就没几个数了。
|
g*****g
发帖数: 34805 | 14 64位你就只能老实哈希了。1v1也不过是哈希的一种。bucket多一些罢了。
总归是数字越少越好，bucket越多越好。
return (int)(value ^ (value >>> 32));
【在 b*******t 的大作中提到】
: 32位问题不大，64位就不行了吧
:
: bitmap
|
n*****t
发帖数: 22014 | 15 多级索引二叉树？先把集合分区，这样 search 的时候最终落到 cache
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
|
d****n
发帖数: 12461 | 16 纯性能的话用bitset就可以了。
big range+sparse要性能可以先用bloom filter加上hash。
【在 b*******t 的大作中提到】
: 我就是要性能，如果集合可能是包括大多数可表示的正整数，踫撞会很多，这样键哈希
: 表时每个哈希筒里会不断需要插入，这样以后査询才会快，感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1，每个bucket会有很多元素
: 简单的方法是先排序，査询时二叉搜索，但这样cache效率会比较差，因为搜索时会到
: 处跳
:
: integer
|
g*********e
发帖数: 14401 | |
N********n
发帖数: 8363 | 18 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. |
b*******s
发帖数: 5216 | 19 对数级他显然不满意
【在 g*********e 的大作中提到】
: std::set
|
b*******t
发帖数: 34 | 20 对数级是极限了吧。 除了复杂度这些硬指标，实现也很重要，比如哪种容易并行化，
有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
把这些放在一块儿比较能省我不少时间。
【在 b*******s 的大作中提到】
: 对数级他显然不满意
|
|
|
w****w
发帖数: 521 | 21 如果不需要实时加新数进去的话，总能offline找个相对均匀的bucket分布，然后
bucket内再建平衡树。
，
TRIE
【在 b*******t 的大作中提到】
: 对数级是极限了吧。 除了复杂度这些硬指标，实现也很重要，比如哪种容易并行化，
: 有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
: ，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
: 把这些放在一块儿比较能省我不少时间。
|
b*******s
发帖数: 5216 | 22 你要是有这种总结性文章，也请给我一份，谢谢
，
TRIE
【在 b*******t 的大作中提到】
: 对数级是极限了吧。 除了复杂度这些硬指标，实现也很重要，比如哪种容易并行化，
: 有没有好的SURVEY比较这些东西的。数组排序并2分搜索， BST, RADIX SORTING, TRIE
: ，B-tree, 他们的并行可行性，CACHE性能，一点一点倒是能找到，如果有文章系统的
: 把这些放在一块儿比较能省我不少时间。
|
y***a
发帖数: 840 | 23 hehe..这个够不够一个MASTER THESIS？
【在 b*******s 的大作中提到】
: 你要是有这种总结性文章，也请给我一份，谢谢
:
: ，
: TRIE
|
w***g
发帖数: 5958 | 24 如果S是固定的不需要支持插入删除，并且S的取值范围确实很大，可以用perfect hash
，用大量离线计算时间换一点speedup。
你这个总得有一些约束才好优化。如果就一个generic的问题，std::set或者std::
unorderd_set基本上就是最好的了。
S
【在 b*******t 的大作中提到】
: 给一个正整数集合S（一个数组） 以及一些整数，需要快速检索这些整数是否在集合S
: 里。 怎么做比较快？
: HASH表应该是比较快， 但是应该怎么设计？比如哈希函数，建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好？ 如果S比较稠密的话，好像不太好组织，因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用，用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没？
|
