buona struttura di dati per efficienti di inserimento/interrogazione sulle proprietà arbitrarie

Sto lavorando su un progetto in cui le matrici sono la struttura dei dati di default per ogni cosa, e ogni query è una ricerca lineare sotto forma di:buona struttura di dati per efficienti di inserimento/interrogazione sulle proprietà arbitrarie

Bisogno un cliente con un nome particolare? customer.Find(x => x.Name == name)
Hai bisogno di un cliente con un particolare ID univoco? customer.Find(x => x.Id == id)
Hai bisogno di un cliente di un particolare tipo ed età? customer.Find(x => x is PreferredCustomer && x.Age >= age)
Hai bisogno di un cliente con un nome particolare ed età? customer.Find(x => x.Name == name && x.Age == age)

In quasi tutti i casi, i criteri per le ricerche sono ben definiti. Ad esempio, cerchiamo solo i clienti con una o più proprietà Id, Tipo, Nome o Età. Raramente cerchiamo da qualcos'altro.

È una buona struttura dati per supportare query arbitrarie di questi tipi con ricerca migliore di O (n)? Qualsiasi implementazione immediata per .NET?

fonte

2010-03-18 Juliet

Un database ... Zing! –

Per la memoria, sono disponibili alcune opzioni.

La maggior parte delle opzioni sarà O (n). Detto questo, le ricerche sui dizionari possono avvicinarsi a O (1).

Un'opzione è quella di memorizzare i clienti in più dizionari, ognuno con una chiave impostata su Nome, ID ed Età. Se si utilizzano gli stessi riferimenti agli oggetti nei dizionari, è possibile effettuare qualsiasi ricerca singola O (1), senza un'enorme quantità di spese generali.

Concesso, questo diventa meno pratico con l'aumentare del numero di criteri, ma con 3, non è male.

Se si desidera maggiore flessibilità, un database è un'opzione appropriata. Molti database hanno la possibilità di lavorare come database completamente in memoria, incluso SQLite, che consente query arbitrarie molto meglio della velocità O (n).

fonte

2010-03-18 21:32:06

Il problema con più dizionari è che non supportano le ricerche composite: un dizionario di età > restituisce un intervallo di clienti per una data età in tempo costante, ma cosa succede se desidero anche effettuare una ricerca per nome? Sono tornato alla ricerca lineare. – Juliet

Se si combinano i risultati (tramite ANDing/ORing), penso che sarebbe meglio che lineare. – micahtan

@ Giulietta: si ritorna alla ricerca lineare, ma in uno spazio molto ristretto. Ogni ricerca aggiuntiva è limitata solo agli elementi validi dal primo, quindi lo spazio di ricerca è molto più piccolo. La seconda ricerca è O (n), ma N diventa molto piccola. Detto questo, l'altra opzione è ancora quella di utilizzare un DB in memoria, che fornisce query veloci con criteri arbitrari ... –

Perché non è possibile inserire i dati in diversi dizionari? Un dizionario associa il nome ai dati, un'altra mappa invecchia, ecc.

fonte

2010-03-18 21:42:27 Vlad

Per cominciare non è una soluzione molto generica. Abbiamo questo tipo di ricerche su più di un semplice cliente, e sarebbe un po 'folle creare un migliaio di dizionari per gli oltre 100 tipi di raccolta che cerchiamo regolarmente. In secondo luogo, più dizionari non supportano le ricerche su chiavi composite in tempi ragionevoli, ad esempio non posso cercare persone con un determinato nome AND età senza una ricerca lineare attraverso uno dei miei dizionari. – Juliet

-1

Suppongo che tutti gli array siano di IEnumerable?

Come utilizzare LINQ per gli oggetti?

http://www.beansoftware.com/ASP.NET-Tutorials/Linq-Objects-Collections-Arrays.aspx

Poi si può scrivere domanda come sintassi LINQ per ottenere risultati dal tuo array.

fonte

2012-09-11 17:03:12 RS999

Che cosa ha a che fare con la struttura dati? –

Non una struttura, ma se sta cercando di interrogare questi array e non vuole girare le ruote cercando di trovare il design perfetto, basta fare LINQ contro i tuoi array e chiamarlo un giorno. – RS999

buona struttura di dati per efficienti di inserimento/interrogazione sulle proprietà arbitrarie

risposta

Problemi correlati