python - 对 x 轴的值进行排序，以便在计算 f(x) 时均匀地填充图 f(x)

Question

一般理解的全局任务:我需要绘制函数 f(x) 的结果。任务简单，但是有两个问题:

对于 x 的每个值，f(x) 需要花费大量时间来计算(数十分钟甚至大约一个小时)。

我不知道 f(x) 的估计形状，因此我不知道在预定义的 x 限制中需要多少 x 值才能正确表示函数。

每次获得新的 f(x) 值时，我都想更新 f(x) 的图。我不想因此解决 f(x)，我想增加细节水平，所以每次我看图时，我都会在我的所有 (x_min, x_max) 范围内看到它，在这个范围内慢慢更新范围。
因此问题是:我需要一个函数，它以正确的顺序提供 x 的列表。
受二分搜索的启发，我提出了以下算法: list x 值中的 a 只包含唯一值并且已排序。

def dissort(a)
    step = len(a) - 1
    picked = [False for x in a]
    out = []
    while False in picked and step > 0:
        for k in range(0, len(a), step):
            if not picked[k]:
                out.append(a[k])
                picked[k] = True
        step = step // 2
    return out

in = [1, 2, 3, 4, 5, 6, 7, 8, 9]
out = [1, 9, 5, 3, 7, 2, 4, 6, 8]
assert(dissort(in) == out)

我在这里看到了一些缺陷: picked数组可能是不必要的，每次细节级别增加时都会不必要地检查选取的值。现在我对性能感到满意，但将来我可以将它用于更大的列表。
有没有办法让它更高效？是否已经在某些 python 包中实现了？我找不到。

Answer 1

如果您的输入大小是 2 的幂，您可以获得与您的算法相同的顺序，如下所示:
要知道将第 n 个值放置在输出数组中的何处，请将 n 的二进制表示反转位的顺序并将其用作输出数组中的索引:
例子

n  | bin   |   rev | out-index 
 
0  = 000   ->  000 = 0
1  = 001   ->  100 = 4
2  = 010   ->  010 = 2
3  = 011   ->  110 = 6
4  = 100   ->  001 = 1
5  = 101   ->  101 = 5
6  = 110   ->  011 = 3
7  = 111   ->  111 = 7

So IN: [A,B,C,D,E,F,G,H] -> OUT: [A,E,C,G,B,F,D,H]

需要 O(n) 时间
如何反转位的顺序参见 Reverse bits in number
优化方式: https://stackoverflow.com/a/746203/1921273