Gesehen
Programmierung
Google
Gemini 2.5 Flash
VS
OpenAI
GPT-5.2
Implementieren Sie eine sperrfreie konkurrierende Skip-Liste mit Bereichsabfragen
Entwerfen und implementieren Sie eine nebenläufige Skip-Liste in einer von Ihnen gewählten Sprache (C++, Java, Rust, Go oder Python), die die folgenden Operationen unterstützt:
1. **insert(key, value)** – Fügen Sie ein Schlüssel-Wert-Paar ein. Falls der Schlüssel bereits existiert, aktualisieren Sie den Wert atomar. Gibt true zurück, wenn ein neuer Schlüssel eingefügt wurde, false, wenn aktualisiert wurde.
2. **remove(key)** – Löschen Sie das Schlüssel-Wert-Paar logisch. Gibt true zurück, wenn der Schlüssel gefunden und entfernt wurde, sonst false.
3. **find(key)** – Geben Sie den dem Schlüssel zugeordneten Wert zurück oder zeigen Sie das Fehlen an.
4. **range_query(low, high)** – Geben Sie alle Schlüssel-Wert-Paare zurück, für die low <= key <= high gilt, als Liste nach Schlüssel sortiert. Das Ergebnis muss ein konsistenter Snapshot sein: Es darf keine Schlüssel enthalten, die niemals gleichzeitig während der Ausführung der Operation vorhanden waren.
5. **size()** – Geben Sie die ungefähre Anzahl aktiver (nicht gelöschter) Elemente zurück.
Anforderungen und Einschränkungen:
- Die Skip-Liste muss sicher für die gleichzeitige Verwendung durch mehrere Threads sein, die beliebige Kombinationen der oben genannten Operationen gleichzeitig ausführen, ohne ein einzelnes globales Lock. Sie können feinmaschige Sperren, sperrfreie Techniken (CAS) oder eine Kombination verwenden.
- Lazy Deletion ist akzeptabel: Knoten können vor der physischen Entfernung logisch als gelöscht markiert werden.
- Die probabilistische Level-Generierung sollte eine Standard-Geometrische Verteilung mit p=0.5 und einem maximalen Level von 32 verwenden.
- Schlüssel sind 64-Bit-Ganzzahlen; Werte sind Strings.
- Berücksichtigen Sie die korrekte Speicherverwaltung. Wenn Sie eine Sprache ohne Garbage Collection verwenden, erklären oder implementieren Sie Ihre Reclamationsstrategie (z. B. epoch-based reclamation, hazard pointers).
Abgaben:
1. Vollständiger, kompilierbarer/ausführbarer Quellcode mit Kommentaren, die Ihre Nebenläufigkeitsstrategie erklären.
2. Ein Test oder eine Demonstration, die mehrere Threads startet, die gleichzeitig Inserts, Deletes, Finds und Range Queries ausführen, und die die Korrektheit validiert (z. B. keine verlorenen Updates, keine Phantom-Leses in Bereichsabfragen, keine Abstürze).
3. Ein kurzer Analyseabschnitt (als Kommentare oder Docstring), der Folgendes diskutiert:
- Die Linearizability- (oder Snapshot-Isolation-)Garantien, die Ihre Implementierung bietet.
- Die erwartete Zeitkomplexität jeder Operation.
- Bekannte Einschränkungen oder mögliche ABA-Probleme und wie Sie diese adressieren.
Ihre Lösung wird hinsichtlich Korrektheit unter Nebenläufigkeit, Codeklarheit, Robustheit der Nebenläufigkeitsstrategie, Qualität des Snapshot-Mechanismus für Bereichsabfragen und Gründlichkeit der Analyse bewertet.
