我應該如何改變我的圖形結構（非常慢的插入）？

Question

我正在做的這個程序是關於一個社交網絡，這意味着有用戶和他們的個人資料。配置文件結構是UserProfile。

現在，有各種可能的圖形實現，我不認爲我使用最好的一個。我有一個Graph結構，裏面有一個指向Vertex類型的鏈表的指針。每個Vertex元素都有一個值，一個指向下一個Vertex的指針和一個指向Edge類型的鏈表的指針。每個Edge元素都有一個值（因此我可以定義權重以及需要的任何值），指向下一個Edge的指針和指向Vertex所有者的指針。

我有一個2樣本文件與數據處理（在CSV樣式），並插入到圖形。第一個是用戶數據（每行一個用戶）;第二個是用戶關係（對於圖）。第一個文件很快插入到圖表中，因爲我總是插入頭部，並且有~18000個用戶。第二個文件需要時間，但我仍然在頭部插入邊緣。該文件具有約520000行用戶關係，需要13-15分鐘才能插入圖表。我做了一個快速測試，讀取數據非常快，真的很快。問題在於插入。

這個問題的存在是因爲我有一個用頂點鏈表實現的圖。每次我需要插入一個關係時，我需要查找2個頂點，以便將它們鏈接在一起。這是問題......爲〜520000關係做這件事需要一段時間。

我應該如何解決這個問題？

解決方案1）有人建議我將Graph（頂點部分）實現爲數組而不是鏈表。這樣我可以直接訪問每個頂點，並且插入可能會大大下降。但是，我不喜歡用[18000]元素分配數組的想法。這實際上如何？我的樣本數據有〜18000，但如果我需要更少或更多，該怎麼辦？鏈表方式具有這種靈活性，只要有內存，我就可以擁有我想要的任何尺寸。但陣列沒有，我該如何處理這種情況？你有什麼建議？

使用鏈接列表對空間複雜性很好，但對時間複雜性不利。使用陣列對於時間複雜性很好，但對空間複雜性不利。

有關此解決方案的任何想法？

解決方案2）該項目還要求我有某種數據結構，允許基於名稱索引和ID索引進行快速查找。爲此，我決定使用哈希表。我的表格使用單獨的鏈接作爲衝突解決方案實現，當達到0.70的加載因子時，我通常會重新創建表格。我在此http://planetmath.org/encyclopedia/GoodHashTablePrimes.html的基礎上創建下一個表格大小。

目前，兩個哈希表都包含一個指向UserProfile的指針，而不是重複用戶配置文件本身。這將是愚蠢的，不斷變化的數據需要3次更改，這樣做真的很愚蠢。所以我只保存指向UserProfile的指針。相同的用戶配置文件指針也被保存爲每個圖形Vertex中的值。

所以，我有3個數據結構，一個Graph和兩個哈希表，它們中的每一個指向相同的確切的UserProfile。 Graph結構將用於查找最短路徑和類似的東西，而Hash Tables可以作爲按名稱和ID的快速索引。

我在想要解決我的圖形問題是，而不是讓哈希表值指向UserProfile，我指向它相應的Vertex。它仍然是一個指針，不會再使用空間，我只是改變我指向的內容。

像這樣，我可以輕鬆快速地查找每個需要的頂點並將它們連接在一起。這會很快插入〜520000關係。

我想到了這個解決方案，因爲我已經有了哈希表，而且我需要它們，那麼，爲什麼不利用它們來索引Graph頂點而不是用戶配置文件？這基本上是一樣的，我仍然可以很快地訪問UserProfile，只需去Vertex，然後到UserProfile。

但是，您看到對第一個解決方案有什麼不利嗎？還是隻有專業人士才能克服第一種解決方案的優點和缺點？

其他解決方案）如果您有任何其他解決方案，我全部耳朵。但請解釋一下前面的解決方案的優點和缺點2.我現在沒有太多時間浪費時間，我需要繼續這個項目，所以，如果我正在做這樣的事情一個變化，我需要明確地知道要改變什麼，如果這真的是一條路要走。

希望沒有人睡着看這個，並關閉瀏覽器，對於大遺書感到遺憾。但我真的需要決定怎麼做，我真的需要做出改變。

P.S：在回答我提出的解決方案時，請列舉他們，因爲我確實知道你在說什麼，不要混淆我自己比我更多。

Answer 1

第一種方法是由於這裏的主要問題是速度，我寧願使用數組方法。

當然，您應該維護名稱索引查找的哈希表。

如果我理解正確，你只處理一次數據。所以沒有動態數據插入。

爲了處理分配問題，我建議：

1 - 閱讀一次文件，以獲得頂點的數量。

2 - 分配該空間

如果數據是動態的，則可以實現一些簡單的方法來增加在50％以下步驟數組的大小。

3 - 在邊緣中，將鏈接列表替換爲數組。這個數組應該以50％的步長動態增加。

即使分配了「額外」空間，當您使用50％的步長增加大小時，陣列使用的總大小也只應略大於鏈表大小。

我希望我可以幫忙。