我将为单个列表编写一个函数来执行此操作,例如
>>> compact([6.23234121,6.23246575], tol=.01)
[6.23234121]
然后,您可以通过 just 让它在您的嵌套结构上工作[compact(l) for l in lst]
。
这些方法中的每一个都将保留列表中没有任何更接近它的第一个元素;对于@DSM 的示例,[0, 0.005, 0.01, 0.015, 0.02]
它们都会返回[0, 0.0.15]
(或者,如果您切换>
到>=
, [0, 0.01, 0.02]
)。如果您想要不同的东西,则必须更仔细地准确定义它。
首先,简单的方法,类似于大卫的回答。这是 O(n^2):
def compact(lst, tol):
new = []
for el in lst:
if all(abs(el - x) > tol for x in new):
new.append(el)
return compact
在三元素列表上,这非常好。但是,如果您想在三百万个元素的列表上执行此操作,那将不会减少它。让我们尝试一些不同的东西:
import collections
import math
def compact(lst, tol):
round_digits = -math.log10(tol) - 1
seen = collections.defaultdict(set)
new = []
for el in lst:
rounded = round(seen, round_digits)
if all(abs(el - x) > tol for x in seen[rounded]):
seen[rounded].add(el)
new.append(el)
return new
如果你tol
是0.01
,那么round_digits
是 1。所以6.23234121
被索引seen
为 just 6.2
。当我们看到6.23246575
时,我们将其四舍五入6.2
并在索引中查找,该索引应包含所有可能在tol
我们正在查找的数字范围内的数字。然后我们仍然必须检查与这些数字的距离,但只检查该索引箱中的极少数数字,而不是整个列表。
这种方法是 O(nk),其中 k 是落在一个这样的 bin 内的平均元素数。仅当 k << n (通常是这样,但这取决于您使用的相对于 的数字的分布)时才会有帮助tol
。请注意,它使用的内存可能是其他方法的两倍多,这对于非常大的列表可能是个问题。
另一种选择是先对列表进行排序;那么您只需查看前面和后面的元素即可检查是否存在冲突。