首页 文章

用于确定数组大小的算法

提问于
浏览 次
1

How does one determine the length of an array in an effective manner?

在寻找一种方法来获得数组或全局的Intersystems Cache时，我开始考虑如何实际确定数组大小 . 我已经找到了原始问题的解决方案，但是有效地确定阵列大小的难题仍然困扰着我，所以这是我到目前为止所提出的：

  • 从索引1开始 .

  • 测试当前索引的值 .

  • 如果找到值，请将索引加倍 .

  • 如果未找到任何值，则减去使用的倒数第二个索引 .

  • 继续步骤4，在每次迭代时将减去的值减半，直到索引足够小以便再次找到值 .

  • 将索引递增一，直到找不到值 .

  • 倒数第二个索引将是大小 .

举个例子，让我们取一个大小为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次迭代） . 在这个例子中，我并没有完全“赢得”这么多 .

现在我可以通过再次增加两个幂的索引来优化这个，但所有这些让我想知道：有更好的方法吗？我是否在正确的轨道上？仅仅使用静态增加尺寸会更好吗？

arrays algorithm

4 回答

  • 1

    而不是单步执行最后的2 ^（n-1）到（2 ^ n）-1，而是对该空间进行二进制搜索 . 所以基本上你的最后一个建议....无论哪种方式，你绝对不希望采用静态增加大小 .

    随机观察：Cache ObjectScript看起来很可怕 .

    回复于
  • 4

    您应该稍微修改算法 .

    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

    这将有效地工作，直到第一次“结束”，但直到结束 .

    回复于
  • 0

    看起来你正试图重新发明binary search . 在您的示例中，一旦64失败，您将在32和64之间的间隔进行二进制搜索 . 因此，在48之后，您应该尝试的下一个值是56.在56失败后，您将返回到52 .

    通常，您应该能够在最多2n次迭代中获得最多2 ^ n个元素的数组大小 .

    回复于
  • 1

    在Cache IF中，您需要查找具有整数索引的单维数组的大小

    W $ Order（数组（“”）， - 1）

    如果您的数组不是整数或多维，则会出现问题...

    回复于

相关问题