計算量的な問題って

具体的な問題がおきてから考えた方が良い気がしてきた。

RindaのTupleSpaceの検索はO(n)です。テンプレートにあんな形のパターンを許しているので、素朴に書くことにしたから。パターンマッチングの規則を単純なワイルドカードと値だけに限定しておけば良かったな。

で、検索がO(n)で問題になるケースってどういうときなのかしら。

タプルがたーくさんあって、takeする人が少なくて、狙った一つを取り出したい、っていうようなシチュエーションかなあ。そうなるのはどういうときだろ。サービス間の協調に使うとすると、たいてい、タプルのwriteとtakeの収支は合っている（合うことで協調する）と思う（甘いかな?）。
ほら、たくさんタプルを入れて取り出そうとすると遅いだろう！っていうのはわかるけど、どういうときそうなるんだっけ。TupleSpaceはデータベースの代わりにはならないものだって、啓蒙（言い訳）しとこう。

そういえば、あんまり関係ないけどこの本よかった。

• http://www.druby.org/ilikeruby/how2para.html

並列プログラムの作り方