Python - 사전 목록 정렬

Question

검색 알고리즘을 실험하고 있는데 A * 알고리즘을 사용하여 문제를 해결하려고합니다.

내부 노드 구조를 유지하기 위해 사전 목록을 사용하고 있습니다. 각 노드는 특정 상태 및 관련 비용으로 특징 지어집니다. 선택 함수는 비용이 가장 낮은 노드를 반환해야합니다. 이렇게하려면 매번 목록을 필터링하고 있습니다. 문제가 매우 작 으면 매우 빠르다는 것을 발견했습니다. 목록이 매우 큰 경우이 함수는 알고리즘의 총 시간 중 84 %를 사용합니다.

내 질문에이 일을하는 더 효율적인 방법이 있습니다.

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

Answer 1

그래, 처음부터 .pop하지 마라! 그것은 선형 시간입니다. 끝에서 .pop는 일정, 그래서 그냥 수행

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

당신은 정렬 된 순서를 유지하려는 경우, 다른 데이터 구조를 고려할 수 있습니다. 꽤 베어 본이지만 표준 라이브러리의 일부인 heapq을 볼 수 있습니다. 또한 라이브러리를 고려해보십시오. 이는 분명히 매우 실적이 좋은입니다.

Answer 2

람다 함수 대신 키에 attrgetter 또는 itemgetter과 같은 함수를 사용하는 것이 좋습니다.

문서 : 자세한 내용은 https://docs.python.org/3/howto/sorting.html

이 대답을 살펴 있습니다. operator.itemgetter or lambda