Algoritmo rapido per trovare corrispondenze tra due array

Question

Algoritmo rapido per trovare corrispondenze tra due array

#1 da (1 voti)
#2 da (0 voti)

0

Ho riscontrato il seguente problema:

Ho un array che viene prodotto dall'analisi di un file yaml che contiene pattern nella seguente struttura.

"Programming books"
    Title:
          a list of titles
    Author:
"Art Books"
    Title:
          foo
          bar
    Author:
          Mrs. Foo
          Mr. Bar
    Year:

il programma dovrebbe ricevere un input casuale e trovare se c'è un libro con quel particolare Titolo, Autore e Anno.

Finora sto utilizzando il seguente

 foreach book_type,values from config{
       tag_match = 0
       foreach tag from values{
            tag_no = values.length()
            foreach value from tag{
                 if value in input
                      tag_match++
            }
      }
      if tag_match == values.length()
           /* tag the book matched continue matching*/
 }

Il programma non dovrebbe ricevere molte linee di corrispondenza, in quanto dovrebbe ricevere un'enorme quantità di dati. Finora deve fare book_type.length () * tag.length () * value.length () iterazioni per ogni riga di input, c'è un modo migliore per farlo?

array algorithms efficiency

posta ndp 08.01.2014 - 09:31

fonte

2 risposte

0

Hashing / indexing è la strada da percorrere. Fino a pochi milioni di oggetti o giù di lì, crea un hashtable / hashmap singolo o multilivello / qualunque sia chiamato nella tua lingua. In C # potrebbe essere Dictionary<string, Dictionary<string, List<Book>>> books_by_title_and_author . La prima chiave è il titolo, la seconda è l'autore e il valore è un elenco di libri corrispondenti, che dovrebbero contenere solo pochi elementi. Se hai troppi dati, dovresti fare ciò che farebbe un database, costruire un indice B-tree. Ancora una volta, questo può essere singolo o multi colonna. Un indice richiede un po 'più tempo per essere compilato, ma può essere più efficiente con molti elementi. Anche una struttura su disco è l'unico modo se i tuoi dati sono troppo grandi per adattarsi alla memoria.

risposta data 08.01.2014 - 10:55

fonte

Leggi altre domande sui tag array algorithms efficiency

Cosa deve succedere quando viene raggiunto il codice che non dovrebbe essere, in base alle regole aziendali o logiche? [duplicare] Estrae tutti gli alias e gli enum del tipo di classe correlati in un file o no

score 1 · Accepted Answer

Utilizza un dizionario o una raccolta, che ha una coppia valore-chiave, se la dimensione dei dati lo consente, se non un database, come indicato sopra.

Ci sono molte implementazioni di raccolte, dizionari, hash table ecc. e quello giusto / più veloce da usare dipenderà dalla natura del suo uso indentato, quindi dovrai guardarti intorno per trovare quello più adatto. Ad esempio alcuni caricano più velocemente, ma richiedono più tempo per leggere, alcuni caricano più lentamente, ma hanno tempi di accesso più rapidi e così via.

Altra cosa, potrebbe essere, attualmente sei O (3n), con cui intendo digitare X tag X valore quindi se questo è loops potrebbe essere 10 + 10 + 10 = 30 worst case. Potresti combinare Tipo e Tag e Valore, che sarebbe il 10 caso peggiore, solo un pensiero.

Ecco un link a un articolo che ho trovato utile, ma è specifico. Opzioni di IDictionary - Test delle prestazioni - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable