python - 对 x 轴的值进行排序,以便在计算 f(x) 时均匀地填充绘图 f(x)
问题描述
用于一般理解的全局任务:我需要绘制函数 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 包中实现了?我找不到它。
解决方案
如果您的输入大小是 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
推荐阅读
- eclipse - 在eclipse中导入项目与通过git克隆然后在eclipse中打开的区别
- apollo - 响应不成功:使用 `datasources` 时收到状态码 500
- reactjs - React:如何在映射中根据状态计数器分配键和增加状态计数器?
- c++ - 在我的项目中创建对象数组的问题:预期的 unqualified-id
- python - Tkinter 在一个框架中创建多个按钮
- elasticsearch - fscrawler 容器不健康(退出代码 126)
- c++ - C++ 实现抽象类
- c - c 打印字符串的实际内容
- java - 嵌入式 Tomcat 给出“不允许 HTTP 升级到 WebSocket”错误
- html - 单击按钮时的 HTML 弹出框