Nicht blockierenden Algorithmus eindeutige negative Zahlen zu erzeugen,
https://stackoverflow.com/questions/579925
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
ich Refactoring vor kurzem ein Stück Code verwendet eindeutige negative Zahlen zu erzeugen.
Bearbeiten Mehrere Threads erhalten diese IDs und als Schlüssel zu einem DB hinzuzufügen; Zahlen müssen leicht erkennbar -am Ende einer Testsitzung als negativ sein sie von der DB entfernt sind.
Ihr Java-Algorithmus sieht wie folgt aus:
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;
}
Die Codestruktur, die oben mit seinem spekulativen Zusätzlich zu dem Satz und „Wiederholen“ Schleife, macht ich denke, es ist ein äquivalenter nonblocking Algorithmus, der den synchronisierten Satz mit einem der Atom-Variablen .
Ich habe ein paar Versuche, neu zu schreiben Atom-Variablen verwenden, aber alle scheiterten die Multi-Thread-Angriffstest.
Gibt es eine elegante nonblocking Äquivalent?
Bearbeiten aus Gründen der Neugier hier ist ein fehlerhaft Versuch, eine Atom ganze Zahl als Wächter mit
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);
}
Bearbeiten Testumgebung unter:
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;
}
Lösung
Von den Anforderungen, die Sie gegeben haben, würde ich persönlich benutze nur einen mittlere Qualität Zufallszahlengenerator, die Sie nicht wissen, Duplikate produzieren innerhalb der Anzahl der eindeutigen Zahlen, die Sie benötigen. Es sei denn, Sie eine zusätzliche Anforderung haben Sie nicht erwähnt haben, scheint es übertrieben die Menge aller zu halten den zuvor erzeugten Zahlen.
Um zum Beispiel eine 32-Bit-Xorshift Generator werden alle 2 ^ 31 4-Byte-negativen ganzen Zahlen in "random" Ordnung erzeugen, bevor das Muster wiederholt wird. Wenn Sie mehr als das Zahlen benötigen, wollen Sie wahrscheinlich nicht, sie in einem Hash-Set sowieso zu setzen. So etwas wie dieser (Warnung: off-Top-of-Kopf ungetestete Code ...):
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;
}
Ich werde es den Leser überlassen, zu konvertieren „Samen“ einen Atomicinteger zu verwenden, wenn die Parallelität notwendig ist ...
Edit:. Tatsächlich, den gleichzeitigen Fall optimieren Sie vielleicht nur zurück zu „Samt“ schreiben wollen nach dem Aufstehen der nächste negativ Zahl
OK, aufgrund der großen Nachfrage würde die Atom Version dann so etwas wie diese:
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;
}
Andere Tipps
Wenn Sie nicht besorgt über die Zufälligkeit sind, können Sie nur einen Zähler verringern, wie folgt aus:
private final AtomicInteger ai=new AtomicInteger(0);
public int nextID() {
return ai.addAndGet(-1);
}
Edit:
Für Zufallszahl, können Sie einfach Ihre Lösung verwenden und beispielsweise verwenden. ConcurrentHashMap oder ConcurrentSkipListSet anstelle des synchronizedSet. Sie müssen sicherstellen, dass verschiedene Threads verschiedene Instanzen des Zufallsgenerators verwenden, und dass diese Generatoren nicht korreliert sind.
Die anderen Antworten, die ausgezeichnet mit einem Zähler vorschlagen, aber wenn nonpredictability (oder zumindest nicht triviale Vorhersagbarkeit) ist wichtig, Ihr ursprünglicher Algorithmus sollte gut sein.
Warum?
Im Grunde genommen, dass die Wahrscheinlichkeit Sie eine Wiederholung ganze Zahl erhalten wird, ist sehr, sehr (sehr) (sehr) kleine, 1 grob durch die Anzahl der ganzen Zahlen geteilt haben Sie noch nicht gesehen. Wenn Sie bereits N Zahlen generiert haben, wird die erwartete Laufzeit des Algorithmus annähernd linear in N mit einem Koeffizienten von 1/2 ^ 32, was bedeutet, dass Sie nur eine Milliarde Zahlen generieren über müßten, um die erwartete Laufzeit erhalten überschreiten 2 Iterationen der Schleife! In der Praxis wird tun das Set für die Existenz einer bestimmten Anzahl Überprüfung weit mehr die Laufzeit Ihres Algorithmus zu strecken als die Möglichkeit, die Schleife zu wiederholen (na ja, es sei denn, Sie eine HashSet vielleicht verwenden - ich vergessen, was seine asymptotische Laufzeit ist).
Für das, was es wert ist, die genaue erwartete Anzahl der Schleifendurchläufe ist
2^64/(2^32 - N)^2
Wenn Sie eine Million Zahlen generiert haben, funktioniert dies auf 1,00047 aus - das heißt, sagen wir, die 1000001. zu erzeugen Zahlen 1,002,000th, werden Sie wahrscheinlich bekommen ein Wiederholungszahl, < em> total , in all diesen Anrufen.
Die elegante Lösung für alle Anforderungen aufgelistet, soweit ich das beurteilen kann, ist nur ein Wert Erniedrigen bei -1 beginnen. Ich vermute aber, dass Sie nicht alle Anforderungen aufgelistet haben.
Versuchen Sie folgendes: http://www.javaconcurrencyinpractice.com/listings.html
Ich würde die OP Antwort mit jpalecek des Mähdreschers zu geben:
private final AtomicInteger ai=new AtomicInteger(0);
public int nextID() {
return ai.addAndGet(-1 - random.nextInt(1000));
}
Die Hoch Skala lib hat eine NonBlockingHashSet, die Sie verwenden können. Ersetzen Sie einfach Ihre Set-Instanz mit einer Instanz von NonBlockingHashSet und Sie sind alle gesetzt.
Ich denke, was Sie meinen, ist nicht blockierend und einspringenden.
Bearbeiten (ersetzt mein ursprünglicher, weil dies viel besser ist)
Ein Thread-basierte Option, die eigentlich recht performant ist kam gerade in dem Sinne (zumindest mehr performant als Ihr Original). Wenn Sie eine schwache Hash-Karte mit einem Thread-Objekt als „Key“ und als „Value“ ein Objekt mit der Fähigkeit, eine Reihe von in der Herstellung setzen geschaffen, sagen sie, 1000 Zahlen aus einem bestimmten Bereich.
So können Sie jeden Thread zuweisen seinen eigenen 1000 Nummernbereich zuweisen aus. Wenn das Objekt aus Zahlen läuft, haben sie eine ungültige Nummer zurück (0?), Und Sie wissen, dass Sie auf dieses Objekt einen neuen Bereich zuzuordnen sind.
Es gäbe keine Synchronisation etwas überall (edit:. Hoppla, war etwas falsch siehe unten), die schwache Karte Hash automatisch freies Threads würde, die (keine besondere Wartung) und der langsamste Teil ein einzelner Hash-Lookup sei zerstört wurden der Faden, der eigentlich sehr schnell ist.
erhält die laufenden Fäden mit:
Thread currThread=Thread.getCurrentThread();
Auch könnte ich falsch sein, und man konnte nur die Methode synchronisiert machen muß, dann würde dies funktionieren:
int n=-1;
synchronized int getNegativeNumber() {
return n--;
}
ging ich weiter und schrieb sie (manchmal dieses Zeug in meinem Kopf stecken bleibt, bis ich es tun, und so lange, wie ich es trotzdem tat, könnte ich auch per Post). Ungeprüfte und alles, aber ich bin mir ziemlich sicher, dass es sollte, wenn nicht in Betrieb direkt aus der Box in der Nähe sein. Nur eine Klasse mit einer statischen Methode aufrufen, eine eindeutige negative Zahl zu erhalten. (Oh, und ich habe einige Synchronisation benötigen, aber es wird nur 0,001% der Zeit verwendet werden).
Ich wünschte es eine Möglichkeit, einen verknüpften Codeblock statt inline wie dies ohne Website abgehend zu schaffen war -. Traurig über die Länge
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;
}
}
Es fiel mir nur, dass statt des einen großen synchronisierten Block von 2 sehr kleinen auf verschiedene Objekte synchronisiert ersetzt werden könnte, eine für die „+ = count“ und eine für den .put (). Wenn Kollisionen noch waren Sie verlangsamen, das könnte helfen (obwohl, wenn Kollisionen noch das Sie verlangsamen (WIRKLICH ???) Sie besser bedient werden, würde nur Zahl zu erhöhen.
