資料科學與工程 /z/data
3
比對大量資料的問題 (www.facebook.com)
10 則討論 ksc91u 張貼於

ksc91u 積分 0

覺得有趣是, 首先把時間複雜度從 n^2 降到 n log n 然後又有人跟我講說query db 很耗時間。 所以想,

  1. 寫 procedure, 但是好像好麻煩
  2. 把資料全部都撈回來 local 跑, 用 DBD 之類的 key value db, key = 他要比對的欄位, value = 他要寫入的資料在檔案的位置(offset) 這樣應該就會快多了吧
回應

chchwy 積分 0

牽涉到Database所以就不能單純看時間複雜度啦。DB query過程中可能會存取硬碟，而存取硬碟的時間遠大於存取記憶體的時間，O()預測法八成會失準(因為常數太大)。

我自己猜測直接用 DB Query 會比較快，因為DB本身的資料結構通常都已經針對硬碟存取優化過了。

真的要硬做的話，直覺的作法就是先排序然後用二分搜尋法，看你的資料量有多「大」，能不能全部塞進記憶體裡面做。

回應

natsu 積分 0
  1. 寫 procedure, 但是好像好麻煩

應該還是寫 procedure 效能會比較快吧...

Hibernate 在這方面好像就無能為力？

  1. 把資料全部都撈回來 local 跑, 用 DBD 之類的 key value db, key = 他要比對的欄位, value = 他要寫入的資料在檔案的位置(offset) 這樣應該就會快多了吧

請問 DBD 是什麼？

回應

ksc91u 積分 0

Link1

Link2

1
https://en.wikipedia.org/wiki/Berkeley_DB
2
https://en.wikipedia.org/wiki/Dbm
回應

natsu 積分 0

原來是 Berkeley DB ...

不過光是把 資料全部都撈回來 local 就要花掉不少時間了吧？(假設資料筆數很多的話)

回應

IngramChen 積分 0

沒試過直接 join ?

回應

kaif 積分 0

幾億的資料不就下班下query明天來再收就好了嗎XD

回應

ksc91u 積分 0

我覺得上班時候跑，等他跑完下班。這樣比較好，要觀察有沒有跑到一半斷掉很辛苦的

回應

popcorny 積分 0 編輯於

方法1: 直接在 DB query. 兩個大table內部就是用 sort merge join

方法2: 用 spark，開兩個 dataset，然後 join, 當然 spark 內部也是用類似 sort merge join。

方法2好處是直接可以輸出到文字檔，對 DB 的impact小。而且可以平行，除了stage 1因為拉資料可能只能有兩個task，stage 2可以 shuffle 到很多個partition 去做平行處理。

回應

chao 積分 0

匯出來用diff 會不會比較快?

回應