連想配列を実装したいと思いませんか?
と、言うわけでいろんな実装をしてみましょう
連想配列とは?
連想配列は、key(鍵)とvalue(値)をセットで持ち、keyを渡すとvalueを取れるというものです。
特徴としてはkeyが数字でなくてもよく意味のある文字列が使用できるのでコードが読みやすくなるのです。
まぁ詳しいことはググってください
実装しよう
実装に当って、仕様を決めましょう。以下の3点を実装するものとします。
・連想配列のkeyはアルファベット(26種)から成る文字列。valueは数字(0以上の整数)
・連想配列にデータを追加する.add(key, value) を持つ。(keyが重複する場合は、valueを上書きする)
・連想配列からデータを取り出す .getValue(key) を持つ。(keyに対応するValueが存在しない場合は-1を返す)
ソートやらなんやら、そういった機能は今回は実装しません
言語は最近業務で使ってるVBで書くのでよろしくです
あと、コードは結構適当です。(境界値エラー出ても、そこはまぁ本質ではないんで見逃してくれ)
単純に実装しよう
まずは配列で実装しましょう。連想”配列”ですからね
Public Class asso
Private arryKey(100) As String
Private arryValue(100) As Integer
Public Sub New()
For Each item In arryKey
item = String.Empty
Next
For Each item In arryValue
item = -1
Next
End Sub
Public Sub add(ByVal key As String, ByVal value As Integer)
For i As Integer = 0 To 99
If arryKey(i) = key Then
arryValue(i) = value
Return
ElseIf arryKey(i) = String.Empty Then
arryKey(i) = key
arryValue(i) = value
End If
Next
End Sub
Public Function getValue(ByVal key As String) As Integer
For i As Integer = 0 To 100
If arryKey(i) = key Then
Return arryValue(i)
End If
Next
Return -1
End Function
End Class
まぁ、いたって普通の、誰でも書けるアレですね。
さて、この実装を評価するにあたって、以下の3点の評価基準を設けましょう
1.データを追加するときにどのぐらい時間がかかるか
2.データを取り出すときにどのぐらい時間がかかるか
3.このクラスがどのぐらいメモリを占有するか
それぞれ見ていくと、
1:格納されているデータ数に比例
2:格納されているデータ数に比例
3:100個分=連想配列の持つことの出来る最大量のデータに等しい数
と、なります
うーん、効率が悪いですね。
と、言うわけでまずは2を改善してみましょう。
二分探索で実装しよう
二分探索を使って、たかだか10回ぐらいでデータを探すことが出来るようにしちゃいましょう
Public Function getValue(ByVal key As String) As Integer
Dim head As Integer = 0
Dim tail As Integer = 99
While (1)
Dim pipot As Integer
pipot = (head + tail) / 2
If arryKey(pipot) = String.Empty OrElse arryKey(pipot) < key Then
head = pipot - 1
ElseIf arryKey(pipot) > key Then
tail = pipot + 1
ElseIf arryKey(pipot) = key Then
Return arryValue(pipot)
ElseIf head = tail Then
Return -1
End If
End While
End Function
getValueだけ実装してみました。これで、たかだか10回程度で検索が終わりますね。
ただ、これにも問題があります。それは
・データが整列していないと意味が無い
ということです。ですので、addも修正しましょう
Public Sub add(ByVal key As String, ByVal value As Integer)
Dim pipot As Integer = 0
For i As Integer = 0 To 99
If key = arryKey(i) Then
arryValue(i) = value
Return
ElseIf key > arryKey(i) Then
pipot = i
Exit For
End If
Next
For i As Integer = 99 To pipot + 1
arryKey(i) = arryKey(i - 1)
arryValue(i) = arryValue(i - 1)
Next
arryKey(pipot) = key
arryValue(pipot) = value
End Sub
こんなもんでしょうか。
さて、ここで皆さん思いませんでしたか?
「おいおい、データを追加するときも二分探索しろよ。」と
そうです。連想配列ではデータの追加は同時にデータの検索(keyの衝突が無いかの確認)を行う必要があるということです。
と、言うわけで検索をしない方法を考えましょう
もう少し効率よく
答えから言ってしまうと、ハッシュを使えば解決できます
ざっくりいうと、「keyから一定のルールに則って数値を生成し、それを配列の添え字に相当させるようにする」という感じです。
まずは、keyから数字を生成してみましょう。
アルファベットをa-zで1~26の値を割り振り、以下のルールで数値を生成しましょう
a(1) = (1文字目のアルファベットに対応した数字 + 0) mod 97
a(n) = {a(n-1) × (n文字目のアルファベットに対応した数字) + (n - 1)} mod 97
まぁ、そこそこバラバラとした値が取れます。
なんで最後に97で割っているかというと、最後に素数で割ることで値がイイ感じでばらけるからです。
(もし、この数式で出てくるのが特定の数字の倍数だったとしても、素数で割ることでそういった事態を防げる。
ただ、配列の要素100を目いっぱい使うことは出来なくなってしまうのが難点です)
と、いうわけで以下のようなハッシュ関数を追加しましょう。
Private Function getHashValue(ByVal key As String)
Dim returnValue As Integer = 1
For i As Integer = 0 To key.Count - 1
returnValue = returnValue * getCharValue(key(i)) + i
returnValue = returnValue Mod 97
Next
Return returnValue
End Function
Private Function getCharValue(ByVal c As Char)
Return Asc(c) - Asc("a") + 1
End Function
これで、keyから数値を生成することが出来ました。
これを使って、以下のようにaddとgetValueを改善しましょう
・addメソッドは、配列のどこに格納するかをgetHashValueメソッドから取得した値で決定する(取得した値=格納するindex)
・getValueメソッドは、受け取ったkeyをgetHashValueに渡し、そこから取得した値をindexとしてデータの有無を判断する
Public Class asso
Private arryValue(100) As Integer
Public Sub New()
For Each item In arryValue
item = -1
Next
End Sub
Public Sub add(ByVal key As String, ByVal value As Integer)
Dim index As Integer
index = getHashValue(key)
arryValue(index) = value
End Sub
Public Function getValue(ByVal key As String) As Integer
Dim index As Integer
index = getHashValue(key)
Return arryValue(index)
End Function
Private Function getHashValue(ByVal key As String)
Dim returnValue As Integer = 1
For i As Integer = 0 To key.Count - 1
returnValue = returnValue * getCharValue(key(i)) + i
returnValue = returnValue Mod 97
Next
Return returnValue
End Function
Private Function getCharValue(ByVal c As Char)
Return Asc(c) - Asc("a") + 1
End Function
End Class
これで、性能がどのように変わったか見てみましょう。
これまで
1:データを追加するときは、格納されているデータ数に比例した時間がかかる
2:データを検索するときは、格納されているデータ数に比例した時間がかかる
3:メモリはデータ100個分(保持できる最大サイズ分)占有する
ハッシュを使ったバージョン
1:一定
2:一定
3:メモリはデータ100個分(保持できる最大サイズ分)占有する
割といい感じに改善されたのではないでしょうか。
と、今日はここまでにしておきます(疲れたので)
気が向いたら続きを書きます