确定两个列表/数组的混洗索引 [英] Determine the shuffled indices of two lists/arrays
问题描述
作为挑战,我给自己这个问题:
As a challenge, I've given myself this problem:
给定2个列表,A和B,其中B是A的洗牌版本,这个想法是弄清洗牌指数。
Given 2 lists, A, and B, where B is a shuffled version of A, the idea is to figure out the shuffled indices.
例如:
A = [10, 40, 30, 2]
B = [30, 2, 10, 40]
result = [2, 3, 0, 1]
A[2] A[3] A[0] A[1]
|| || || ||
30 2 10 40
请注意,相同元素的关系可以任意解决。
Note that ties for identical elements can be resolved arbitrarily.
我想出了一个解决方案,涉及到使用字典来存储索引。这个问题有哪些其他可能的解决方案?使用库的解决方案也有效。 Numpy,pandas,一切都很好。
I've come up with a solution that involves the use of a dictionary to store indices. What other possible solutions does this problem have? A solution using a library also works. Numpy, pandas, anything is fine.
推荐答案
作为对当前解决方案的改进,你可以使用 collections.defaultdict
并避免 dict.setdefault
:
As an improvement over your current solution, you could use collections.defaultdict
and avoid dict.setdefault
:
from collections import defaultdict
A = [10, 40, 30, 2]
B = [30, 2, 10, 40]
idx = defaultdict(list)
for i, l in enumerate(A):
idx[l].append(i)
res = [idx[l].pop() for l in B]
print(res)
以下是使用给定样本输入的两种方法的时间安排:
Here are the timings for the two methods using the sample input given:
用于测试的脚本
from timeit import timeit
setup = """
from collections import defaultdict;
idx1 = defaultdict(list); idx2 = {}
A = [10, 40, 30, 2]
B = [30, 2, 10, 40]
"""
me = """
for i, l in enumerate(A):
idx1[l].append(i)
res = [idx1[l].pop() for l in B]
"""
coldspeed = """
for i, l in enumerate(A):
idx2.setdefault(l, []).append(i)
res = [idx2[l].pop() for l in B]
"""
print(timeit(setup=setup, stmt=me))
print(timeit(setup=setup, stmt=coldspeed))
结果
original: 2.601998388010543
modified: 2.0607256239745766
所以看来使用 defaultdict
实际上会产生轻微的速度提升。这实际上是因为 defaultdict
是用C而不是Python实现的。更不用说原始解决方案的属性查找 - idx.setdefault1
- 费用很高。
So it appears that using defaultdict
actually yields a slight speed increase. This actually makes since though since defaultdict
is implemented in C rather than Python. Not to mention that the attribute lookup of the original solution - idx.setdefault1
- is costly.
这篇关于确定两个列表/数组的混洗索引的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!