Verteilt Sortieren

Der hier verwendete Dialekt von Lisp enthält Funktionen, mit denen Berechnungen über mehrere Computer verteilt werden können: Die Funktion get-places erwartet keine Argumente und liefert eine Liste von Orten, an denen Berechnungen ausgeführt werden können und die Funktion at erwartet zwei Argumente, einen Ort und einen Ausdruck, führt dann den Ausdruck am gewünschten Ort aus und liefert das Ergebnis zurück. Wenn nil als Ort angegeben wird, erfolgt die Auswertung lokal.

Als Demonstration für die Nutzung dieser Funktionen ist im Folgenden ein Sortieralgorithmus angegeben, der mehreren Computern jeweils einen Teil der Arbeit zuweist.

Die Methode distributed-sort ruft ihre dreiargumentige Variante mit einer Liste von bekannten Orten (zuzüglich dem lokalen Ort nil), der zu sortierenden Liste und der Vergleichsfunktion auf.

(defmethod distributed-sort (unsorted-list comparator)
  t
  (distributed-sort
    (cons nil (get-places))
    unsorted-list
    comparator))

Die dreiargumentige Variante der Methode erledigt die eigentliche Arbeit. Zunächst werden einige Fälle unterschieden: Wenn weniger als zwei Elemente zu sortieren sind, dann ist die Eingabe bereits sortiert und wird unverändert als Ausgabe geliefert.

Wenn nur ein Ort für die Verteilung der Teilaufgaben zur Verfügung steht, dann wird die Eingabe lokal mit der Grundfunktion sort sortiert.

Der verbleibende Fall ist der interessante: Die Eingabe und die Orte werden mit split in zwei möglichst gleichgroße Teile aufgeteilt, die Teile gehen in zwei rekursive Aufrufe (siehe Rekursion) an entfernten Orten ein und die Resultate werden mit der Grundfunktion merge kombiniert.

(defmethod distributed-sort (places unsorted-list comparator)
  t
  (cond
    ((or (null? unsorted-list) (single? unsorted-list))
      unsorted-list)
    ((single? places)
      (sort unsorted-list comparator))
    (t
      (let
        ((halfed-places (split places 2))
         (halfed-list (split unsorted-list 2)))
        (merge
          (quote list)
          (at
            (first (first halfed-places))
            (distributed-sort
              (first halfed-places)
              (first halfed-list)
              comparator))
          (at
            (first (second halfed-places))
            (distributed-sort
              (second halfed-places)
              (second halfed-list)
              comparator))
          comparator)))))

Für praktische Zwecke ist dieser Algorithmus nur sinnvoll, wenn der Vergleich zweier Elemente sehr aufwendig ist. Sonst ist das Verhältnis aus Kommunikation (der Eingaben an entfernte Orte und der Ausgaben zurück) zu geleisteter Rechenarbeit zu ungünstig und es wäre besser, die Eingabe einfach lokal zu sortieren.


distributed-sort.sheet.xml