Python equivalente a std :: set y std :: multimap

Question

Estoy portando un programa C++ a Python. Hay algunos lugares donde usa std::set para almacenar objetos que definen sus propios operadores de comparación. Desde la biblioteca estándar Python no tiene equivalente de std::set (una estructura de datos de mapeo clave-valor ordenada) I intentado usar un diccionario normal y luego la clasificación que cuando se repite, como este:

def __iter__(self): 
    items = self._data.items() 
    items.sort() 
    return iter(items) 

Sin embargo, el perfil ha demostrado que todos las llamadas de .sort() a __cmp__ son un serio cuello de botella. Necesito una mejor estructura de datos, esencialmente un diccionario ordenado. ¿Alguien sabe de una implementación existente? En su defecto, ¿alguna recomendación sobre cómo debo implementar esto? El rendimiento de lectura es más importante que el rendimiento de escritura y el tiempo es más importante que la memoria.

Puntos de bonificación si admite varios valores por clave, como C++ std::multimap.

Tenga en cuenta que la clase OrderedDict no se ajusta a mis necesidades, porque devuelve los elementos en el orden de inserción, mientras que los necesito ordenados usando sus métodos __cmp__.

Answer 1

Para el diccionario ordenado, puede (ab) usar la naturaleza estable del timsort de Python: básicamente, mantenga los elementos parcialmente ordenados, agregue los elementos al final cuando sea necesario, cambie una bandera "sucia" y ordene el resto antes iterando Ver esta entrada para los detalles y la aplicación (la respuesta de un Martelli): Key-ordered dict in Python

Answer 2

Python no tiene estructuras de datos integradas para esto, aunque el módulo bisect proporciona la funcionalidad para mantener una lista ordenada con algoritmos apropiadamente eficientes.

Si tiene una lista de claves ordenadas, puede acoplarla con collections.defaultdict(list) para proporcionar una funcionalidad de tipo multimap.

Answer 3

En su libro "Programming in Python 3", Mark Summerfield presenta una clase de diccionario ordenada. El código fuente está disponible en this zip archive - busque SortedDict.py. La clase SortedDict se describe en detalle en el libro (que recomiendo mucho). Admite claves arbitrarias para comparación y múltiples valores por clave (lo que hace cualquier diccionario en Python, así que no es tan importante, creo).

Answer 4

Debe usar sort(key=...).
La función clave que usa estará relacionada con el cmp que ya está utilizando. La ventaja es que la función clave se llama n veces mientras que cmp se llama nlog n veces, y normalmente la tecla hace la mitad del trabajo que hace cmp

Si puede incluir su __cmp__(), probablemente podamos mostrarle cómo convertirlo a una función clave

Si está realizando muchas iteraciones entre modificaciones, debe almacenar en caché el valor de los elementos ordenados.