Multidimensionales Array sortieren

[Dr.Speck]

Hallo,

ich habe ein Array aus Arrays, die nach einem komplexen Filter sortiert und gefiltert werden müssen und suche noch einen guten Algorithmus dafür.

Ziel ist es eine Menge von unbekannten Einträgen nach einer definierten Priorität aufzulisten und dabei ggf. auch zu filtern.

------------------

Die Sortierung soll die Daten aufgrund eines Filters gewichten. Dieser Filter soll im Stringformat so aussehen:

K11:[1-12]:C,M,Y; MK01:*:*; *:*:*

- Jedes Filterargument ist durch ";" getrennt.
- Die Reihenfolge der Argumente, bzw. deren Sub-Argumente entscheided die Reihenfolge der Ausgabe
- Jedes Argument ist so aufgebaut: ID ':' PAGES ':' INKS
- ID ist ein string der verglichen werden muss, oder ein '*' für alle IDs.
- PAGES ist entweder ein '*' für alle Seiten oder eine Nummer oder eine Range in "[]" oder eine Kombination aus alledem. Hier ist ebenfalls die Reihenfolge wichtig, so hat z.B. bei "5,6,7,1,2,3" die Seite 5 mehr "gewicht" als die Seite 1.
- INKS verhält sich wie PAGES, hier sind jedoch wieder Strings statt Zahlen am Werk.

Ein '*' bedeutet ALLES matched. Fehlt dieser, werden die Angaben nicht in das Ergebnis übernommen.

Die zu sortierenden Daten bestehen aus 4 Angaben:
1. deren "natürliche" Reihenfolge (index im Array)
2. die ID der Seite
3. die PAGE
4. die INK

$found = array(
0 => array( id=>'MK01', page=>'15', ink=>'K' ),
1 => array( id=>'K11', page=>'4', ink=>'K' ),
2 => array( id=>'MK01', page=>'15', ink=>'C' ),
3 => array( id=>'K14', page=>'1', ink=>'M' ),
4 => array( id=>'K11', page=>'4', ink=>'C' ),
);

Mit folgendem Filter müsste das Array nach dem Sort dann so aussehen:
$filter = "K11:[1-12]:C,M,Y; MK01:*:*"
$sorted = array(
2 => array( id=>'K11', page=>'4', ink=>'C' ),
1 => array( id=>'MK01', page=>'15', ink=>'K' ),
0 => array( id=>'MK01', page=>'15', ink=>'C' ),
);

(! Die wichtigste Seite soll den höchsten Index haben um die Werte mit array_pop zu verarbeiten)

Erklärung: K11 und K14 kommen nicht, weil keine Regel existiert. K11/4/C fällt in die erste Regel, hat also die höchste Priorität.

------------------

Soweit die Einleitung. Mein bisheriger Lösungsansatz sieht so aus das ich für jedes Attribut ein "Gewicht" festlegen möchte und später diese addiere. Z.B. kann die Natürliche Reihenfolge von 1-9999 liegen. Die Farbe (INK) dann von 10000 bis 10099, die PAGE von 10100-10999 und die ID von 11000-11099.

Wenn ich also für jede gefundene Seite im $found Array anhand ihrer Werte im Vergleich zum Filter ein Gewicht für jedes Attribut errechene und diese dann addiere müsste ich eine Art Quersumme haben, die jede Seite eindeutig in Relation zu den anderen setzt. Anschliessend müsste man "nur noch" numerisch sortieren.
Zum Vergleich mit den Filterregeln müsste jede Regel dann aufgrund ihres Indexes (natürliche Folge) bewertet werden.

Hui, ich hoffe das ist nicht zu komplex um es zu verstehen. Mir qualmt schon der Kopf... :-)

[ghostgambler]

Warum arbeitest du den Filter nicht einfach von hinten ab?
Du arbeitest dich von hinten nach vorne durch und wenn ein Datensatz auf den aktuellen Filter passt, setzt du ihn an die erste Stelle. Wenn du ganz vorne bist, sollte alles richtig sein?! oo

[Dr.Speck]

>> Warum arbeitest du den Filter nicht einfach von hinten ab?

Gute Idee, ich versuche das jetzt mal geistig umzusetzen:

Also, mein Filter soll sein: "K11:[6-9]:C,M,Y; MK01:*:*; K11:*:K;"

Meine Daten:
"K11_6_K"
Verwende Filter[3]:
Prüfe Farbe (K) gegen Filterfarbe (K) = Match
Prüfe Seite (6) gegen Filterseite (*) = Match
Prüfe ID (K11) gegen Filter-ID(K11) = Match
--> Der Datensatz wird gepushed, keine weiteren Filter mehr für diesen prüfen

"K11_7_M"
--> Der Datensatz wird durch Filter[1] abgedeckt und kommt an den Anfang.

"MK01_14_K"
--> Der Datensatz wird durch Filter[2] abgedeckt und kommt an den Anfang.

"K11_7_Y"
--> Der Datensatz wird durch Filter[1] abgedeckt und kommt an den Anfang.

So steht da jetzt:
[0] K11_6_K
[1] K11_7_M
[2] MK01_14_K
[3] K11_7_Y

Also ich kann da jetzt keine Wunschsortierung erkennen, oder mache ich einen Denkfehler?

[ghostgambler]

Das Array verändert sich doch...

Wenn du das Array hast:
[0] K11_6_K
[1] K11_7_M
[2] MK01_14_K
[3] K11_7_Y

Und dann setzt du K11_7_Y an den Anfang, und dann MK01_14_K an den Anfang, ist das Array doch nicht
[3] K11_7_Y
[2] MK01_14_K
[0] K11_6_K
[1] K11_7_M

sondern

[2] MK01_14_K
[3] K11_7_Y
[0] K11_6_K
[1] K11_7_M

[Dr.Speck]

Okay, ich habe es also nicht verstanden...
Kannst Du mir bitte etwas konkreter erläutern wie diese Sortierung stattfinden soll, also in ner Art Pseudo-Code? Ich habe es versucht aber mein Ergebnis war ja scheinbar nicht richtig.

[ghostgambler]

$found = array(
0 => array( id=>'MK01', page=>'15', ink=>'K' ),
1 => array( id=>'K11', page=>'4', ink=>'K' ),
2 => array( id=>'MK01', page=>'15', ink=>'C' ),
3 => array( id=>'K14', page=>'1', ink=>'M' ),
4 => array( id=>'K11', page=>'4', ink=>'C' ),
);
mit dem Filter hier:
$filter = "K11:[1-12]:C,M,Y; MK01:*:*"

nach 1. Schritt
$found = array(
0 => array( id=>'MK01', page=>'15', ink=>'K' ),
1 => array( id=>'K11', page=>'4', ink=>'K' ),
2 => array( id=>'MK01', page=>'15', ink=>'C' ),
3 => array( id=>'K14', page=>'1', ink=>'M' ),
4 => array( id=>'K11', page=>'4', ink=>'C' ),
);
nach 2. Schritt
$found = array(
2 => array( id=>'MK01', page=>'15', ink=>'C' ),
0 => array( id=>'MK01', page=>'15', ink=>'K' ),
1 => array( id=>'K11', page=>'4', ink=>'K' ),
3 => array( id=>'K14', page=>'1', ink=>'M' ),
4 => array( id=>'K11', page=>'4', ink=>'C' ),
);
nach 3. Schritt
$found = array(
1 => array( id=>'K11', page=>'4', ink=>'K' ),
2 => array( id=>'MK01', page=>'15', ink=>'C' ),
0 => array( id=>'MK01', page=>'15', ink=>'K' ),
3 => array( id=>'K14', page=>'1', ink=>'M' ),
4 => array( id=>'K11', page=>'4', ink=>'C' ),
);
nach 4. Schritt
$found = array(
4 => array( id=>'K11', page=>'4', ink=>'C' ),
1 => array( id=>'K11', page=>'4', ink=>'K' ),
2 => array( id=>'MK01', page=>'15', ink=>'C' ),
0 => array( id=>'MK01', page=>'15', ink=>'K' ),
3 => array( id=>'K14', page=>'1', ink=>'M' ),
);

Das was halt nicht beachtet wird ist, dass page und ink aufsteigend ist (was es wohl sein soll) - da musst du dir noch was einfallen lassen...
Aber es sollte ja auch kein Problem sein, bei einem Filterdurchgang, alle passenden Elemente raus zu fischen und die dann per multisort zu sortieren, bevor man sie gebündelt vorne ans Array setzt.

[PHP-Desaster]

Ich denke, er meint so etwas:

foreach_reverse( filter ) {
  foreach( elemente im array ) {
    if( filter matcht element ) {
      packe element vorne auf das ergebnisarray;
    }
  }
}

[Dr.Speck]

Hallo,

Original geschrieben von PHP-Desaster
Ich denke, er meint so etwas:

foreach_reverse( filter ) {
  foreach( elemente im array ) {
    if( filter matcht element ) {
      packe element vorne auf das ergebnisarray;
    }
  }
}

Ja, ich glaube ich habs kapiert. Das "foreach"-Elemente müsste aber dann auch reverse sein, denn ein Filterelement kann eine Liste enthalten und ich möchte das das Ergebnis "entlang" dieser Liste sortiert wird. Beispiel:
Ich fillter bei INK nach "C,M,Y,K". Dann möchte ich das die jeweilige C-Form wirklich auch vor der M-Form eingereiht ist.

Ich habe es im Scoring-Verfahren versucht und obwohl es anfänglich funktioniert hatte, stosse ich schnell an die Grenzen des Verfahrens. Der Vorteil hierbei war das jede Seite nur einmal geprüft werden musste. Aber ich will es gerne mit der genannten Taktik versuchen.

Das genannte Problem der fehlenden, aufsteigenden, Sortierung von Page und Ink ist wohl nur beim "*" Operator. Hier ist es theoretisch egal, denn es ist ein Wildcard. Ich wollte es nur grundsätzlich so halten, das bei fehlenden eindeutigen Matches letztenendes die Natürliche Position innerhalb des Arrays entscheidend ist.

Ich werde erstmal versuchen die Code wie vorgeschlagen umzusetzen und melde mich dann wieder :-)

Achja, "vielen Dank!" (hätt ich glatt vergessen ;-)

[Dr.Speck]

Hallo,

folgende Umsetzung habe ich versucht:

$joblist ist gefüllt mit den im Thread-Start genannten werten...

$ordered = array();
foreach (array_reverse($filter) as $subfilter) {
  foreach ($joblist as $job) { 
    if (filter_match($subfilter, $job))
      array_unshift($ordered, $job);
  }
} 

Folgende Probleme haben sich ergeben:
a) Aufträge sind mehrfach vorhanden.
b) Die Matches aus jedem Filter stehen in umgekehrter Reihenfolge im Ergebnis als in der Joblist. Die "natürliche" Reihenfolge ist nicht mehr gegeben.
c) Die Ergebnisse im subfilter sind nicht in der Reihenfolge der Elemente des subfilters.

Folgende Lösungen kann ich mir vorstellen:
zu a) Schleife durch alle $ordered und ein Lookup-Hash aus den Attributwerten des Jobs bauen. Ist der Key im Lookup schon vorhanden, den Eintrag entfernen, bzw. nicht im Ergebnis mit aufnehmen.
zu b) Vor der Schleife die Einträge der $joblist mit array_reverse umdrehen.

Zu c) habe ich keine Lösung.

[ghostgambler]

Dann matche halt erst alle passenden Elemente, entferne diese dabei aus dem Array $joblist, sortiere die Elemente danach nach belieben, oder halt auch nicht, wenn du die "natürliche Ordnung" beibehalten willst, und füge sie danach gebündelt vorne an...


Abgesehen davon solltest du vielleicht mal lernen ein Problem in Teilprobleme zu zerlegen und diese dann auf einem niedrigen Level zu lösen, nach irgendeinem gleich-bleibenden Schema, was der PC auch nachvollziehen kann.
Es macht nicht unbedingt Spaß Fragen nach der Logik eines Algorithmus zu beantworten, wenn man am anderen Ende der Tastatur sitzt und sich denkt "Die Frage ist doch wohl nicht ernst gemeint?" - denn das Gefühl hab ich irgendwie bei diesem Thread jetzt zum zweiten Mal... tut mir Leid