给定一个未排序的浮点列表作为输入,找到最接近的元素到某个值的索引的最有效方法是什么?我想到了一些潜在的解决方案:
为了:
x = random.sample([float(i) for i in range(1000000)], 1000000)
1)自己的功能:
def min_val(lst, val):
min_i = None
min_dist = 1000000.0
for i, v in enumerate(lst):
d = abs(v - val)
if d < min_dist:
min_dist = d
min_i = i
return min_i
结果:
%timeit min_val(x, 5000.56)
100 loops, best of 3: 11.5 ms per loop
2)
%timeit min(range(len(x)), key=lambda i: abs(x[i]-5000.56))
100 loops, best of 3: 16.8 ms per loop
3)脾气暴躁(包括转换)
%timeit np.abs(np.array(x)-5000.56).argmin()
100 loops, best of 3: 3.88 ms per loop
通过该测试,似乎将列表转换为numpy数组是最好的解决方案。但是,我想到两个问题:
考虑QuickSort中的分区算法。分区算法重新排列列表,以使枢轴元素在调用后位于其最终位置。然后,根据枢轴的值,可以对可能包含最接近目标的元素的数组部分进行分区。找到所要查找的元素或具有长度为1的分区(包含元素)后,就可以完成。
您要解决的一般问题是选择问题。
在您的问题中,您想知道要使用哪种数组/列表实现,这将对性能产生影响。更大的因素将是搜索算法,而不是列表/数组表示。
根据@Andrzej的评论进行编辑
啊,那我误会了你的问题。严格来说,线性搜索始终为O(n),因此无论基础数据结构如何,Big-Oh分析范围内的效率都是相同的。这里的问题是,对于线性搜索,您需要一个很好的简单数据结构来使运行时性能尽可能地好。
Python列表是对象的引用数组,而(据我所知)Numpy数组是对象的连续数组。Numpy数组的性能更好,因为它不必取消引用对象即可获取值。
对于Python列表与Numpy数组,您的比较技术似乎是合理的。我不愿意说Numpy数组是解决问题的最快方法,但它的性能应比Python列表更好。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句