Sortieralgorithmus auf lokalen Daten gesucht

Java-Forum
1

Hi, ich suche einen Sortieralgorithmus der eine lokale Sortierung in eine globale überführt.

Beispiel:

  • Gegeben ist Objekt A B C und D
  • B will auf A folgen
  • C will auf B folgen
  • D will vor C
  • A hat keinen Wunsch

Die Sortierung wäre z.B.:
0: (D)
1: A (und D)
2: B (und D)
3: C

Sinn des ganzen ist ein Präprozessor, der Anweisungen in Reihenfolge ausführen soll. Jede Anweisung kann angeben ob sie vor oder nach einer anderen ausgeführt werden möchte.
Der Algorithmus soll mir ausspucken was die nächste(n) Anweisung(en) wären.

In dem Beispiel von oben könnte D zeitgleich wie A und B ausgeführt werden.

Vielleicht gibt es da ja was fertiges?

2

Hm. Auf Basis der bisherigen Beschreibung klingt das, als würde es einfach um eine Topologische Sortierung gehen - oder gibt es noch irgendwelche Zusatzbedingungen oder Einschränkungen?

1 „Gefällt mir“
3

Perfekt. Danke. :grin:

Einzig weitere Anforderung wäre daraus eine optimale Sortierung heraus zu filtern.

Also wenn
A > B
und
C > D

Und optimal wäre, wenn B und C gleichzeitig ausgeführt würden, um maximale Ressourcenauslastung zu erreichen.
Also würde die optimale Sortierung lauten
A > [B C] > D

Also parallele Prozesse sollen optimal zusammen gefasst werden.

4

Das erinnert frappierend an etwas, was ich auch in GitHub - javagl/Flow: Libraries for flow-based programming gebraucht habe: Der Flow ist ein Graph, der aus Module (Knoten) und Link (Kante) Instanzen besteht. Wenn so ein Flow ausgeführt werden soll, mache ich einfach folgendes:

  • Eingabe: Alle Module M
  • Ausgabe: Eine Liste E = { E0 … En } von Mengen von Modulen (die ich „Execution Sets“ (oder früher IIRC auch mal „Wavefronts“) genannt habe)
  • Solange M nicht leer ist:
    • Suche alle Module, die keine Vorgänger (in M) haben, und nenne sie Ei
    • Füge Ei zu E hinzu
    • Entferne alle Module, die in Ei sind, aus M

(Für „große“ Graphen könnte/sollte man sich da was geschickteres überlegen - das hängt aber auch stark davon ab, welche Graph-Datenstruktur man verwendet (d.h. wie einfach es ist, die „Module ohne Vorgänger (in M)“ zu finden). Die aktuelle Implementierung in FlowExecutorUtils ist ziemlich straightforward, und würde bei wirklich großen Graphen vielleicht etwas in die Knie gehen (und vielleicht würde es ihn auch raushauen, wenn er Zyklen enthält), aber für meine Zwecke hat’s das getan).

Wenn man dann diese „Execution Sets“ hat, kann man jedes einzelne davon parallel ausführen. Also sowas hier machen:

List<Set<Module>> executionSets = 
    FlowExecutorUtils.computeExecutionSets(modules);
for (Set<Module> executionSet : executionSets)
{
    executeAll(executionSet);
}

wobei das executeAll die Module eben (als Callable-instanzen) in einen ThreadPoolExecutor wirft.

Die Frage, wo die Ergebnisse der „Vorgänger“ gespeichert werden, damit die „Nachfolger“ sie als Eingabe verwenden können, drängt sich natürlich auf. Im Moment wird das ganze bei mir in den Links gespeichert (d.h. die sind eine einelementige blocking queue), aber … das wäre einer der ersten Punkte, wo ich refactorn und verallgemeinern würde, wenn… ich … naja, halt „Software entwickeln“ würde. (Ich vermisse das Softwareentwicklen :frowning: ).

5

Gebraucht oder auch umgesetzt? :smile: was du jetzt beschrieben hast hört sich für mich jetzt erst mal nach topologischer Sortierung (Frage1) an. :slight_smile:

6

Nun, die Links zeigen: Es ist auch umgesetzt. Das ganze ist „live“, in dem Sinne, dass man es relativ leicht auch ausprobieren können sollte (auch wenn es natürlich etliche Baustellen gibt - ich habe zuletzt „viel“ gemacht, was ich gerne mit dieser „Flow“-Lib verheiraten würde, aber … zu oft stelle ich mir die Frage: „Wozu eigentlich?“ und es wird immer schwieriger, darauf Antworten zu finden…)

Jedenfalls ist das, was da berechnet wird, nicht „direkt“ eine „reine“ topologische Sortierung: Die topologische Sortierung ist ja nicht eindeutig. Mit

A->B
A->C

kann man sowohl

A->B->C
A->C->B

bekommen.

Das, was in der Flow-Lib berechnet wird, ist in diesem Sinne etwas weniger „spzifisch“: Das Endergebnis ist keine „komplette“ Sortierung. Es sagt nichts darüber aus, ob es mit B->C endet oder mit C->B. Dort wird

{ A } -> { B, C }

berechnet, was (übertragen auf deine Frage) bedeutet, dass B und C parallel ausgeführt werden können.

7

Und wenn

A->B->D
A->C

?

ich bin gerade noch am hin und her überlegen. Gerade für so Fälle wie

A->B->C->D
A->E->F->G

Optimale Kombinationen: C&E, D&F, B&G parallel

Wird mein Anwendungsfall wahrscheinlich zu ressourcenintensiv. Theoretisch müsste ich jede mögliche Kombination durchgehen und Gewichten. Ich hab das Gefühl das läuft auf ein NP-Problem hinaus.

8

Nah, NP? Alle möglichen Kombinationen durchprobieren? Muss ja nicht sein. Bei

A->B->D
A->C

wäre das Ergebnis

{ A }, { B, C }, { D }

und beim letzten eben

    { A }, { B, E }, { C, F  }, { D, G  }

Ansonsten müßtest du begründen, warum „C&E, D&F, B&G parallel“ da „optimal“ wäre…