sort, ne und merkwürdiges Verhalten (Allgemeines zu Perl)

[thread]19361[/thread]

sort, ne und merkwürdiges Verhalten

Tags: perl5 Ähnliche Threads

Leser: 12

Articles: hide open all | hide show old branches

+6 replies
Gast Wastl

2014-11-04 21:18
Moin zusammen,

teste gerade ein wenig sort. Bei Versuch ein uniq nachzubilden, erhielt ich folgendes seltsames Ergebnis:
Code: (dl )

1 2 3

my @list = split //, "qwertz"; print @list; print sort {$a ne $b} @list;
Ergebnis:

qwertz
ztrewq

also quasi ein reverse. Das funktioniert auch relativ zuverlässig, vorausgesetzt, man verwendet kein Wort mit gleichen, nebeneinander liegenden Buchstaben. Ersetzt man bspw. qwertz durch Rindfleischetikettierungsueberwachungsaufgabenuebertragungsgesetz erhält man folgendes Ergebnis:

Rindfleischetikettierungsueberwachungsaufgabenuebertragungsgesetz
zttteesegsgnugartrebeunebagfuasgnuhcawrebeusgnureikitehcsielfdniR

Hat dafür jemand eine Erklärung?
Last edited: 2014-11-04 21:36:03 +0100 (CET)
- +5 replies
- Linuxer
  
  2014-11-04 22:18
  User since
  2006-01-27
  3891 Artikel
  HausmeisterIn
  Ohne mich je mit einem Sort-Algorithmus in der Tiefe auseinander gesetzt zu haben, behaupte ich:
  
  Dein merkwürdiges Verhalten beruht darauf, dass Du den Vergleich auf Ungleichheit machst:
  
  perldoc perlop
  ...
  Binary "<=>" returns -1, 0, or 1 depending on whether the left argument is numerically less than, equal to, or greater than the right argument. If your platform supports NaNs (not-a-numbers) as numeric values, using them with "<=>" returns undef. NaN is not "<", "==", ">", "<=" or ">=" anything (even NaN), so those 5 return false. NaN != NaN returns true, as does NaN != anything else. If your platform doesn't support NaNs then NaN is just a string with numeric value 0
  
  ...
  
  Binary "ne" returns true if the left argument is stringwise not equal to the right argument.
  
  Binary "cmp" returns -1, 0, or 1 depending on whether the left argument is stringwise less than, equal to, or greater than the right argument.
  
  Mit ne fehlt schon mal der "-1" Zweig. Wenn die verglichenen Buchstaben gleich sind, ergibt ne FALSE, also 0. Wenn sie ungleich sind, TRUE, bzw. 1. Dementsprechend verarbeitet sort das dann.
  
  Betrachten wir das Wort 'eva';
  
  'e' wird mit 'v' verglichen; Ungleich == 1 => e wird als größer betrachtet und "nach hinten geschoben";
  'v' wird mit 'a' verglichen; Ungleich == 1 => v wird als größer betrachtet und "nach hinten geschoben";
  'a' bleibt übrig und bleibt stehen; so wird aus 'eva' 'ave';
  
  Das gleiche kannst Du beobachten, wenn Du eine Liste von Zahlen mit Ungleichheit sortierst:
  
  Code (perl): (dl )
  
  1 2 3
  
  @list = 1 .. 4; print sort { $a != $b } @list; # == 4321
  
  meine Beiträge: I.d.R. alle Angaben ohne Gewähr und auf Linux abgestimmt!
  Die Sprache heisst Perl, nicht PERL. - Bitte Crossposts als solche kenntlich machen!
  - +4 replies
  - Muffi
    
    2014-11-05 06:34
    
    User since
    2012-07-18
    1465 Artikel
    BenutzerIn
    
    Ich würd sagen es kommt stark auf den Algorithmus an, den Perl intern zum Sortieren benutzt.
    Also im Endeffekt kommt (schlechter) Zufall raus
    1 + 1 = 10
    - +3 replies
    - Gast Wastl
      
      2014-11-05 13:25
      
      @Linuxer
      Stimmt, die fehlende -1 könnte auf jeden Fall ein Grund für das seltsame Verhalten sein.
      
      @Muffi
      Na ja, so ganz schlechter Zufall kann das nicht sein. Sortiert man auf diese Weise bassist, ferrari oder 1255354 erhält man folgendes Ergebnis:
      
      Code: (dl )
      
      perl -le 'print sort {$a ne $b} split //, "<WORT>"'
      
      tssabsi
      irrefra
      4552153
      
      also immer die gleiche Reihenfolge relativ zum Begriff.
      Habe das Ganze noch ein bisschen aufgedröselt:
      
      Code: (dl )
      
      1 2
      
      my @list = qw(b1 a2 s3 s4 i5 s6 t7); my @tsil = sort {substr($a, 0, 1) ne substr($b, 0, 1)} @list;
      
      Das Resultat: t7 s3 s4 a2 b1 s6 i5
      
      Gleiches gilt auch für ferrari oder 1255354. Mit anderen Worten, eine beliebige 7-stellige Zeichenkette mit demselben Buchstaben an der 3., 4. und 6. Stelle, die restlichen Buchstaben unterschiedlich, führt zur selben Sortierung, nämlich:
      
      7., 3., 4., 2., 1., 6. und 5. Buchstabe
      
      @Community
      Sorry, bin krankgeschrieben und hocke zu Hause rum, da kommt man halt auf solche Ideen ;)
      Last edited: 2014-11-05 14:00:45 +0100 (CET)
      - Linuxer
        
        2014-11-05 14:18
        
        User since
        2006-01-27
        3891 Artikel
        HausmeisterIn
        
        Wenn Dich das tiefergehend interessiert, kannst Du ja mit den vorliegenden Informationen mal losziehen und Dir die zugrunde liegenden Sortier-Algorithmen anschauen:
        
        perldoc -f sort
        ...
        Perl 5.6 and earlier used a quicksort algorithm to implement sort. That algorithm was not stable, so could go quadratic. (A stable sort preserves the input order of elements that compare equal. Although quicksort's run time is O(NlogN) when averaged over all arrays of length N, the time can be O(N**2), quadratic behavior, for some inputs.) In 5.7, the quicksort implementation was replaced with a stable mergesort algorithm whose worst-case behavior is O(NlogN). But benchmarks indicated that for some inputs, on some platforms, the original quicksort was faster. 5.8 has a sort pragma for limited control of the sort. Its rather blunt control of the underlying algorithm may not persist into future Perls, but the ability to characterize the input or output in implementation independent ways quite probably will. See the sort pragma.
        ...
        
        Quelle: perlfunc sort
        
        Also wären es wohl quicksort und mergesort, die Du Dir näher anschauen könntest.
        meine Beiträge: I.d.R. alle Angaben ohne Gewähr und auf Linux abgestimmt!
        Die Sprache heisst Perl, nicht PERL. - Bitte Crossposts als solche kenntlich machen!
      - Raubtier
        
        2014-11-05 14:21
        
        User since
        2012-05-04
        1083 Artikel
        BenutzerIn
        
        Guest Wastl
        @Linuxer
        Stimmt, die fehlende -1 könnte auf jeden Fall ein Grund für das seltsame Verhalten sein.
        
        Nicht "könnte sein", sondern "ist"!
        Wenn du unter perldoc -f sort nachliest, wirst du feststellen, dass die Sortierfunktion bestimmte Eigenschaften erfüllen MUSS, die deine "ne"-Funktion nicht erfüllt. Somit hast du keine Garantie für irgendein Ergebnis.
        
        Quote
        @Muffi
        Na ja, so ganz schlechter Zufall kann das nicht sein. Sortiert man auf diese Weise bassist, ferrari oder 1255354 erhält man folgendes Ergebnis:
        
        Code: (dl )
        
        perl -le 'print sort {$a ne $b} split //, "<WORT>"'
        
        "Zufall" ist vielleicht das falsche Wort. Das Ergebnis hängt vielmehr von der Implementierung der sort-Funktion ab. Die hat sich auch bei Perl mal irgendwann geändert, d.h. verschiedene Perl-Versionen können dir auch unterschiedliche Ergebnisse liefern.
        
        Hängt also u.a. von dem hier ab: http://perldoc.perl.org/sort.html

View all threads created 2014-11-04 21:18.