对xaxis的值进行排序，以便在计算f（x）时均匀填充图f（x）

Question

总体理解的全局任务：我需要绘制函数f（x）的结果。任务很简单，但有两个问题：

1. 对于x的每一个值，f（x）都需要花费大量的计算时间（几十分钟甚至大约一小时）
2. 我不知道f（x）的估计形状，因此我不知道在预定义的x限制中需要多少x值才能正确表示函数

我想在每次得到新的f（x）值时更新f（x）的绘图。我不想顺理成章地解f（x），我想增加细节的层次，所以每次我看一个图，我看到它在我的（x_min，x_max）范围内，在这个范围内缓慢地更新

因此，问题是：我需要一个函数，它以适当的顺序提供x的列表

受二进制搜索的启发，我提出了以下算法：

lista的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

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

Answer 2

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值数量的迭代中，您是否也希望从上一次迭代中重复？或者上述情况是否足够

Answer 3

为什么要把事情弄得这么复杂？
为什么不将x和f（x）值存储在dict中，并对dict键进行排序：

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分钟到1小时才能收敛到f（x）的每个值，每当出现一个新值时，即使使用O（n*ln（n））排序，也会使用所有现有结果，将比新值排序的等待时间快很多。（Python sorted可以在不到2.5毫秒的时间内对10000个数字进行排序。关键是，与10分钟的算法相比，再减少0.5到1.0毫秒不会对整个过程产生任何影响）