2

如何以有效的方式确定数组的长度?

在寻找一种在 Intersystems Cache 中获取数组或全局大小的方法时,我开始考虑如何实际确定数组大小。从那以后,我找到了解决我最初问题的方法,但是有效地确定数组大小的难题仍然困扰着我,所以这是我到目前为止想出的:

  1. 从索引 1 开始。
  2. 测试当前索引处的值。
  3. 如果找到一个值,则将索引加倍。
  4. 如果没有找到值,则减去使用的倒数第二个索引。
  5. 继续第 4 步,在每次迭代中将减去的值减半,直到索引小到足以再次找到值为止。
  6. 将索引加一,直到找不到值。
  7. 倒数第二个索引将是大小。

例如,让我们采用一个大小为 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 的幂,但是如果我使用一个非常大的数组会发生什么,比如说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 回答