generano rapidamente il "sequenza triangolo": evitando previsioni sbagliate avvengono

Question

Sono interessati a calcolare la sequenza triangolo, che è la sequenza di coppie (i, j): (0, 0), (1, 0), (1, 1), (2, 0), (2, 1) ... che itera se tutte le coppie (i, j) con la limitazione che i >= j. La stessa sequenza con ma con la restrizione i> j è anche interessante.

Queste sequenze rappresentano, tra le altre cose, tutti i modi per scegliere 2 elementi (possibilmente identici) da un insieme di n elementi (per la sequenza fino a ), o gli indici degli elementi triagular inferiori di una matrice . La sequenza di valori per i da sola è A003056 in OEIS, mentre j da solo è A002262. La sequenza si presenta frequentemente in algoritmi combinatori, in cui le loro prestazioni possono essere critiche.

Un modo semplice ma ramoso per generare il valore successivo nella sequenza è:

if (i == j) { 
    j = 0; 
    i++; 
    } else { 
    j++; 
    }  
} 

Tuttavia, questo soffre di numerosi mispredicts durante il calcolo degli elementi iniziali della sequenza, quando si verifica la condizione (i == j) - generalmente un errore ogni volta che i viene incrementato. All'aumentare della sequenza, il numero di imprevisti si riduce poiché viene incrementato con con frequenza ridotta, pertanto il ramo j++ domina ed è ben previsto. Tuttavia, alcuni tipi di ricerca combinatoria ripetono ripetutamente i termini piccoli nella sequenza , quindi sto cercando un approccio privo di branch o un altro approccio che soffra meno di previsioni errate.

Per molti usi, l'ordine delle sequenze non è così importante, quindi la generazione dei valori in ordine diverso da quello sopra è ammissibile se porta a una soluzione migliore. Ad esempio, j potrebbe eseguire il conto alla rovescia anziché aumentare: (0, 0), (1, 1), (1, 0), (2, 2), (2, 1), ....

---

Mi interessa sapere che cosa il nome giusto per questa sequenza è (forse così faccio un titolo migliore per questa domanda) anche. Ho appena creato una "sequenza triangolare".

Qui, la versione i >= j rappresenta sotto-multinsiemi (ripetizione consentita), mentre la variante i > j rappresenta sottoinsiemi normali (senza ripetizione).

Qui, la versione i >= j include diagonale principale, mentre la variante i > j esclude.

Answer 1

Qui ci sono due approcci senza filiali che non utilizzano eventuali calcoli costosi. Primo usa comparatore e logica AND:

const bool eq = i == j; 
i += eq; 
j = (j + 1) & (eq - 1); 

seconda utilizza comparatore e moltiplicazione:

"moltiplicazione" variante

const bool eq = i == j; 
i += eq; 
j = (j + 1) * (1 - eq); 

In teoria dovrebbe essere più lento "logico", ma misurazioni mostrano poca differenza .

Entrambi gli approcci risulterebbero in un codice senza ramo solo per processori che consentono confronti senza branchie (ad esempio x86). Anche questi approcci presuppongono di essere implementati utilizzando un linguaggio in cui i risultati delle espressioni condizionali potrebbero essere facilmente convertiti in numeri interi (ad esempio C/C++, dove i confronti "falsi" vengono convertiti in numeri interi zero e quelli "veri" in interi uguali a " 1").

L'unico problema con questi approcci è la prestazione. Potrebbero in teoria sovraperformare il codice branchy, ma solo quando i misundict sono molto frequenti. Un semplice test in cui non c'è altro lavoro oltre alla generazione di "sequenza triangolare" (vedi su ideone) mostra una miserabile velocità di errore e quindi entrambi i metodi senza ramo circa 3 volte più lenti di uno ramificato. La spiegazione è semplice: non ci dovrebbero essere molti imprevedibili per sequenze più lunghe; per quanto riguarda quelli più corti, i processori moderni hanno ottimi predittori di branca che quasi mai falliscono in caso di pattern a diramazioni corte; quindi non abbiamo molti imprevedibili, il codice ramificato esegue quasi sempre solo 2 istruzioni (confronto, incremento), mentre il codice senza ramo esegue sia "rami" attivi che incitativi più alcune istruzioni specifiche per l'approccio senza rami.

---

Nel caso in cui si desidera repeatedly iterate over the small terms in the sequence, probabilmente altro approccio sarebbe preferibile. Si calcola la sequenza solo una volta, quindi si legge ripetutamente dalla memoria.

Answer 2

Questo sembra così semplice sono sicuro di aver perso molto ...ma non è vero solo in cerca di un ciclo annidato come questo (pseudocodice)

for(i=0, i<4, i++) 
    for(j=0, j<i+1, j++) 
     print(i,j) 

Answer 3

È possibile derivare j da I:

...set val... 
old_j = j; 
j = (j + 1) % (i + 1); 
if (i == old_j) { 
    i++; 
} 
...loop if more... 

E inoltre derivare i INCREMENTO da j e corrente i:

...set val... 
old_j = j; 
j = (j + 1) % (i + 1); 
i = i + (i/old_j); 
...loop if more... 

(non possibile verificare in questo momento ... si prega di rivedere)

Answer 4

In Python possiamo esprimere questo come:

i, j = i + (i == j), (j + 1) * (i != j) 

, ma si scopre, a circa un milione di iterazioni o meno, sulla mia macchina, il seguente, più lungo senza fiato, il codice di valutazione pigra è di circa il 20% veloce:

from itertools import count, repeat 

def gen_i(): 
    """ A003056 """ 
    for x in count(0): # infinitely counts up 
     yield from repeat(x, x + 1) # replication 

def gen_j(): 
    """ A002262 """ 
    for x in count(0): # infinitely counts up 
     yield from range(x + 1) # count up to (including) x 

sequence = zip(gen_i(), gen_j()) 

for _ in range(1000000): 
    i, j = next(sequence) 

Nel codice precedente, gen_i(), gen_j(), count(), repeat(), e zip() sono tutti i generatori (e range() è un iteratore) così sequence continua t o chiamare il codice su richiesta quando sono richieste nuove coppie (i, j). Presumo che l'implementazione di range() e repeat() termini con un errore di lettura.

Semplice non è necessariamente anche veloce (cioè considerare tutte le aggiunte non necessarie di zero e le moltiplicazioni di una in forma compatta.)

Quindi, cosa è più importante, generare rapidamente la sequenza o evitare errori di previsione?