我有一個關于切片在Go中的效用的問題。我剛剛看到為什么列表在Go中很少使用？和為什么使用數組而不是切片？但是有一些問題我沒有看到答案。在我的應用程序中：我讀取了一個包含大約1000萬條記錄的CSV文件，每條記錄有23列。對于每條記錄，我創建一個結構并將其放入鏈表中。讀取完所有記錄后，應用程序邏輯的其余部分將使用此鏈接列表（處理邏輯本身與此問題無關）。我更喜歡列表而不是切片的原因是數組/切片需要大量的連續內存。另外，由于我不知道文件中確切的記錄數的大小，因此我無法預先指定數組大?。ㄎ抑繥o可以根據需要動態地重新調整切片/數組的尺寸，但對于如此龐大的數據集，這似乎非常低效）。我讀過的每篇Go教程或文章似乎都建議我應該使用切片而不是列表（因為切片可以完成列表可以做的所有事情，但以某種方式做得更好）。但是，我不明白切片如何或為什么對我的需求更有幫助？任何人有什么想法嗎？
1 回答
梵蒂岡之花
TA貢獻1900條經驗 獲得超5個贊
...大約1000萬條記錄，每條記錄23列...我更喜歡列表而不是切片的原因是數組/切片需要大量的連續內存。
這種連續的記憶是它自己的優點，也是它自己的缺點。讓我們考慮這兩個部分。
（請注意，也可以使用混合方法：塊列表。不過，這似乎不太可能非常值得。
另外，由于我不知道文件中確切的記錄數的大小，因此我無法預先指定數組大小（我知道Go可以根據需要動態地重新調整切片/數組的尺寸，但對于如此龐大的數據集，這似乎非常低效）。
顯然，如果有 n 條記錄，并且您分配并填寫每條記錄一次（使用列表），則為 O（n）。
如果使用切片，并且每次都分配一個額外的切片條目，則從 none 開始，將其增大到大小 1，然后將 1 復制到大小為 2 的新數組并填充項目 #2，將其增大到大小 3 并填充項目 #3，依此類推。對于 n（n+1）/2 = O（n 2） 個副本，n 個實體中的第一個被復制 n 次，第二個實體被復制 n-1 次，依此類推。但是，如果您使用乘法擴展技術（Go的實現確實如此），則會下降到O（log n）副本。不過，每個都會復制更多的字節。它最終是O（n），攤銷（請參閱為什么動態數組必須幾何地增加其容量以獲得O（1）攤銷push_back時間復雜度？）。append
與切片一起使用的空間顯然是O（n）。用于鏈表方法的空間也是 O（n）（盡管記錄現在至少需要一個正向指針，因此每條記錄需要一些額外的空間）。
因此，就構造數據所需的時間以及保存數據所需的空間而言，無論哪種方式都是O（n）。您最終會得到相同的總內存要求。無論如何，乍一看，主要區別在于鏈表方法不需要連續內存。
那么：使用連續記憶時，我們會失去什么，我們會得到什么？
我們失去什么
我們失去的東西是顯而易見的。如果我們已經有碎片化的內存區域，我們可能無法獲得正確大小的連續塊。也就是說，給定：
used: 1 MB (starting at base, ending at base+1M) free: 1 MB (starting at +1M, ending at +2M) used: 1 MB (etc) free: 1 MB used: 1 MB free: 1 MB
我們總共有6 MB，3個已使用，3個免費。我們可以分配 3 個 1 MB 塊，但我們不能分配一個 3 MB 塊，除非我們能以某種方式壓縮三個“已使用”區域。
由于Go程序傾向于在大內存空間計算機（虛擬大小為64 GB或更大）的虛擬內存中運行，因此這往往不是一個大問題。當然，每個人的情況都不同，所以如果你真的受到VM的限制，這是一個真正的問題。（其他語言有壓縮GC來處理這個問題，未來的Go實現至少在理論上可以使用壓縮GC。
我們收獲什么
第一個增益也很明顯：我們不需要每條記錄中的指針。這樣可以節省一些空間 - 確切的數量取決于指針的大小，我們是否使用單鏈表等。我們假設 2 個 8 字節指針，或每條記錄 16 個字節。乘以1000萬條記錄，我們在這里看起來相當不錯：我們節省了160兆字節。（Go 的實現使用雙鏈表，在 64 位機器上，這是所需的每個元素線程的大小。container/list
然而，我們一開始得到了一些不太明顯的東西，而且是巨大的。由于 Go 是一種垃圾回收語言，因此每個指針都是 GC 必須在不同時間檢查的內容。切片方法每條記錄沒有額外的指針;鏈表方法有兩種。這意味著GC系統可以避免檢查不存在的2000萬個指針（在1000萬條記錄中）。
結論
有時使用 。如果你的算法真的需要一個列表，并且以這種方式更清晰，那就這樣做，除非它在實踐中被證明是一個問題?；蛘撸绻幸恍╉椖靠梢晕挥谀硞€列表集合中（實際上已共享的項目，但其中一些在 X 列表中，一些在 Y 列表中，一些在兩者上），這需要一個列表樣式的容器。但是，如果有一種簡單的方法可以將某些內容表示為列表或切片，請先選擇切片版本。由于切片內置于 Go 中，因此您還可以獲得第一個鏈接中提到的類型安全性/清晰度（為什么列表在 Go 中很少使用？）。container/list
- 1 回答
- 0 關注
- 80 瀏覽
添加回答
舉報
0/150
提交
取消