Skip to content

Instantly share code, notes, and snippets.

@sasaki-shigeo
Created October 14, 2021 09:48
Show Gist options
  • Save sasaki-shigeo/c0e3f8ad738b7619ffb99bf3d434e6ae to your computer and use it in GitHub Desktop.
Save sasaki-shigeo/c0e3f8ad738b7619ffb99bf3d434e6ae to your computer and use it in GitHub Desktop.
A sample code of linear search in Scala
import scala.collection.mutable
class LinearSearchTable[K, V] extends mutable.AbstractMap[K, V] {
protected val table = new mutable.ArrayBuffer[(K,V)]
private def lin_search(key: K): Int = {
var (ix, result) = (0, -1)
while (ix < table.size &&
{ if (key == table(ix)._1) { result = ix; false } else true })
ix += 1
result
}
protected def index(key: K): Int = lin_search(key)
def get(key: K): Option[V] = {
val ix = index(key)
if (ix == -1)
None
else
Some(table(ix)._2)
}
// put
def addOne(kv: (K, V)) = {
val (key, value) = kv
val ix = index(key)
if (ix == -1)
table += kv
else
table(ix) = kv
this
}
// remove
def subtractOne(key: K) = {
val ix = index(key)
if (ix >= 0)
table.remove(ix)
this
}
def iterator = table.iterator
override def size: Int = table.size
override def clear(): Unit = table.clear()
}
@sasaki-shigeo
Copy link
Author

Scala による線形探索プログラム例

線形探索のアルゴリズムは自明なので,このプログラムは Map の実装例を示すことが目的である。

Scala では AbstractMap トレートを継承すると,Map クラスの様々なメソッドが(自動的に)実装される。
ただし次のメソッドは自前で定義しなければならない。

  • get(key: K): Option[V]
  • addOne(elem: (K, V))
  • subtractOne(key: K)
  • iterator: Iterator[(K, V)]

get で key からvalue を得る,addOne でエントリーを追加する,subtractOne でエントリーを削除するメソッドを定義すればよい。
iterator は,全てのエントリーを得る,先頭のエントリーを得る,末尾のエントリーを得るといった操作を定義するために使用する。
このコードでは,たまたま 1行で記述できたが,通常は iteratorメソッドを定義するのが最も面倒である。

また実行性能を悪化させないため,size メソッド,clear() メソッドも独自に定義する。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment