Realloc與鏈接列表掃描

Question

我必須從文件中讀取未知數量的行並將它們保存到結構中（我想避免預先計算元素的總數）。 閱讀階段之後，我必須對這些行的每個元素進行一些計算。

我想通了兩種方式：

1. 使用realloc每次我讀了一排。這樣，分配階段很慢，但由於索引訪問，計算階段更容易。

2. 每當我讀一行時使用鏈表。這樣分配階段更快，但計算階段更慢。

從複雜性的角度來看哪個更好？

Answer 1

你將經常瀏覽鏈表嗎？如果只有一次去鏈接列表。還有一些事情：會有很多小的分配？你可以製作一些較小的緩衝區，讓我們說10行，並鏈接那些人。但這全是一個分析問題。

我會先做最簡單的事情，看看是否符合我的需求，然後我會考慮優化。

有時候人們會浪費太多時間來思考最佳解決方案，即使第二個最佳解決方案也能完美地滿足需求。

Answer 2

沒有關於如何使用這些信息的更多細節，對複雜性進行評論有點困難。但是，這裏有一些想法：

• 如果您使用realloc，它可能會更好地重新分配添加「一些」更多的項目（而不是每一次）。通常，一個好的算法是每次將尺寸加倍。
• 如果您使用鏈接列表，則可以在簡單的後處理步驟中加快訪問速度。爲項目分配一個指針數組，並在將數組元素設置爲列表中的每個項目時遍歷列表。
• 如果文件中的項目大小固定，您可以簡單地通過查找文件末尾，確定大小，除以項目大小並獲得結果來預先計算大小。即使它不是固定的大小，你也可以用它作爲估計來「接近」所需的大小，並減少所需的realloc數量。

Answer 3

其他用戶已經指出：

過早的優化是 根萬惡

高德納

我有使用realloc不同的建議：在每當插入一個對象並且沒有足夠的可用空間時，C++ STL std::vector容器就會增長。增長的規模取決於當前的預先分配的大小，但是具體實現。例如，您可以保存預分配對象的實際數量。如果尺寸用完，您可以撥打reallocate，使用當前分配的雙倍空間。我希望這有點可以理解！

洞穴當然是，你會分配更多的空間，而不是實際消耗和需要。