#79 JasmineTeaでマージソートを書いてみた

2023 / 12 / 18

本記事は Jasmine Tea アドベントカレンダー 2023の18日目です。

学習用プログラミング言語/環境であるJasmineTeaというのがあります。

ブラウザだけでプログラムを書いて実行できます。アカウント登録なしでもお試しできます。こちらから。

マージソート

マージソートはアルゴリズム学習の序盤ででてくるソートです。配列Aを入力として、次のようにソートします。

1. 配列Aを前半と後半の2つにわける
2. 前半と後半をそれぞれ(マージ)ソートする
3. ソート済の前半と後半をマージする

マージする操作は次のようにやります。ソート済のトランプの山を2つ用意して、小さい順にカードを取っていくイメージです。

1. 前半が空だったら、後半の残りを全部くっつける
2. 後半が空だったら、前半の残りを全部くっつける
3. 前半の先頭と後半の先頭をみて、小さいほうを1つとってくっつける
4. 1番に戻る

よく訓練されたエンジニアはGoを使っているはずなので、Goで書いてみましょう。

package main

import (
  "fmt"
  "math/rand"
  "time"
)
  
func mergeSort(arr []int) []int {
  if len(arr) <= 1 {
    return arr
  }
  mid := len(arr) / 2
  left := mergeSort(arr[:mid])
  right := mergeSort(arr[mid:])
  return merge(0, left, 0, right)
}
  
func merge(l int, left []int, r int, right []int) []int {
  if l == len(left) {
    return right[r:]
  }
  if r == len(right) {
    return left[l:]
  }
  if left[l] <= right[r] {
    return append([]int{left[l]}, merge(l+1, left, r, right)...)
  }
  return append([]int{right[r]}, merge(l, left, r+1, right)...)
}
  
func main() {
  // 計算量を体験するために2倍に増やしながら実行してみる
  size := 10
  for size < 200000 {
    arr := make([]int, size)
    for i := 0; i < size; i++ {
      arr[i] = rand.Intn(10000)
    }
    start := time.Now().UnixMilli()
    sorted := mergeSort(arr)
    _ = sorted
    end := time.Now().UnixMilli()
    fmt.Printf("size=%d Time taken: %v ms\n", size, end-start)
    size *= 2
  }
}

JasmineTeaで書いてみる

JasmineTeaはBASIC風味の文法に配列と関数定義等が入った言語です。関数を定義できるのでがんばってマージソートを書いてみます。

function mergeSort@(arr@)
  size = len(arr@)
  if size = 0 then
    return []
  else if size = 1 then
    return [arr@[0]]
  end if
  center = truncate(size / 2, 0)
  left@ = split@(arr@, 0, center)
  right@ = split@(arr@, center, size)

  left@ = mergeSort@(left@)
  right@ = mergeSort@(right@)
  return merge@(0, left@, 0, right@)
end function

function split@(arr@, i, e)
  if i = e then
    return []
  end if
  return [arr@[i]] + split@(arr@, i + 1, e)
end function

function merge@(l, leftArr@, r, rightArr@)
  if l = len(leftArr@) then
    if r = len(rightArr@) then
      return []
    end if 
    return [rightArr@[r]] + merge@(l, leftArr@, r + 1, rightArr@)
  else if r = len(rightArr@) then
    return [leftArr@[l]] + merge@(l + 1, leftArr@, r, rightArr@)
  else
    if leftArr@[l] < rightArr@[r] then
      return [leftArr@[l]] + merge@(l + 1, leftArr@, r, rightArr@)
    else
      return [rightArr@[r]] + merge@(l, leftArr@, r + 1, rightArr@)
    end if
  end if
end function


print "入力作成中"
startTime = time()
in@ = []
for i = 1 to 100
  in@ = in@ + [random(0, 10000)]
next
endTime = time()
print "時間は"; (endTime - startTime)

print "ソートするよ"
startTime = time()
sorted@ = mergeSort@(in@)
endTime = time()
print sorted@
print "時間は"; (endTime - startTime)

入力を作るところ以外はforを使わず再帰で書いてみました。いくつか気をつける点があります。

割り算に気をつける

JasmineTeaはJavaScriptのように数値型しかありません。なので配列の長さの半分を求める際、 size / 2 と書くと奇数のときに0.5が登場してしまいます。これを避けるために truncate(value, 0) を使います。

配列に要素を追加する際に[]が必要

JasmineTeaの配列は+で連結することができます。オペランドは両方配列である必要があるので、1要素だけ追加したい場合は[]を使って1要素の配列とする必要があります。

動かしてみる

入力の長さを変えながら実行してみます。


// 100個  
入力作成中
時間は32
ソートするよ
(中略)
時間は211
OK

// 200個
入力作成中
時間は45
ソートするよ
(中略)
時間は380
OK

// 400個
入力作成中
時間は60
ソートするよ
(中略)
時間は840
OK

// 800個
入力作成中
時間は83
ソートするよ
(中略)
時間は1954
OK

// 1600個
入力作成中
時間は265
ソートするよ
関数の呼び出し回数が多すぎます(36行目)
OK

1600個でスタックオーバーフローしてるようです。また入力の作成でも線形でない時間がかかっているように見えます。JasmineTeaの制約の中で改善してみましょう。

mergeの再帰をループで書き直してみる

mergeの中でスタックオーバーフローしているので、残念ではありますがforループで書き直してみます。

function merge@(leftArr@, rightArr@)
  l = 0
  r = 0
  result@ = []
  do
    if l = len(leftArr@) then
      if r = len(rightArr@) then
        return result@
      end if
      result@ = result@ + [rightArr@[r]]
      r = r + 1
    else if r = len(rightArr@) then
      result@ = result@ + [leftArr@[l]]
      l = l + 1
    else
      if leftArr@[l] < rightArr@[r] then
        result@ = result@ + [leftArr@[l]]
        l = l + 1
      else
        result@ = result@ + [rightArr@[r]]
        r = r + 1
      end if
    end if
  loop
end function

これで1600個もソートできました。

入力作成中
時間は242
ソートするよ
(中略)
時間は6060
OK

splitもループで書き直してみる

さらに入力を増やし、3200個で試すと今度はsplit()でスタックオーバーフローしました。こちらもループで書き直してみます。

function split@(arr@, i, e)
  result@ = []
  // 引数でiを使っちゃったのでjを使う
  for j = i to e - 1
    result@ = result@ + [arr@[j]]
  next
  return result@
end function

これで少なくとも12800個の要素までソートできました(72秒もかかりました)。

まとめ

JasmineTeaでマージソートを書いてみました。配列のみで書くのは結構たいへんですが、他のアルゴリズムも時間があれば実装してみたいと思います。