对 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 a of x 个值仅包含唯一值并且已排序。

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

为什么要搞得这么复杂？
为什么不将 x 和 f(x) 值存储在字典中，并对字典键进行排序：

data = {}

# every time you get a new x and f(x) value, store it in the dict:

data[x] = f(x)

# then when you want to plot:

xvals = sorted(data.keys())
yvals = [data[x] for x in xvals]

# Now you have a x values and y values, sorted by x value, so just:

plot(xvals,yvals)

类似的东西对你有用吗？

此外，顺便说一句：作为一般规则，您想要一些高性能的东西是可以理解的，但是相对于您的算法需要 10 分钟到一个小时来收敛于 f(x) 的每个值，每当一个新的值进来，将所有现有结果与新结果相结合，即使是 O(n*ln(n)) 排序，也将是非常比等待新值排序的时间更快。（Python sorted 可以在不到 2.5 毫秒的时间内对 10,000 个数字进行排序。关键是，与 10 分钟的算法相比，再减少 0.5 到 1.0 毫秒，这不会对您的整个过程产生任何影响）。

Answer 2

如果您的输入大小是 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

优化方式：

Answer 3

x 值的随机顺序是否可以？如果是：

import random
xvals = random.sample(range(10),10)

结果：

 [9, 5, 1, 7, 6, 2, 3, 0, 4, 8]

数字将不会重复。当然每次调用的结果都会不同。您可以生成任意数量的 x 值：

random.sample(range(20),20)
 [10, 5, 0, 18, 13, 14, 19, 3, 1, 2, 17, 6, 4, 11, 15, 7, 9, 8, 12, 16]

我相信这也是O(n)。

唯一的问题可能是：在每次增加 x 值数量的迭代中，您是否也不想要来自先前迭代的任何重复？或者以上是否足够？

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

Sort values of x-axis in order to fill the plot f(x) evenly while computing f(x)

python

sorting

algorithm

level-of-detail