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 瀏覽
添加回答
舉報