numerisch/alpha gemischter Sortier-Algorithmus

[Beat]

Hallo

Ich möchte einen Sortieralgorithmus erstellen.

Ein zu sortierender Key ist ein String, bestehend aus numerischen und nicht numerischen Zeichen.

also aus \d und \D

Sortiertes Beispiel aufsteigend sortert
(undef)
1
2
11
a
aa
b
c1
c2
c11
d1
d1a
d1aa
d1ab
d1ab1
d1ab2
d1ab11
e1a1a1a1a1a1a1a1a1....a
e1a1a1a1a1a1a1a1a1....aa
f

Es wäre möglich einen String in mehrere Felder zu splitten. Ich weiss aber nicht, nach welcher Weise ich jedes Feld sortieren muss.

$a<=>$b führt bei \D zu einem Error.

Schwierigkeit: Ein String kann auch beliebig lange sein.

Die Frage wäre, nach welchem Prinzip liesse sich ein solcher gemischter Algorithmus erstellen.

gesucht ist ein sekundärer Sortierkey.

mfg Beat

[Pryos.org]

Ein zu sortierender Key ist ein String, bestehend aus numerischen und nicht numerischen Zeichen.

also aus \d und \D

also aus allen möglichen Zeichen

Es wäre möglich einen String in mehrere Felder zu splitten. Ich weiss aber nicht, nach welcher Weise ich jedes Feld sortieren muss.

garnicht, den du willst ja nicht INNERHALB des Strings sortieren, sondern das Array

$a<=>$b führt bei \D zu einem Error.

Ich muss zugeben, ich kenne diesen Operator nicht und ehrlich gesagt kann ich nicht mal raten welche sinnvolle Funktion diese Opterator-Kombination hat, da er Numerisch gesehen immer WAHR wäre.

Schwierigkeit: Ein String kann auch beliebig lange sein.

Was sich herausfinden lässt.

Die Frage wäre, nach welchem Prinzip liesse sich ein solcher gemischter Algorithmus erstellen.

Theoretisch kannst du sortieren wonach du willst, dank Callback Funktion

gesucht ist ein sekundärer Sortierkey.

Was willst du genau machen? Eine Sortierfunktion, welche zuerst Sonderzeichen, dann Zahlen und dann Buchstaben anzeigt?

[Beat]

Ein zu sortierender Key ist ein String, bestehend aus numerischen und nicht numerischen Zeichen.

also aus \d und \D
also aus allen möglichen Zeichen

Wobei bei meinem beispiel folgende Definition unterblieb:

0 < 1
aber ist undef < 0 ?
derzeit noch nicht entschieden.

Es wäre möglich einen String in mehrere Felder zu splitten. Ich weiss aber nicht, nach welcher Weise ich jedes Feld sortieren muss.
garnicht, den du willst ja nicht INNERHALB des Strings sortieren, sondern das Array

ja schon klar. Sortiert wird immer ein Array von irgend etwas.

$a<=>$b führt bei \D zu einem Error.
Ich muss zugeben, ich kenne diesen Operator nicht und ehrlich gesagt kann ich nicht mal raten welche sinnvolle Funktion diese Opterator-Kombination hat, da er Numerisch gesehen immer WAHR wäre.

Perl numerisch
sort{ $a <=> $b } @array

Perl alphabetisch
sort{ $a cmp $b } @array

gleichwertig mit
sort @array

Die Frage wäre, nach welchem Prinzip liesse sich ein solcher gemischter Algorithmus erstellen.
Theoretisch kannst du sortieren wonach du willst, dank Callback Funktion

ja schon klar dass ich auch
sort my_algorythm() @array
verwenden kann

gesucht ist ein sekundärer Sortierkey.
Was willst du genau machen? Eine Sortierfunktion, welche zuerst Sonderzeichen, dann Zahlen und dann Buchstaben anzeigt?

Ich suche die Eierlegende Wollmilchsau.
Ein String besteht aus Ketten von \d*\D* oder ist undef.
Es soll das skizzierte sortierte Beispiel herauskommen.

Mein Denkansatz geht in eine Art Heap-Prozedur.
Ich knabbere jeweils die vordersten \d+ bzw \D+ Zeichen der Keys an und ordne dann diese einem hash zu.

Ich zeuge dadurch einen hash von hashes und muss nun nur noch den hash rekursiv ausgeben, hier dürfte sort mit callback funktionieren.

mfg Beat

[Gunther]

Hi Beat!

Das ganze soll in Perl geschrieben werden?

Perl numerisch
sort{ $a <=> $b } @array

Perl alphabetisch
sort{ $a cmp $b } @array

gleichwertig mit
sort @array

Ich suche die Eierlegende Wollmilchsau.
Ein String besteht aus Ketten von \d*\D* oder ist undef.
Es soll das skizzierte sortierte Beispiel herauskommen.

Mein Denkansatz geht in

die Richtung, dass ich das Gesamt-Array in Teil-Arrays splitten würde und zwar jeweils in solche mit Strings gleicher Länge. Diese dann per einer 08/15 Standard-Sortierfunktion sortieren lassen und zum Schluss wieder zu einem einzigen Array zusammenfügen.

Gruß Gunther

[Beat]

Das ganze soll in Perl geschrieben werden?

Ja. Aber es spielen designfragen eine Rolle. Reduziere die Vergleiche auf das Minimum.

Mein Denkansatz geht in
die Richtung, dass ich das Gesamt-Array in Teil-Arrays splitten würde und zwar jeweils in solche mit Strings gleicher Länge.

definiere "gleiche Länge"
offensichtlich gibt es keine definierte Länge für die subchunks.

Diese dann per einer 08/15 Standard-Sortierfunktion sortieren lassen und zum Schluss wieder zu einem einzigen Array zusammenfügen.

mal naiv. Länge der Subchunks = 1

sortiere 72b und 7a3
Nach meiner Vorstellung ist
7.a.3 < 72.b.
Nach deiner Vorstellung aber
7.a.3 > 72.b.

Ich streiche aus deinem Tipp 'gleiche Länge'. Heraus kommen Felder für die gelten muss:

undef < 0 < 1 < 2 < 11 < a < ab < b

simple sort reicht auf keinen Fall.
Aber die Sortiersub ist hier kein Problem. Die bekomme ich schon hin.

Die Frage ist bloss, ist es sinnvoll, unnötige (weil undef) Felder für alle Elemente des Arrays zu erzeugen?
Das will ich vermeiden. Darum denke ich an die Erzeugung eines hashes von hashes.

Die Elemente
'', 0,0,0, 1, '1ac', 'a', 'a1', 'a11'
sollten zuerst in diese Datenstruktur umgebaut werden:

%elem = (
  undef => [1,],
  0 => [3,],        # 3 Elemente 0
  1 => [1,
         {ac=>[1,]},
       ],
  a => [1,
         {
          1=>[1,],
          11=>[1,],
         },
       ],
);

Diesen hash kann ich dann rekursiv sortiert ausgeben, bzw einen sortieren Array zusammenbauen.

mfg Beat

[Gunther]

Hi!

Das ganze soll in Perl geschrieben werden?

Ja. Aber es spielen designfragen eine Rolle. Reduziere die Vergleiche auf das Minimum.

Ich hatte nur nachgefragt, weil ich von Perl keine Ahnung habe. Aber (auch wenn ich jetzt gleich von Perl'ern gesteinigt werde) was in PHP geht, lässt sich imho ja auch in Perl realisieren, und das meist sogar sehr ähnlich.

Mein Denkansatz geht in
die Richtung, dass ich das Gesamt-Array in Teil-Arrays splitten würde und zwar jeweils in solche mit Strings gleicher Länge.

definiere "gleiche Länge"
offensichtlich gibt es keine definierte Länge für die subchunks.

Mit gleicher Länge meinte ich strlen($a) == strlen($b), also die Anzahl der Zeichen im jeweiligen String. Aber ich habe gestern Abend dein Beispiel wohl fehlinterpretiert.

Aber heute, nach nochmaligem Studium, erscheint es mir "unlogisch", bzw. "fehlerhaft/ inkosistent".

Du schreibst:
...
a
aa
b
...
d1ab1
d1ab2
d1ab11
...
Das sah für mich auf den ersten Blick so aus (aufgrund des zweiten Parts, den ich zitiert habe), als wenn gelten würde, dass wenn strlen($a) > strlen($b) dann für die Sortierung gilt $b < $a.

Diese dann per einer 08/15 Standard-Sortierfunktion sortieren lassen und zum Schluss wieder zu einem einzigen Array zusammenfügen.

mal naiv. Länge der Subchunks = 1

sortiere 72b und 7a3
Nach meiner Vorstellung ist
7.a.3 < 72.b.
Nach deiner Vorstellung aber
7.a.3 > 72.b.

Hier verstehe ich deine beabsichtigte Sortierreihenfolge schon nicht mehr.

• Sind Zahlen generell "kleiner" als Buchstaben?
• Wird jede Ziffer einzeln betrachtet, oder ist a8b < a72b, weil 8 < 72? Und welche Basis (10)?

simple sort reicht auf keinen Fall.
Aber die Sortiersub ist hier kein Problem. Die bekomme ich schon hin.

Die Frage ist bloss, ist es sinnvoll, unnötige (weil undef) Felder für alle Elemente des Arrays zu erzeugen?

Ab hier kann ich dir nicht mehr ganz folgen, aber imho kann es grundsätzlich keinen Sinn machen, irgendwelche "undef" Felder in irgendeine Form von Sortierung einzubeziehen.

Das will ich vermeiden. Darum denke ich an die Erzeugung eines hashes von hashes.

Die Elemente
'', 0,0,0, 1, '1ac', 'a', 'a1', 'a11'
sollten zuerst in diese Datenstruktur umgebaut werden:

%elem = (
  undef => [1,],
  0 => [3,],        # 3 Elemente 0
  1 => [1,
         {ac=>[1,]},
       ],
  a => [1,
         {
          1=>[1,],
          11=>[1,],
         },
       ],
);

Diesen hash kann ich dann rekursiv sortiert ausgeben, bzw einen sortieren Array zusammenbauen.

Ab hier kann ich dann gar nicht mehr folgen.
Meiner (sehr bescheidenen) Erfahrung nach, liegt das "Problem" aber auch eher auf der Seite der "Datenstruktur", wenn man mit den "normalen" Sortierfunktionen nicht auskommt. Da du aber nicht verraten hast, wo und wie diese zu sortierenden Daten herkommen, kann man dazu nichts sagen.
Sorry, dass ich keinen brauchbaren Tipp für dich habe, aber ich werde den Thread aufmerksam verfolgen, um deine Lösung, die du bestimmt finden wirst, zu studieren. Vielleicht verstehe ich dann im Nachhinein auch deine jetzigen Überlegungen. ;-)

Viel Erfolg!

Gruß Gunther

[Pryos.org]

Du schreibst:
...
a
aa
b
...
d1ab1
d1ab2
d1ab11
...
Das sah für mich auf den ersten Blick so aus (aufgrund des zweiten Parts, den ich zitiert habe), als wenn gelten würde, dass wenn strlen($a) > strlen($b) dann für die Sortierung gilt $b < $a.

Ich grübel da auch schon etwas dran, aber ich glaube das er Numerische Zeichen als echte Zahl sortiert und den Rest als einzelnes Zeichen.

Deshalb auch den String teilen, ich habs vorhin auhc nicht ganz verstanden, aber letztendlich sieht es so aus

a
a-a
b
...
b-1-a-b-1
b-1-a-b-2
b-1-a-b-11

@TE

letztendlich bleibt dir pro "Vergleich" nichts anderes als
Schritt für Schritt... ich denke mal das selbst natural sort "b-1-a-b-2" > "b-1-a-b-11" setzt

[hotti]

hi,

Schwierigkeit: Ein String kann auch beliebig lange sein.

In der Tat, das ist Mist. Gibts da wirklich keine Begrenzung?

Die Frage wäre, nach welchem Prinzip liesse sich ein solcher gemischter Algorithmus erstellen.

Wenn irgendwo eine Grenze wäre, sagen wir mal bei 3. Dann hätten wir also 3 Zeichen, das sind 3 Byte. 1 Byte hat den Wertebereich von 0..255 (8 bit). Algebraisch ergibt sich dann ein numerischer Wert (nach dem sortiert werden kann) wie folgt für einen ZeichenString xyz:

x * 256^2 + y * 256^1 + z * 256^0

Wobei wir nun die Basis 256 nach unten korrigieren können, weil wir bei alphanumerischen Zeichen 0..9. a..z, A..Z nur noch eine Bais von 62 haben. Entsprechend länger kann der zu sortierende String dann sein, hat aber Grenzen in der Rechnerarchitektur (32||64 bit).

Hotte

[JürgenB]

Hallo Beat,

nur eine Idee:

in einer eigenen Vergleichsfunktion prüfen, ob Zahl (11) oder String (aa,a1,1a,...)

wenn beide Zahl, dann Zahlvergleich
wenn beide String, dann Stringvergleich
sonst Zahl kleiner String

Gruß, Jürgen

[Bademeister]

Hi Beat.

Liefert das folgende im wesentlichen das, was Du willst?

Du zerlegst die Strings in (maximale) Tokens, die jeweils nur aus numerischen[1] oder nur aus nicht-numerischen Zeichen bestehen. (Sagen wir Typ num bzw. string).

Du vergleichst zwei Tokens wie folgt:

• beide Typ num: numerischer Vergleich (klar)
• beide Typ string: string-Vergleich (Achtung: [2])
• Typ num < Typ string

und zwei Strings anhand des ersten Paares von ungleichen Tokens. Gibts die nicht, ist der String mit weniger Tokens kleiner. (Haben sie gleich viele Tokens, die jeweils gleich sind, dann sind - klar - auch die Strings gleich.)

[1] Was ist mit Minuszeichen? Ist "-3" < "-2"? Ich würde denken, ja, das wäre natürlich, d.h. ein numerisches Token kann (u.U.) ein Minuszeichen haben. Was ist mit "a-3" und "a-2"? Und: Was ist mit Pluszeichen? Ist "+3" == "3"?

Viele Grüße,
der Bademeister

[Beat]

Du zerlegst die Strings in (maximale) Tokens, die jeweils nur aus numerischen[1] oder nur aus nicht-numerischen Zeichen bestehen. (Sagen wir Typ num bzw. string).

Du vergleichst zwei Tokens wie folgt:

• beide Typ num: numerischer Vergleich (klar)
• beide Typ string: string-Vergleich (Achtung: [2])
• Typ num < Typ string

ja natürlich. Mit der ergänzung, dass der Fall gelöst ist, wenn für einen der beiden Strings kein Token vorliegt.

und zwei Strings anhand des ersten Paares von ungleichen Tokens.

Der Sonderfall ist notwendig, denn jeder Sring besteht aus mindestens einem ersten Token.

Gibts die nicht, ist der String mit weniger Tokens kleiner. (Haben sie gleich viele Tokens, die jeweils gleich sind, dann sind - klar - auch die Strings gleich.)

[1] Was ist mit Minuszeichen? Ist "-3" < "-2"? Ich würde denken, ja, das wäre natürlich, d.h. ein numerisches Token kann (u.U.) ein Minuszeichen haben. Was ist mit "a-3" und "a-2"? Und: Was ist mit Pluszeichen? Ist "+3" == "3"?

Das ist noch eine Frage, ob \d* und \D* Tokens ausschliesslich gebildet werden.
Ich glaube numerische gegen nicht numerische Tokens wäre eine andere Version eines sortieralgorithmus. Sozusagen die goldene Eier legende Wollmilchsau. Ich versuche mich zuerst an den normalen Eiern.

PS: Migräne, mein Kopf wie während der Defragmentierung. Werde das Thema heute wieder aufgreifen.

mfg Beat

[dedlfix]

Hi!

Die Frage wäre, nach welchem Prinzip liesse sich ein solcher gemischter Algorithmus erstellen.

Wenn ich dich richtig verstanden habe, willst du die Zahlenanteile als solche und nicht deren Ziffern einzeln vergleichen. Ein Verfahren dazu heißt "natürliche Sortierung" (natural sorting).

Lo!

[Beat]

Die Frage wäre, nach welchem Prinzip liesse sich ein solcher gemischter Algorithmus erstellen.
Wenn ich dich richtig verstanden habe, willst du die Zahlenanteile als solche und nicht deren Ziffern einzeln vergleichen. Ein Verfahren dazu heißt "natürliche Sortierung" (natural sorting).

Danke für das richtige Stichwort.
Das hat mir jetzt schon mal weiter geholfen.

mfg Beat

[Beat]

Hallo

Meine Frage hat sich durch das richtige Stichwort "natural sort" erledigt.

Für Perl gibt es ein Modul Sort::Naturally.
Ich muss nun aber noch testen, ob es meinen Erwartungen entspricht.

mfg Beat

[Beat]

Für Perl gibt es ein Modul Sort::Naturally.
Ich muss nun aber noch testen, ob es meinen Erwartungen entspricht.

Ein Test:

#!perl  
use warnings;  
use strict;  
use constant { NL => "\n" };  
  
BEGIN {  
	use CGI::Carp qw(carpout);  
	open(LOG, ">error.txt")  or  die "Unable to append to error.txt: $!\n";  
	carpout(*LOG);  
}  
  
use Sort::Naturally qw(nsort);  
  
my @unsorted = ( qw( 1.1 11.1 1,1 1#1 11 1\)1 11-1 11- 1a 1z 1-1 1+1 1-z ) , '1 1');  
my @sorted = nsort @unsorted;  
print join NL, @sorted;  
  
<>;  
exit;  

gibt aus:
1a
1z
1-z
1 1
1#1
1)1
1,1
1.1
1+1
11        <----- warum
1-1       <----- warum
11-
11.1
11-1

Es ist merkwürdig, dass "1-1" oder "11" anders sortiert wird
Das Element 11 ist die einzige "Zahl".

mfg Beat

[hotti]

Hallo

Meine Frage hat sich durch das richtige Stichwort "natural sort" erledigt.

wie, hast Du das jetzt erst entdeckt? Tse ;-)

Hotti

[Beat]

Meine Frage hat sich durch das richtige Stichwort "natural sort" erledigt.

wie, hast Du das jetzt erst entdeckt? Tse ;-)

Sei getrost. Irgendwann entdecke ich alle deine Geheimnisse.

Ja natürklich ist das nicht, was Sort::Naturally sortiert. Um es genauer zu sagen, es ist höchst buggy, sobald ein "-" involviert ist.

Deshalb mein eigener Ansatz, hier noch ziemlich straight forward.

  
my @unsorted = ( 1.1, 'a', '1/1', 11.1, '1,1', 10, 0, '1#1', 11, '1)1', 12, '12-', '11-1', '11-', '1a', '1z', '1-1', '1+1', '1-z', '1 1');  
  
# Schwartian Transform  
my @sorted = map { $_->[0] }  
		sort { $a->[1] cmp $b->[1] }  
		map { [$_, makekey($_) ] } @unsorted;  
sub makekey{  
	my $ret;  
	foreach( my @a = ( $_[0] =~ /(\d+|\D+)/g ) ){ # <-- sollte \d{1,5 sein}  
		/^\d/ and $ret .= sprintf("%05d", $_ );  
		/^\D/ and $ret .= $_ ;  
	}  
	return $ret;  
}  
  
print join NL, @sorted;  

Ich nutze den Umstand aus, dass Integer die rechts mit 000 gepadded sind, sich in cmp richtig verhalten.

Jetzt kommen Tests und dann Performance Optimierungen.

mfg Beat

[Beat]

So das sieht langsam gut aus.

Jetzt stellt sich die Frage, wie \p{L} für > 127 sortiert werden sollen.

#!perl  
use warnings;  
use strict;  
use constant { NL => "\n" };  
  
BEGIN {  
	use CGI::Carp qw(carpout);  
	open(LOG, ">error.txt")  or  die "Unable to append to error.txt: $!\n";  
	carpout(*LOG);  
}  
  
use utf8;  
  
my @unsorted = ( 1.1, 111116, 111107, 'a', '*', '$', '}', '(', 'a27', 'a+', 'a090909', 'a11-11', '1/1', 11.1, '1,1', 10, 0, '1#1', 11, '1)1', 12, '12-', '11-1', '11-', '1a', '1z', '1-1', '1+1', '1-z', '1 1');  
push @unsorted, qw( 23n4n2 232kl1d hallo ä ö ü é zz d\)3 d\)3A 5'5 6'8'8 123.12.22 );  
  
print join NL, SELF::sort(@unsorted);  
<>;  
exit;  
  
#_____________________________________________  
package SELF;  
sub sort{  
	return( map { $_->[0] }  
		sort { $a->[1] cmp $b->[1] }  
		map { [$_, makekey($_) ] } @_  
	);  
}  
  
sub makekey{  
	my $ret = '';  
	foreach( my @a = ( $_[0] =~ /(\d{1,10}|\w+|\W)/g ) ){  
		/^\d/ and $ret .= sprintf("%010d", $_ ) and next;  
		/^\W/ and $ret .= "\x{FFFD}\x{FFFD}" . $_ and next;  
		/^\D/ and $ret .= "\x{FFFD}" . $_ ;  
	}  
	return $ret;  
}  

mfg Beat

[Vinzenz Mai]

Hallo Beat,

Ja natürklich ist das nicht, was Sort::Naturally sortiert. Um es genauer zu sagen, es ist höchst buggy, sobald ein "-" involviert ist.

vielleicht ist ja Sort::Key::Natural einen Test wert?

Freundliche Grüße

Vinzenz

[Beat]

Ja natürklich ist das nicht, was Sort::Naturally sortiert. Um es genauer zu sagen, es ist höchst buggy, sobald ein "-" involviert ist.

vielleicht ist ja Sort::Key::Natural einen Test wert?

Im Prinzip ja.

Ich bin aber auf die Idee gekommen, dass ich meiner sort Funktion nun auch Attribute übergeben könnte.
SELF::sort({attr1=>0, attr2=>1, attr3=>2 }, @unsorted )

wobei attr1 ein spezieller Typ sein könnte
und der Wert bezeichnet, wie gefilterte Resultate sortiert werden
  0 aus dem Ergebnis löschen
  > 0 Rangstufe in der Sortierung aufsteigend.
Attribute könnten sein:
date logische Datumssortierung
time logische Zeitsortierung
ipv4 logische ipv4 Sortierung
ipv6 logische ipv4 Sortierung
coord logische Geo-Koordinaten Sortierung
filter Spezialattribut,
       wenn true, filtert Elemente,
       welche nicht auf ein anderes Attribut matchen

mfg Beat