Tutti i libri che ho letto sulle strutture dati finora sembrano utilizzare C/C++ e fanno un uso pesante del controllo puntatore "manuale" che offrono. Poichè Python nasconde questo tipo di gestione della memoria e di garbage collection da parte dell'utente, è persino possibile implementare strutture di dati efficienti in questo linguaggio, e c'è qualche ragione per farlo invece di usare i built-in?Strutture dati in Python
Python offre alcune potenti strutture dati ottimizzate , sia come built-in che come parte di alcuni moduli nella libreria standard (list s e dict s, naturalmente, ma anche tuple s, set s, array s nel modulo array e alcuni altri contenitori nel modulo collections).
Combinazioni di queste strutture di dati (e forse alcune delle funzioni da moduli helper quali heapq e bisect) sono generalmente sufficienti per attuare la maggior parte delle strutture più ricche che possono essere necessari in programmazione vita reale; tuttavia, questo non è sempre il caso.
Quando avete bisogno di qualcosa di più della ricca libreria, considerate il fatto che gli attributi di un oggetto (e gli oggetti nelle raccolte) sono essenzialmente "puntatori" ad altri oggetti (senza aritmetica del puntatore), cioè "riferimenti resettabili", in Python come in Java.In Python, si utilizza normalmente un valore None in un attributo o elemento per rappresentare ciò che NULL significherebbe in C++ o null significherebbe in Java.
Così, per esempio, si potrebbe implementare alberi binari tramite, ad esempio:
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
più metodi o funzioni per l'attraversamento e operazioni simili (l'attributo __slots__ classe è facoltativo - per lo più un'ottimizzazione della memoria, per evitare ciascuna istanza Node con il proprio __dict__, che sarebbe sostanzialmente più grande dei tre attributi/riferimenti necessari).
Altri esempi di strutture di dati che possono essere meglio rappresentati da classi Python dedicati, anziché composizione diretta di altre strutture Python esistenti, comprendono tries (si veda ad esempio here) e graphs (si veda ad esempio here).
Per alcune semplici strutture di dati (ad esempio uno stack), è sufficiente utilizzare l'elenco incorporato per svolgere il proprio lavoro. Con strutture più complesse (ad esempio un filtro di fioritura), dovrai implementarle tu stesso usando i primitivi supportati dalla lingua.
Dovresti usare i builtin se servono davvero al tuo scopo dato che sono stati debugati e ottimizzati da un'orda di persone per molto tempo. Provarlo da zero probabilmente produrrà una struttura di dati inferiore.
Se tuttavia, è necessario qualcosa che non è disponibile come primitivo o se la primitiva non funziona abbastanza bene, sarà necessario implementare il proprio tipo.
I dettagli come la gestione del puntatore ecc. Sono solo delle conversazioni di implementazione e non limitano realmente le capacità del linguaggio stesso.
I libri di struttura dati C/C++ stanno solo tentando di insegnarti i principi sottostanti alle varie strutture - in genere non ti consigliano di uscire e reinventare la ruota costruendo la tua libreria di pile e liste.
Sia che si utilizzi Python, C++, C#, Java, qualunque sia, si dovrebbe sempre controllare prima le strutture dei dati incorporate. Saranno generalmente implementati usando le stesse primitive di sistema che dovresti usare tu stesso, ma con il vantaggio di essere stati testati e testati.
Solo quando le strutture dati fornite non ti consentono di realizzare ciò che ti serve, e non c'è una libreria alternativa e affidabile a tua disposizione, dovresti cercare di creare qualcosa da zero (o estendere ciò che è fornito).
In che modo Python gestisce gli oggetti a un livello basso non è comunque troppo strano. This document dovrebbe disambiggerlo un po '; in pratica è tutta la logica del puntatore a cui sei già abituato.
Non è possibile implementare qualcosa come un vettore C++ in Python, poiché non si hanno primitive di array come fa C/C++. Tuttavia, qualsiasi cosa più complicata può essere implementata (in modo efficiente) su di essa, inclusi, ma non limitati a: elenchi concatenati, tabelle hash, multiset, filtri bloom, ecc.
Non ho dimestichezza con l'attuazione del vettore C++, ma il tipo di lista Python * è * implementato come un array (http://bytes.com/topic/python/answers/101848-list-implementation) piuttosto che un legato elenco. Non è quello che fondamentalmente è un vettore? –
Sì, un Python è implementato come una matrice (come un vettore C++). Quello che sto dicendo è che non è possibile implementare la propria lista * in * Python, eccetto che sopra quella esistente. –
Bene, il tipo di lista python è molto più simile a ArrayList di Java (cioè una matrice di puntatori a Object). –
Con Python si ha accesso a un vasto assortimento di moduli di libreria scritti e corretti da altre persone. Le probabilità sono molto buone che da qualche parte là fuori, c'è un modulo che fa almeno una parte di quello che vuoi, e le probabilità sono anche buone che potrebbero essere implementate in C per le prestazioni.
Ad esempio, se è necessario eseguire Matrix Matrix, è possibile utilizzare NumPy, che è stato scritto in C e Fortran.
Python è abbastanza lento da non essere felice se si tenta di scrivere una sorta di codice ad alta intensità di calcolo (esempio, una trasformazione di Fourier veloce) in Python nativo. D'altra parte, è possibile ottenere una Trasformata di Fourier con codice C come parte di SciPy, e basta usarla.
Non ho mai avuto una situazione in cui volevo risolvere un problema in Python e ho detto "dannatamente, non riesco proprio ad esprimere la struttura dati di cui ho bisogno."
Se sei un pioniere e stai facendo qualcosa in Python per il quale non esiste alcun modulo di libreria, puoi provare a scriverlo in puro Python. Se è abbastanza veloce, hai finito. Se è troppo lento, puoi tracciarlo, capire dove sono le parti lente e riscriverlo in C usando l'API di Python C. Non ho mai avuto bisogno di farlo ancora.
maggior C/C++ strutture "heav [ily] utilizzare i puntatori manuale" perché devono, piuttosto che perché è più efficace per farlo. – notnoop