【Golang】配列の要素を結合する

アムハライさん

2023年8月8日 17:59

はじめに

Go言語の実行時間はPythonよりもはるかに短いため、前にPythonで解いたpaizaラーニングのソート問題集をGoで書いたらどのくらい速いのか試してみたくなりました。

挿入ソート Go編（paizaラーニング　レベルアップ問題集）

問題へのリンクはこちら。

タイムオーバーするの巻

挿入ソートの関数は問題文に擬似言語で書かれているので、Go言語の文法さえ知っていれば難なく書けます。

標準入力の使い方を忘れてしまったので、講座を振り返ったりググったりして何とか書きました（データ受け取り部のコードはこの記事には書きませんが、別の記事で触れようと計画しています）。

ソート後の配列をそのままfmt.Println()の引数にしても、ブラケットが付くので正答にはなりません。
Goでどうすれば良いのか知らないので「Pythonより速いんだし、まあforループで回せばええやろ」と思ったら大誤算でした。

package main

import (
	"fmt"
)

func insertionSort(arr []int) {
	n := len(arr)

	for i := 1; i < n; i++ {
		key := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > key {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = key
		
		// Display the sorted array
		for k:=0; k<n; k++ {
		    fmt.Print(arr[k])
		    if k != n-1 {
		        fmt.Print(" ")
		    }
		}
		fmt.Println()
	}
}

（main関数略）

このコードを通すと、テスト4までは全然問題なし。テスト5から実行時間が爆増し、テスト9でタイムオーバー。（テスト10は通った）

ローカルで実行したところ、テスト9の実行には6秒以上かかるようでした。

生成AIに聞いてみた

挿入ソート部分はどう考えてもこれで間違いない……標準入力もさほど影響はない……となるとforループで出力するのが駄目なのでしょう。
他にどうすれば良いのか？　Pythonのjoin()みたいな関数があるのではないか？
よしAIに聞いてみよう。

生成AIといえばChatGPTという風潮ですが、今回は何となくPerplexityに聞いてみようと思い、質問文を英訳してから突っ込みました。

プロンプト

How to implement a function to join a slice of integers with a space delimiter in Golang

Go言語は配列とはちょっと異なる「スライス」という概念があるので、用語は正確に。

Perplexityの回答

To implement a function to join a slice of integers with a space delimiter in Golang, we can use the `Join()` function from the `strings` package[2][5]. However, since `Join()` expects a slice of strings, we need to convert the slice of integers to a slice of strings first. We can use a loop to convert each integer to a string using the `strconv.Itoa()` function[1][5]. Here's an example of how to implement the function:

情報源
[1] Golang Convert Slice to String: int, string Slices - Dot Net Perls https://www.dotnetperls.com/convert-slice-string-go
[2] How to join a slice to a string in Golang - Educative.io https://www.educative.io/answers/how-to-join-a-slice-to-a-string-in-golang
[3] How to combine (join) strings separated by a separator in a slice of strings in Golang | by Tremaine Eto | Dev Genius https://blog.devgenius.io/how-to-combine-strings-separated-by-a-separator-in-a-slice-of-strings-in-golang-dd5f1b083ea7
[4] Golang concatenate or merge two or more slices [SOLVED] - GoLinuxCloud https://www.golinuxcloud.com/merge-slices-golang/
[5] strings.Join() Function in Golang With Examples - GeeksforGeeks https://www.geeksforgeeks.org/strings-join-function-in-golang-with-examples/
[6] Join a string by delimiter or a separator in Go (Golang) https://golangbyexample.com/go-join-string-delimiter/


package main

import (
    "fmt"
    "strconv"
    "strings"
)

func joinIntsWithDelimiter(ints []int, delimiter string) string {
    strs := make([]string, len(ints))
    for i, num := range ints {
        strs[i] = strconv.Itoa(num)
    }
    return strings.Join(strs, delimiter)
}

func main() {
    arr := []int{1, 2, 3}
    delimiter := " "
    result := joinIntsWithDelimiter(arr, delimiter)
    fmt.Println(result) // "1 2 3"
}

In this example, we define a function `joinIntsWithDelimiter()` that takes a slice of integers `ints` and a delimiter `delimiter` as parameters. Inside the function, we create a new slice of strings `strs` with the same length as the input slice of integers, and use a loop to convert each integer to a string using `strconv.Itoa()`. Finally, we use the `Join()` function to join the resulting slice of strings with the specified delimiter. In the `main()` function, we call `joinIntsWithDelimiter()` with the array and delimiter, and print the result to standard output.

Go言語にも結合用関数があるようですね。Pythonと同じく文字列のみ対応しているので、数値の配列は一旦文字列に変換しなくてはなりません。

integersをstringsにすれば文字列を結合する関数が……と言いたいところですが、 strings.Join() で直接書けるので必要ありませんね。

通過コード（の一部）

この問題の本質は挿入ソートです。処理が一巡するたびに配列の中身を出力するという点が、通常のプログラミングとは異なります（何百、何千というデータ数になんでこんなことするんだろう…とは思います）。

（中略）

func insertionSort(arr []int) {
	n := len(arr)

	for i := 1; i < n; i++ {
		key := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > key {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = key
		
		// Display the sorted array
		fmt.Println(joinIntsWithDelimiter(arr, " "))
	}
}

（main関数略）

実行結果と時間

劇的に改善されました。
Pythonで実行時間が0.03秒になるケースがGoでは0.01秒。C++並みに速いです。

おわりに

いかなGo言語といえど、無計画にループ処理でゴリ押しすると簡単にタイムオーバーになってしまいます。これがスキルテストでなくて良かったです。

Join関数もライブラリ関数があって良かったです~~（ググるだけでも見つかったのでは）~~。