我必須從文件中讀取未知數量的行並將它們保存到結構中(我想避免預先計算元素的總數)。 閱讀階段之後,我必須對這些行的每個元素進行一些計算。Realloc與鏈接列表掃描
我想通了兩種方式:
使用
realloc
每次我讀了一排。這樣,分配階段很慢,但由於索引訪問,計算階段更容易。每當我讀一行時使用鏈表。這樣分配階段更快,但計算階段更慢。
從複雜性的角度來看哪個更好?
我必須從文件中讀取未知數量的行並將它們保存到結構中(我想避免預先計算元素的總數)。 閱讀階段之後,我必須對這些行的每個元素進行一些計算。Realloc與鏈接列表掃描
我想通了兩種方式:
使用realloc
每次我讀了一排。這樣,分配階段很慢,但由於索引訪問,計算階段更容易。
每當我讀一行時使用鏈表。這樣分配階段更快,但計算階段更慢。
從複雜性的角度來看哪個更好?
你將經常瀏覽鏈表嗎?如果只有一次去鏈接列表。還有一些事情:會有很多小的分配?你可以製作一些較小的緩衝區,讓我們說10行,並鏈接那些人。但這全是一個分析問題。
我會先做最簡單的事情,看看是否符合我的需求,然後我會考慮優化。
有時候人們會浪費太多時間來思考最佳解決方案,即使第二個最佳解決方案也能完美地滿足需求。
+1最簡單的事情 – Krishna 2011-05-11 14:31:39
沒有關於如何使用這些信息的更多細節,對複雜性進行評論有點困難。但是,這裏有一些想法:
其他用戶已經指出:
過早的優化是 根萬惡
高德納
我有使用realloc
不同的建議:在每當插入一個對象並且沒有足夠的可用空間時,C++ STL std::vector
容器就會增長。增長的規模取決於當前的預先分配的大小,但是具體實現。例如,您可以保存預分配對象的實際數量。如果尺寸用完,您可以撥打reallocate
,使用當前分配的雙倍空間。我希望這有點可以理解!
洞穴當然是,你會分配更多的空間,而不是實際消耗和需要。
鏈接列表閱讀然後mallock'ing計算? – BlackBear 2011-05-11 14:27:11