Algorithmus - Implementieren Sie zwei Funktionen, die/assign in einzigartige ids aus einem Pool

Question

er eine gute Lösung für diese Frage zu finden versuchen -

Implementieren zwei Funktionen, die/in einzigartige ids aus einem Pool zuweisen. Die Speicherauslastung sollte minimiert werden und die Zuweisung/Freigabe sollte schnell sein, auch bei hoher Konkurrenz. alloc() returns verfügbar ID release (id) gibt die zuvor zugewiesene ID frei

Der erste Gedanke war, eine Karte mit IDs und Verfügbarkeit (in Boolean) zu erstellen. So etwas wie diese

Map<Integer, Boolean> availabilityMap = new HashMap(); 

public Integer alloc() { 
    for (EntrySet es : availabilityMap.entrySet()) { 
     if (es.value() == false) { 
      Integer key = es.key(); 
      availabilityMap.put(key, true); 
      return key; 
     } 
    } 
} 

public void release(Integer id) { 
    availabilityMap.put(id, false); 
} 

Dies ist jedoch nicht ideal für mehrere Threads und „Speicherverbrauch minimiert werden soll, und die assign/Release sollte schnell sein, auch bei hohen Konkurrenz.“

Was wäre ein guter Weg, um sowohl die Speichernutzung als auch die Geschwindigkeit zu optimieren? Für Speicherverbrauch, ich denke Karte sollte mit einigen anderen Datenstruktur ersetzt werden, aber ich bin mir nicht sicher, was es ist. So etwas wie Bitmap oder Bit-Set? Wie kann ich ID und Verfügbarkeit in diesem Fall erhalten? Für die Nebenläufigkeit muss ich Sperren verwenden, aber ich bin mir nicht sicher, wie ich effektiv Konflikte bewältigen kann. Eventuell verfügbare IDs in separaten Chunks ablegen, so dass jeder einzeln darauf zugreifen kann? Irgendwelche guten Vorschläge?

Answer 1

Zunächst möchten Sie nicht die gesamte Karte durchlaufen, um die verfügbare ID zu finden.

Sie können also zwei Sätze von IDs verwalten, die erste für verfügbare IDs und die zweite für zugewiesene IDs.

Dann wird es Zuweisung/Freigabe ziemlich einfach und schnell machen.

Sie können auch ConcurrentMap für beide Container (Sets) verwenden, es wird die Konkurrenz reduzieren.

Answer 2

Edit: Changed Boden Sentinel, wurde ein Fehler behoben

---

Zunächst nicht die gesamte Karte iterieren eine verfügbare ID zu finden. Du solltest nur konstante Zeit dafür brauchen.

Was Sie tun könnten, um es schnell zu machen ist, dies zu tun:

1. ein int index = 1; für Ihren Zähler erstellen. Dies ist technisch die Anzahl der erzeugten IDs + 1 und immer > 0.

2. Erstellen Sie eine ArrayDeque<Integer> free = new ArrayDeque<>(); für die freien IDs. Garantierter konstanter Zugriff.

3. Wenn Sie eine ID zuweisen, wenn die freie ID-Warteschlange leer ist, können Sie den Zähler einfach zurückgeben und inkrementieren (z. B. return index++;). Ansonsten nimm den Kopf und gib das zurück.

4. Wenn Sie eine ID freigeben, drücken Sie die zuvor verwendete ID auf die free Deque.

5. Denken Sie daran, synchronize Ihre Methoden.

Dies garantiert O(1) Zuteilung und Freigabe, und es hält auch Zuweisung recht niedrig (wörtlich einmal pro free). Obwohl es synchronisiert ist, ist es schnell genug, dass es kein Problem sein sollte.

Eine Implementierung könnte wie folgt aussehen:

import java.util.ArrayDeque; 

public class IDPool { 
    int index = 1; 
    ArrayDeque<Integer> free = new ArrayDeque<>(); 

    public synchronized int acquire() { 
     if (free.isEmpty()) return index++; 
     else return free.pop(); 
    } 

    public synchronized void release(id) { 
     free.push(id); 
    } 
} 

---

Wenn Sie darüber hinaus die freie ID-Liste ist einzigartig sicherstellen wollen (wie Sie sollte für etwas Wichtiges) sowie persistent, können Sie tun die folgenden:

1. Verwenden Sie eine HashMap<Integer id, Integer prev>, um alle generierten IDs zu halten. Denken Sie daran, es muss nicht bestellt oder sogar iteriert werden.

   • Dies ist technisch ein Stapel in einer Hash-Karte codiert werden.
   • Hocheffiziente Implementierungen von diesem existieren.
   • In der Realität wird jede ungeordnete int ->int Karte hier tun.

2. Verfolgen Sie die top ID für die freie ID-Set. Denken Sie daran, dass 1 nichts darstellen und null verwendet werden kann, so dass Sie es nicht boxen müssen. (IDs sind immer positiv.) Am Anfang, das ist nur int top = 1;

3. werden würde, wenn eine ID-Zuweisung, wenn es freie IDs (dh top >= 2) sind, gehen Sie wie folgt vor:

   • Stellen Sie den neuen top auf die alt head Wert in der free Karte.
   • Setzen Sie den alten top Wert in der Karte auf 0 und markieren Sie ihn.
   • Geben Sie die alte top zurück.

4. Wenn ein altes ID Freigabe, dies zu tun, statt:

   • Wenn die alte ID bereits im Pool ist, kehren früh, so dass wir es nicht beschädigt.
   • Setzen Sie den Wert der ID in der Karte auf den alten top.
   • Setzen Sie die neue top auf die ID, da sie immer die letzte ist.

Die optimierte Implementierung enden würde wie folgt aussehen:

import java.util.HashMap; 

public class IDPool { 
    int index = 2; 
    int top = 1; 
    HashMap<Integer, Integer> pool = new HashMap<>(); 

    public synchronized int acquire() { 
     int id = top; 
     if (id == 1) return index++; 
     top = pool.replace(id, 0); 
     return id; 
    } 

    public synchronized void release(id) { 
     if (pool.getOrDefault(id, 1) == 0) return; 
     pool.put(id, top); 
     top = id; 
    } 
} 

Wenn es sein muss, können Sie anstelle der Hash-Karte eine wachstumsfähige Integer-Array verwenden könnte (es ist immer zusammenhängend), und erkennen, deutliche Leistungssteigerungen. Tatsache ist, dass ich das wahrscheinlich umsetzen würde. Es würde nur eine kleine Menge an Bit Twiddling erfordern, da ich die Größe des Arrays beibehalten würde, um auf die nächste Potenz von 2 aufgerundet zu werden.

---

Ja ... Ich musste tatsächlich einen ähnlichen Pool in JavaScript schreiben, weil ich eigentlich mäßig schnell IDs in Node.js für potenziell Hochfrequenz langlebige IPC Kommunikation benötigt.

Das gute daran ist, dass es im Allgemeinen Zuweisungen vermeidet (im schlimmsten Fall einmal pro erworbene ID, wenn keine freigegeben sind), und es ist sehr anfällig für spätere Optimierung, wo nötig.