2

効果的な方法で配列の長さを決定するにはどうすればよいですか?

Intersystems Cache で配列またはグローバルのサイズを取得する方法を探しているときに、配列のサイズを実際に決定する方法を考え始めました。それ以来、元の問題の解決策を見つけましたが、配列のサイズを効果的に決定するパズルはまだ私を悩ませているので、これまでに思いついたものは次のとおりです。

  1. インデックス 1 から開始します。
  2. 現在のインデックスで値をテストします。
  3. 値が見つかった場合は、インデックスを 2 倍にします。
  4. 値が見つからない場合は、使用された最後から 2 番目のインデックスを減算します。
  5. 手順 4 に進み、値が再び検出されるのに十分なほどインデックスが小さくなるまで、反復ごとに減算された値を半分にします。
  6. 値が見つからなくなるまで、インデックスを 1 ずつ増やします。
  7. 最後から 2 番目のインデックスがサイズになります。

例として、サイズ 52 の配列を見てみましょう。

1  - OK
2  - OK
4  - OK
8  - OK
16 - OK
32 - OK
64 - OVER
48 - OK (64-16)
49 - OK
50 - OK
51 - OK
52 - OK
53 - OVER

13回の反復で配列の長さを取得するため、これは公平に思えますが、配列のサイズが63に増加すると、反復が10増加します-配列が増加したのと同じサイズです。

かなり小さい配列の場合、配列の長さが 2 のべき乗より 1 だけ少ない場合でも、最後の数ループで受けるノックはほとんど許容できると考えることができますが、非常に大きな配列を使用するとどうなりますか。 2097152 (2^21 - 1) 要素? つまり、21 回の反復で最初の「オーバー」に到達し、インデックスを 1572864 まで下げて、非常に長いループ (1572864 回の反復) を開始します。この例では、私はそれほど「勝っている」わけではありません。

これで、もう一度インデックスを 2 のべき乗で増やすことでこれを最適化できますが、これらすべてが疑問に思いました。それを行うためのより良い方法はありますか? 私はリモートで正しい軌道に乗っていますか? 単純に静的増加サイズを使用したほうがよいでしょうか?

4

4 に答える 4

4

二分探索を再発明しようとしているようです。あなたの例では、64 が失敗すると、32 と 64 の間の間隔でバイナリ検索を実行しています。したがって、48 の後、次の値は 56 です。56 が失敗した後、52 に戻ります。

一般に、最大 2n 回の反復で最大 2^n 要素の配列のサイズを取得できるはずです。

于 2013-08-05T12:50:47.920 に答える
1

最後の 2^(n-1) から (2^n)-1 をステップ実行する代わりに、そのスペースのバイナリ検索を実行します。つまり、基本的に最後の提案です.... いずれにせよ、静的な増加サイズを使用したくないことは間違いありません。

ランダムな観察: Cache ObjectScriptを使用するのは恐ろしいように見えます。

于 2013-08-05T12:49:56.510 に答える
1

アルゴリズムを少し変更する必要があります。

1 Start at index 0.
2 Add 1 to index
4 Stash it
5 Test for a value at the current index.
6 If 
   a value is found, double the index, go to 4
   else - if 
        current index = stashed index + 1, stashed index is the size of array, quit
        else set the current index to a stashed value, go to 2

これは、最初の「オーバー」までだけでなく、最後まで効果的に機能します。

于 2013-08-05T12:53:08.097 に答える
0

Cache IF では、整数インデックスを持つ単一次元配列のサイズを探しています。必要なのは、

W $Order(Array(""),-1)

配列が整数でない場合、または多次元である場合に問題が発生します...

于 2014-02-13T15:30:04.210 に答える