Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

sort: I test the sort package, and find the quicksort is slower than my quicksort. #10578

Closed
ldnvnbl opened this issue Apr 27, 2015 · 3 comments
Closed

Comments

@ldnvnbl
Copy link

@ldnvnbl ldnvnbl commented Apr 27, 2015

package main

import (
    "bufio"
    "fmt"
    "log"
    "os"
    "sort"
    "strconv"
    "time"
)

func checkErr(err error) {
    if err != nil {
        log.Fatal(err)
    }
}

func qsort(nums []int) {
    if len(nums) <= 1 {
        return
    }
    i := 0
    j := len(nums) - 1

    m := nums[0]
    minBlank := true
    blankPos := 0
    for i <= j {
        if minBlank {
            if nums[j] < m {
                nums[blankPos] = nums[j]
                blankPos = j
                minBlank = false
            }
            j--
        } else {
            if nums[i] > m {
                nums[blankPos] = nums[i]
                blankPos = i
                minBlank = true
            }
            i++
        }
    }
    nums[blankPos] = m
    qsort(nums[:blankPos+1])
    qsort(nums[blankPos+1:])
}

func main() {

    numFile, err := os.Open("numbers.txt")  // this file have 10,000,000 rand number
    checkErr(err)
    defer numFile.Close()

    nums1 := []int{}
    nums2 := []int{}
    nums3 := []int{}
    scanner := bufio.NewScanner(numFile)
    for scanner.Scan() {
        n, err := strconv.Atoi(scanner.Text())
        checkErr(err)
        nums1 = append(nums1, n)
        nums2 = append(nums2, n)
        nums3 = append(nums3, n)
    }
    checkErr(scanner.Err())

    t1 := time.Now().UnixNano()
    qsort(nums1)
    t1 = time.Now().UnixNano() - t1

    t2 := time.Now().UnixNano()
    sort.Ints(nums2)
    t2 = time.Now().UnixNano() - t2

    t3 := time.Now().UnixNano()
    sort.Stable(sort.IntSlice(nums3))
    t3 = time.Now().UnixNano() - t3

    for k, v := range nums1 {
        // fmt.Println(v, nums2[k])
        if v != nums2[k] {
            fmt.Println("error")
        }
    }
    fmt.Println(t1)
    fmt.Println(t2)
    fmt.Println(t3)
}

and my program output is:

1293848796
3958747280
13863178941

You can find that my qsort is about three times faster than golang package sort.Ints.

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Apr 27, 2015

A lot of work has been spent on Go's sort package.

Also, Go's sort package doesn't provide quicksort (since it's worst case O(n^2)). It provides Sort and SortStable.

If you want to work on performance of Sort or SortStable, you need to use Go's built-in benchmarking facilities in the testing package.

@bradfitz bradfitz closed this Apr 27, 2015
@minux
Copy link
Member

@minux minux commented Apr 27, 2015

@bradfitz
Copy link
Contributor

@bradfitz bradfitz commented Apr 27, 2015

Also, this is comparing a concrete qsort against sort.Stable, not sort.Sort.

@mikioh mikioh changed the title I test the sort package, and find the quicksort is slower than my quicksort. sort: I test the sort package, and find the quicksort is slower than my quicksort. Apr 27, 2015
@golang golang locked and limited conversation to collaborators Jun 25, 2016
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.