python - Rendimiento de OrderedDict(comparado con deque)

ordereddict python 3

Question

He estado tratando de optimizar el rendimiento de una implementación BFS en Python y mi implementación original estaba usando deque para almacenar la cola de nodos para expandir y un dict para almacenar los mismos nodos para tener una búsqueda eficiente para ver si ya está abierto .

Intenté optimizar (simplicidad y eficiencia) moviéndome a un OrderedDict. Sin embargo, esto lleva significativamente más tiempo. 400 búsquedas de muestra realizadas toman 2 segundos con deque / dict y 3,5 segundos con solo OrderedDict.

Mi pregunta es, si OrderedDict tiene la misma funcionalidad que las dos estructuras de datos originales, ¿no debería al menos ser similar en rendimiento? ¿O me estoy perdiendo algo aquí? Código de ejemplos a continuación.

Usando sólo un OrderedDict:

open_nodes = OrderedDict()
closed_nodes = {}
current = Node(start_position, None, 0)
open_nodes[current.position] = current

while open_nodes:
  current = open_nodes.popitem(False)[1]
  closed_nodes[current.position] = (current)

  if goal(current.position):
    return trace_path(current, open_nodes, closed_nodes)

  # Nodes bordering current
  for neighbor in self.environment.neighbors[current.position]:
    new_node = Node(neighbor, current, current.depth + 1)
    open_nodes[new_node.position] = new_node

Usando tanto un deque como un diccionario:

open_queue = deque()
open_nodes = {}
closed_nodes = {}
current = Node(start_position, None, 0)
open_queue.append(current)
open_nodes[current.position] = current

while open_queue:
  current = open_queue.popleft()
  del open_nodes[current.position]
  closed_nodes[current.position] = (current)

  if goal_function(current.position):
    return trace_path(current, open_nodes, closed_nodes)

  # Nodes bordering current
  for neighbor in self.environment.neighbors[current.position]:
    new_node = Node(neighbor, current, current.depth + 1)
    open_queue.append(new_node)
    open_nodes[new_node.position] = new_node

Answer 1

Como dijo Sven Marnach, OrderedDict se implementa en Python, quiero agregar que se implementa usando dict y list .

dict en python se implementa como hashtable. No estoy seguro de cómo se implementa el deque , pero la documentación dice que el deque está optimizado para agregar o acceder rápidamente al primer / último elemento, por lo que supongo que el deque se implementa como una lista enlazada.

Creo que cuando haces pop en OrderedDict, python hace una búsqueda de tabla hash que es más lenta en comparación con la lista enlazada que tiene punteros directos a los últimos y primeros elementos. Agregar un elemento al final de la lista enlazada también es más rápido en comparación con la tabla hash.

Por lo tanto, la causa principal por la que OrderDict en su ejemplo es más lenta, es porque es más rápido acceder al último elemento de la lista enlazada, que a acceder a cualquier elemento utilizando la tabla hash.

Mis pensamientos se basan en la información del libro Beautiful Code, describe los detalles de implementación detrás de dict , sin embargo no conozco muchos detalles detrás de list y deque , esta respuesta es solo mi intuición de cómo funcionan las cosas, por lo que en caso de que me equivoque merecen votos por hablar de cosas de las que no estoy seguro. ¿Por qué hablo de cosas de las que no estoy seguro? -Porque quiero probar mi intuición :)

Answer 2

Tanto deque como dict se implementan en C y se ejecutarán más rápido que OrderedDict que se implementa en Python puro.

La ventaja de OrderedDict es que tiene O (1) getitem, setitem y delitem como dictos regulares. Esto significa que se escala muy bien, a pesar de la implementación de Python pura más lenta.

Las implementaciones en competencia que utilizan deques, listas o árboles binarios suelen renunciar a los grandes tiempos rápidos en una de esas categorías para obtener un beneficio de velocidad o espacio en otra categoría.

Actualización: A partir de Python 3.5, OrderedDict () ahora tiene una implementación en C. Y aunque no ha sido altamente optimizado como algunos de los otros contenedores. Debería ejecutarse mucho más rápido que la implementación pura de python. Luego, comenzando con Python 3.6, se ordenaron los diccionarios regulares (aunque el comportamiento de pedido aún no está garantizado). Los que deberían correr más rápido aún :-)