我正在解決這個歐拉計劃問題。首先，我嘗試了蠻力，花了0.5秒，然后我嘗試了動態(tài)編程來利用記憶，期望有巨大的改進，但我驚訝地發(fā)現(xiàn)結果是0.36秒。經(jīng)過一點點谷歌搜索，我發(fā)現(xiàn)你不能在函數(shù)（find_collatz_len）中使用指針來訪問外部地圖數(shù)據(jù)（備忘錄）。因此，每次運行下面的函數(shù)時，它都會復制整個字典。這聽起來像是對處理器能力的巨大浪費。我的問題是，什么是解決方法，以便我可以使用指向函數(shù)外部映射的指針來避免復制。這是我的丑陋代碼：package main//project euler 014 - longest collatz sequenceimport ( "fmt" "time")func find_collatz_len(n int, memo map[int]int) int { counter := 1 initital_value := n for n != 1 { counter++ if n < initital_value { counter = counter + memo[n] break } if n%2 == 0 { n = int(float64(n)/2) } else { n = n*3+1 } } memo[initital_value] = counter return counter}func main() { start := time.Now() max_length := 0 number := 0 current_length := 0 memo := make(map[int]int) for i:=1; i<1_000_000; i++ { current_length = find_collatz_len(i, memo) if current_length > max_length { max_length = current_length number = i } } fmt.Println(max_length, number) fmt.Println("Time:", time.Since(start).Seconds())}
1 回答
胡說叔叔
TA貢獻1804條經(jīng)驗 獲得超8個贊
地圖已經(jīng)是引擎蓋下的指針。傳遞映射值將傳遞單個指針。有關詳細信息，請參閱為什么切片值有時會過時，但永遠不會映射值？
創(chuàng)建沒有容量提示的映射時，分配的映射具有足夠的內(nèi)部結構來存儲相對較少的條目（大約 7 個）。隨著映射的增長，實現(xiàn)有時需要分配更多內(nèi)存并重新構建（重新哈希）映射以容納更多元素。如果使用預期的最終容量初始化映射，則可以避免@mkopriva：
memo := make(map[int]int, 1_000_000).
因此，將分配足夠的空間來存儲所有條目（在你的示例中），因此在應用的生存期內(nèi)不會發(fā)生重新哈希。這會將運行時間從 0.3 秒減少到 0.2 秒。1_000_000
您也可以將 替換為 ，因為在您使用的整數(shù)范圍內(nèi)，它們會給出相同的結果。這將進一步提高5%（在我的機器上為0.19秒）。int(float64(n)/2)n/2
- 1 回答
- 0 關注
- 77 瀏覽
添加回答
舉報
0/150
提交
取消