I have 2 lists
我有两个列表
A = [{'g': 'goal'}, {'b': 'ball'}, {'a': 'apple'}, {'f': 'float'}, {'e': 'egg'}]
B = [{'a': None}, {'e': None}, {'b': None}, {'g': None}, {'f': None}]
I want to sort A according to B. The reason I'm asking this is, I can't simply copy B's contents into A and over-writing A's object values with None. I want to retain A's values but sort it according to B's order.
我想根据B对A进行排序,我问这个问题的原因是,我不能简单地将B的内容复制到A中,然后在没有A的情况下重写A的对象值。我想保留A的值但要按照B的顺序排序。
How do I achieve this? Would prefer a solution in Python
我该如何做到这一点?想要Python中的解决方案吗
4 个解决方案
#1
2
spots = {next(iter(d)): i for i, d in enumerate(B)}
sorted_A = [None] * len(A)
for d in A:
sorted_A[spots[next(iter(d))]] = d
Average-case linear time. Place each dict directly into the spot it needs to go, without slow index
calls or even calling sorted
.
平均情况线性时间。将每个命令直接放置到需要执行的位置,不需要缓慢的索引调用,甚至调用排序。
#2
1
You could store the indices of keys in a dictionary and use those in the sorting function. This would work in O(n log(n))
time:
您可以在字典中存储键的索引,并在排序函数中使用这些索引。这将在O(n log(n))时间内工作:
>>> keys = {next(iter(v)): i for i, v in enumerate(B)}
>>> keys
{'a': 0, 'e': 1, 'b': 2, 'g': 3, 'f': 4}
>>> A.sort(key=lambda x: keys[next(iter(x))])
>>> A
[{'a': 'apple'}, {'e': 'egg'}, {'b': 'ball'}, {'g': 'goal'}, {'f': 'float'}]
#3
1
You can avoid sorting by iterating over the existing, ordered keys in B
:
可以通过遍历B中现有的、有序的键来避免排序:
- Merge list
A
into a single lookup dict - 将列表A合并为单个查找命令。
- Build a new list from the order in
B
, using the lookup dict to find the value matching each key - 根据B中的顺序构建一个新的列表,使用查找命令找到与每个键匹配的值
Code:
代码:
import itertools
merged_A = {k: v for d in A for k, v in d.items()}
sorted_A = [{k: merged_A[k]} for k in itertools.chain.from_iterable(B)]
# [{'a': 'apple'}, {'e': 'egg'}, {'b': 'ball'}, {'g': 'goal'}, {'f': 'float'}]
If required, you can preserve the original dict objects from A
instead of building new ones:
如果需要,你可以从A保存原始的dict对象,而不是建立新的:
keys_to_dicts = {k: d for d in A for k in d}
sorted_A = [keys_to_dicts[k] for k in itertools.chain.from_iterable(B)]
#4
1
How about this? Create a lookup dict on A
and then use B
's keys to create a new list in the right order.
这个怎么样?在a上创建查找命令,然后使用B的键以正确的顺序创建新的列表。
In [103]: lookup_list = {k : d for d in A for k in d}
In [104]: sorted_list = [lookup_list[k] for d in B for k in d]; sorted_list
Out[104]: [{'a': 'apple'}, {'e': 'egg'}, {'b': 'ball'}, {'g': 'goal'}, {'f': 'float'}]
Performance
Setup:
设置:
import random
import copy
x = list(range(10000))
random.shuffle(x)
A = [{str(i) : 'test'} for i in x]
B = copy.deepcopy(A)
random.shuffle(B)
# user2357112's solution
%%timeit
spots = {next(iter(d)): i for i, d in enumerate(B)}
sorted_A = [None] * len(A)
for d in A:
sorted_A[spots[next(iter(d))]] = d
# Proposed in this post
%%timeit
lookup_list = {k : d for d in A for k in d}
sorted_list = [lookup_list[k] for d in B for k in d]; sorted_list
Results:
结果:
100 loops, best of 3: 9.27 ms per loop
100 loops, best of 3: 4.92 ms per loop
45% speedup to the original O(n)
, with twice the space complexity.
比原来的O(n)快45%,空间复杂度是原来的两倍。
#1
2
spots = {next(iter(d)): i for i, d in enumerate(B)}
sorted_A = [None] * len(A)
for d in A:
sorted_A[spots[next(iter(d))]] = d
Average-case linear time. Place each dict directly into the spot it needs to go, without slow index
calls or even calling sorted
.
平均情况线性时间。将每个命令直接放置到需要执行的位置,不需要缓慢的索引调用,甚至调用排序。
#2
1
You could store the indices of keys in a dictionary and use those in the sorting function. This would work in O(n log(n))
time:
您可以在字典中存储键的索引,并在排序函数中使用这些索引。这将在O(n log(n))时间内工作:
>>> keys = {next(iter(v)): i for i, v in enumerate(B)}
>>> keys
{'a': 0, 'e': 1, 'b': 2, 'g': 3, 'f': 4}
>>> A.sort(key=lambda x: keys[next(iter(x))])
>>> A
[{'a': 'apple'}, {'e': 'egg'}, {'b': 'ball'}, {'g': 'goal'}, {'f': 'float'}]
#3
1
You can avoid sorting by iterating over the existing, ordered keys in B
:
可以通过遍历B中现有的、有序的键来避免排序:
- Merge list
A
into a single lookup dict - 将列表A合并为单个查找命令。
- Build a new list from the order in
B
, using the lookup dict to find the value matching each key - 根据B中的顺序构建一个新的列表,使用查找命令找到与每个键匹配的值
Code:
代码:
import itertools
merged_A = {k: v for d in A for k, v in d.items()}
sorted_A = [{k: merged_A[k]} for k in itertools.chain.from_iterable(B)]
# [{'a': 'apple'}, {'e': 'egg'}, {'b': 'ball'}, {'g': 'goal'}, {'f': 'float'}]
If required, you can preserve the original dict objects from A
instead of building new ones:
如果需要,你可以从A保存原始的dict对象,而不是建立新的:
keys_to_dicts = {k: d for d in A for k in d}
sorted_A = [keys_to_dicts[k] for k in itertools.chain.from_iterable(B)]
#4
1
How about this? Create a lookup dict on A
and then use B
's keys to create a new list in the right order.
这个怎么样?在a上创建查找命令,然后使用B的键以正确的顺序创建新的列表。
In [103]: lookup_list = {k : d for d in A for k in d}
In [104]: sorted_list = [lookup_list[k] for d in B for k in d]; sorted_list
Out[104]: [{'a': 'apple'}, {'e': 'egg'}, {'b': 'ball'}, {'g': 'goal'}, {'f': 'float'}]
Performance
Setup:
设置:
import random
import copy
x = list(range(10000))
random.shuffle(x)
A = [{str(i) : 'test'} for i in x]
B = copy.deepcopy(A)
random.shuffle(B)
# user2357112's solution
%%timeit
spots = {next(iter(d)): i for i, d in enumerate(B)}
sorted_A = [None] * len(A)
for d in A:
sorted_A[spots[next(iter(d))]] = d
# Proposed in this post
%%timeit
lookup_list = {k : d for d in A for k in d}
sorted_list = [lookup_list[k] for d in B for k in d]; sorted_list
Results:
结果:
100 loops, best of 3: 9.27 ms per loop
100 loops, best of 3: 4.92 ms per loop
45% speedup to the original O(n)
, with twice the space complexity.
比原来的O(n)快45%,空间复杂度是原来的两倍。