EssenMemo0005

Essenの開発メモ#0005

• (by K, 2017.05.24)

virtual-index

• (1) 現在、Essenに仮想インデックスという仕組みを導入したらどうだろうかと考えています。

• (2) 順を追って説明します。たとえば、以下のような配列があったとします。

  a[0] = (name:"Taro" age:15)
  a[1] = (name:"Jiro" age:12)
  a[2] = (name:"Sabu" age:10)

• ここでa[0]は誰ですか？と問い合わせて答えを得ることは、ほぼすべての言語で標準的にできるでしょう。
• Essenでもできますが、それ以外にも、name順で並べたときのa[1]は誰か？という問い合わせもできます。さらにage順で並べたときのa[2]は誰か？ということも答えられます。
• 記法をまだ考えていないのですが、とりあえずこうしておきましょう。

  >print searchElement(a, "name", 1)
  (name:"Sabu" age:10)
  
  >print searchElement(a, "age", 2)
  (name:"Taro" age:15)

• こういうことができるので、最大値とか最小値とかを簡単に探せます。わざわざループとかまわさないでいいです。

• 次にできることとして、要素を返すのではなく、配列の何番目なのかを答えさせることもできます（サブインデックスから、メインインデックスを答えさせる）。

  >print searchIndex(a, "name", 1)
  2
  
  >print searchIndex(a, "age", 2)
  0

• まあ要するに、 searchElement(a, ...) == a[searchIndex(a, ...)] であります。

• さらに発展させて、a[1]は"name"では何番目なのか？という問い合わせも可能です（メインインデックスから、サブインデックスを答えさせる）。

  >print searchIndex(a, 1, "name")
  0

• (3) さて本題の仮想インデックスです。
• 仮想インデックスは、要素内の定数ではなく、動的に変わる変数のような性質を持つものです。

  a[0] = (name:"Taro" age:15 extra:virtualIndex)
  a[1] = (name:"Jiro" age:12 extra:virtualIndex)
  a[2] = (name:"Sabu" age:10 extra:virtualIndex)

• それでは、extraの値を表示してみます。

  >print (a[0].extra a[1].extra a[2].extra)
  (0 1 2)

• ほら、なんだか分からないですが、なにやら整数が入っているようです。
• では、値を変更してみましょう。

  >a[2].extra = 0
  >print (a[0].extra a[1].extra a[2].extra)
  (1 2 0)

• これは何が起きたかというと、a[2].extraが0になったので、a[0].extraとa[1].extraが後ろへずれたんです。

  - イメージ -
  before: a[0] a[1] a[2]
  after:  a[2] a[0] a[1]

• つまりvirtual-indexは要素の順番を管理する機能を持っていて、この"extra"を参照したり操作したりすればいいわけです。
• ひとつの配列に複数のvirtual-indexを持たせて、別々の順番を持たせることもできます。
  • 「extraでの8番目の要素を削除」
  • 「extraでの2番目の要素は、extra2での何番目なのか？」
• virtual-indexは値を変更すると後ろが全部自動でずれるので、さぞかし処理速度が遅いだろうなと思うかもしれませんが、内部ではFastIndexを使っているので、O(logN)で済みます。つまりNが大きくても問題にならないくらい高速です。

Essenが目指しているもの

• このように、Essenではたいていのことが配列だけでできます。・・・リスト構造をどうしようかとか、二分木をいれようとか、そういうことを悩む必要はないです。面倒なことは全部言語に任せて、とにかく配列に入れておいて、いろんな順序を管理する必要があればvirtual-indexを追加すればいいんです。それでも十分な速度が出るんです（たぶん）。
• また、データの型もあまり気にしなくていいのです。

  a[0] = 1
  a[1] = "abc"
  a[2] = 3.14

• みたいに適当に入れてしまっていいわけです。C言語ではunionとか使って苦労しましたが、そういう瑣末なことからは解放され、本来のアルゴリズムに集中できます。

• なお、Essenではデータをソートするという考え方はしません。データの順番は変わりません。内部でいろんな順序の対応表を持っているイメージです。だからこそ、「○○で2番目の要素は、××での何番目なのか？」みたいなことができるわけです。私はこの仕様のほうが格段に柔軟だと思っています。
  • もちろん何か適当なキーで並べ替えた配列を別途つくり、もとの配列を捨てることもできますが。

こめんと欄