go - Go の慣用的なクイックソート

Question

私は を見ていてGo、言語の感触をつかむために古典的なアルゴリズムの慣用的な実装を見つけようとしていました。

私がクイックソートを選んだのは、配列とスライス、インプレースとコピーの取引に特に興味があるからです。いくつかの概念が落ち着いたら、並列実装を書きたいと思います。

誰かが私にクイックソートの慣用的な実装を見せてもらえますGoか?

Answer 1

さて、私はこれで終わりました。慣用的Goとは言えませんが、スライス、1 行のスワップ、および句を使用しました。書くのはかなり参考になったので、共有する必要があると思いました。range

func qsort(a []int) []int {
  if len(a) < 2 { return a }

  left, right := 0, len(a) - 1

  // Pick a pivot
  pivotIndex := rand.Int() % len(a)

  // Move the pivot to the right
  a[pivotIndex], a[right] = a[right], a[pivotIndex]

  // Pile elements smaller than the pivot on the left
  for i := range a {
    if a[i] < a[right] {
      a[i], a[left] = a[left], a[i]
      left++
    }
  }

  // Place the pivot after the last smaller element
  a[left], a[right] = a[right], a[left]

  // Go down the rabbit hole
  qsort(a[:left])
  qsort(a[left + 1:])


  return a
}

Answer 2

C などの 1 つの言語から単純にコードを取得し、それを Go などの別の言語に単純に変換しても、慣用的なコードが生成されることはめったにありません。

パッケージを並べ替える-- sort.cソースファイル

func quickSort(data Interface, a, b, maxDepth int) {
    // . . .
    // Avoiding recursion on the larger subproblem guarantees
    // a stack depth of at most lg(b-a). 
    // . . . 
}

このコメントは、再帰的なソリューションを実装することが最善の戦略ではない可能性があるという手がかりです。Go はショート スタックを使用します。

これは、反復的なクイックソート ソリューションです。

package main

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

type Item int
type Items []Item

// Algorithms and Data Structures, N. Wirth
// http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf
// 2.3.3 Partition Sort, Quicksort, NonRecursiveQuickSort.
func qSort(a Items) {
    const M = 12
    var i, j, l, r int
    var x Item
    var low, high = make([]int, 0, M), make([]int, 0, M)

    low, high = append(low, 0), append(high, len(a)-1)
    for { // (*take top request from stack*)
        l, low = low[len(low)-1], low[:len(low)-1]
        r, high = high[len(high)-1], high[:len(high)-1]
        for { // (*partition a[l] ... a[r]*)
            i, j = l, r
            x = a[l+(r-l)/2]
            for {
                for ; a[i] < x; i++ {
                }
                for ; x < a[j]; j-- {
                }
                if i <= j {
                    a[i], a[j] = a[j], a[i]
                    i++
                    j--
                }
                if i > j {
                    break
                }
            }
            if i < r { // (*stack request to sort right partition*)
                low, high = append(low, i), append(high, r)
            }
            r = j // (*now l and r delimit the left partition*)
            if l >= r {
                break
            }
        }
        if len(low)+len(high) == 0 {
            break
        }
    }
}

func main() {
    nItems := 4096
    a := make(Items, nItems)
    rand.Seed(time.Now().UnixNano())
    for i := range a {
        a[i] = Item(rand.Int31())
    }
    qSort(a)
    for i := range a[1:] {
        if a[i] > a[i+1] {
            fmt.Println("(* sort error *)")
        }
    }
}

明らかに、やるべきことはまだあります。たとえば、パーティショニング アルゴリズムを改善し、qsort関数シグネチャを Gointerface型を使用するように変更します。

Answer 3

私はちょうど今行くことを学んでおり、qsort では配列をピボットした後に両方の半分を同時にソートできるため、チャネルと並列処理を使用して qsort を単純なタスクとして実装することにしました。私はそのようなもので終わった：

package main

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

func qsort_pass(arr []int, done chan int) []int{
    if len(arr) < 2 {
        done <- len(arr)
        return arr
    }
    pivot := arr[0]
    i, j := 1, len(arr)-1
    for i != j {
        for arr[i] < pivot && i!=j{
            i++
        }
        for arr[j] >= pivot && i!=j{
            j--
        }
        if arr[i] > arr[j] {
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    if arr[j] >= pivot {
        j--
    }
    arr[0], arr[j] = arr[j], arr[0]
    done <- 1;

    go qsort_pass(arr[:j], done)
    go qsort_pass(arr[j+1:], done)
    return arr
}

func qsort(arr []int) []int {
    done := make(chan int)
    defer func() {
        close(done)
    }()

    go qsort_pass(arr[:], done)

    rslt := len(arr)
    for rslt > 0 {
        rslt -= <-done;
    }
    return arr
}

func main() {
    fmt.Println("About to sort.")
    rand.Seed(time.Now().UTC().UnixNano())
    arr_rand := make([]int, 20)
    for i := range arr_rand {
        arr_rand[i] = rand.Intn(10)
    }
    fmt.Println(arr_rand)
    qsort(arr_rand)
    fmt.Println(arr_rand)
}

ここには、パーティションごとに新しい go-routine を生成する代わりに go-routine のプールを使用したり、len(arr) が十分に小さい場合は挿入ソートでソートしたり、[]int 以外のものを使用したりするなど、改善の余地がたくさんあります。しかし、一般的には、開始するのに適した場所のようです。