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

Question

I wrote this crude min heap code that is a translation of a similar program I wrote in C++. I think I must be using slices incorrectly because the go code is way slower than the C++ code. Inserting and deleting 100,000 integers takes about 19 seconds in Go, but only 1.73 seconds in C++. Can anyone offer some advice? Or is Go that much slower than C++? I time the code like this under Linux: "time ./pqgo -n 100000 -d 100000 >/dev/null". Here is the code:

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
", 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
", 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
", 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
",lPrintTo )
      fmt.Printf("pq.size = %d
", 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

Does your C++ version generate the same amount of output?

The last loop runs lNumToDelete (100,000) times, and prints up to 64 values from the queue on each iteration. That is a lot of output, and it takes time to format and write out, even if it is going to /dev/null.

Commenting out the fmt.Printf() calls inside the delete loop made the program run significantly faster for me.

A few other suggestions:

• fmt.Printf("a = %d ", b) can be replaced with fmt.Println("a =", b)
• lPq[:] can be replaced with lPq
• Check out the Go profiling tools: http://blog.golang.org/profiling-go-programs