二元选择过程

Question

我一直致力于一项似乎是一项让我疯狂的简单任务.所以,如果您喜欢编程挑战......请继续阅读.

我希望能够采用数字范围,例如[1:20],并使用类似于二元搜索算法的机制打印数值.因此,首先打印最低值(在这种情况下为1)然后打印中间值(例如在这种情况下为10)然后将范围分成四分之一并打印值为1/4和3/4(在这种情况下为5)然后分成8个等等,直到打印出范围内的所有值.

应用这个(这里没有必要理解)是一种内存页面访问机制,当首先在中间范围访问页面时,它的行为更有效.

对于这个问题,采用任何数字范围并以上述方式打印值就足够了.

有什么想法吗？假的代码解决方案没问题.我会尝试这一点,但到目前为止我尝试的一切并没有削减它.谢谢.

更新:根据要求,示例[1:20]的所需输出将是这样的:1,10,5,15,3,7,12,17,2,4,6,8,11,13, 16,18,9,19,20

根据所使用的算法,该输出可以以许多类似的方式呈现.但是,我们的想法是首先显示半值,然后是四分之一,然后是八分之一,然后是16分等,而不是先前显示的值.

Answer 1

下面是一些Python代码,为您的示例生成类似的输出:

def f(low, high):
    ranges = collections.deque([(low, high)])
    while ranges:
        low, high = ranges.popleft()
        mid = (low + high) // 2
        yield mid
        if low < mid:
            ranges.append((low, mid))
        if mid + 1 < high:
            ranges.append((mid + 1, high))

例:

>>> list(f(0, 20))
[10, 5, 15, 2, 8, 13, 18, 1, 4, 7, 9, 12, 14, 17, 19, 0, 3, 6, 11, 16]

该low, high范围不包括端点,如同惯例在Python,所以结果包含数字0至19.

代码使用FIFO来存储仍需要处理的子范围.FIFO以全范围初始化.在每次迭代中,弹出下一个范围并产生中点.然后,如果它们非空,则将当前范围的下部和上部子范围附加到FIFO.

编辑:这是C99中完全不同的实现:

#include <stdio.h>

int main()
{
    const unsigned n = 20;
    for (unsigned i = 1; n >> (i - 1); ++i) {
        unsigned last = n;    // guaranteed to be different from all x values
        unsigned count = 1;
        for (unsigned j = 1; j < (1 << i); ++j) {
            const unsigned x = (n * j) >> i;
            if (last == x) {
                ++count;
            } else {
                if (count == 1 && !(j & 1)) {
                    printf("%u\n", last);
                }
                count = 1;
                last = x;
            }
        }
        if (count == 1)
            printf("%u\n", last);
    }
    return 0;
}

这通过使用一些技巧来确定在先前的迭代中是否已经出现整数来避免FIFO的必要性.

您也可以在C中轻松实现原始解决方案.因为您知道FIFO的最大大小(我猜它类似于(n + 1)/ 2,但您需要仔细检查),您可以使用环形缓冲区保持排队的范围.

编辑2:这是C99中的另一个解决方案.它被优化为仅进行一半的循环迭代,并且仅使用位操作和添加,不使用乘法或除法.它也更简洁,并且不包含0在结果中,因此您可以在最初的预期开始时使用它.

for (int i = 1; n >> (i - 1); ++i) {
    const int m = 1 << i;
    for (int x = n; x < (n << i); x += n << 1) {
        const int k = x & (m - 1);
        if (m - n <= k && k < n)
            printf("%u\n", x >> i);
    }
}

(这是我打算从头开始编写的代码,但我花了一些时间来绕过它.)