作者johnhao1206 (Ya大熊)
看板java
標題[問題] 資料量很大的處理
時間Thu Mar 8 21:37:13 2012
現在正在寫一個程式處理一個極大的文章 (256MB)
目前寫的方法是硬把他存到二維陣列之中再去做處理
基本的格式是這樣
id data1 data2 data3 ...
現在困擾的是要去找到對應id的資料去做處理的時候
搜尋整個array需要花費相當多的時間 (也要考慮記憶體的問題)
上網看了幾個方法但是好像不是我要的
1.File Channel
不用讀入整個檔案可以減少記憶體花費
(但是external search不是很花時間嗎?)
2.Map
有嘗試用map的方法去做，但是這樣耗費的記憶體好像會相當龐大
(我初始給到512MB了還是會爆炸)
3.
這個不知道是不是方法，
想把原本的資料按照id排序之後再用binary search
希望可以增加搜尋速度
不知道各位有沒有什麼方法處理這種問題?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.188.43
1F：→ pico2k:改用x64的環境 03/08 21:47
2F：→ Lordaeron:NoSQL 來處理吧, 256GB 都好(我隨便講的) 03/08 21:51
3F：→ james732:丟進sqlite 03/08 22:12
4F：→ Chikei:存Map<Id, FilePos>，找Id之後直接跳到檔案中FilePos存取 03/08 22:17
5F：→ johnhao1206:謝謝!! 我試試看Map(id,FilePos)的方法 03/08 22:21
6F：→ awert:RandomAccessFile ? 不知道適不適合 03/08 22:24
7F：→ qrtt1:重點不是資料量，而是你最後要得到什麼。有這個才能提策略. 03/08 22:46
我要的就很像是做一個查表法，要依照id去取得不同的數值
但是id不是照順序排列，
而且查詢的key分別有(id1)、(id1,id2)、(id1,id2,id3)三種組合
(所以不能用id當作array的index直接去access)
array裡面的資料只要取得，不用更動 (增加、刪除等等)
○ 剛剛用存Map<Id, FilePos>測試效率提升很多，謝謝
○ 我錯了!! 因為我程式寫錯的關係，所以它只存到(id1)的組合
難怪跑這麼順，處理三種組合還是會爆炸 繼續嘗試看看
8F：推 LaPass:id1 id2 id3分別是什麼? 03/09 13:09
9F：→ johnhao1206:都是數字 (0~72646) 但我把它存成String 03/09 13:41
Map1<String,int> Map2<String[],int> Map3<String[],int>
三種組合我分別做三個map處理這樣
10F：→ johnhao1206:照理來說應該分別是會有72646,72646^2,72646^3筆資料 03/09 13:47
11F：推 LaPass:你的文章格是是像這樣嗎? 03/09 15:15
12F：→ LaPass: 2433 5215 6544 5644 03/09 15:16
13F：推 LaPass:後面的部分看不太懂到底想幹什麼..... 03/09 15:19
不好意思 我舉個例子
一整個檔案分為三個區段
id1 data data
------------
0 0.1 0.2 我現在存的方法是把三個區段分別存在三個Map中
1 0.5 0.2
2 0.1 0.2 String section1 = id
3 0.4 0.2 Map1.put(section1,FilePos)
id1 id2 data data
---------------
0 0 0.3 0.2 String[] section2 = {id1,id2}
0 1 0.5 0.2
0 2 0.1 0.4 Map2.put(section2,FilePos)
0 3 0.1 0.2
1 0 0.3 0.6 Map2跟Map3都是存String[]當作key
id1 id2 id3 data data
------------------
0 0 0 0.1 0.1
0 0 1 0.1 0.1
0 0 2 0.1 0.1
0 0 3 0.1 0.1
14F：推 LaPass:用TreeMap<String,Integer>，然後Key為 0 0_0 0_0_0 03/09 16:34
15F：→ LaPass:Integer為行數，或是其他可以找到檔案位置的東西。 03/09 16:36
16F：→ LaPass:FilePos我沒用過，不清楚那個東西的特性，我還要再看。 03/09 16:37
17F：→ LaPass:不行.... 感覺起來還是會有問題.... = = 03/09 16:39
18F：→ LaPass:你還是用資料庫吧 (暈死) 03/09 16:40
19F：→ johnhao1206:後來我把VM的記憶體改更大硬跑可以了 03/09 17:31
20F：→ johnhao1206:但我想還是學學資料庫才是長久之計，謝謝大家 03/09 17:33
21F：→ Lordaeron:就NoSQL 了嘛, 快去學吧, 紅哦 03/09 21:32
22F：推 LaPass:NoSQL也聽一陣子了，那東西到底怎麼用.... = = 03/09 23:54
23F：→ johnhao1206:那個我也不是很清楚，是像hadoop之類的東西嗎? 03/10 08:40
24F：推 SansWord:學資料庫吧。用資料庫輕鬆搞定的問題，不用自己造輪子 03/10 11:51
今天改成資料庫的做法去寫
但是速度實在是太悲劇了... 可能因為太頻繁存取的關係
晚點改成X64的環境好了 ~"~
25F：→ qrtt1:你現在是寫成什麼樣子啊，真好奇QQ 03/11 00:19
我現在要做的舉個簡單的例子就像是食字路口的遊戲，從頭走到尾要花最少的錢
因為考慮的狀況很多而且算錢的時候必須去參考那個大的檔案表
而且價錢會因為上一個食物跟上上個食物而有所不同
所以才會遇到這樣的困難
我現在的作法是先把檔案表讀入二維陣列之中
讀取資料的時候順便把它丟到Map之中建立
Key是食物的名子，Value是存在陣列之中的index
這樣速度有快很多，只是記憶體真的吃很大
※ 編輯: johnhao1206 來自: 114.44.179.244 (03/11 08:16)
26F：→ qrtt1:你的 key 重複那麼多，可以用同一個物件會再省很多。 03/11 10:10
27F：→ Lordaeron:NoSQL 你要跟hadoop 劃上等號也可以, 反正台式簡化 03/11 21:13
28F：→ qrtt1:hadoop 其實是一大群專案的名稱，用什麼功能要細看xd 03/11 21:57
29F：→ Lordaeron:說來說去hadoop 就是一個人家幫你寫好的DHT. 03/11 22:34
30F：推 Chikei:72646^3筆資料冏，先想想演算法來減少資料量吧 03/12 11:37
31F：→ braveht:如果有72646^3筆資料，檔案大小應該遠遠大於256MB。 03/12 21:55
32F：→ braveht:如果資料量是256MB，又強調速度的話，塞進記憶體是最佳解 03/12 21:58
33F：→ braveht:如要再省空間可參考qrtt1的建議，或用int來取代string 03/12 22:07
34F：→ johnhao1206:謝謝您的建議，現在也朝著這個想法努力中 也謝謝qrtt1 03/13 00:24
35F：推 chen1025:資料庫建索引應該就可以解決了 03/13 23:50
資料庫有測試過，但速度方面不太能夠接受
※ 編輯: johnhao1206 來自: 114.44.179.244 (03/14 00:54)
36F：→ nick23:用SQLite 把資料放到ram disk 會好一點嗎？ 03/18 02:08