我写了这个粗略的最小堆代码,它是我用 C++ 编写的类似程序的翻译。我想我一定是错误地使用了切片,因为 go 代码比 C++ 代码慢得多。在 Go 中插入和删除 100,000 个整数大约需要 19 秒,但在 C++ 中只需 1.73 秒。任何人都可以提供一些建议吗?还是 Go 比 C++ 慢得多?我在 Linux 下为这样的代码计时:“time ./pqgo -n 100000 -d 100000 >/dev/null”。这是代码:package mainimport ( "fmt" "time" "math/rand" "flag")func insert( key int, lPq []int) []int { lPq = append( lPq[:], key ) i := len(lPq) - 1 for ; i > 1 && lPq[ i/2 ] > lPq[i] ; { lTemp := lPq[ i/2 ] lPq[ i/2 ] = lPq[i] lPq[i] = lTemp i = i / 2 } return lPq}func delete_min( lPq []int) (int, []int) { lRetVal := lPq[1] lPq[1] = lPq[ len(lPq)-1 ] lPq = lPq[0:len(lPq)-1 ] k := 1 for ; 2*k <= len(lPq); { j := 2*k if k < len(lPq) && lPq[j] > lPq[j+1] { j++ } if lPq[k] <= lPq[j] { break } lTemp := lPq[k] lPq[k] = lPq[j] lPq[j] = lTemp } return lRetVal, lPq}func main() { var lPq []int lPq = append(lPq[:], -9999) var ip *int = flag.Int("n", 8, "help message") var ip2 *int = flag.Int("d", 8, "help message2") flag.Parse() lNum := *ip fmt.Printf( "lNum= %d\n", lNum) lPq = insert( 17, lPq[:] ); lPq = insert( 19, lPq[:] ); lPq = insert( 9, lPq[:] ); lPq = insert( 4 , lPq[:]); lPq = insert ( 12, lPq[:] ); rand.Seed(time.Now().UnixNano()) for i := 0; i < lNum; i++ { lKey := rand.Intn( 4*lNum ) lPq = insert(lKey, lPq[:]) } fmt.Printf("pq.size = %d\n", len(lPq) ) lPrintTo := len(lPq) if lPrintTo > 64 { lPrintTo = 64 } var num int for _, num = range lPq[0:lPrintTo] { fmt.Printf( "%d ", num) } fmt.Println(""); var lMin int for index := 1; index < 3; index++ { lMin, lPq = delete_min( lPq[:] ) fmt.Printf( "lMin = %d\n", lMin) for _, num = range lPq[0:lPrintTo] { fmt.Printf( "%d ", num) } fmt.Println(""); }
1 回答
- 1 回答
- 0 关注
- 215 浏览
添加回答
举报
0/150
提交
取消