IndexOf troppo lento nella lista. soluzione più veloce?

StackOverflow https://stackoverflow.com/questions/1075734

  •  21-08-2019
  •  | 
  •  

Domanda

Ho elenco generico che deve essere un ordine conservato in modo da poter recuperare l'indice di un oggetto nell'elenco. Il problema è IndexOf è troppo lento. Se io commento l'IndexOf fuori, il codice corre veloce come può essere. C'è un modo migliore, come ad esempio un conservato ordinato lista di hash per C #?

Grazie, Nate

  • Modifica - L'ordine in cui vengono aggiunti i prodotti / inserita è l'ordine ha bisogno di essere. Nessun ordinamento su di essi è necessario. Anche questa lista ha il potenziale per essere aggiornato spesso, aggiungere, rimuovere, inserire. Fondamentalmente ho bisogno di tradurre l'oggetto ad un indice loro dovuto essendo rappresentati in un controllo griglia in modo posso eseguire operazioni sul controllo griglia in base indice.
È stato utile?

Soluzione

Se non è ordinato, ma l'ordine ha bisogno di essere conservato , allora si potrebbe avere un separato Dictionary<YourClass, int> che conterrebbe l'indice per ogni elemento.

Se si desidera un elenco ordinato, quindi controllare post precedenti -. È possibile utilizzare SortedList<Tkey, TValue> a Net 3.5, oppure ordinare e utilizzare BinarySearch nelle vecchie versioni Net

[Modifica] È possibile trovare esempi simili sul web, ad esempio: orderedlist . Questo utilizza internamente un ArrayList e un HashTable, ma si può facilmente rendere generico.

[Edit2] Ops .. l'esempio che ti ho dato non implementa IndexOf modo che ho descritto all'inizio ... Ma si ottiene il punto - un elenco deve essere ordinato, l'altro utilizzato per la ricerca rapida <. / p>

Altri suggerimenti

Ordina utilizzando List<T>.Sort , quindi utilizzare il List<T>.BinarySearch metodo: "Ricerche tutto ordinato per List(T) un elemento [...] Questo metodo è un'operazione O (log n), dove n è il numero di elementi della serie ".

Vedere la parte inferiore della questo articolo qui .

Sembra che scrivere il proprio metodo per recuperare l'indice è molto più veloce rispetto al metodo IndexOf, a causa del fatto che si chiama in un metodo virtuale a seconda del tipo.

Una cosa come questa può quindi migliorare le vostre prestazioni. Ho scritto un piccolo test di unità per verificare che questo migliora le prestazioni della ricerca, e lo ha fatto, di circa 15x in un elenco con 10.000 articoli. 

static int GetIndex(IList<Item> list, Item value)
{
    for (int index = 0; index < list.Count; index++)
    {
        if (list[index] == value)
        {
             return index;
        } 
    }
    return -1;
}

Forse siete alla ricerca di SortedList<TKey, TValue> ?

Suggerisco di utilizzare la SortedList<TKey, TValue> o SortedDictionary<TKey, TValue> classe se avete bisogno degli articoli ordinati. Le differenze sono le seguenti.

  
      

  • Dictionary<TKey, TValue> utilizza meno memoria rispetto <=>.

    •   

  • <=> ha le operazioni di inserimento e rimozione rapidi per   Dati indifferenziati:. O (log n) al contrario di O (n) per <=>

    •   

  • Se l'elenco è popolato tutto in una volta dai dati ordinati, <=> è   più veloce di <=>.

    •   

Se si desidera solo per preservare l'ordinamento, si può semplicemente utilizzare un < => e memorizzare l'oggetto come chiave e l'indice come valore. Lo svantaggio è che riordinare gli articoli, inserzioni, o delezione sono piuttosto costosi da fare.

Se l'ordine degli oggetti nella lista ha per essere preservata allora l'unico modo che posso pensare a dove si sta andando ad ottenere l'accesso più veloce possibile è quello di raccontare l'oggetto ciò che il suo indice di la posizione è quando il suo aggiunto, ecc alla lista. In questo modo è possibile interrogare l'oggetto per ottenere il suo indice nella lista. Il rovescio della medaglia, e il suo un grande svantaggio, a mio avviso, è che gli oggetti inseriti ora hanno una dipendenza sulla lista.

Beh non v'è alcun motivo si dovrebbe mai avere a ordinare un elenco di hash ... che è questo il punto. Tuttavia, un elenco hash dovrebbe fare il trucco abbastanza prontamente.

Se si utilizza la classe List allora si potrebbe utilizzare il metodo Sort per ordinare dopo è inizialmente popolato quindi utilizzare il metodo BinarySearch di trovare l'elemento appropriato.

Non sono sicuro circa le specifiche in C #, ma si potrebbe essere in grado di risolvere la (QuickSort?) E poi usare una ricerca binaria su di esso (performance BinarySearch è O (log 2 (N)), contro sequenziale, come ad esempio indexOf, che è O (n)). (IMPORTANTE: Per una ricerca binaria, la struttura deve essere ordinato)

Quando si inserisce elementi alla struttura dei dati, si potrebbe provare una ricerca binaria modificata per trovare il punto di inserimento così, o se si sta aggiungendo un grande gruppo, li si dovrebbe aggiungere e poi ordinarli.

L'unico problema è che l'inserimento sarà più lento.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top