インタプリタ処理系のMicroPythonとコンパイラのTinyGoを比べるのもどうかと思うのですが。MicroPythonは「フルセットのPythonのライブラリのサブセット」を実装、一方TinyGoは「フルセットのGoのライブラリの一部」を使用可能というスタンスみたいっす。今回は乱雑な順に乱雑な値を入れても出すときは順番にならんでいるヒープ構造をTinyGoで使ってみます。
※「GoにいればGoに従え」Go関連記事の総Index
ヒープ構造（ヒープ・ソートのヒープね）
以下のMicroPython記事で、heapqと呼ぶモジュールを使ってみてます。
MicroPython的午睡(112) ESP32版、heapqで乱雑タプルを昇順にとりだす
ランダムな値をこれまたランダムな順番に投入しても、取り出すときにはあら不思議、数値の小さいものから取り出せる構造です。
TinyGoの場合、Go言語の標準ライブラリにheapと呼ぶコンテナあり、これを使うとheapq的なものを作成することが可能であります。Go言語のマニュアルページが以下に。
上記の標準ライブラリは、以下のTinyGoのサポートパッケージリストでは、ImportableかつPasses testsということで安心して使えるみたいっす。
ただし、出来合いでテキトーに使えるMicroPythonのheapqに比べると、汎用性の高い入れ物が用意されていて、それに合わせた内部構造は自前で準備しないとならないGo言語のライブラリという行き方の違いがあるみたいです。
今回は、Go言語のマニュアルページのサンプルプログラムをベースに、まずは「簡単な」テキトーに乱数をぶち込んでも順番に出てくる様子を実験してみたいと思います。なお、乱数生成には、ターゲット機 BBC micro:bit v2搭載のハードウエア乱数発生器を利用です。実験記事が以下に。
GoにいればGoに従え(21) TinyGo、乱数発生器よみとり、micro:bit v2
今回実験のTinyGoソースコード
TinyGoは、Go言語とほぼほぼ同等なソースで書ける感じです。今回の「ヒープ」に関してもGoの例題そのままデス。注意が必要なのは machineパッケージのようなマイコン機種依存性のある部分だけですかね。
package main
import (
"container/heap"
"fmt"
"machine"
)
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
for i := 0; i < 5; i++ {
rnd, er := machine.GetRNG()
if er == nil {
heap.Push(h, int(rnd >> 2))
}
}
fmt.Printf("minimum: %d\n", (*h)[0])
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
}
前の方に、「func (h なんたら」という奴らが並んでますが、こやつらがユーザ定義型 type IntHeapを container/heapを使ってヒープ化するときに必須のメソッドみたいです。ダラダラならんでいるメソッドの中にはこのソース内で使われていないメソッドもあるのですが、こやつらを定義しないとヒープとして働けないのでエラーになります。
実験結果
上記のソースをビルドしてターゲット機BBC micro:bit v2 に書き込むのはプロジェクトフォルダ内でいつものように以下です。
$ tinygo flash --target microbit-v2
実行結果が以下に。
ちゃんと昇順で取り出せてるみたいです。ヒープソートは出来るってこってすかい？