數據結構存儲數據內存不夠如何解決？

01-13

給一個特別大的單詞本(是那種任意字元串的，比如aa也算一個單詞，aaaaaaa也算一個單詞)，統計其中各個單詞的頻次。
我是這麼解決的：
第一層是存a~z，用的struct data{int num;data NEXT[26];}table;
table.NEXT[i].num存儲a~z的頻次，然後每個NEXT[i]=(data)malloc(sizeof(data))構造第二層，表示aa~zz
這樣依次下去。

但是這樣特別耗內存，大概50M（遠遠小於單詞本大小）多一點的單詞本要用將近2G的內存。
不知道有什麼解決的方法。

首先，題主你要好好學學演算法，好好讀書，書上這種例子很多，不要把知乎當成百度知道。

其次，我可以給你幾個思路：

1、你這個程序，耗內存的原因之一是指針太多，如果你的單詞本里短單詞太多的話，僅僅指針一項就消耗大量的內存，並且由於內存申請需要對齊，導致內存碎片特別多。

2、對於小規模的單詞本，比如單詞本小於1G的這種，你完全可以申請一個巨大的連續的內存塊然後自己來維護內存並且把所有的單詞都保存進去，不用鏈表而是用哈希索引，大概的結構是：

struct node {int num; char * ptr; int hash}; 其中ptr指向的就是大內存塊的字元串，用哈希索引，速度不會太慢。（你可以進一步優化，我只幫你到這一步，優化空間還很大）。

3、或者，因為你的內存都是一次申請知道最後才釋放了，即使你把所有的東西都放到大內存塊里，你最終消耗的內存都比零散申請要小。

4、檢查一下是否有內存泄露，如果不是字典的特性問題，那麼不排除你代碼哪裡寫錯了。

5、可以把數據存到文件里，反正你不涉及數據刪除。

以上僅供參考，好久不練習演算法了，手生，等高手給更好的信息

補充一下，大數據是專用詞，最好別輕易用。

這結構這麼多層有必要麼？

正常應用的話，第一個字母做成桶，剩下鏈式時間消耗都可以接受。

兩層足夠了。如果想任意層，用b樹。

題主在試圖構造一個Trie樹？如果按題主描述的從a到z、aa到zz、aaa到zzz。。等表項都構造出來的話，那空間消耗當然大了，如果輸入串最大長度是n的話，這個空間複雜度就是O(2^n)。。這不是Trie的正確姿勢。

另外Trie的確是最適合本場合的數據結構。Trie也有優化了空間消耗的版本（Patricia Trie）。參見Radix tree

如果只判斷存在性，使用 adfa (Acyclic DFA)，如果還需要判斷匹配的是「哪個單詞」，使用 DAWG 或者 nlt。

還是你那 50M 的單詞本，你看看用 bzip2 可以把那個單詞本壓縮到多少，這些數據結構的內存用量可能比 bzip2 壓縮後更小。

Map-Reduce的入門項目就是Word Count

你可以去看一下，就不用苦惱內存這種東西了

如果允許有誤差的話 BloomFilter

TST

數據結構的最後一章：外存儲

深入搜索引擎--海量信息的壓縮、索引和查詢

管理海量數據(壓縮索引和查詢）

雙數組版的字典樹比較適合你。你寫的這種代碼是實驗課驗收前幾天不得已寫的demo版代碼。。。不過如果確定代碼沒問題的話，加內存條解決問題更快

不請自來。

我是跟著蕭大進來的，

我就是講故事的，摺疊我吧。

看到這個問題想起了我們上個學期做的用戶個性化新聞推薦的東西。。

我做的是中文分詞部分，那是第一次接觸分詞，之後接觸到了好多奇奇怪怪的東西。尤其是編碼，一不小心就全是亂碼。

數據量也比較大，大概有近萬條新聞左右。

我分詞就是去把句子中的詞分開(廢話。。。)，然後隊友統計詞頻，用的C++和MySQL。

開始時和你一樣，我分完詞給他們，數據根本跑不出來，也是內存不足的問題。

頭疼了好幾天。。然後他們就開始搞優化。。

(這期間我在想這麼把分詞優化的正常一點。。)

大概過了一周吧，手裡沒有靠譜的詞典，我這裡進展很慢，他們的數據終於能跑起來了。。。

你猜跑了多久？

n個小時。。。

從那之後開始狂補數據結構。

全是大二的，3個人搞程序2個人文檔，老師精通Java，C++全是我們自己搞。。

那一陣子真是資料都翻爛了。。

最後還得個獎，真是不可思議。。

(我c++寫的這麼爛，這輩子也趕不上輪子哥了，可恥的匿了。。)

字典樹

買內存條

lz學時空分析沒有...你這樣搞明顯指數級...後綴樹/後綴自動機可以在線性時間內搞定它...

為什麼不用string加鏈表的形式呢。

typedef struct node *PtrToNode;

struct Node｛

string s;

int count;

PtrToNode next;

｝;

來一個單詞加上就OK啦

劈成若干組，放在若干文件里，一個文件一個文件地讀和算。然後可以把結果也存在文件上。這麼小的數據沒必要上Hadoop。用lucene倒也是可以考慮的，lucene就是把數據做索引然後分拆到若干文件里做了。

字典樹正解，每層有公共字母的只需存一個即可。