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.generano rapidamente il "sequenza triangolo": evitando previsioni sbagliate avvengono
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.
Perché non si srotolano i casi piccoli-n? E se stai facendo più di qualche istruzione del codice dell'applicazione con ogni coppia, non sarà dominante? –
Sì, sul "altro lavoro potrebbe dominare" punto - ma in almeno uno scenario chiave, la quantità di lavoro è solo poche istruzioni in modo che il sovraccarico del triangolo è una grande parte. – BeeOnRope
Il problema con lo srotolamento è che il codice effettivo non è in un ciclo (ad esempio utilizzando l'iterazione esterna) ma utilizzato invece nel rientro di un iteratore. Inoltre, il limite non è fisso, quindi non so al momento della compilazione se sono nel caso small n o big n, e anche i diversi casi piccoli n necessitano di diversi srotoli. – BeeOnRope