16
¿Existen complementos de Python o bibliotecas de Python ampliamente utilizadas para realizar una búsqueda en una secuencia ordenada?¿Buscar en una lista ordenada?
A
Respuesta
22
bisect es parte de la biblioteca estándar, ¿es ese el tipo de cosa que está buscando?
+0
que no explica cómo buscar el valor en la lista. –
13
Vale la pena señalar que hay un par de bibliotecas de Python de alta calidad para mantener una lista ordenada que también implementa la búsqueda rápida: sortedcontainers y blist. Usar estos depende, por supuesto, de la frecuencia con la que insertes/elimines elementos de la lista y necesites buscar. Cada uno de esos módulos proporciona una clase SortedList que mantiene los elementos en orden de manera eficiente.
De la documentación para SortedList:
L.bisect_left(value)
Similar to the bisect module in the standard library, this returns
an appropriate index to insert value in L. If value is already present
in L, the insertion point will be before (to the left of) any existing
entries.
L.bisect(value)
Same as bisect_left.
L.bisect_right(value)
Same as bisect_left, but if value is already present in L, the
insertion point will be after (to the right of) any existing entries.
Ambas implementaciones usar la búsqueda binaria para encontrar el índice correcto del valor dado. Hay una página performance comparison para elegir entre los dos módulos.
Descargo de responsabilidad: Soy el autor del módulo sortedcontainers.
Cuestiones relacionadas
- 1. buscar valores antes y después en una larga lista ordenada
- 2. Buscar el próximo artículo más bajo en una lista ordenada
- 3. ¿Cómo buscar eficientemente en una matriz ordenada?
- 4. ¿Cómo aleatorizar una lista ordenada?
- 5. ¿Cambiar la numeración en una lista ordenada?
- 6. Buscar existencia de número en una lista ordenada en tiempo constante? (Pregunta de la entrevista)
- 7. Creación de una lista ordenada al azar de una lista ordenada
- 8. La mejor manera de buscar un valor de saturación en una lista ordenada
- 9. Obtenga sumas ordenadas de una lista ordenada
- 10. WPF mantiene una lista de TreeView ordenada
- 11. Horizontal lista ordenada (e IE)
- 12. Lista ordenada, recursiva, ordenada, legible, de los archivos más grandes
- 13. cómo mapear la lista ordenada en nhibernate?
- 14. ¿Cómo puedo conservar una lista ordenada en Core Data
- 15. ¿Cómo determinar si una lista está ordenada en Java?
- 16. Compruebe si una lista está ordenada en javascript con underscore.js
- 17. Probar una lista está ordenada en el orden correcto capybara
- 18. buscar duplicados en la lista de arrays
- 19. jquery buscar por índice en una lista
- 20. Cómo buscar una lista en C#
- 21. Buscar un elemento en una lista Lua
- 22. Buscar subcadena en una lista de cadenas
- 23. ¿Lista ordenada de pares de valores clave?
- 24. Lista ordenada reorganizable con Ruby on Rails
- 25. Retire el espacio izquierdo de una lista ordenada (OL)
- 26. ¿Cómo puedo verificar si una lista está ordenada?
- 27. ¿Cómo crear una lista ordenada centrada con HTML/CSS?
- 28. ¿Cómo puedo obtener un primer elemento de una lista ordenada?
- 29. ¿Seleccionar resultados del centro de una lista ordenada?
- 30. Obteniendo la posición ordenada ¿Lista ordenable JQuery?
Secuencia de qué? Además, ¿qué tipo de búsqueda (binaria, etc.)? –
Creo que la pregunta es tratar de ser "canónico" o "genérico" y el significado de "secuencia" puede estar usando la [definición de documentación de Python de una 'secuencia' (es decir, python 2.x" Hay siete tipos de secuencia: cadenas, cadenas Unicode, listas, tuplas, bytearrays, búferes y objetos xrange. ")] (https://docs.python.org/2/library/stdtypes.html#sequence-types-str-unicode-list-tuple -bytearray-buffer-xrange) –