猿问

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

我写了这个粗略的最小堆代码,它是我用 C++ 编写的类似程序的翻译。我想我一定是错误地使用了切片,因为 go 代码比 C++ 代码慢得多。在 Go 中插入和删除 100,000 个整数大约需要 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("");

    }


茅侃侃
浏览 216回答 1
1回答
随时随地看视频慕课网APP

相关分类

Go
我要回答