Appiattimento di cicli annidati/complessità decrescente - algoritmo di conteggio coppie complementari

Question

Recentemente ho cercato di risolvere alcune attività in Python e ho trovato la soluzione che sembra avere la complessità di O (n log n), ma io ci credo è molto inefficiente per alcuni input (ad esempio il primo parametro è 0 e pairs è un elenco molto lungo di zeri).

Ha anche tre livelli di loop for. Credo che può essere ottimizzato, ma al momento non posso ottimizzare più, io sono probabilmente solo manca qualcosa di ovvio;)

Quindi, in sostanza, il problema è il seguente:

lista Data di numeri interi (values), la funzione deve restituire il numero di coppie di indici che soddisfano i seguenti criteri:

• Assumiamo pair indice unico è una tupla come (index1, index2),
• poi values[index1] == complementary_diff - values[index2] i s vero,

Esempio: Se dato una lista come [1, 3, -4, 0, -3, 5] come values e 1 come complementary_diff, la funzione dovrebbe restituire 4 (che è la lunghezza della seguente lista di coppie di indici: [(0, 3), (2, 5), (3, 0), (5, 2)]).

Questo è ciò che ho finora, dovrebbe funzionare perfettamente la maggior parte del tempo, ma - come ho detto - in alcuni casi potrebbe funzionare molto lentamente, nonostante il ravvicinamento della sua complessità O (n log n (sembra che la complessità pessimistica sia O (n^2)).

def complementary_pairs_number (complementary_diff, values): 
    value_key = {} # dictionary storing indexes indexed by values 
    for index, item in enumerate(values): 
     try: 
      value_key[item].append(index) 
     except (KeyError,): # the item has not been found in value_key's keys 
      value_key[item] = [index] 
    key_pairs = set() # key pairs are unique by nature 
    for pos_value in value_key: # iterate through keys of value_key dictionary 
     sym_value = complementary_diff - pos_value 
     if sym_value in value_key: # checks if the symmetric value has been found 
      for i1 in value_key[pos_value]: # iterate through pos_values' indexes 
       for i2 in value_key[sym_value]: # as above, through sym_values 
        # add indexes' pairs or ignore if already added to the set 
        key_pairs.add((i1, i2)) 
        key_pairs.add((i2, i1)) 
    return len(key_pairs) 

Per il nostro esempio si comporta così:

>>> complementary_pairs_number(1, [1, 3, -4, 0, -3, 5]) 
4 

Se si vede come il codice potrebbe essere "appiattita" o "semplificata", per favore fatemelo sapere.

Non sono sicuro che la semplice ricerca di complementary_diff == 0 ecc. Sia l'approccio migliore. Se lo ritieni opportuno, faccelo sapere.

MODIFICA: Ho corretto l'esempio (grazie, unutbu!).

Answer 1

penso che questo migliora la complessità di O(n):

• value_key.setdefault(item,[]).append(index) è più veloce rispetto all'utilizzo di i try..except blocchi. È anche più veloce rispetto all'utilizzo di collections.defaultdict(list). (Ho provato questo con ipython% time.)
• Il codice originale visita ogni soluzione due volte. Per ogni pos_value in value_key, esiste un numero unico sym_value associato a pos_value. Ci sono soluzioni quando sym_value è anche in value_key.Ma quando iteriamo sopra le chiavi in ​​value_key, pos_value viene infine assegnato al valore di sym_value, che a fa ripetere al codice il calcolo che ha già eseguito. Quindi puoi tagliare il lavoro a metà se puoi smettere di pos_value di uguagliare il sym_value vecchio10. L'ho implementato con un seen = set() per mantenere la traccia di vista sym_value s.

• Il codice interessa solo len(key_pairs), non lo key_pairs. Quindi, invece di tenere traccia delle coppie (con un set), possiamo semplicemente tenere traccia del conteggio (con num_pairs). Così possiamo sostituire i due interno per-loop con

  num_pairs += 2*len(value_key[pos_value])*len(value_key[sym_value]) 
  

  o mezzo che, nel caso "unico diagonale", pos_value == sym_value.

---

def complementary_pairs_number(complementary_diff, values): 
    value_key = {} # dictionary storing indexes indexed by values 
    for index, item in enumerate(values): 
     value_key.setdefault(item,[]).append(index) 
    # print(value_key) 
    num_pairs = 0 
    seen = set() 
    for pos_value in value_key: 
     if pos_value in seen: continue 
     sym_value = complementary_diff - pos_value 
     seen.add(sym_value) 
     if sym_value in value_key: 
      # print(pos_value, sym_value, value_key[pos_value],value_key[sym_value]) 
      n = len(value_key[pos_value])*len(value_key[sym_value]) 
      if pos_value == sym_value: 
       num_pairs += n 
      else: 
       num_pairs += 2*n 
    return num_pairs 

Answer 2

Si consiglia di guardare in idiomi di programmazione funzionale, come ad esempio ridurre, ecc

Spesso, la logica array nidificato possono essere semplificati utilizzando funzioni come ridurre, carta, rifiutare, ecc.

Per un esempio (in javascript) controllare il carattere di sottolineatura js. Non sono molto intelligente con Python, quindi non so quali librerie hanno a disposizione.

Answer 3

Penso che (alcuni o tutti) questi sarebbero d'aiuto, ma non sono sicuro di come lo dimostrerei ancora.

1) Dai valori e ridurlo ad un insieme distinto di valori, registrando il conteggio di ciascun elemento (O (n))

2) ordinare l'array risultante. (n log n)

3) Se è possibile allocare molta memoria, suppongo che sia possibile popolare una matrice sparsa con i valori, quindi se l'intervallo di valori è -100: +100, allocare un l'array di [201] e qualsiasi valore esistente nel set ridotto ne visualizza uno sull'indice value nell'array sparse grande.

4) Qualsiasi valore che si desidera verificare se soddisfa la propria condizione ora deve esaminare l'indice nell'array sparse in base alla relazione x-y e vedere se esiste un valore lì.

5) come sottolineato poco fa, è banalmente simmetrico, quindi se {a, b} è una coppia, allora è {b, a}.

Answer 4

Penso che si possa migliorare separando la parte algebra dalla ricerca e utilizzando strutture di dati più intelligenti.

1. Passare attraverso l'elenco e sottrarre dalla differenza complementare per ciascuna voce nell'elenco.

   resultlist[index] = complementary_diff - originallist[index] 
   

   È possibile utilizzare una mappa o un ciclo semplice. -> Prende il tempo O (n).

2. Verificare se il numero nell'elenco risultante esiste nell'elenco originale.

   • Qui, con una lista ingenuo, si potrebbe effettivamente ottenere O (n^2), perché si può finire per cercare l'intero elenco originale per voce nella lista risultante.

   • Tuttavia, ci sono modi più intelligenti per organizzare i dati di questo. Se avete l'elenco originale ordinato, il tempo di ricerca si riduce a O (+ nlogn nlogn) = O (nlogn), nlogn per l'ordinamento, e nlogn per la ricerca binaria per elemento.

   • Se si voleva essere ancora più intelligente è possibile rendere la vostra lista in un dizionario (o hash table) e poi questo passo diventa O (n + n) = O (n), n per creare il dizionario e * n per cercare ogni elemento nel dizionario. (* EDIT:. * Dato che non si può assumere unicità di ogni valore nella lista originale Si potrebbe voler tenere il conto di quante volte ogni valore viene visualizzato nell'elenco originale.)

Quindi, con questo ora si ottiene O (n) runtime totale.

Usando il tuo esempio:

1, [1, 3, -4, 0, -3, 5], 

1. Genera l'elenco dei risultati:

   >>> resultlist 
   [0, -2, 5, 1, 4, -4]. 
   

2. Ora cerchiamo:

   • appiattire la lista originale in un dizionario . Ho scelto di usare l'indice della lista originale come il valore che sembra un dato lato che ti interessa

     >>> original_table 
     {(1,0), (3,1), (-4,2), (0,3), (-3,4), (5,5)} 
     

   • Per ogni elemento nella lista dei risultati, di ricerca nella tabella hash e rendere la tupla.:

     (resultlist_index, original_table[resultlist[resultlist_index]]) 
     

     Questo dovrebbe assomigliare alla soluzione di esempio che avevi.

3. Ora si trova la lunghezza dell'elenco risultante di tuple.

Ora ecco il codice:

example_diff = 1 
example_values = [1, 3, -4, 0, -3, 5] 
example2_diff = 1 
example2_values = [1, 0, 1] 

def complementary_pairs_number(complementary_diff, values): 
    """ 
     Given an integer complement and a list of values count how many pairs 
     of complementary pairs there are in the list. 
    """ 
    print "Input:", complementary_diff, values 
    # Step 1. Result list 
    resultlist = [complementary_diff - value for value in values] 
    print "Result List:", resultlist 

    # Step 2. Flatten into dictionary 
    original_table = {} 
    for original_index in xrange(len(values)): 
     if values[original_index] in original_table: 
      original_table[values[original_index]].append(original_index) 
     else: 
      original_table[values[original_index]] = [original_index] 
    print "Flattened dictionary:", original_table 

    # Step 2.5 Search through dictionary and count up the resulting pairs. 
    pair_count = 0 
    for resultlist_index in xrange(len(resultlist)): 
     if resultlist[resultlist_index] in original_table: 
      pair_count += len(original_table[resultlist[resultlist_index]]) 
    print "Complementary Pair Count:", pair_count 

    # (Optional) Step 2.5 Search through dictionary and create complementary pairs. Adds O(n^2) complexity. 
    pairs = [] 
    for resultlist_index in xrange(len(resultlist)): 
     if resultlist[resultlist_index] in original_table: 
      pairs += [(resultlist_index, original_index) for original_index in 
       original_table[resultlist[resultlist_index]]] 
    print "Complementary Pair Indices:", pairs 

    # Step 3 
    return pair_count 

if __name__ == "__main__": 
    complementary_pairs_number(example_diff, example_values) 
    complementary_pairs_number(example2_diff, example2_values) 

uscita:

$ python complementary.py 
Input: 1 [1, 3, -4, 0, -3, 5] 
Result List: [0, -2, 5, 1, 4, -4] 
Flattened dictionary: {0: 3, 1: 0, 3: 1, 5: 5, -4: 2, -3: 4} 
Complementary Pair Indices: [(0, 3), (2, 5), (3, 0), (5, 2)] 
Input: 1 [1, 0, 1] 
Result List: [0, 1, 0] 
Flattened dictionary: {0: [1], 1: [0, 2]} 
Complementary Pair Count: 4 
Complementary Pair Indices: [(0, 1), (1, 0), (1, 2), (2, 1)] 

Grazie!

Answer 5

modificato la soluzione fornita da @unutbu:

Il problema può essere ridotto a confronto tra questi 2 dizionari:

1. valori

2. pre-calcolate dizionario per (complementary_diff - valori [ i])

   def complementary_pairs_number(complementary_diff, values): 
       value_key = {} # dictionary storing indexes indexed by values 
       for index, item in enumerate(values): 
        value_key.setdefault(item,[]).append(index) 
   
       answer_key = {} # dictionary storing indexes indexed by (complementary_diff - values) 
       for index, item in enumerate(values): 
        answer_key.setdefault((complementary_diff-item),[]).append(index) 
   
       num_pairs = 0 
       print(value_key) 
       print(answer_key) 
       for pos_value in value_key: 
        if pos_value in answer_key: 
         num_pairs+=len(value_key[pos_value])*len(answer_key[pos_value]) 
       return num_pairs