Todos los libros que he leído sobre estructuras de datos hasta ahora parecen usar C/C++, y hacen un uso intensivo del control de puntero "manual" que ofrecen. Dado que Python oculta ese tipo de gestión de memoria y recolección de basura del usuario, ¿es posible incluso implementar estructuras de datos eficientes en este lenguaje, y hay alguna razón para hacerlo en lugar de utilizar los complementos?Estructuras de datos en Python
Python le ofrece algunas estructuras de datos potentes y altamente optimizadas , tanto como muebles empotrados y como parte de un par de módulos de la biblioteca estándar (list s y dict s, por supuesto, pero también tuple s, set s, array s en el módulo de array, y algunos otros contenedores en módulo collections).
Las combinaciones de estas estructuras de datos (y tal vez algunas de las funciones de módulos auxiliares como heapq y bisect) son generalmente suficientes para implementar las estructuras más ricas que pueden ser necesarias en la programación de la vida real; sin embargo, ese no es invariablemente el caso.
Cuando necesite algo más de lo que ofrece la biblioteca enriquecida, considere el hecho de que los atributos de un objeto (y elementos en colecciones) son esencialmente "punteros" a otros objetos (sin aritmética de puntero), es decir, "referencias rescatables", en Python como en Java.En Python, normalmente utiliza un valor None en un atributo o elemento para representar lo que NULL significaría en C++ o null en Java.
Así, por ejemplo, se podría poner en práctica a través de los árboles binarios, por ejemplo:
class Node(object):
__slots__ = 'payload', 'left', 'right'
def __init__(self, payload=None, left=None, right=None):
self.payload = payload
self.left = left
self.right = right
más métodos o funciones para el recorrido y operaciones similares (el atributo __slots__ clase es opcional - sobre todo una optimización de la memoria, para evitar cada instancia de Node que lleva su propio __dict__, que sería sustancialmente más grande que los tres atributos/referencias necesarios).
Otros ejemplos de estructuras de datos que mejor pueden estar representados por las clases de Python dedicado, en lugar de por la composición directa de otras estructuras de Python existentes, incluyen tries (véase, por ejemplo here) y graphs (véase, por ejemplo here).
Para algunas estructuras de datos simples (por ejemplo, una pila), puede usar la lista integrada para realizar su trabajo. Con estructuras más complejas (por ejemplo, un filtro de floración), tendrá que implementarlas usted mismo usando las primitivas que admite el lenguaje.
Debe usar los edredones si realmente sirven para su propósito, ya que son eliminados y optimizados por una horda de personas durante mucho tiempo. Si lo hace desde cero, probablemente producirá una estructura de datos inferior.
Sin embargo, si necesita algo que no está disponible como primitivo o si la primitiva no funciona lo suficientemente bien, tendrá que implementar su propio tipo.
Los detalles como la administración de punteros, etc., son solo conversaciones de implementación y realmente no limitan las capacidades del lenguaje en sí.
Los libros de estructura de datos C/C++ solo intentan enseñarle los principios subyacentes detrás de las diversas estructuras; generalmente no le aconsejan que realmente salga a reinventar la rueda construyendo su propia biblioteca de pilas y listas.
Si está utilizando Python, C++, C#, Java, lo que sea, siempre debe mirar primero a las estructuras de datos integradas. En general, se implementarán utilizando las mismas primitivas del sistema que tendrías que usar para hacerlo tú mismo, pero con la ventaja de haber sido probado y probado.
Solo cuando las estructuras de datos proporcionadas no le permiten lograr lo que necesita, y no hay una biblioteca alternativa y confiable disponible para usted, debe buscar construir algo desde cero (o ampliar lo que se proporciona).
Cómo Python maneja los objetos a un nivel bajo no es muy extraño de todos modos. This document debe desambiguar un poco; Básicamente es toda la lógica del puntero con la que ya estás familiarizado.
No es posible implementar algo así como un vector C++ en Python, ya que no tiene primitivas de matriz como lo hace C/C++. Sin embargo, cualquier cosa más complicada puede implementarse (de manera eficiente) además de, pero no se limita a: listas vinculadas, tablas hash, multisedes, filtros de bloom, etc.
No estoy familiarizado con la implementación del vector C++, pero el tipo de lista Python * está * implementado como una matriz (http://bytes.com/topic/python/answers/101848-list-implementation) en lugar de un enlace lista. ¿No es eso básicamente un vector? –
Sí, una Python se implementa como una matriz (igual que un vector de C++). Lo que estoy diciendo es que no podría implementar su propia lista * en * Python, excepto en la parte superior de la existente. –
Bueno, el tipo de lista de Python es realmente más parecido a ArrayList de Java (es decir, una matriz de punteros a Object). –
Con Python tiene acceso a una gran variedad de módulos de biblioteca escritos y depurados por otras personas. Las probabilidades son muy buenas de que en algún lugar, hay un módulo que hace al menos parte de lo que desea, y las probabilidades son incluso buenas de que pueda implementarse en C para el rendimiento.
Por ejemplo, si necesita hacer cálculos matemáticos, puede usar NumPy, que se escribió en C y Fortran.
Python es lo suficientemente lento como para no estar contento si intenta escribir algún tipo de código realmente intensivo en cómputo (por ejemplo, una Transformada Rápida de Fourier) en Python nativo. Por otro lado, puedes obtener una Transformada de Fourier codificada en C como parte de SciPy, y solo usarla.
Nunca he tenido una situación en la que quisiera resolver un problema en Python y dije "maldita sea, no puedo expresar la estructura de datos que necesito".
Si eres un pionero, y estás haciendo algo en Python para el cual simplemente no hay ningún módulo de biblioteca, entonces puedes intentar escribirlo en Python puro. Si es lo suficientemente rápido, has terminado. Si es demasiado lento, puede crear un perfil, averiguar dónde están las partes lentas y volver a escribirlas en C con la API de Python C. Nunca he necesitado hacer esto todavía.
La mayoría de las estructuras C/C++ "heav [ily] usan punteros manuales" porque tienen que hacerlo, en lugar de porque es más eficiente hacerlo. – notnoop