CODEWITHSUNDEEP
pythonarraysdictionary
foxtrot3009
foxtrot3009

Reputation: 149

Sorting a list of dicts based on another list of dicts in Python

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.

How do I achieve this? Would prefer a solution in Python

Upvotes: 2

Views: 91

Answers (4)

cs95
cs95

Reputation: 403248

How about this? Create a lookup dict on A and then use B's keys to create a new list in the right order.

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.

Upvotes: 1

pylang
pylang

Reputation: 44615

You can avoid sorting by iterating over the existing, ordered keys in B:

  1. Merge list A into a single lookup dict
  2. Build a new list from the order in B, using the lookup dict to find the value matching each key

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:

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)]

Upvotes: 1

Eugene Yarmash
Eugene Yarmash

Reputation: 150188

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:

>>> 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'}]

Upvotes: 1

user2357112
user2357112

Reputation: 282104

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.

Upvotes: 2

Related Questions