» 微民網(wǎng)碼農(nóng)多。。。求個算法。10w個聯(lián)系人進行分組。。
數(shù)學(xué)模型很簡單 有10w個聯(lián)系人。
要把他們分組。
也就是相等的放在一起。
相等的條件是 名字 或者 電話號碼 相同。
比如說 有3個聯(lián)系人 zhou:123 mushi:123 zhou:456
那這3個聯(lián)系人 就要放在一組。。
在不考慮空間和 線程數(shù)量對cpu的影響下 。要求最快的速度把這10w個聯(lián)系人完成分組 有什么好的算法么/?
網(wǎng)友評論2013-08-15 15:04
不難吧
建立一個 集合(user 10W用戶信息)
int k=0
for(i=1,i<10w,i++){
新建一個分組實體
for(j=i+1,j<10w,j++){
if(條件符合){
分組實體.add(user)
集合.delete(user)
}
}
K++
}
結(jié)果 是K 是多少 就是有多少個分組
網(wǎng)友評論2013-08-15 15:19
被一樓終結(jié)了?
網(wǎng)友評論2013-08-15 15:21
不考慮空間,先建立個已經(jīng)分類完的表
然后一次賦值,齊活,O(1)...
網(wǎng)友評論2013-08-15 15:23
Reply Post by yuanyixy123 (2013-08-15 15:04):
不難吧
建立一個 集合(user 10W用戶信息)
int k=0
for(i=1,i<10w,i++){
新建一個分組實體
for(j=i+1,j<10w,j++){
if(條件符合){
分組實體.add(user)
集合.delete(user)
}
}
K++
}
結(jié)果 是K 是多少 就是有多少個分組
現(xiàn)在就是用的這個方法 在最差的情況下。跑的太慢了。
網(wǎng)友評論2013-08-15 15:24
如果是這種情況
A 123
B 123
A 456
D 456
D 789
那么這5個算一組嗎?
網(wǎng)友評論2013-08-15 15:25
就一樓的想法,lz是做cc的吧
網(wǎng)友評論2013-08-15 15:26
看成排序了
網(wǎng)友評論2013-08-15 15:26
Reply to Reply Post by mjutghn1226 (2013-08-15 15:23)
那就百度下 排序方法好了 找到 匹配次數(shù)最少的算法 能提升一點性能 這個本身就有10W的量你們是要多快 才算快
網(wǎng)友評論2013-08-15 15:30
我想可不可以這樣:
用一個HashMap,用姓名的hash值做key,后面每個記錄的姓名hash一下然后到hashmap中查找,有這個key就放入一組,否則插入新key。
不過hashmap底層是不是用linklist做的,好久沒搞過了都忘記了。
網(wǎng)友評論2013-08-15 15:35
理解錯了 編輯掉
網(wǎng)友評論2013-08-15 15:41
Reply Post by 東方未名 (2013-08-15 15:30):
我想可不可以這樣:
用一個HashMap,用姓名的hash值做key,后面每個記錄的姓名hash一下然后到hashmap中查找,有這個key就放入一組,否則插入新key。
不過hashmap底層是不是用linklist做的,好久沒搞過了都忘記了。
我覺得是一張二維的哈希表,縱軸是姓名的hash,橫軸是號碼的hash,先用10w數(shù)據(jù)填充著張表,然后再通過條件一組一組取出來?
網(wǎng)友評論2013-08-15 16:00
Reply Post by yuanyixy123 (2013-08-15 15:26):
那就百度下 排序方法好了 找到 匹配次數(shù)最少的算法 能提升一點性能 這個本身就有10W的量你們是要多快 才算快
實際的業(yè)務(wù)比這個復(fù)雜的多。我是換了一種數(shù)學(xué)模型來闡述這個業(yè)務(wù)需求。
網(wǎng)友評論2013-08-15 16:07
Reply Post by 卡斯布兒 (2013-08-15 15:41):
我覺得是一張二維的哈希表,縱軸是姓名的hash,橫軸是號碼的hash,先用10w數(shù)據(jù)填充著張表,然后再通過條件一組一組取出來?
我現(xiàn)在改的算法 跟你差不多。有一定提升。但是hash 算法 要改一下。還在找。。。大學(xué)學(xué)的都忘光了。。hashcode值 范圍太大 空間占用太高了。。
數(shù)學(xué)一般的人真是難。。。不過還是謝謝你。。這條路應(yīng)該優(yōu)化一下 能繼續(xù)走下去
網(wǎng)友評論2013-08-15 16:08
微民網(wǎng)碼農(nóng)多。。。求個算法。10w個聯(lián)系人進行分組。。
不考慮空間,那方法就是做多組二叉樹,一次性設(shè)定好每種排序,比如名字,號碼,男女…………然后提取的時候從不同的樹中提取吧……根據(jù)名字的,就從名字來找,從效率來說,第一次慢點,以后每次尋找,判斷次數(shù)不會超過32次吧
網(wǎng)友評論2013-08-15 19:48