php-resource



Zurück   PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr > Scripts > BRAINSTORMING PHP/SQL/HTML/JS/CSS
 

Login

 
eingeloggt bleiben
star Jetzt registrieren   star Passwort vergessen
 

 

 


BRAINSTORMING PHP/SQL/HTML/JS/CSS Ihr habt eine Idee, aber keinen genauen Ansatz? Diskutiert mit anderen Usern des Forums über eure Gedankengänge um evtl. hilfreiche Ideen zu bekommen!
Normale Fragen bitte weiterhin in die entsprechenden Foren!

Antwort
 
LinkBack Themen-Optionen Thema bewerten
  #1 (permalink)  
Alt 08-09-2007, 08:27
Dr.Speck
 Registrierter Benutzer
Links : Onlinestatus : Dr.Speck ist offline
Registriert seit: Sep 2007
Beiträge: 54
Dr.Speck ist zur Zeit noch ein unbeschriebenes Blatt
Question Multidimensionales Array sortieren

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... :-)
Mit Zitat antworten
  #2 (permalink)  
Alt 08-09-2007, 10:46
ghostgambler
 Master
Links : Onlinestatus : ghostgambler ist offline
Registriert seit: Jul 2004
Ort: DE - NRW
Beiträge: 4.620
ghostgambler ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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
Mit Zitat antworten
  #3 (permalink)  
Alt 09-09-2007, 16:42
Dr.Speck
 Registrierter Benutzer
Links : Onlinestatus : Dr.Speck ist offline
Registriert seit: Sep 2007
Beiträge: 54
Dr.Speck ist zur Zeit noch ein unbeschriebenes Blatt
Standard

>> 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?
Mit Zitat antworten
  #4 (permalink)  
Alt 09-09-2007, 17:44
ghostgambler
 Master
Links : Onlinestatus : ghostgambler ist offline
Registriert seit: Jul 2004
Ort: DE - NRW
Beiträge: 4.620
ghostgambler ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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
Mit Zitat antworten
  #5 (permalink)  
Alt 10-09-2007, 09:15
Dr.Speck
 Registrierter Benutzer
Links : Onlinestatus : Dr.Speck ist offline
Registriert seit: Sep 2007
Beiträge: 54
Dr.Speck ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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.
Mit Zitat antworten
  #6 (permalink)  
Alt 10-09-2007, 10:32
ghostgambler
 Master
Links : Onlinestatus : ghostgambler ist offline
Registriert seit: Jul 2004
Ort: DE - NRW
Beiträge: 4.620
ghostgambler ist zur Zeit noch ein unbeschriebenes Blatt
Standard

$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.
Mit Zitat antworten
  #7 (permalink)  
Alt 10-09-2007, 10:36
PHP-Desaster
 PHP Expert
Links : Onlinestatus : PHP-Desaster ist offline
Registriert seit: Mar 2006
Beiträge: 3.105
PHP-Desaster befindet sich auf einem aufstrebenden Ast
Standard

Ich denke, er meint so etwas:
Code:
foreach_reverse( filter ) {
  foreach( elemente im array ) {
    if( filter matcht element ) {
      packe element vorne auf das ergebnisarray;
    }
  }
}
Mit Zitat antworten
  #8 (permalink)  
Alt 16-09-2007, 18:11
Dr.Speck
 Registrierter Benutzer
Links : Onlinestatus : Dr.Speck ist offline
Registriert seit: Sep 2007
Beiträge: 54
Dr.Speck ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Hallo,

Zitat:
Original geschrieben von PHP-Desaster
Ich denke, er meint so etwas:
Code:
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 ;-)
Mit Zitat antworten
  #9 (permalink)  
Alt 17-09-2007, 12:10
Dr.Speck
 Registrierter Benutzer
Links : Onlinestatus : Dr.Speck ist offline
Registriert seit: Sep 2007
Beiträge: 54
Dr.Speck ist zur Zeit noch ein unbeschriebenes Blatt
Standard

Hallo,

folgende Umsetzung habe ich versucht:

PHP-Code:
$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.
Mit Zitat antworten
  #10 (permalink)  
Alt 17-09-2007, 20:19
ghostgambler
 Master
Links : Onlinestatus : ghostgambler ist offline
Registriert seit: Jul 2004
Ort: DE - NRW
Beiträge: 4.620
ghostgambler ist zur Zeit noch ein unbeschriebenes Blatt
Standard

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
Mit Zitat antworten
Antwort

Lesezeichen


Aktive Benutzer in diesem Thema: 1 (Registrierte Benutzer: 0, Gäste: 1)
 

Themen-Optionen
Thema bewerten
Thema bewerten:

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are an


PHP News

ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlicht
ebiz-trader 7.5.0 mit PHP7 Unterstützung veröffentlichtDie bekannte Marktplatzsoftware ebiz-trader ist in der Version 7.5.0 veröffentlicht worden.

28.05.2018 | Berni

Wissensbestand in Unternehmen
Wissensbestand in UnternehmenLebenslanges Lernen und Weiterbilden sichert Wissensbestand in Unternehmen

25.05.2018 | Berni


 

Aktuelle PHP Scripte

PHP Server Monitor

PHP Server Monitor ist ein Skript, das prüft, ob Ihre Websites und Server betriebsbereit sind.

11.09.2018 Berni | Kategorie: PHP/ Security
PHP WEB STATISTIK ansehen PHP WEB STATISTIK

Die PHP Web Statistik bietet Ihnen ein einfach zu konfigurierendes Script zur Aufzeichnung und grafischen und textuellen Auswertung der Besuchern Ihrer Webseite. Folgende zeitlichen Module sind verfügbar: Jahr, Monat, Tag, Wochentag, Stunde Folgende son

28.08.2018 phpwebstat | Kategorie: PHP/ Counter
Affilinator - Affilinet XML Produktlisten Skript

Die Affilinator Affilinet XML Edition ist ein vollautomatisches Skript zum einlesen und darstellen der Affili.net (Partnerprogramm Netzwerk) Produktlisten und Produktdaten. Im Grunde gibt der Webmaster seine Affilinet PartnerID ein und hat dann unmittelb

27.08.2018 freefrank@ | Kategorie: PHP/ Partnerprogramme
 Alle PHP Scripte anzeigen

Alle Zeitangaben in WEZ +2. Es ist jetzt 21:19 Uhr.