EssenMemo0005 のバックアップ(No.2) - khfdpl-wiki

[ トップ ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
EssenMemo0005 へ行く。
- 1 (2017-05-24 (水) 09:34:28)
- 2 (2017-05-24 (水) 12:35:07)

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とか使って苦労しましたが、そういう瑣末なことからは解放され、本来のアルゴリズムに集中できます。

こめんと欄

コメント	お名前	NameLink