まずは、List型からみて見ましょう。と、その前に。RedisのList型の概要と、サポートされる操作のドキュメントがどこにあるか見ておきましょう。
公式のドキュメント があります。Listの概要はデータ型に関するドキュメントに書かれていますね。Listがサポートするコマンドのドキュメントもあるようです。英語ですけど、今は気にしないでおいてください。今は、「ふーん、List型ってのがあって、そのリスト型に対してなんかいろんな操作が出来るんだな」って眺めるくらいでいいです。
わたしがドキュメントを見た感じ、どうやら Redis の List 型はいわゆる「双方向リスト」のようです。では、双方向リストというのがどういうものなのか、実例を交えてみてみましょう。
と、その前に、最も簡単なリストの例、「単方向リスト」を見てみましょう。リストは、「要素」が複数集まったものです。では、この「集合」をどのようにデータで表現すればいいでしょうか。自分で 書いてみましょう。言語に用意された配列を使ったらそれは「ずる」だからダメですよ！
# -*- coding: utf-8 -*-
class Element
# リストの各要素は、「値」と、「次の要素」を持つ
attr_accessor :next_element
attr_reader :value
def initialize(value)
@value = value
end
end
class List
# newした時点ではからっぽ
def initialize
# リストは「最初の要素」を持つ
@first_element = :end_of_list
end
# リストの最初に値を追加する
def unshift(value)
# 要素を作って
element = Element.new(value)
# 「次の要素」に「この時点での最初の要素」を指定して
element.next_element = @first_element
# 「最初の要素」を、今作った要素に更新する
@first_element = element
end
# リストの内容を全て表示する
def dump
current_element = @first_element
# 最初の要素からどんどん「次の要素」を辿って行く
print "[ "
loop do
break if current_element == :end_of_list
print "#{current_element.value} "
current_element = current_element.next_element
end
print "]\n"
end
end
list = List.new
list.dump # =>[ ]
list.unshift(1) # 1という値をlistの最初につっこむ
list.dump # => [ 1 ]
list.unshift("はぁアスカ")
list.dump # => [ "はぁアスカ" 1 ]
list.unshift("にゃん")
list.dump # => [ "にゃん" "はぁアスカ" 1 ]こんな感じで、各要素が「自分のうしろの要素はこいつだよ！」っていう情報を持っておけば、「最初の要素」からぐんぐん要素を辿って行くことで、リストを表現することができます。
今は List#unshift メソッドしか存在しないので、n番目の要素を取り出したい、みたいなことができないですね、では、n番目の要素を取り出す、List#[]メソッドを定義してみましょう。
def [] requested_index
current_index = 0
current_element = @first_element
loop do
raise ArgumentError "invalid index" if current_element == :end_of_list
return current_element.value if requested_index == current_index
current_element = current_element.next_element
current_index += 1
end
endはい、同じような感じで、前から順に辿って行って要素を見つけることができました。
おなじような感じで、listの要素数を求める List#size とか、n番目に要素を挿入する List#insert とかも書けそうですね。めでたしめでたし。
でもちょっと待ってください。こういうデータの持ち方(データ型)をしておくと、リストの要素数が知りたくなるたびに要素を全部辿って行かないとだめですね。非効率です。それどころか、リストの最後のほうに要素を挿入したい、なんてときにも、えらく大変です。要素数が5個のときにはまだ全然いいけれど、要素数が1000000個だったらけっこう無視できないくらい効率が悪くなりそうです。そこで、計算量の話をしましょう。
O(n) とか O(1) とか、O(log n)とかそういうアレです。ここはほんとうに「ざっくり」で説明します。
これは何を表しているかというと、「処理すべきデータの量が n 倍になったときに、計算量がどれくらい増えるか」、つまり、データの量によって増える計算量の「増え方」のことを表しています。たとえば、O(n)ならば、データの量が n 倍になったら、計算量も n 倍になることを示します。たとえば、先ほどの実装の単方向リストにおける、List#size なんかは、データが1個のときには、1回要素を辿るだけで済みます。データが 1000 個あれば、1000 回要素を辿らなければいけません。つまり、データが 1000 倍の量になったとき、処理量が 1000 倍になっていますね。こういうようなものを、「計算量がO(n)である」みたいに言います。
ちなみに、例えばデータの量が n 倍になったときに計算量が 2n 倍になるみたいなやつとか 2n + 2倍になるみたいなでも、O(n)と表記します。というのは、(あとで出てきますが) n の 2 乗倍とか、 n の n 乗倍になるみたいなやつとかとくらべたら、定数倍なんてのは誤差みたいなもんで、増えるその増え方の次数くらいしか現実では問題にならないからです。このへんの、「実を取る」感じが工学っぽくて面白いなって思いますね。
今回実装した単方向リストでは、List#index の計算量はO(n)になります。あいまいな日本語で言い直せば、「データが増えれば増えるほど、計算量がデータが増える量と同じような増え方で増えて行く」ってことですね。100 個の要素を持った list の List#index は、1 個の要素を持ったList#indexよりも 100 倍(というよりも、その定数倍)遅くなるわけです。
では、リストの要素をリストの最初に突っ込む List#unshift はどうでしょうか。いくら大きなリストに大しても、やることは変わりません、現在の最初の要素の前に、新しい要素を挿入するだけです。10個の要素を持ったリストであろうが、10000000000個の要素を持ったリストであろうが、計算量が変わりませんね。つまり、データが n 倍になっても、計算量は1倍のままです。これはO(1)ですね。
さて、今は単方向リストの例を見てみましたが、双方向リストはどうでしょうか。単方向リストは「前から順々に辿ることができる」リストでしたが、双方向リストはそれを「後ろからも辿れる」ようにしたものです。
Element クラスは next_element のほかに previous_element を持つ必要があるでしょう。Listクラスは、first_element だけではなく、last_elementも持つ必要がありそうですね。
データの探索系の計算量は、うまくいくと単方向リストの 1/2 にできますね。でもこれは定数倍なので、探索系の計算量はO(n)です。 unshift のコストは :next_element だけじゃなくて :previous_element も持つ必要があるので、うまくやっても単方向リストの 2 倍かかりそうです。もちろんここも定数倍なので、計算量はO(1)で変わりません。
では、リストの最後に要素を追加するようなメソッド List#push を考えてみましょう。単方向リストの場合、まずは「末尾」を探すために最初からじゅんぐりにデータを辿って行く必要があり、これはデータが増えれば増えるほど、「それとおなじように」増大するコストです。O(n)ですね。一方、双方向リストであれば、List自体が「最後の要素」を持ってるので、最後の要素を探す必要がなく、どんなにおおきなリストであろうとも、一発で最後の要素を見つけることができます。O(1)ですね！Yay！
ではここで、Redisのドキュメントに戻りましょう。
まずは、リストのサイズを問い合わせるLLENというコマンドのドキュメントを読んでみましょう。
Time complexity: O(1)
エッ！？ 単純な双方向リストでは数を数えるためにすべての要素をたぐる必要があったし、O(N)のはずでは！？ と思われた方、するどいですね。これはおそらく、Redis の List 型は、内部に要素数も持っているのでしょう。要素が挿入されるときにその要素数をインクリメントして、要素が削除されるときにその要素数をデクリメントするようにすれば、要素数はすでにList自身が知っているので、O(1)で返すことができますね。賢いやり方だと言えると思います。
次に、前からみてn番目の要素を取り出す、LINDEXというコマンドのドキュメント を読んでみましょう。
Time complexity: O(N) where N is the number of elements to traverse to get to the element at index. This makes asking for the first or the last element of the list O(1).
とありますね。N 番目のエレメントをgetするための計算量は O(N) だよ、まあ、そんなわけで、最初のエレメントとか最後のエレメントはO(1)で取って来れるよ、と言ってますね。うん、双方向リストだから、当然っちゃ当然です。さらに、前からn番目の要素を取り出すコマンドなのに、最後の要素をO(1)で取り出せるのは、先ほどの LLEN がO(1)で取り出せるのが利いてますね。LIST は自分の要素数を知っているので、 LINDEXで指定されたインデックスが後ろに近いインデックスならば内部では後ろからたぐればいいし、LINDEXで指定されたインデックスが前に近ければ、前からたぐればいいわけです。逆に言うと、真ん中のほうにあるデータを取ってくるときが一番遅い、ということですね。
と思ったら、ちゃんと公式のデータ型に関するドキュメントにその旨が書いてありました。
Accessing elements is very fast near the extremes of the list but is slow if you try accessing the middle of a very big list, as it is an O(N) operation.
その他のコマンドについても、双方向リストであることを頭に入れた上でドキュメントを読んでみると、「あーなるほどねーたしかにねー」って感じになると思います。
余談になってしまいますが、わたしが「こりゃ面白いな」と思ったコマンドとして、BLPOPとBRPOPがあります。前から/後ろから要素を一個抜き出して持ってくるものなのですが、リストが空だったときにはそこでブロックして、リストに要素が挿入されたタイミングでブロッキングを抜けて要素を返すというコマンドですね。なんかおもしろいことに使えそうな感じがします。というか、ジョブキューみたいなのにぴったりですね。ブロッキングって何？ってひとは、(手前味噌ですが)Shinpeim/process-bookがオススメです。
You can do many interesting things with Redis Lists, for instance you can:
- Model a timeline in a social network, using LPUSH in order to add new elements in the user time line, and using LRANGE in order to retrieve a few of recently inserted items.
- You can use LPUSH together with LTRIM to create a list that never exceeds a given number of elements, but just remembers the latest N elements.
- Lists can be used as a message passing primitive, See for instance the well known Resque Ruby library for creating background jobs.
こういうリストがうれしいパターンについて、公式は「こんなときとかに良いかもね」と言ってくれていますね。なるほど感あります。
このような、ある要素が別の要素に対して参照を持つ形で表現されるリストのことを、「リンクリスト」とか「連結リスト」と言います。リンクリストには、今回見た単方向リスト、双方向リストの他にも、循環リスト(一番最後の要素が一番最初の要素を参照していて、ぐるぐると循環するリスト)などがあるので、興味のある方は調べてみると良いかと思います。