avatar
b*t
2
给一个正整数集合S(一个数组) 以及一些整数,需要快速检索这些整数是否在集合S
里。 怎么做比较快?
HASH表应该是比较快, 但是应该怎么设计?比如哈希函数,建哈希表的时候落入同一
个BUCKET里的元素怎么组织比较好? 如果S比较稠密的话,好像不太好组织,因为
BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用,用链表性能又不
好。
RADIX树也是集合稠密的时候没什么优势。
有什么想法没?
avatar
a*3
3
是丁丁么。。。。

【在 b*s 的大作中提到】
: 这种格式画在纽约也不少……
avatar
g*g
4
通常都是先上简单的,性能不够再优化吧。比如java的integer hash就是返回integer
本身。
稠密不应该是问题。

S

【在 b*******t 的大作中提到】
: 给一个正整数集合S(一个数组) 以及一些整数,需要快速检索这些整数是否在集合S
: 里。 怎么做比较快?
: HASH表应该是比较快, 但是应该怎么设计?比如哈希函数,建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好? 如果S比较稠密的话,好像不太好组织,因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用,用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没?

avatar
b*s
5
对,还有那个船长……

是丁丁么。。。。

【在 a********3 的大作中提到】
: 是丁丁么。。。。
avatar
l*t
6
any mainstream language has built-in hash functions. Do you have to write
your own hash function?
avatar
s*o
7
没算狗

【在 b*s 的大作中提到】
: 对,还有那个船长……
:
: 是丁丁么。。。。

avatar
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树也是集合稠密的时候没什么优势。
: 有什么想法没?

avatar
b*s
9
你还鸡兔同笼呢……

没算狗

【在 s*****o 的大作中提到】
: 没算狗
avatar
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树也是集合稠密的时候没什么优势。
: 有什么想法没?

avatar
z*i
11
Brussels是个好城市。

【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗

avatar
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

avatar
M*N
13
tintin是那里人?

【在 z*i 的大作中提到】
: Brussels是个好城市。
avatar
b*t
14
我就是要性能,如果集合可能是包括大多数可表示的正整数,踫撞会很多,这样键哈希
表时每个哈希筒里会不断需要插入,这样以后査询才会快,感觉建表的开销太大了吧。
一般哈希表会有多少bucket?如果我的集合有2^32-1,每个bucket会有很多元素
简单的方法是先排序,査询时二叉搜索,但这样cache效率会比较差,因为搜索时会到
处跳

integer

【在 g*****g 的大作中提到】
: 通常都是先上简单的,性能不够再优化吧。比如java的integer hash就是返回integer
: 本身。
: 稠密不应该是问题。
:
: S

avatar
T*e
15
你没数那只小白狗

【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗

avatar
b*s
16
最简单的是先排序,以后都二分查找
这样不需要额外存储,速度也是logn级别的,和一般hash实现没大区别
另外如果很稠密,可以设计个好点的hash函数
比如发现数据有一半在 0-1000,其余的离散
就可以把这段做线性的array,其余的用前述方法
这样查到这一段内的是o(1),其余的是o(logn)

S

【在 b*******t 的大作中提到】
: 给一个正整数集合S(一个数组) 以及一些整数,需要快速检索这些整数是否在集合S
: 里。 怎么做比较快?
: HASH表应该是比较快, 但是应该怎么设计?比如哈希函数,建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好? 如果S比较稠密的话,好像不太好组织,因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用,用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没?

avatar
p*s
17
啊!!!
你击中了我的软肋
不过不稀奇,因为埃尔热就是比利时人嘛。

【在 b*s 的大作中提到】
: 你还鸡兔同笼呢……
:
: 没算狗

avatar
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

avatar
s*o
19
我每年都要去玩,一定要建设好Brussels

【在 z*i 的大作中提到】
: Brussels是个好城市。
avatar
g*g
20
不知道你的应用是不是内存受限。这年头内存白菜价,2^32也不过4G,如果你用bitmap
不过500M。
如果涵盖大部分正整数,反转不就没几个数了。

【在 b*******t 的大作中提到】
: 我就是要性能,如果集合可能是包括大多数可表示的正整数,踫撞会很多,这样键哈希
: 表时每个哈希筒里会不断需要插入,这样以后査询才会快,感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1,每个bucket会有很多元素
: 简单的方法是先排序,査询时二叉搜索,但这样cache效率会比较差,因为搜索时会到
: 处跳
:
: integer

avatar
M*N
21
为啥每年去啊

【在 s*****o 的大作中提到】
: 我每年都要去玩,一定要建设好Brussels
avatar
b*s
22
呵呵

bitmap

【在 g*****g 的大作中提到】
: 不知道你的应用是不是内存受限。这年头内存白菜价,2^32也不过4G,如果你用bitmap
: 不过500M。
: 如果涵盖大部分正整数,反转不就没几个数了。

avatar
a*3
23
下班了。。。
包大人周末不准灌哦。。。
人家这个周末有party....
下周一再战~~~~
嘿嘿

【在 b*s 的大作中提到】
: 对,还有那个船长……
:
: 是丁丁么。。。。

avatar
N*K
24
最大数和最小数的差值多少?

【在 b*******t 的大作中提到】
: 集合里只有32位正整数,你要开数组至少要2^32/8=2^29 byte, 这不可行吧
avatar
s*o
25


【在 T****e 的大作中提到】
: 你没数那只小白狗
avatar
b*t
26
32位问题不大,64位就不行了吧

bitmap

【在 g*****g 的大作中提到】
: 不知道你的应用是不是内存受限。这年头内存白菜价,2^32也不过4G,如果你用bitmap
: 不过500M。
: 如果涵盖大部分正整数,反转不就没几个数了。

avatar
z*i
27
没问题,比利时人务实,比法国人靠谱多了。
而且Brussels的 vision 是 capital of EU, 还是挺多元化的。

【在 s*****o 的大作中提到】
: 我每年都要去玩,一定要建设好Brussels
avatar
g*g
28
64位你就只能老实哈希了。1v1也不过是哈希的一种。bucket多一些罢了。
总归是数字越少越好,bucket越多越好。
return (int)(value ^ (value >>> 32));

【在 b*******t 的大作中提到】
: 32位问题不大,64位就不行了吧
:
: bitmap

avatar
w*r
29
前两天我还谷歌地图上查了一下
221B Baker St., London, UK
结果。。。
avatar
n*t
30
多级索引二叉树?先把集合分区,这样 search 的时候最终落到 cache

【在 b*******t 的大作中提到】
: 我就是要性能,如果集合可能是包括大多数可表示的正整数,踫撞会很多,这样键哈希
: 表时每个哈希筒里会不断需要插入,这样以后査询才会快,感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1,每个bucket会有很多元素
: 简单的方法是先排序,査询时二叉搜索,但这样cache效率会比较差,因为搜索时会到
: 处跳
:
: integer

avatar
M*N
31
这么早啊。。。

【在 a********3 的大作中提到】
: 下班了。。。
: 包大人周末不准灌哦。。。
: 人家这个周末有party....
: 下周一再战~~~~
: 嘿嘿

avatar
d*n
32
纯性能的话用bitset就可以了。
big range+sparse要性能可以先用bloom filter加上hash。

【在 b*******t 的大作中提到】
: 我就是要性能,如果集合可能是包括大多数可表示的正整数,踫撞会很多,这样键哈希
: 表时每个哈希筒里会不断需要插入,这样以后査询才会快,感觉建表的开销太大了吧。
: 一般哈希表会有多少bucket?如果我的集合有2^32-1,每个bucket会有很多元素
: 简单的方法是先排序,査询时二叉搜索,但这样cache效率会比较差,因为搜索时会到
: 处跳
:
: integer

avatar
s*o
33
突然想到这句,就跟小茶想蓝妹妹一个道理。。。

【在 M****N 的大作中提到】
: 为啥每年去啊
avatar
g*e
34
std::set
avatar
M*N
35
@@

【在 s*****o 的大作中提到】
: 突然想到这句,就跟小茶想蓝妹妹一个道理。。。
avatar
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.
avatar
z*i
37
? 没问题啊。
street view上一堆人排队呢。

【在 w***r 的大作中提到】
: 前两天我还谷歌地图上查了一下
: 221B Baker St., London, UK
: 结果。。。

avatar
b*s
38
对数级他显然不满意

【在 g*********e 的大作中提到】
: std::set
avatar
s*o
39
成都是个好地方 我每年都要去玩 一定要建设好成都
--少将

【在 M****N 的大作中提到】
: @@
avatar
b*t
40
对数级是极限了吧。 除了复杂度这些硬指标,实现也很重要,比如哪种容易并行化,
有没有好的SURVEY比较这些东西的。数组排序并2分搜索, BST, RADIX SORTING, TRIE
,B-tree, 他们的并行可行性,CACHE性能,一点一点倒是能找到,如果有文章系统的
把这些放在一块儿比较能省我不少时间。

【在 b*******s 的大作中提到】
: 对数级他显然不满意
avatar
M*N
41
题字的那位?

【在 s*****o 的大作中提到】
: 成都是个好地方 我每年都要去玩 一定要建设好成都
: --少将

avatar
w*w
42
如果不需要实时加新数进去的话,总能offline找个相对均匀的bucket分布,然后
bucket内再建平衡树。


TRIE

【在 b*******t 的大作中提到】
: 对数级是极限了吧。 除了复杂度这些硬指标,实现也很重要,比如哪种容易并行化,
: 有没有好的SURVEY比较这些东西的。数组排序并2分搜索, BST, RADIX SORTING, TRIE
: ,B-tree, 他们的并行可行性,CACHE性能,一点一点倒是能找到,如果有文章系统的
: 把这些放在一块儿比较能省我不少时间。

avatar
z*i
43
你能忘了这个茬儿么。。。。

【在 s*****o 的大作中提到】
: 突然想到这句,就跟小茶想蓝妹妹一个道理。。。
avatar
b*s
44
你要是有这种总结性文章,也请给我一份,谢谢


TRIE

【在 b*******t 的大作中提到】
: 对数级是极限了吧。 除了复杂度这些硬指标,实现也很重要,比如哪种容易并行化,
: 有没有好的SURVEY比较这些东西的。数组排序并2分搜索, BST, RADIX SORTING, TRIE
: ,B-tree, 他们的并行可行性,CACHE性能,一点一点倒是能找到,如果有文章系统的
: 把这些放在一块儿比较能省我不少时间。

avatar
s*o
45
爷扑

【在 M****N 的大作中提到】
: 题字的那位?
avatar
y*a
46
hehe..这个够不够一个MASTER THESIS?

【在 b*******s 的大作中提到】
: 你要是有这种总结性文章,也请给我一份,谢谢
:
: ,
: TRIE

avatar
s*o
47
看心情吧。。。

【在 z*i 的大作中提到】
: 你能忘了这个茬儿么。。。。
avatar
w*g
48
如果S是固定的不需要支持插入删除,并且S的取值范围确实很大,可以用perfect hash
,用大量离线计算时间换一点speedup。
你这个总得有一些约束才好优化。如果就一个generic的问题,std::set或者std::
unorderd_set基本上就是最好的了。

S

【在 b*******t 的大作中提到】
: 给一个正整数集合S(一个数组) 以及一些整数,需要快速检索这些整数是否在集合S
: 里。 怎么做比较快?
: HASH表应该是比较快, 但是应该怎么设计?比如哈希函数,建哈希表的时候落入同一
: 个BUCKET里的元素怎么组织比较好? 如果S比较稠密的话,好像不太好组织,因为
: BUCKET里面的元素需要在建里的时候排序插入。这样导致数组不好用,用链表性能又不
: 好。
: RADIX树也是集合稠密的时候没什么优势。
: 有什么想法没?

avatar
M*N
49
。。。

【在 s*****o 的大作中提到】
: 爷扑
avatar
w*r
50
对呀,还真能找到这个地方。街景看上去和电视剧里一样啊。

【在 z*i 的大作中提到】
: ? 没问题啊。
: street view上一堆人排队呢。

avatar
z*i
51
那个剧下一季啥时候出来?

【在 w***r 的大作中提到】
: 对呀,还真能找到这个地方。街景看上去和电视剧里一样啊。
avatar
s*e
52
羊羊原来这么可爱~~~~~~~~~哈哈

【在 s*****o 的大作中提到】
: 看心情吧。。。
avatar
w*r
53
不知道啊,Netflix 用户表示不赶趟。

【在 z*i 的大作中提到】
: 那个剧下一季啥时候出来?
avatar
L*s
54
最近羊羊心情很好啊,草肥马壮么?

【在 s*****o 的大作中提到】
: 看心情吧。。。
avatar
z*i
55
草肥马壮, 这是气死羊的节奏啊。

【在 L**********s 的大作中提到】
: 最近羊羊心情很好啊,草肥马壮么?
avatar
L*s
56
羊不是食草动物么?

【在 z*i 的大作中提到】
: 草肥马壮, 这是气死羊的节奏啊。
avatar
b*s
57
跟马竞争食物啊。马把草吃了,羊吃啥?

【在 L**********s 的大作中提到】
: 羊不是食草动物么?
avatar
s*e
58
敲你下头!对我家米妮温柔点~~~~~

【在 b*s 的大作中提到】
: 跟马竞争食物啊。马把草吃了,羊吃啥?
avatar
O*a
59
我滴爱
avatar
z*i
60
赤裸裸?

【在 O*****a 的大作中提到】
: 我滴爱
avatar
b*s
61
捂眼睛……

【在 z*i 的大作中提到】
: 赤裸裸?
avatar
O*a
62
从小看白雪长大的呀...

【在 z*i 的大作中提到】
: 赤裸裸?
avatar
z*i
63
what? 你不是85后啊。。。

【在 O*****a 的大作中提到】
: 从小看白雪长大的呀...
avatar
b*s
64
侬是eurocrat么?

我每年都要去玩,一定要建设好Brussels

【在 s*****o 的大作中提到】
: 我每年都要去玩,一定要建设好Brussels
avatar
b*s
65
那主要还是新教荷兰人flemish的功劳。南方法语区的比利时人跟法国人一样懒散……

没问题,比利时人务实,比法国人靠谱多了。
而且Brussels的 vision 是 capital of EU, 还是挺多元化的。

【在 z*i 的大作中提到】
: 没问题,比利时人务实,比法国人靠谱多了。
: 而且Brussels的 vision 是 capital of EU, 还是挺多元化的。

avatar
b*s
66
米妮是谁?

敲你下头!对我家米妮温柔点~~~~~

【在 s*****e 的大作中提到】
: 敲你下头!对我家米妮温柔点~~~~~
avatar
z*i
67
没王室存在早就分了。

【在 b*s 的大作中提到】
: 那主要还是新教荷兰人flemish的功劳。南方法语区的比利时人跟法国人一样懒散……
:
: 没问题,比利时人务实,比法国人靠谱多了。
: 而且Brussels的 vision 是 capital of EU, 还是挺多元化的。

avatar
b*s
68
在Flemish地区,英语比法语管用。我住的地方,就有法语区来的人抱怨前台的不说法
语,只说荷兰语和英语……

【在 z*i 的大作中提到】
: 没王室存在早就分了。
avatar
L*s
69
背后有靠山就是爽啊,哦耶~~~

【在 s*****e 的大作中提到】
: 敲你下头!对我家米妮温柔点~~~~~
avatar
O*a
70
what... are you here to push my buttons? >_<

【在 z*i 的大作中提到】
: what? 你不是85后啊。。。
avatar
z*i
71
遁~

【在 O*****a 的大作中提到】
: what... are you here to push my buttons? >_<
avatar
O*a
72
too late, damages done... T___T

【在 z*i 的大作中提到】
: 遁~
avatar
b*s
73
毛……

what... are you here to push my buttons? >_<

【在 O*****a 的大作中提到】
: what... are you here to push my buttons? >_<
avatar
O*a
74
Furby... ^^

【在 b*s 的大作中提到】
: 毛……
:
: what... are you here to push my buttons? >_<

avatar
z*i
75
晕,一放狗才发现是这么个萌物啊。。。

【在 O*****a 的大作中提到】
: Furby... ^^
avatar
M*N
76
侬不用微信sticker?

【在 z*i 的大作中提到】
: 晕,一放狗才发现是这么个萌物啊。。。
avatar
g*r
77
我以为那是为00后准备的呢

【在 M****N 的大作中提到】
: 侬不用微信sticker?
avatar
O*a
78
they bite... ^^

【在 z*i 的大作中提到】
: 晕,一放狗才发现是这么个萌物啊。。。
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。