3

私は Go にかなり慣れていないのですが、私のコードには理解できないことが 1 つあります。簡単なバブルソート アルゴリズムを作成しました (あまり効率的ではないことはわかっています ;))。ここで、3 つの GoRoutine を開始します。各スレッドは、他のスレッドとは独立して配列をソートする必要があります。終了したら、fun. 「完了」メッセージを出力する必要があります。

ここに私のコードがあります:

package main 

import (
    "fmt"
    "time" //for time functions e.g. Now()
    "math/rand" //for pseudo random numbers
)


/* Simple bubblesort algorithm*/
func bubblesort(str string, a []int) []int {
    for n:=len(a); n>1; n-- {
        for i:=0; i<n-1; i++ {
            if a[i] > a[i+1] {
                a[i], a[i+1] = a[i+1], a[i] //swap
            }
        }
    }
    fmt.Println(str+" done") //done message
    return a
}

/*fill slice with pseudo numbers*/
func random_fill(a []int) []int {
    for i:=0; i<len(a); i++ { 
        a[i] = rand.Int()
    }
    return a
}

func main() {
   rand.Seed( time.Now().UTC().UnixNano()) //set seed for rand.

   a1 := make([]int, 34589) //create slice
   a2 := make([]int, 42) //create slice
   a3 := make([]int, 9999) //create slice

   a1 = random_fill(a1) //fill slice
   a2 = random_fill(a2) //fill slice
   a3 = random_fill(a3) //fill slice
   fmt.Println("Slices filled ...")

   go bubblesort("Thread 1", a1) //1. Routine Start
   go bubblesort("Thread 2", a2) //2. Routine Start
   go bubblesort("Thread 3", a3) //3. Routine Start
   fmt.Println("Main working ...")

   time.Sleep(1*60*1e9) //Wait 1 minute for the "done" messages
}

これは私が得るものです：

Slices filled ...
Main working ...
Thread 1 done
Thread 2 done
Thread 3 done

彼のスライスが最小なので、スレッド 2 を最初に終了するべきではありませんか? スライスがどれほど大きくても、「完了」メッセージが同時に表示されるため、すべてのスレッドが他のスレッドの終了を待っているようです..

私のブレインバグはどこですか？=)

前もって感謝します。

*編集：バブルソート機能のforループに「time.Sleep（1）」を入れるとき。それはうまくいくようです..しかし、このコードを使用してさまざまなマシンで期間を計りたいので（ランダムなものを変更する必要があることはわかっています）、スリープすると結果が改ざんされます。

4

3 に答える 3

9

確かに、あなたのゴルーチンが実行される順序に関して保証はありません。

ただし、2つのプロセッサコアを明示的に実行させて真の並列処理を強制する場合：

import (
    "fmt"
    "time" //for time functions e.g. Now()
    "math/rand" //for pseudo random numbers
    "runtime"
)
...

func main() {
   runtime.GOMAXPROCS(2)

   rand.Seed( time.Now().UTC().UnixNano()) //set seed for rand.
...

次に、期待される結果が得られます。

Slices filled ...
Main working ...
Thread 2 done
Thread 3 done
Thread 1 done

よろしくお願いします

于 2013-01-18T13:01:27.823 に答える
3

重要なことは、潜在的に長時間実行されるワークロード全体が終了する前に、プロセッサを他のプロセスに「譲る」機能です。これは、シングルコア コンテキストまたはマルチコア コンテキストにも当てはまります (同時実行性は Parallelism と同じではないため)。

これはまさにruntime.Gosched()関数が行うことです:

Gosched はプロセッサーを譲り渡し、他のゴルーチンを実行できるようにします。現在のゴルーチンを中断しないため、実行は自動的に再開されます。

「コンテキストの切り替え」は無料ではないことに注意してください。毎回少し時間がかかります。

  • 私のマシンでは、あなたのプログラムは 5.1 秒で動作します。
  • 外側のループ ( for n:=len(a); n>1; n--) で譲歩すると、5.2 秒で実行されます。わずかなオーバーヘッドです。
  • 内側のループ ( for i:=0; i<n-1; i++) で譲ると、61.7 秒で実行されます: 巨大なオーバーヘッド !!

以下は、わずかなオーバーヘッドで、正しく生成される変更されたプログラムです。

package main

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

/* Simple bubblesort algorithm*/
func bubblesort(str string, a []int, ch chan []int) {
    for n := len(a); n > 1; n-- {
        for i := 0; i < n-1; i++ {
            if a[i] > a[i+1] {
                a[i], a[i+1] = a[i+1], a[i] //swap
            }
        }
        runtime.Gosched() // yield after part of the workload
    }
    fmt.Println(str + " done") //done message
    ch <- a
}

/*fill slice with pseudo numbers*/
func random_fill(a []int) []int {
    for i := 0; i < len(a); i++ {
        a[i] = rand.Int()
    }
    return a
}

func main() {
    rand.Seed(time.Now().UTC().UnixNano()) //set seed for rand.

    a1 := make([]int, 34589) //create slice
    a2 := make([]int, 42)    //create slice
    a3 := make([]int, 9999)  //create slice

    a1 = random_fill(a1) //fill slice
    a2 = random_fill(a2) //fill slice
    a3 = random_fill(a3) //fill slice
    fmt.Println("Slices filled ...")

    ch1 := make(chan []int) //create channel of result
    ch2 := make(chan []int) //create channel of result
    ch3 := make(chan []int) //create channel of result

    go bubblesort("Thread 1", a1, ch1) //1. Routine Start
    go bubblesort("Thread 2", a2, ch2) //2. Routine Start
    go bubblesort("Thread 3", a3, ch3) //3. Routine Start
    fmt.Println("Main working ...")

    <-ch1 // Wait for result 1
    <-ch2 // Wait for result 2
    <-ch3 // Wait for result 3
}

出力:

Slices filled ...
Main working ...
Thread 2 done
Thread 3 done
Thread 1 done

また、以前のコメントで提案したように、チャネルを使用してランデブーを実装しました。

よろしくお願いします ：）

于 2013-01-21T11:05:32.353 に答える
3

Go 1.2 のリリース以降、元のプログラムが動作 するようになりました。修正しなくても問題なく動作する可能性があります。Playgroundで試すことができます。

これは、Go 1.2 リリース ノートで説明されています。

以前のリリースでは、永久にループしていたゴルーチンが同じスレッド上の他のゴルーチンを枯渇させる可能性がありました。これは、GOMAXPROCS が 1 つのユーザー スレッドしか提供しなかった場合に深刻な問題でした。Go 1.2 では、これは部分的に対処されています。スケジューラは、関数へのエントリ時に時々呼び出されます。

于 2013-12-30T09:04:48.950 に答える