python - 二元选择过程

Question

我一直在做一个看起来很简单的任务，但让我抓狂。因此，如果您喜欢编程挑战……请继续阅读。

我希望能够取一个数字范围，例如[1:20] 并使用类似于二进制搜索算法的机制打印值。因此，首先打印最低值(在本例中为 1)，然后打印中间值(例如在本例中为 10)，然后将范围分成四分之一并打印 1/4 和 3/4 处的值(在本例中为 5和 15)，然后分成 8 等，直到该范围内的所有值都被打印出来。

这个应用(在这里并不是真正需要理解)是一种内存页面访问机制，当首先在中间范围访问页面时，该机制的行为更有效。

对于这个问题，取任意数字范围并以上述方式打印值就足够了。

对此有什么想法吗？伪代码解决方案就可以了。我会对此进行尝试，但到目前为止我尝试过的一切都没有成功。谢谢。

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

根据所使用的算法，此输出可以以许多类似的方式呈现。但是，我们的想法是首先显示一半的值，然后是四分之一，然后是八分之一，然后是十六分之一，等等，而忽略了之前显示的值。

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);
    }
}

(这是我一开始就打算写的代码，但我花了一些时间来思考它。)