Qual è la struttura dati più complicata che hai usato in una situazione pratica? [chiuso]

Hanno usato skip list per la ricerca. Dove lavoro, c'è un'implementazione standard e tutti sono incoraggiati a usarlo. Hanno usato patricia per archiviare e recuperare gli indirizzi IP in modo efficiente. Ancora una volta l'implementazione era già presente.

Sono uno sviluppatore Java. Java Collection Framework può risolvere i miei problemi di struttura dati del 90%, altri 10% richiedono sforzi. Penso che se capisci davvero la sofisticata lib standard scritta dagli esperti, troverai che aiutano nella maggior parte dei casi.

Le strutture dati complesse sono difficili da mantenere nel mondo reale. Per evitare di incasinare il codice, dividerò un problema ad alcuni più piccoli. Ogni piccolo problema può essere risolto con Java Collection Framework . Forse la soluzione non è la più intelligente (ha bisogno di più memoria e più lentamente), ma funziona e è facile da mantenere. È trade-off.

Se devo scrivere una struttura dati complessa, prenderò il libro di testo:)

La struttura dati più complicata che ho usato nel lavoro era un trie. Tuttavia, è stato vent'anni fa.

Il problema con lo sviluppo di software industriale è che la maggior parte dei programmatori industriali non sono laureati in informatica (CompSci); pertanto, le tecniche che il livello medio di CompSci dà per scontate sono considerate troppo difficili da mantenere per i programmatori pane-burro.

La mancanza di conoscenza generale CompSci nel settore è un problema serio. Ad esempio, ho perso il conto del numero di sviluppatori di software che ho incontrato che non capiscono espressioni come! (A! = 5 & b! = 3) e a == 5 || b == 3 sono logicamente equivalenti. Chiunque sappia come applicare il Teorema di DeMorgan può riconoscere che queste espressioni sono logicamente equivalenti. La maggior parte dei laureati non CompSci non ha mai sentito parlare del Teorema di DeMorgan. Se si esamina una base di codice sostanziale, si troveranno molte occorrenze di espressioni che annullano le sottoespressioni logiche negative. La leggibilità del codice che contiene sottoespressioni logiche negative negative è quasi sempre migliorata trasformando queste espressioni nella loro forma non negata.

Una volta ho scritto una coda di calendario (coda di priorità O (1)) per una simulazione basata su eventi in cui la profilazione mostrava che l'heap esistente era un collo di bottiglia.

Ho anche rilasciato un prodotto che conteneva una macchina a stati finiti con circa 80000 stati: il codice per generarlo era un po 'laborioso, per usare un eufemismo.

Lungo, molto tempo fa, in una galassia ... Ha lavorato in una squadra che utilizzava i "buddy buffers" di Knuth in un RTOS in assembler.

Inoltre, Conway's Game of Life con 256 generazioni per un mondo di 1024 x 1024.

Non ho usato nulla di troppo speciale, da zero sarebbe una lista doppiamente collegata .

Non molto eccitante, ho usato altre strutture. Ma la tua domanda ha detto da zero.

Un albero di hashtables che contiene elenchi generici di dati finanziari - non lo chiedono nemmeno. A volte vorrei essere un cowboy. Ah, la vita semplice sotto le stelle ...

Ho dovuto scrivere una struttura circolare Double-Linked-List da zero per l'algoritmo Dancing Links per un risolutore di Sudoku. Sembrava progettare un cubo di Rubik. L'intera struttura era fondamentalmente un elenco di elenchi - con ogni nodo che punta a quattro altri.

Una volta ho usato un albero della lunghezza del percorso ponderato per una cache specializzata. È stato divertente. Ho anche scritto le mie routine di gestione dell'heap per una sostituzione malloc() , ma molte persone lo hanno fatto.

Avendo preso una decisione, la struttura dei dati più "complicata" che ho fatto da zero è la modellazione di una rete di elementi basata su liste doppiamente collegate. Ma quello era anni fa quando usavo la programmazione a livello di sistema.

In questi giorni non creo quasi nessuna struttura di dati di fantasia. La maggior parte di essi avviene nel database in cui si decide cosa inserire in una tabella, forse un valore precalcolato, forse l'ID di alcuni record correlati per il recupero rapido, per evitare una visualizzazione non necessaria.

Personalmente ritengo che il compito a portata di mano definisca i mezzi. Perché cercare di utilizzare qualche struttura di dati esotici se non ci si usa per questo? E se posso dire che nella maggior parte delle applicazioni pratiche di programmazione non è probabilmente necessario reinventare la ruota.

La coda di priorità conta? Questo si presenta in quasi tutte le applicazioni in tempo reale che ho scritto. È diventato parte della libreria Java standard solo di recente (Java 1.5).

Oltre a questo, non riesco a pensare a niente di complicato che volessi davvero che non fossi in grado di uscire da una biblioteca. Non mi permetterei di fermarmi, ma mi chiederei perché avevo bisogno di una struttura dati troppo esotica per le librerie da includere. Cercherò sicuramente un'implementazione open source esistente di un filtro trie o bloom o di una skip list prima di provare a scriverne una anch'io.

In generale sono d'accordo con il tuo manager sul fatto che il costo di costruire e mantenere una struttura di dati personalizzata troppo esoterica perché non ci sia alcuna versione di libreria probabilmente supererà qualsiasi beneficio derivante da esso. Vorrei mostrarti, tramite la creazione di profili, che le normali strutture di libreria stanno causando una significativa penalizzazione delle prestazioni prima che ti permettessi di andare avanti e ottimizzarle con qualcosa di stravagante. Poiché come regola generale, è più economico acquistare cicli del processore rispetto ai cicli di progettazione.