sorting_parallel_quicksort_compare.go

//usr/bin/env go run $0 $@ ; exit

package main

import (
    "fmt"
    "time"
    "math/rand"
    "runtime"
)

type SortFunc func([]int) []int

type SortAlgorithm struct {
    name string
    sortfunc SortFunc
    available bool
}

func main() {
    runtime.GOMAXPROCS(runtime.NumCPU())

    algorithms := []*SortAlgorithm{
        &SortAlgorithm{"quick_sort", quick_sort, true},
        &SortAlgorithm{"parallel_quick_sort", parallel_quick_sort, true},
    }

    fmt.Print("# \t")
    for _, algo := range algorithms {
        fmt.Print(algo.name + "\t")
    }
    fmt.Println("")

    for n := 1024; n < 1024*1024*1024; n *= 2 {
        fmt.Printf("%d\t", n)

        for _, algo := range algorithms {
            if algo.available {
                rand.Seed(0)
                times := []float64{}
                for i := 0; i < 5; i++ {
                    var data = make([]int, n)
                    for i, _ := range data {
                        data[i] = int(rand.Int31())
                    }

                    t0 := time.Now()
                    data = algo.sortfunc(data)
                    dt := time.Since(t0)
                    times = append(times, dt.Seconds())
                }
                time_avg := 0.0
                for _, dt := range times {
                    time_avg += dt
                }
                time_avg /= float64(len(times))
                fmt.Printf("%f\t", time_avg)

                if time_avg > 10 {
                    algo.available = false
                }
            } else {
                fmt.Printf("n/a\t")
            }
        }
        fmt.Println("")
    }
}


// Quick sort

func quick_sort(data []int) []int {
    quick_sort_inner(data, 0, len(data))
    return data
}

func quick_sort_inner(data []int, low int, up int) {
    // sanity check
    if up - low < 0 {
        panic("quick_sort: Invalid argument")
    }

    if up - low <= 1 {
        return
    }

    if up - low == 2 {
        if data[low] > data[up - 1] {
            data[low], data[up - 1] = data[up - 1], data[low]
        }
        return
    }

    pivot := data[low + (up - low) / 2]

    i, j := low, up - 1
    for {
        // move i
        for data[i] < pivot && i < j {
            i++
        }

        // move j
        for data[j] > pivot && i < j {
            j--
        }

        if i < j {
            data[i], data[j] = data[j], data[i]
            i++
            continue
        } else {
            quick_sort_inner(data, low, i)
            quick_sort_inner(data, i, up)
            break
        }
    }

    return
}

func parallel_quick_sort(data []int) []int {
    parallel_quick_sort_inner(nil, 10, data, 0, len(data))
    return data
}

func parallel_quick_sort_inner(ch chan int, lv int, data []int, low int, up int) {
    // sanity check
    if up - low < 0 {
        panic("quick_sort: Invalid argument")
    }

    if up - low <= 1 {
        if ch != nil {
            ch <- 0
        }
        return
    }

    if up - low == 2 {
        if data[low] > data[up - 1] {
            data[low], data[up - 1] = data[up - 1], data[low]
        }
        if ch != nil {
            ch <- 0
        }
        return
    }

    pivot := data[low + (up - low) / 2]

    i, j := low, up - 1
    for {
        // move i
        for data[i] < pivot && i < j {
            i++
        }

        // move j
        for data[j] > pivot && i < j {
            j--
        }

        if i < j {
            data[i], data[j] = data[j], data[i]
            i++
            continue
        } else {
            if lv > 0 {
                cch := make(chan int)
                go parallel_quick_sort_inner(cch, lv - 1, data, low, i)
                go parallel_quick_sort_inner(cch, lv - 1, data, i, up)
                // wait for termination
                <- cch
                <- cch
            } else {
                parallel_quick_sort_inner(nil, lv - 1, data, low, i)
                parallel_quick_sort_inner(nil, lv - 1, data, i, up)
            }

            break
        }
    }

    // notify termination
    if ch != nil {
        ch <- 0
    }
    return
}