Entiendo la diferencia entre conjuntos ordenados y no ordenados, y entiendo por qué, para muchos propósitos, no necesitamos conjuntos ordenados. Pero todas las operaciones de conjuntos siguen siendo posible en conjuntos ordenados, y los conjuntos deben almacenarse internamente con algún orden de todos modos, entonces, ¿por qué no están ordenados los conjuntos por defecto? ¿Es demasiado grande el impacto en el rendimiento de conservar el orden de los conjuntos?
Comentarios
- Tenga en cuenta que el » ordenar » de valores en una colección desordenada puede depender más del orden de inserción y menos (si es que lo hace) de los valores mismos, que no es ‘ t un orden en el sentido que se usa habitualmente (que proviene del término matemático).
- Esta pregunta puede considerarse fuera de tema, ya que no es ‘ Se trata de desarrollar un programa en particular, sino más bien del diseño del lenguaje.
- @outis No estaba ‘ seguro en cuanto al subsitio correcto, ¿hay otro que sugeriría?
Respuesta
El punto no es que la sobrecarga sea particularmente grande, sino que está ahí en absoluto .
Las funciones del lenguaje siempre deben lograr un equilibrio de rentabilidad. Los diccionarios son absolutamente fundamentales para la programación de Python, por lo que sería muy malo que fueran incluso un poco más lentos de lo que tienen que ser solo para preservar el orden de inserción, cuando la mayoría de las veces no es necesario realizar pedidos. Fue la decisión correcta descartar la orden de inserción a cambio de un acceso un poco más rápido y dejar la estructura de datos que preserva el orden para las clases especiales. Si hubiera otra estructura de datos que pudiera hacer todo lo que puede hacer un dict, y dict fuera una arruga del lenguaje menos usada, cosas podría verse diferente.
Comentarios
- Mi contraargumento sería: usar un tipo de datos dict desordenado más eficiente para diccionarios internos (como allí ‘ s
dequepara optimizar el rendimiento en ciertos otros contextos) pero deje que el tipo de datos del dictado principal de cara al usuario mantenga el orden. - Además, ¿tengo razón al entender que la implementación CPython de 3.6 de hecho conserva el orden de inserción para dicts?
Responder
Tienes razón en que el artículo se almacena internamente con algún pedido, pero este pedido interno es determinado por el código hash de la clave, que es lo que permite que la recuperación sea tan rápida. Entonces, si se debe ordenar un set / dict, necesitaría mantener una estructura de datos interna separada (digamos una lista ordenada de claves) para esto.
Esto, por supuesto, aumentaría el tamaño. Pero quizás peor aún, afectará el rendimiento. Por ejemplo, eliminar un elemento de un conjunto es una operación O (1), pero si también tiene que eliminar la clave de una lista ordenada interna, se convertiría en O (n). Tal costo sería desastroso para algunas aplicaciones. Dado que es bastante raro que necesite un conjunto ordenado, tal compensación no vale la pena para los tipos de conjunto / dictado estándar.
Respuesta
Su premisa es incorrecta. A partir de Python 3.6, dict s recuerdan su orden de inserción . Este fue un detalle de implementación y se promovió a la función de lenguaje completo en 3.7. En 3.6, para el caso específico de **kwargs, la conservación del pedido está específicamente garantizada.
Comentarios
- Sí, no estaba ‘ consciente de esto cuando hice la pregunta, ya que ‘ todavía no es una característica del idioma, solo una implementación detalle en una implementación. Pero parece que al menos los diccionarios se ordenarán a largo plazo y, con suerte, también se establecerán.
- @oulenz it ‘ ya no es un detalle de implementación, ‘ s requerido a partir de Python 3.7
Respuesta
Una orden set solo es posible cuando los elementos que se almacenarán tienen un orden (es decir, un método de comparación) en primer lugar, pero eso no siempre es un hecho.
La implementación predeterminada de set / map en la mayoría de los entornos hoy en día es basado en una tabla hash de autoresizing, que tiene estas ventajas:
- más rápido
- usa menos memoria
- no requiere los elementos para proporcionar un orden
los conjuntos deben almacenarse internamente con algún orden de todos modos
Pero este orden interno no necesariamente tiene ningún significado, ni permanece igual. De hecho, una propiedad de las tablas hash que a veces confunde a los desarrolladores sin experiencia es que el orden de iteración, que está basado en el orden interno, puede cambiar completamente cuando se agregan elementos (es decir, cuando se activa un cambio de tamaño) o entre diferentes carreras.
Comentarios
- No ‘ entiendo su primer comentario. No ‘ t necesitamos un método de comparación, el orden podría simplemente heredarse, p. Ej. de una lista o una cadena literal
{3, 5, 4}. - @oulenz: si no ‘ no le importa que el orden sea sin sentido y variando con el tiempo, entonces cada conjunto está ordenado, porque habrá algún tipo de orden de iteración. Pero » conjunto ordenado » implica que el orden es semántico para los elementos, y eso no siempre es posible. No ‘ realmente entiendo por qué desea que se ordenen todos los conjuntos.
- » Conjunto ordenado » no implica que el orden sea semántico, solo que hay algún orden. Por supuesto, me importa que una vez que se establezca este orden, se mantenga, a menos que se modifique su contenido.
- Lo siento, no ‘ no sabía que existía una implicación para algunas personas. Simplemente tenía en mente un conjunto ordenado linealmente a partir de las matemáticas. en.wikipedia.org/wiki/Total_order
- @jameslarge la relación de orden no ‘ t tiene que ser desconocido para mí. Si derivo un conjunto ordenado de una lista, sé exactamente cuál es su orden. Si quiero asegurar un cierto orden, puedo ordenar el conjunto. Pero si no ‘ no necesita el pedido, puede simplemente ignorarlo.
Responder
La idea general detrás de un conjunto o un diccionario es que planea realizar muchas operaciones de búsqueda. Está optimizado para dichas operaciones de búsqueda mediante el uso de un hash que permite la búsqueda O (1) en la mayoría de los casos.
El orden se realiza mediante matrices o listas enlazadas y de hecho realizando operaciones donde el orden es importante, se optimizan para eso como agregar un valor al final o al principio.
Por la naturaleza de estas dos estructuras de datos, ninguna está optimizada para ambas. Esto no quiere decir que no sea posible, pero involucra ambas estructuras de datos si desea optimizar tanto las operaciones de búsqueda como las basadas en órdenes.
Así que tiene esta compensación entre:
optimización de la operación de búsqueda < => operaciones basadas en pedidos < => uso de memoria
El consenso general es que, como programador, generalmente desea optimizar para uno u otro, pero no para ambos, y ciertamente nadie aboga por duplicar el uso de memoria cuando solo necesita para optimizar uno de los dos.
Dicho esto, hay implementaciones con ambos, o al menos en Java, específicamente LinkedHashMap es tanto una matriz como un hash- diccionario basado. A veces es posible que necesite ambos, pero se recomienda usar ArrayList si solo necesita una lista y un HashMap si solo necesita un diccionario .
Comentarios
- ¿Eh? Un LinkedHashMap de Java no es » tanto una matriz como un diccionario basado en hash «. Es ‘ básicamente un HashMap (es decir, utiliza una matriz internamente) superpuesto con una lista vinculada para permitir la iteración en el orden de inserción.
- Las estructuras de datos lineales no son ‘ t las únicas estructuras de datos ordenadas; También se pueden ordenar árboles binarios (como árboles rojo-negro y AVL). Otra operación que puede estar involucrada en la compensación es la inserción (las matrices son bastante eficientes en términos de búsqueda, iteración y uso de memoria, pero más lentas cuando se trata de inserción).