Non bloccante algoritmo per generare numeri negativi unici
https://stackoverflow.com/questions/579925
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Recentemente ho refactoring un pezzo di codice utilizzato per generare numeri negativi unici.
modifica: Più thread ottenere questi ID e aggiungere come chiavi di una DB; numeri devono essere negativo da essere facilmente identificabili -alla fine di una sessione di test che stanno rimossi dal DB.
Il mio algoritmo di Java si presenta così:
private final Set<Integer> seen = Collections.synchronizedSet(new HashSet<Integer>());
public Integer generateUniqueNegativeIds() {
int result = 0;
do {
result = random.nextInt();
if (result > 0) {
result *= -1;
}
} while (!seen.add(result));
return result;
}
La struttura del codice di cui sopra, con la sua speculativa, oltre al set e "riprovare" loop, mi fa pensare ci sia un algoritmo non bloccante equivalente che sostituisce il set sincronizzato con uno qualsiasi dei variabili atomiche .
Ho fatto alcuni tentativi di ri-scrivere utilizzando le variabili atomiche ma tutti fallito il test di attacco multithread.
C'è un bloccante elegante equivalente?
modifica per curiosità, ecco un tentativo imperfetto utilizzando un intero atomica come guardia
private final AtomicInteger atomi = new AtomicInteger(0);
public Integer generateUniqueNegativeIdsWithAtomicAlgo() {
boolean added = false;
int result = 0;
do {
result = random.nextInt();
if (result > 0) {
result *= -1;
}
if (atomi.compareAndSet(0, result)) {
added = cache.add(result);
}
} while (!added);
return atomi.getAndSet(0);
}
modifica di test harness di seguito:
public static void main(String[] args) {
final int NUMBER_OF_THREADS = 10000;
final Set<Integer> uniques = Collections.synchronizedSet(new HashSet<Integer>());
final List<Integer> positives = Collections.synchronizedList(new ArrayList<Integer>());
final NegativeUniqueIdGenerator nuig = new NegativeUniqueIdGenerator();
Thread[] workers = new Thread[NUMBER_OF_THREADS];
long start = System.nanoTime();
for (int i = 0; i < workers.length; i++) {
Runnable runnable = new Runnable() {
public void run() {
int number = nuig.generateUniqueNegativeIds();
if (number > 0) {
positives.add(number);
}
uniques.add(number);
}
};
workers[i] = new Thread(runnable);
workers[i].start();
}
for (int i = 0; i < workers.length; i++) {
try {
workers[i].join();
} catch (InterruptedException ie) {}
}
long end = System.nanoTime();
System.out.println(String.format("duration = %dns", (end - start)));
System.out.println(String.format("#threads = %d", NUMBER_OF_THREADS));
System.out.println(String.format("#uniques = %d", uniques.size()));
System.out.println(String.format("#positives = %d", positives.size()));
System.out.println(String.format("#duplicates = %d", NUMBER_OF_THREADS - uniques.size()));
System.out.println(String.format("ratio = %f",
((double) NUMBER_OF_THREADS - uniques.size())
/ NUMBER_OF_THREADS));
assert uniques.size() == NUMBER_OF_THREADS;
}
Soluzione
Da requisiti che hai dato, io personalmente basta usare un media qualità generatore di numeri casuali che si sa non produrrà i duplicati entro il numero di numeri univoci che si richiedono. A meno che non si dispone di un requisito in più che non hai menzionato, sembra eccessivo per mantenere l'insieme di tutti i numeri precedentemente generati.
Ad esempio, utilizzando un generatore XORShift 32 bit produrrà tutti i 2 ^ 31 negative integer a 4 byte in ordine "casuale" prima di ripetere il modello. Se avete bisogno di più numeri di quello, probabilmente non si vuole essere mettendoli in un hash set comunque. Quindi, qualcosa di simile (attenzione: off-top-di-testa codice non testato ...):
int seed = (int) System.nanoTime();
final int origSeed = seed;
public int nextUniqueNegativeNumber() {
int n = seed;
do {
n ^= (n << 13);
n ^= (n >>> 17);
n ^= (n << 5);
seed = n;
if (n == origSeed) {
throw new InternalError("Run out of numbers!");
}
} while (n > 0);
return n;
}
Lascio al lettore per convertire "seme" per usare un AtomicInteger se la concorrenza è necessario ...
Modifica:. In realtà, per ottimizzare il caso concomitante si forse solo vuole scrivere di nuovo al "seme" dopo avere ottenuto il prossimo negativo numero
OK, a grande richiesta, la versione atomica sarebbe allora qualcosa di simile:
AtomicInteger seed = new AtomicInteger((int) System.nanoTime());
public int nextUniqueNegativeNumber() {
int oldVal, n;
do {
do {
oldVal = seed.get();
n = oldVal ^ (oldVal << 13); // Added correction
n ^= (n >>> 17);
n ^= (n << 5);
} while (seed.getAndSet(n) != oldVal);
} while (n > 0);
return n;
}
Altri suggerimenti
Se non si è preoccupato per la casualità, si può solo diminuire un contatore, in questo modo:
private final AtomicInteger ai=new AtomicInteger(0);
public int nextID() {
return ai.addAndGet(-1);
}
Modifica:
Per i numeri casuali, si può semplicemente utilizzare la soluzione e usare, ad esempio. ConcurrentHashMap o ConcurrentSkipListSet al posto del synchronizedSet. È necessario garantire che i vari fili utilizzano differenti istanze del generatore casuale, e che questi generatori non sono correlati.
Le altre risposte che suggeriscono utilizzando un contatore sono eccellenti, ma se nonpredictability (o almeno, non banale prevedibilità) è importante, l'algoritmo originale dovrebbe essere più che bene.
Perché?
In sostanza, la probabilità che si otterrà un numero intero di ripetizione è molto molto (molto) (molto) piccolo, circa 1 diviso per il numero di interi non avete ancora visto. Se hai già generato numeri N, il runtime previsto dell'algoritmo è approssimativamente lineare N con un coefficiente di 1/2 ^ 32, il che significa che si dovrebbe generare oltre un miliardo di numeri solo per ottenere il runtime dovrebbe superare 2 iterazioni del ciclo! In pratica, controllando il set per l'esistenza di un certo numero farà molto di più per allungare il tempo di esecuzione del vostro algoritmo che la possibilità di ripetere il ciclo (beh, a meno che non si sta utilizzando un HashSet forse - ho dimenticato ciò che il suo tempo di esecuzione asintotico è).
Per quello che vale, il numero esatto atteso di iterazioni del ciclo è
2^64/(2^32 - N)^2
Dopo aver generato un milione di numeri, questo funziona a 1,00,047 mila - il che significa, ad esempio, per generare il 1000001o a 1,002,000th numeri, probabilmente otterrete una il numero di ripetizione, < em> totale , in tutte quelle chiamate.
La soluzione elegante per tutti i requisiti elencati, per quanto posso dire, è solo decrementare un valore a partire da -1. Ho il sospetto, tuttavia, che non hai elencato tutti i requisiti.
Prova questo: http://www.javaconcurrencyinpractice.com/listings.html
Vorrei unire la risposta del PO con jpalecek di dare:
private final AtomicInteger ai=new AtomicInteger(0);
public int nextID() {
return ai.addAndGet(-1 - random.nextInt(1000));
}
Il lib alta scala ha un NonBlockingHashSet che si può usare. Basta sostituire l'istanza set con un'istanza di NonBlockingHashSet e voi siete tutti insieme.
Credo che quello che vuoi dire è non-blocking e rientrante.
modifica (sostituisce il mio originale, perché questo è molto meglio)
Una scelta filo-based che è in realtà abbastanza performante appena venuto in mente (almeno più performante rispetto l'originale). Se si è creata una mappa debole hash con un oggetto thread come la "chiave" e come il "Valore" mettere un oggetto con la capacità di produrre una serie di, diciamo, 1000 numeri da uno specifico intervallo.
In questo modo si assegna ogni thread è propria gamma 1000 Numero allocare. Quando l'oggetto si esaurisce di numeri, fare restituire un numero non valido (0?) E saprete che si deve allocare una nuova gamma a tale oggetto.
Non ci sarebbe alcuna sincronizzazione nulla da nessuna parte (edit:. Whoops, era un po 'sbagliato, vedi sotto), la mappa di hash deboli sarebbe discussioni automaticamente liberi che sono stati distrutti (nessuna manutenzione speciale) e la parte più lenta sarebbe una sola ricerca hash del filo che è in realtà molto breve.
ottenere il filo conduttore corrente con:
Thread currThread=Thread.getCurrentThread();
Inoltre ho potuto essere sbagliato e si può solo bisogno di fare il metodo sincronizzato, allora questo dovrebbe funzionare:
int n=-1;
synchronized int getNegativeNumber() {
return n--;
}
Sono andato avanti e scritto (a volte questa roba viene bloccato nella mia testa fino a quando lo faccio, e finchè ho fatto comunque, tanto vale post-it). Non testato e tutto, ma sono abbastanza sicuro che dovrebbe essere vicino, se non proprio operativa, fuori dalla scatola. Solo una classe con un metodo statico da chiamare per ottenere un numero negativo unico. (Oh, e ho fatto un po 'bisogno di sincronizzazione, ma sarà usato solo .001% del tempo).
Vorrei che ci fosse un modo per creare un blocco di codice collegato al posto di linea come questo senza andare fuori dal sito -. Spiace per la lunghezza
package test;
import java.util.WeakHashMap;
public class GenNumber {
// Static implementation goes first.
private static int next = -1;
private static final int range = 1000;
private static WeakHashMap<Thread, GenNumber> threads = new WeakHashMap<Thread, GenNumber>();
/**
* Generate a unique random number quickly without blocking
*
* @return the random number < 0
*/
public static int getUniqueNumber() {
Thread current = Thread.currentThread();
int next = 0;
// Have to synchronize some, but let's get the very
// common scenario out of the way first without any
// synchronization. This will be very fast, and will
// be the case 99.9% of the time (as long as range=1000)
GenNumber gn = threads.get(current);
if (gn != null) {
next = gn.getNext();
if (next != 0)
return next;
}
// Either the thread wasn't found, or the range was
// used up. Do the rest in a synchronized block.
// The three lines tagged with the comment "*" have
// the potential to collide if this wasn't synchronized.
synchronized (threads) {
if (gn == null) {
gn = new GenNumber(next -= range); // *
threads.put(current, gn); // *
return gn.getNext(); // can't fail this time
}
// now we know the range has run out
gn.setStart(next -= range); // *
return gn.getNext();
}
}
// Instance implementation (all private, nobody needs to see this)
private int start;
private int count;
private GenNumber(int start) {
setStart(start);
}
private int getNext() {
if (count < range)
return start - count;
return 0;
}
private GenNumber setStart(int start) {
this.start = start;
return this;
}
}
Appena mi ha colpito che invece di un grande blocco sincronizzato potrebbe essere sostituito da 2 molto piccoli sincronizzati su oggetti differenti, uno per il "+ = valore" e uno per la .Put (). Se le collisioni sono state ancora rallentare, che potrebbero aiutare (anche se le collisioni sono state ancora rallentare (davvero ???) si sarebbe meglio servita solo alzando il conto.
