NSArray mit NSURL "Finder like" sortieren

little_pixel · 29. Mai 2016, 19:49

Hallo,

bislang habe ich eine Helfer-Methode, die Strings in einem Array "Finder like" sortiert.
Mittlerweile habe ich aber alle Pfade auf NSURL umgestellt.

Jetzt die Frage: Wie sortieren?
Alle URL zu einem Textpfad umbauen und dann wieder zu URL finde ich ekelhaftig.

Sieht hier jemand eine bessere Lösung?

Viele Grüße

Chris · 29. Mai 2016, 20:24

~~Da kannst du doch einen NSSortDescriptor auf @"path" loslassen.~~

Edit:
So ungefähr

Quellcode

array = [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
return [obj1.path compare: obj2.path options: NSCaseInsensitiveSearch | NSNumericSearch | NSWidthInsensitiveSearch | NSForcedOrderingSearch];
}];

Chris

gritsch · 30. Mai 2016, 08:12

Wenn es nicht auf performance ankommt dann kann man das so machen wie oben beschrieben, sonst würd ich mir eine eigene klasse erstellen welche jeweils die url hält und einen numerischen sortierungswert um die sortierung extrem zu beschleunigen.

little_pixel · 30. Mai 2016, 11:06

Huhu,

Danke Chris, aber da wird auch jedes Mal jede URL zum Text konvertiert.

Klar, das muss immer gemacht werden, aber ich dachte, dass irgend ein Vergleich von Apple gibt, der das besser und schneller kann.

Gabriel, ich blicke es nicht.
Kannst Du noch ein paar Stichworte nennen?
Wie würdest Du das numerisch abbilden?

Viele Grüße

gritsch · 30. Mai 2016, 11:15

ich muss zb einige hundert-tausend strings sortieren. das dauert zwar nichtmal eine sekunde, ist abere eben doch schon sichtbar und daher nicht gewünscht.
Also einfach ein einziges mal für jeden wert einen numerische abbildung erstellen: in meinem fall die ersten 8 ascii-zeichen in einen uint64 gepackt. sind die ersten 8 zeichen nicht alles ascii-zeichen (kommt extrem selten vor), so setze ich den wert auf 0. Großbuchstaben werden zu kleinbuchstaben. Natürlich hätten in 64 bit vile mehr solcher zecihen platz, der einfachheithalber hab ich aber eben nur 8 verwendet.
dann beim sortieren brauche ich nur noch die zwei zwahlen vergleichen außer sie sind identisch oder mindestens eine davon 0, dann wird auf die langsame string-compare-methode zurückgegriffen).
Bei mir gehts um strings und nicht um pfade. wenn die dateien bei dir nicht alle im gleichen ordner liegen, dann kannst du eventuell noch jeweils die inode-nummer und nummerische-compare-nummer für jede pfadkomponente.

little_pixel · 30. Mai 2016, 11:49

Danke für die Erklärung!

Viele Grüße

mattik · 31. Mai 2016, 01:29

Kommt ganz darauf an, wie Finder-Like du es haben willst. Und was dir wichtiger ist: Schnell oder schön.

Gritschs Idee, Objekte mit Namen und URL zu erzeugen und diese dann zu sortieren finde ich fein. Gritsch, nimm's mir nicht übel, aber die Sache mit dem uint64 finde ich für "Finder-Like" nicht so prickelnd - kann gut sein, dass das für deinen Fall passt, aber in diesem Fall würden für mich mehrere Sachen dagegen sprechen:

- Rein ASCII-basierte Ansätze will zumindest ich nicht mehr in meinen Programmen haben, schon gar nicht bei Strings, die der Nutzer zu sehen bekommt. Unicode ist langsam, aber dein Freund. Ich habe keine Ahnung, in welchen Ländern Leute ihre Namen mit lustigen kringeligen Buchstaben benennen. Und ich will es in diesem Fall auch gar nicht wissen, ich will nur, dass es funktioniert.
- Selbst die besten vergleichsbasierten Sortieralgorithmen haben ein Laufzeitverhalten O(n)=n*log(n), mit anderen Worten: Ab einer bestimmten Menge bringt die Beschleunigung des Vergleichs selbst nicht mehr viel, weil die Menge der Vergleiche schneller anwächst als die Anzahl der Elemente (klar: 10x schneller bleibt 10x schneller)
- Der Finder sortiert nicht einfach alphabetisch von links nach rechts, z.B. kommt "Bild2.jpg" vor "Bild10.jpg". Das Verhalten ist ziemlich trickreich, Locale-abhängig und kann sich jederzeit ändern. Das nachzubauen ist also nicht ganz einfach, mit - localizedStandardCompare (NSString) bekommt man es geschenkt.

Ich würde mir also ein Objekt bauen, das die URL und den lokalisierten Display-Namen der Datei hält (ggf. die versteckten Dateien rausfiltern) und das Ganze dann per localizedStandardCompare sortieren. Wenn die Anzahl der Dateien eine bestimmte Größe überschreitet würde ich mit einigen anfangen und dann inkrementell die restlichen Elemente einsortieren. Zugegebenermaßen nicht die schnellste Lösung, aber das ist manchmal nicht das einzige Kriterium.

Amin Negm-Awad · 31. Mai 2016, 04:14

Ich glaube auch nicht, dass der Vergleich auf ints anstelle chars den größten Performancevorteil bringt, da das ohnehin so implementiert sein dürfte. Mutmaßlich liegt der Gewinn in der Erzeugung "normalisierter" Hilfsobjekte gleich welchen Typs.

gritsch · 31. Mai 2016, 08:37

mattik schrieb:

Kommt ganz darauf an, wie Finder-Like du es haben willst. Und was dir wichtiger ist: Schnell oder schön.

Gritschs Idee, Objekte mit Namen und URL zu erzeugen und diese dann zu sortieren finde ich fein. Gritsch, nimm's mir nicht übel, aber die Sache mit dem uint64 finde ich für "Finder-Like" nicht so prickelnd - kann gut sein, dass das für deinen Fall passt, aber in diesem Fall würden für mich mehrere Sachen dagegen sprechen:

- Rein ASCII-basierte Ansätze will zumindest ich nicht mehr in meinen Programmen haben, schon gar nicht bei Strings, die der Nutzer zu sehen bekommt. Unicode ist langsam, aber dein Freund. Ich habe keine Ahnung, in welchen Ländern Leute ihre Namen mit lustigen kringeligen Buchstaben benennen. Und ich will es in diesem Fall auch gar nicht wissen, ich will nur, dass es funktioniert.
- Selbst die besten vergleichsbasierten Sortieralgorithmen haben ein Laufzeitverhalten O(n)=n*log(n), mit anderen Worten: Ab einer bestimmten Menge bringt die Beschleunigung des Vergleichs selbst nicht mehr viel, weil die Menge der Vergleiche schneller anwächst als die Anzahl der Elemente (klar: 10x schneller bleibt 10x schneller)
- Der Finder sortiert nicht einfach alphabetisch von links nach rechts, z.B. kommt "Bild2.jpg" vor "Bild10.jpg". Das Verhalten ist ziemlich trickreich, Locale-abhängig und kann sich jederzeit ändern. Das nachzubauen ist also nicht ganz einfach, mit - localizedStandardCompare (NSString) bekommt man es geschenkt.

Ich würde mir also ein Objekt bauen, das die URL und den lokalisierten Display-Namen der Datei hält (ggf. die versteckten Dateien rausfiltern) und das Ganze dann per localizedStandardCompare sortieren. Wenn die Anzahl der Dateien eine bestimmte Größe überschreitet würde ich mit einigen anfangen und dann inkrementell die restlichen Elemente einsortieren. Zugegebenermaßen nicht die schnellste Lösung, aber das ist manchmal nicht das einzige Kriterium.

ich verwende den numerischen wert nur wenn die ersten 8 zeichen a-z oder A-Z (werden zu a-z) sind. Das sind in meinem fall eben 99% der werte. Falls ein anderes zeichen enthalten ist, so setze ich den numerischen wert auf 0 und weiß somit nachher beim direkten vergleichen dass ich bei den werten eben die compare-methode von NSString verwenden muss.
Es ist bedeutend mehr als faktor 10 - und sollte vor allem in dem fall sehr viel mehr sein weil allein ja schon die umwandlung von NSURL in NSString wegfällt (und falls das gecached wird, ist es eben schnell ein speicherproblem).
Es kann vielleicht sein dass apple das inzwischen optimiert hat, in 10.10 wars jedenfalls noch schnarchlangsam. Da gings bei mir darum ob es 0,7 sekunden dauert oder eben 0,02 oder sowas in der art.

gritsch · 31. Mai 2016, 08:37

Amin Negm-Awad schrieb:

Ich glaube auch nicht, dass der Vergleich auf ints anstelle chars den größten Performancevorteil bringt, da das ohnehin so implementiert sein dürfte. Mutmaßlich liegt der Gewinn in der Erzeugung "normalisierter" Hilfsobjekte gleich welchen Typs.

hätte ich ja auch vermutet, ist aber nicht so!

macmoonshine · 31. Mai 2016, 08:59

Dein verfahren ist ja schon sehr speziell. Bei Ziffern oder überwiegend nicht-lateinischen Zahlen geht es gründlich in die Hose. In Asien würde ich das so nicht anbieten.

Liegen die Dateien alle in einem Ordner oder musst du komplette Pfade vergleichen? Im zweiten Fall hast du im besten Fall eine Variante von Bucketsort kombiniert mit einem vergleichsbasierten Sortierverfahren.

gritsch · 31. Mai 2016, 09:04

macmoonshine schrieb:

Dein verfahren ist ja schon sehr speziell. Bei Ziffern oder überwiegend nicht-lateinischen Zahlen geht es gründlich in die Hose. In Asien würde ich das so nicht anbieten.

Liegen die Dateien alle in einem Ordner oder musst du komplette Pfade vergleichen? Im zweiten Fall hast du im besten Fall eine Variante von Bucketsort kombiniert mit einem vergleichsbasierten Sortierverfahren.

es funktioniert auch mit nicht lateinischen buchstaben perfekt (eben so wie die apple-methode es macht) dann aber eben nicht mit optimierter geschwindigkeit.

bei mir ist es eine liste von dateinamen ohne pfaden, aber wie ich ja geschrieben habe würd ich bei pfaden auf die pfad-komponenten in jeweils ein solches sortierobjekt aufteilen.

das ganze würd ich natürlich auch nur machen wenns nötig ist und am ende auch was bringt!

macmoonshine · 31. Mai 2016, 09:20

gritsch schrieb:

es funktioniert auch mit nicht lateinischen buchstaben perfekt (eben so wie die apple-methode es macht) dann aber eben nicht mit optimierter geschwindigkeit.

Ich habe ja auch nicht gesagt, dass es mit nicht-lateinischen Zeichen nicht funktioniert, sondern dass deine aufwändige Optimierung da eben nichts bringt. Bei einem Ordner mit beispielsweise lauter chinesischen Dateinamen sitzt der Nutzer vor dem Rechner und hält Maulaffen feil.

gritsch schrieb:

das ganze würd ich natürlich auch nur machen wenns nötig ist und am ende auch was bringt!

Klar, aber eben nur in einem vielleicht häufigen aber sehr eingeschränkten Fall. Mit festen Präfixen und einem Dictionary bekommt man sicherlich eine geschicktere und allgemeinere Version von Bucketsort hin.

gritsch · 31. Mai 2016, 09:30

macmoonshine schrieb:

gritsch schrieb:

es funktioniert auch mit nicht lateinischen buchstaben perfekt (eben so wie die apple-methode es macht) dann aber eben nicht mit optimierter geschwindigkeit.

Ich habe ja auch nicht gesagt, dass es mit nicht-lateinischen Zeichen nicht funktioniert, sondern dass deine aufwändige Optimierung da eben nichts bringt. Bei einem Ordner mit beispielsweise lauter chinesischen Dateinamen sitzt der Nutzer vor dem Rechner und hält Maulaffen feil.

gritsch schrieb:

das ganze würd ich natürlich auch nur machen wenns nötig ist und am ende auch was bringt!

Klar, aber eben nur in einem vielleicht häufigen aber sehr eingeschränkten Fall. Mit festen Präfixen und einem Dictionary bekommt man sicherlich eine geschicktere und allgemeinere Version von Bucketsort hin.

in meinem konkreten fall gehts aber nicht um dateinamen sondern um beschreibungen die aus den files selbst ausgelesen wurden. die gibts nur auf englisch und ganz selten auch auf deutsch. Also auch in china oder japan siehst du die englischen werte (und das wollen sie auch so).
Und es wäre selbst dann nicht langsamer oder anders sortiert wenn es um non-latin zeichen ginge.

Hab grad schnell einen test geschrieben und unter 10.11 ist es nur noch faktor 5 und nicht mehr über 10 - jedoch merkt man einen unterschied ob etwas 1 sekunde dauert oder eben nur 0,2 sec (ich kann den code hier posten wenn gewünscht).

string duration: 1.095190
number duration: 0.203033

übringes, ...UsingComparator ist um EINIGES LANGSAMER als ...UsingSelector.
Klar es ist auch flexibler aber wenn man eh nur compare: aufruft reicht der selector. man braucht ja nicht den kompletten scope...

Amin Negm-Awad · 31. Mai 2016, 11:00

gritsch schrieb:

Amin Negm-Awad schrieb:

Ich glaube auch nicht, dass der Vergleich auf ints anstelle chars den größten Performancevorteil bringt, da das ohnehin so implementiert sein dürfte. Mutmaßlich liegt der Gewinn in der Erzeugung "normalisierter" Hilfsobjekte gleich welchen Typs.

hätte ich ja auch vermutet, ist aber nicht so!

Woher willst du wissen, welches der beiden Elemente den Performancegewinn bringt?

gritsch · 31. Mai 2016, 11:03

Amin Negm-Awad schrieb:

gritsch schrieb:

Amin Negm-Awad schrieb:

Ich glaube auch nicht, dass der Vergleich auf ints anstelle chars den größten Performancevorteil bringt, da das ohnehin so implementiert sein dürfte. Mutmaßlich liegt der Gewinn in der Erzeugung "normalisierter" Hilfsobjekte gleich welchen Typs.

hätte ich ja auch vermutet, ist aber nicht so!

Woher willst du wissen, welches der beiden Elemente den Performancegewinn bringt?

Ganz einfach: durch Messungen!

Amin Negm-Awad · 31. Mai 2016, 11:43

gritsch schrieb:

Amin Negm-Awad schrieb:

gritsch schrieb:

Amin Negm-Awad schrieb:

Ich glaube auch nicht, dass der Vergleich auf ints anstelle chars den größten Performancevorteil bringt, da das ohnehin so implementiert sein dürfte. Mutmaßlich liegt der Gewinn in der Erzeugung "normalisierter" Hilfsobjekte gleich welchen Typs.

hätte ich ja auch vermutet, ist aber nicht so!

Woher willst du wissen, welches der beiden Elemente den Performancegewinn bringt?

Ganz einfach: durch Messungen!

Wie hast du denn gemessen, welche Laufzeit ein System zwar mit Integer-Hash, aber ohne Normalisierung gegenüber -stringCompare: hat, ohne die Normalisierung von -stringCompare: et al. und damit eben -stringCompare: et al. zu verwenden?

gritsch · 31. Mai 2016, 11:44

Amin Negm-Awad schrieb:

gritsch schrieb:

Amin Negm-Awad schrieb:

gritsch schrieb:

Amin Negm-Awad schrieb:

Ich glaube auch nicht, dass der Vergleich auf ints anstelle chars den größten Performancevorteil bringt, da das ohnehin so implementiert sein dürfte. Mutmaßlich liegt der Gewinn in der Erzeugung "normalisierter" Hilfsobjekte gleich welchen Typs.

hätte ich ja auch vermutet, ist aber nicht so!

Woher willst du wissen, welches der beiden Elemente den Performancegewinn bringt?

Ganz einfach: durch Messungen!

Wie hast du denn gemessen, welche Laufzeit ein System zwar mit Integer-Hash, aber ohne Normalisierung gegenüber -stringCompare: hat, ohne die Normalisierung von -stringCompare: et al. und damit eben -stringCompare: et al. zu verwenden?

einfach nur werte verwendet die kein string-compare benötigen.

Amin Negm-Awad · 31. Mai 2016, 12:42

Das ist nicht dasselbe, weshalb ein Vergleich mit Birnen und Äpfeln ist.

mattik · 31. Mai 2016, 12:53

Performance ist schön, Korrektheit ist notwendig.

Mein Problem ist, dass man (zumindest mit localizedStandardCompare) nicht weiß, was der im Detail tut. Mit dem Verfahren "Zahlen mit Fallback" werden zwei Vergleichsmethoden vermischt. Selbst wenn beide einzeln genommen Ordnungsrelationen sind ist nicht garantiert, dass die Kombination den Anforderungen an eine Ordnungsrelation genügt. Wenn diese Bedingung nicht gegeben ist, ist das Ergebnis der meisten Sortieralgorithmen nicht definiert. Man kann sich da bestimmt Fälle schon mit drei Elementen ausdenken (zwei ohne Sonderzeichen, eins mit), bei denen das knallt (A < B, B < C, C < A), z.B. mit der oben genannten Sortierung der Zahlen im Namen.

Klar: Ist bestimmt konstruiert, kommt im echten Leben vielleicht nie oder nur selten vor. Aber genau solche Probleme will ich mir um jeden Preis vom Hals halten.

Edit: Ein Beispiel wäre Bild3.jpg, Bild22ü.jpg, Bild111.jpg.