Scalaで定番なアルゴリズムを書いてみる

ユークリッドの互除法

最大公約数をもとめるやつです

GPT-4

// 再帰的なユークリッドの互除法
def gcd(a: Int, b: Int): Int = {
  if (b == 0) {
    a // bが0のとき、aが最大公約数
  } else {
    gcd(b, a % b) // そうでなければ、bとa % bで再帰的に求める
  }
}

// テスト
val a = 56
val b = 98
println(s"最大公約数: ${gcd(a, b)}") // 予想される結果: 14

Claude3 Opus

def gcd(a: Int, b: Int): Int = {
  if (b == 0) a else gcd(b, a % b)
}

// 使用例
val num1 = 24
val num2 = 36

val result = gcd(num1, num2)
println(s"$num1 と $num2 の最大公約数は $result です。")

GPT-4は一発で動くコードを書いてきた
Opusは変数と文字のスペースがなくてビルドエラーしてて、直させたコード
関数の書き方はOpusの方が簡潔にみえる

僕は仕事でJavaを書いているけどScalaって戻り値あっても
return書く必要ないっぽい！
最後の行が結果として返却される！
簡潔で良い！
Scala好き

エラトステネスのふるい

素数を求める

GPT-4

// エラトステネスのふるいを実装
def sieveOfEratosthenes(n: Int): List[Int] = {
  // すべての数を素数と仮定し、後で確認していく
  val primes = Array.fill(n + 1)(true) // 素数であるかどうかのフラグ
  primes(0) = false // 0は素数ではない
  primes(1) = false // 1も素数ではない

  // 2から開始し、平方根まで範囲を広げる
  for (p <- 2 to math.sqrt(n).toInt) {
    if (primes(p)) { // pが素数なら
      // pの倍数はすべて素数ではないとマーク
      for (i <- p * p to n by p) {
        primes(i) = false
      }
    }
  }

  // 素数のリストを返す
  (2 to n).filter(primes(_)).toList
}

// テスト
val limit = 50 // 0から50までの素数を求める
println(s"素数: ${sieveOfEratosthenes(limit)}")

Claude3 Opus

def sieve(n: Int): List[Int] = {
  val primes = collection.mutable.ListBuffer.range(2, n + 1)
  val limit = math.sqrt(n).toInt

  for (i <- 2 to limit) {
    if (primes.contains(i)) {
      primes --= (i * i to n by i)
    }
  }

  primes.toList
}

// 使用例
val maxNumber = 100
val primeNumbers = sieve(maxNumber)
println(s"$maxNumber 以下の素数: $primeNumbers")

今回はOpusも一発でビルドできるコード書いてくれた
これはステップ数見ても明らかにOpusの方が
簡潔でみやすいコード書いてくれてる。
ただ、ChatGPTはコメントをつけてくれていて親切。

あとJavaやPythonで見慣れない記号があったので聞いてみた

--=と<-は、Scalaの構文で使用される特殊な記号です。それぞれの意味を説明しますね。--=：
--=は、ミュータブルなコレクション（ListBufferなど）から複数の要素を削除するために使用されます。
例えば、primes --= (i * i to n by i)という式は、primesというListBufferから、i * iからnまでの範囲でiの倍数である要素を削除することを意味します。
--=の左側にはミュータブルなコレクションを指定し、右側には削除したい要素またはコレクションを指定します。
<-：
<-は、Scalaのfor式で使用される記号で、ジェネレータと呼ばれます。
ジェネレータは、コレクションや範囲から要素を順番に取り出すために使用されます。
例えば、for (i <- 2 to limit)という式は、2からlimitまでの範囲の値をiに順番に割り当てながらループを実行することを意味します。
<-の左側には変数を指定し、右側にはコレクションや範囲を指定します。

Claude3 Opus

なるほど。
関数型プログラミングは奥が深いな。

線形探索

線形探索（Linear Search）は、配列やリストなどのデータ構造内で、要素を順番にチェックしていく単純な検索アルゴリズムです。目的の要素を見つけると、そのインデックスを返し、見つからない場合は特定の値（例えば、-1）を返します。

GPT-4

GPT-4

// 線形探索を実装
def linearSearch[T](array: Array[T], key: T): Int = {
  for (i <- array.indices) { // インデックスを使って探索
    if (array(i) == key) { // キーと一致する場合
      return i // インデックスを返す
    }
  }
  -1 // 見つからなかった場合は -1 を返す
}

// テスト
val arr = Array(5, 2, 8, 3, 7, 1, 9)
val key = 7
val index = linearSearch(arr, key)
if (index != -1) {
  println(s"要素 $key はインデックス $index にあります")
} else {
  println(s"要素 $key は見つかりませんでした")
}

Claude3 Opus

def linearSearch[T](list: List[T], target: T): Option[Int] = {
  val index = list.indexOf(target)
  if (index != -1) Some(index) else None
}

// 使用例
val numbers = List(5, 2, 8, 12, 1, 6, 9, 3)
val target = 6

val result = linearSearch(numbers, target)
result match {
  case Some(index) => println(s"$target は インデックス $index に見つかりました。")
  case None => println(s"$target は見つかりませんでした。")
}

線形探索は順番に探していくだけなのでシンプルなアルゴリズムですね。
Opusは簡潔、GPT-4は親切ですね。

２分探索

GPT-4

// 2分探索を実装
def binarySearch(array: Array[Int], key: Int): Int = {
  var low = 0 // 探索範囲の下限
  var high = array.length - 1 // 探索範囲の上限

  while (low <= high) { // 範囲がある限り探索を続ける
    val mid = (low + high) / 2 // 中間点
    if (array(mid) == key) {
      return mid // キーが見つかった場合、中間点を返す
    } else if (array(mid) < key) {
      low = mid + 1 // キーが中間点よりも大きければ、下限を更新
    } else {
      high = mid - 1 // キーが中間点よりも小さければ、上限を更新
    }
  }

  -1 // キーが見つからなかった場合、-1を返す
}

// テスト
val sortedArray = Array(1, 3, 5, 7, 9, 11, 13, 15)
val key = 7
val index = binarySearch(sortedArray, key)
if (index != -1) {
  println(s"要素 $key はインデックス $index にあります")
} else {
  println(s"要素 $key は見つかりませんでした")
}

Claude3 Opus

def binarySearch[T](list: List[T], target: T)(implicit ord: Ordering[T]): Option[Int] = {
  def search(low: Int, high: Int): Option[Int] = {
    if (low > high) {
      None
    } else {
      val mid = (low + high) / 2
      val midValue = list(mid)
      if (ord.equiv(midValue, target)) {
        Some(mid)
      } else if (ord.lt(midValue, target)) {
        search(mid + 1, high)
      } else {
        search(low, mid - 1)
      }
    }
  }

  search(0, list.length - 1)
}

// 使用例
val numbers = List(1, 2, 3, 5, 6, 8, 9, 12)
val target = 6

val result = binarySearch(numbers, target)
result match {
  case Some(index) => println(s"$target は インデックス $index に見つかりました。")
  case None => println(s"$target は見つかりませんでした。")
}

Opus側、繰り返し処理どこにあるんだ？
と思ったらsearch内で自分で自分を呼び出していた！
再帰関数というらしい。
勉強になるなぁ。