関数プログラミングのアプローチ (25)

配列

配列は、プログラミングにおいて、もっとも基本的なデータ構造です。しかし、関数プログラミングにおいて、配列の取り扱いは問題を孕んでいます。今回は、関数プログラミングにおける配列の問題について考える前に、配列の特徴について確認します。
配列の特徴は次のようにまとめられます。

サイズが可変長で初期化時に決まる
キーが０から始まる連続的な整数
メモリ上での表現が非常にコンパクト
参照と更新が定数時間で非常に効率的

このような特徴のため、プログラミングにおいて配列は、さまざまな重要なアルゴリズムで利用されています。ここでは例として２つのアルゴリズムを取り上げます。

ハッシュテーブル

ハッシュテーブルは、シンボルテーブルの実装アルゴリズムの１つで、定数時間の参照・更新を実現します。これは、バランス木による実装よりも効率的であるため、特別な理由がない場合はシンボルテーブルはハッシュテーブルとして実装することが普通です。
ハッシュテーブルは、内部で配列を利用します。

table = [None] * TABLESIZE

そして、要素にアクセスするには、キーのハッシュ値を取得して、それをインデックスとして配列にアクセスします。配列の値のキーが等しければそれが求める要素で、違うならば配列の次の要素を順に確認します。

def get (key):
    idx = hash(key) % len(table)
    while table[idx]:
        if key == getKey(table[idx]):
            return getValue(table[idx])
        else:
            idx = (idx + 1) % len(table)

更新の場合も、同様の方法で対応する配列のインデックスを取得し、新しい値で配列の値を書き換えます。

ダイクストラ法

ダイクストラ法は、グラフ中の２つのノードをつなぐ最短のパスを求めるの１つです。この手法は動的計画法（Dynamic Programming）の１種で、計算中の状態を記録する配列を用意し、計算が進むに従って配列を書き換えていきます。
ダイクストラ法では、各ノードについての開始ノードからの現在の距離を記録する配列と、各ノードの直前のノードを記録する配列と、計算が進行中のノードを管理するプライオリティキューを利用します。

def shortestPath (graph, s, t):
    wt = [MAXNUM] * graph.size
    spt = [-1] * graph.size
    pq = PriorityQueue(graph.size)

    pq.insert(graph.node(s))
    while pq.empty():
        v = pq.getMin()
        if v.idx == t:
            ls = [t]
            while spt[t] >= 0:
                t = spt[t]
                ls.insert(0, t)
            return ls

        for e in graph.adjacent(v.idx):
            if wt[e.idx] > wt[v.idx] + 1:
                wt[e.idx] = wt[v.idx] + 1
                if spt[e.idx] < 0:
                    pq.insert(e)
                else:
                    pq.update(e)
                spt[e.idx] = v.idx

    return None

さらに、プライオリティキューの代表的なアルゴリズムにヒープがありますが、これも配列を用います。ヒープは２分木の１種ですが、木を配列とインデックスの値を用いて表現します。

pq = [None] * HEAPSIZE
lastindex

def insert (e):
    lastindex = lastindex + 1
    pq[lastindex] = e
    idx = lastindex
    while idx > 1:
        idx2 = idx / 2
        if pq[idx2] > pq[idx]:
            t = pq[idx2]
            pq[idx2] = pq[idx]
            pq[idx] = t
            idx = idx2
        else:
            break

このように、配列はさまざまなアルゴリズムで基本的なデータ構造として利用されています。