b*t
2 楼
给一个正整数集合S(一个数组) 以及一些整数,需要快速检索这些整数是否在集合S
里。 怎么做比较快?
HASH表应该是比较快, 但是应该怎么设计?比如哈希函数,建哈希表的时候落入同一
个BUCKET里的元素怎么组织比较好? 如果S比较稠密的话,好像不太好组织,因为
BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用,用链表性能又不
好。
RADIX树也是集合稠密的时候没什么优势。
有什么想法没?
里。 怎么做比较快?
HASH表应该是比较快, 但是应该怎么设计?比如哈希函数,建哈希表的时候落入同一
个BUCKET里的元素怎么组织比较好? 如果S比较稠密的话,好像不太好组织,因为
BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用,用链表性能又不
好。
RADIX树也是集合稠密的时候没什么优势。
有什么想法没?
g*g
4 楼
l*t
6 楼
any mainstream language has built-in hash functions. Do you have to write
your own hash function?
your own hash function?
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树也是集合稠密的时候没什么优势。
: 有什么想法没?
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树也是集合稠密的时候没什么优势。
: 有什么想法没?
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树也是集合稠密的时候没什么优势。
: 有什么想法没?
w*r
29 楼
前两天我还谷歌地图上查了一下
221B Baker St., London, UK
结果。。。
221B Baker St., London, UK
结果。。。
g*e
34 楼
std::set
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.
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树也是集合稠密的时候没什么优势。
: 有什么想法没?
O*a
59 楼
我滴爱
相关阅读
为啥码农现在膨胀得一个个都要拿股份当创始人? (转载)现在用Scala语言的多吗?有三赢的可能?swift是脑子被驴踢了,这帮孙子都是吃屎的AI.小黑屋 projectaws ses 发信 SPF & DMARC 求助怎么在原来的Fortran 95串行代码中插入OpenMP?Re: 请教万能的买买提一个数学建模问题 (转载)android的字典意思就是机器人K8s野史和未来统计的兄弟们,可能需要有点紧迫感让你印象深刻的业界洞察力?Python有沒有atomic int的庫?寫了兩天程序,之前的幾個貼有點看不懂了Tesla joins Apple in trade secret case tied to China's Xpeng: Bloomberg再有正式fulltime的情况下 还能做一个contract 的job吗自创理论MSFT Intelligent cloud持续成功智力与编译器Android