Python - Sorting a list of dictionaries

Question

I am experimenting with a search algorithm, and I am trying to use an A* algorithm to solve the problem.

I am using a list of dictionaries to mantain the internal node structure. Each node is characterised by a certain state and associated cost. The selection function should return the node with the lowest cost. To be able to do this, I am filtering the list every time. I found this is very fast if the problem is very small, but in the case the list is very big, this function uses 84% of the total time of the algorithm.

My question is if there is a more efficient way of doing this.

def select(self, frontier):
    frontier.sort(key = lambda x: x['f_cost'])
    #select the node with the lowest f_cost
    return frontier.pop(0)

You might also want to look into using a priority queue instead. E.g., [`heapq`](https://docs.python.org/3/library/heapq.html). — , Oct 27 '17 at 19:07

juanpa.arrivillaga · Answer 1 · 2017-10-27T19:10:27.673

2

Yeah, don't .pop from the beginning! That is linear-time. .pop from the end is constant, so just do:

def select(self, frontier):
    frontier.sort(key = lambda x: x['f_cost'], reverse=True)
    #select the node with the lowest f_cost
    return frontier.pop()

You might want to consider alternative data-structures, if you are trying to maintain a sorted sequence. You could look at heapq which is part of the standard-library, although it is pretty bare-bones. You might also consider the sortedcontainers library, which apparently, is very performant.

edited Oct 27 '17 at 19:10

answered Oct 27 '17 at 19:04

juanpa.arrivillaga

88,713
10
131
172

That "pop from the beginning" (O(n)) is probably not as bad as the sort (O(n log n)), so the second part of the answer (use another data structure) looks more promising. – Sebastian Oct 27 '17 at 19:15
@Sebastian True, but keep in mind, timsort is *worst case* O(n log n), but it is *blazingly fast* at sorting nearly-sorted lists. That being said, your point still stands. – juanpa.arrivillaga Oct 27 '17 at 19:18
@juanpa.arrivillaga It's not blazingly fast compared to popping from the front. It's very slow compared to that. Try it. – Stefan Pochmann Oct 27 '17 at 19:46

score 0 · Answer 2 · answered Oct 27 '17 at 19:12

0

You should use functions like attrgetter or itemgetter for your key instead of lambda function as it is considered to be faster.

Docs: https://docs.python.org/3/howto/sorting.html

For details, have a look at this answer. operator.itemgetter or lambda

answered Oct 27 '17 at 19:12

utengr

3,225
3
29
68

that would only make a marginal difference. – juanpa.arrivillaga Oct 27 '17 at 19:48

Python - Sorting a list of dictionaries

2 Answers2