我剛剛開始學習go，我正在研究數據結構。我習慣于使用像listinpython或std::vectorin這樣的動態數組C++，但在go. 動態數組的優點是添加新元素的時間復雜度為 O(1)，索引的時間復雜度為 O(1)。起初我以為slice是這樣，但后來我意識到當我使用append函數時，整個切片都被復制，因此它是一個 O(N) 操作，而不是動態數組中的 O(1)。然后我遇到了列表，但這是一個雙向鏈表，這意味著索引是 O(N)，而不是 O(1)。我是否缺少我正在尋找的數據結構？
1 回答
呼喚遠方
TA貢獻1856條經驗 獲得超11個贊
起初我以為
slice是這樣，但是 [n] 我意識到當我使用append函數時，整個切片都被復制，因此它是一個 O(N) 操作，而不是動態數組中的 O(1)。
這是不正確的。
根據Go 編程語言規范，append檢查支持切片的數組的容量，如果支持數組中沒有足夠的空間，則僅分配新內存（復制切片）。[鏈接] 我在規范中沒有看到任何內容指定應該分配多少內存，但根據您鏈接到的博客文章，新的內存塊將是切片當前大小的 1.5 倍。即是，一個再分配后/復制插入裝置，下一個? / 2的插入將不會需要重新分配/復制。整體效果是攤銷 O(1) 時間。這與您在其他語言（list在 Python 中，std::vector在 C++ 中）中提到的示例所使用的方法相同。
因此，切片正是您所需要的。
- 1 回答
- 0 關注
- 172 瀏覽
添加回答
舉報
0/150
提交
取消