Lehrplan Lektion 76 von 148 · Ungerade Grenzen
Ungerade Grenzen

Offline zuerst

Warum das wichtig ist "Sende die ganze Liste, der letzte Schreibvorgang gewinnt" funktioniert, bis zwei Geräte offline bearbeiten. Dann verschwinden die Änderungen einer Person still und niemand kann sagen, wo sie hingegangen sind.

Eine

A Einkaufslisten-App muss in einem Supermarktkeller ohne Signal funktionieren. Jedes Gerät führt ein Protokoll darüber, was es getan hat. Wenn die Geräte wieder verbunden werden, werden die zwei Protokolle zu einer Liste zusammengeführt. Beide Protokolle beginnen mit der gleichen gemeinsamen Historie (alles synchronisiert, bevor sie offline gingen), dann hat jedes seine eigenen Änderungen.

Operationstagebuch: eine Aufzeichnung der vorgenommenen Änderungen (dies hinzufügen, das entfernen), anstatt einer Kopie des Ergebnisses. Logs können zusammengeführt werden; Kopien können nur überschreiben.

("add", "milk", "p7")             # tag p7 is unique to this add
("remove", "milk", ["p7", "s2"])  # removes exactly the adds this device had seen
Du bist dran

Schreibe merge(log_a, log_b) und gib die sortierte Liste der Artikel auf der zusammengeführten Einkaufsliste zurück (jeder Artikel einmal). Ein Log ist eine Liste von Operationen: ("add", item, tag), wobei jeder add einen eindeutigen Tag hat, und ("remove", item, tags), wobei tags die adds dieses Artikels auflistet, die das Gerät sehen konnte, als es ihn entfernt hat.

Limits. Keine Bearbeitung darf verloren gehen: ein Element ist in der Liste, wenn mindestens einer seiner adds nie entfernt wurde. Ein remove hebt nur die Tags auf, die es auflistet, also überlebt ein add, das das andere Gerät während der Offline-Zeit gemacht hat. Beide Logs können die gleichen gemeinsamen Operationen enthalten (zähle sie einmal). merge(a, b) muss merge(b, a) entsprechen.

Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion

Diese Übung öffnet bald

Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.