go - 我的优先级队列测试程序很慢是因为我没有正确使用 Go 吗？

Question

我编写了这个粗略的最小堆代码，它是我用 C++ 编写的类似程序的翻译。我想我一定是错误地使用了 slice ，因为 go 代码比 C++ 代码慢得多。插入和删除 100,000 个整数在 Go 中大约需要 19 秒，但在 C++ 中只需 1.73 秒。谁能提供一些建议？还是 Go 比 C++ 慢那么多？我在 Linux 下为这样的代码计时:“time ./pqgo -n 100000 -d 100000 >/dev/null”。这是代码:

package main

import (
       "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("");
    }

  lPq = insert( 3, lPq[:] );
  lPq = insert( 4, lPq[:] );
  lPq = insert( 1, lPq[:] );
  lPq = insert( 8, lPq[:] );
  lPq = insert( 20, lPq[:] );
  lPq = insert( 21, lPq[:] );
  lPq = insert( 6, lPq[:] );
  lPq = insert ( 11, lPq[:]  );

    lNumToDelete := len( lPq )
    lNumToDelete = *ip2

    for index := 1; index < lNumToDelete-1; index++ {
    lMin, lPq = delete_min( lPq[:] )

        lPrintTo = len(lPq)
        if lPrintTo > 64 {
          lPrintTo = 64
      }
        fmt.Printf("lPrintTo = %d\n",lPrintTo )
      fmt.Printf("pq.size = %d\n", len(lPq) )
      for _, num = range lPq[0:lPrintTo] {
            fmt.Printf( "%d ", num)
      }
    fmt.Println("");
    }

}

// gccgo -Og -I/devserv-home/rspikol/include -o pqgo pq.go -L/devserv-home/rspikol/lib

Answer 1

您的 C++ 版本是否生成相同数量的输出？

最后一个循环运行 lNumToDelete (100,000) 次，并在每次迭代中从队列中打印最多 64 个值。那是很多输出，格式化和写出来也需要时间，即使是去/dev/null。

注释掉删除循环内的 fmt.Printf() 调用使程序运行速度明显加快。

其他一些建议:

• fmt.Printf("a = %d\n", b) 可以替换为 fmt.Println("a =", b)
• lPq[:] 可以替换为 lPq
• 查看 Go 分析工具:http://blog.golang.org/profiling-go-programs