LesezeichenAbonnierenRSS-Feed abonnieren
AndreasMenrath
Pyrite | Level 9

Hallo zusammen,

 

ich habe mal wieder eine kleine Übungsaufgabe für professionelle SAS Entwickler und solche die es werden wollen. Gefunden habe ich die Aufgabe mal wieder als aktuelles Rätsel bei Spiegel Online unter:

http://www.spiegel.de/wissenschaft/mensch/raetsel-der-woche-verflixte-quersumme-a-1061371.html

 

Es wird ein Zahlenpaar gesucht,das die folgenden Bedingungen erfüllt:

  • Die Quersumme beider Zahlen ist durch 10 teilbar
  • Die Differenz beider Zahlen soll lediglich 1 betragen

Da es mehrere Zahlenpaare gibt, die diese Bedingungen erfüllen, wird im Rätsel explizit nach der kleinsten Zahl und ihrem Nachfolger gefragt.

Die Lösung lässt sich zwar auch theoretisch herleiten (siehe Lösung), aber als Entwickler lasse ich natürlich lieber SAS für mich denken. Das die Aufgabe vollständig durch einen Algorithmus beschrieben und gelöst werden kann, wähle ich also den Brute Force Ansatz.

 

Ich lade alle CoDe SAS Mitglieder ein hier ihre Lösung zu präsentieren. Ich selbst werde wieder verstärkt Wert auf eine möglichst einfache und leicht nachvollziehbare Lösung legen und nächste Woche meine Lösung vorstellen.

 

Bis dahin wünsche ich allen viel Spass beim tüfteln.

 

PS: in der Vorbereitung auf diese Aufgabe habe ich schon mal ein paar Performancetests durchgeführt und festgestellt, dass die Laufzeit für eine vollständige Suche im Zahlenraum zwischen 1 und 2*10^10 mehrere Stunden dauert. Ich schlage daher vor den Suchraum für den Algorithmus durch zwei Makrovariablen start_number und end_number zu definieren, damit man leichter entwickeln und testen kann.

 

Viele Grüße,

Andreas Menrath

19 ANTWORTEN 19
mfab
Quartz | Level 8

Hallo zusammen,

 

bei der Bearbeitung bin ich auf ein Thema mit der LAG-Funktion gestoßen, das ich mir nicht erklären kann, vielleicht weiß hier jemand mehr.

Mein Code (zugegeben, eher auf rasch programmiert) sieht wie folgt aus. Nein, es erfolgt keine Prüfung, ob die Start-Variable kleiner als die End-Variable ist 😉

 

 

DATA _null_;
  length findme $20.;
  start_number = 18999999900;
  end_number = 99999999999;

  DO n = start_number TO end_number;
    findme = INPUT(n,$20.);
    quersumme = 0;
    
         DO i = 1 TO length(findme);
           quersumme = quersumme + (substr(findme,i,1)); /* scheint ohne explizite Typkonvertierung mit "INT()" um den substr minimal performanter zu laufen */
         END;

         /* Test: Quersumme durch 10 teilbar? */
         IF MOD(quersumme,10) EQ 0 THEN DO;
         /*  put "zahl gefunden: " n " mit quersumme " quersumme; */
		   findlag = lag(findme); put findlag=;

/* Quersumme der vorherigen Zahl auch durch 10 teilbar? */ IF (PUT(lag(findme),20.) + 1) EQ PUT(findme,20.) THEN DO; lagnumber = lag(findme); lagnumber2 = PUT(lag(findme),20.); PUT "Ergebnis: " lagnumber " | " lagnumber2 " | " findlag " und " findme; /* hier hätte ich erwartet, dass sowohl lagnumber und lagnumber2 angezeigt werden sollten */ STOP;
END; END; END; RUN;

 

Folgende Frage stellt sich mir:

 

Wieso funktioniert das lag innerhalb der Prüfung des zweiten IF-Statements einwandfrei, aber nicht im nachfolgenden Code? Man sieht, dass ich hier ein bisschen probiert habe. Auch ein lag(n) funktioniert dort leider nicht.

 

Zur performanten Ausführung des Programms würde ich natürlich die Ausgaben im Log aus dem Code nehmen. Mir geht es hier lediglich um die Funktionsweise des lag. (natürlich könnte ich mir die vorherige Zahl mit durch 10 teilbarer Quersumme auch für die Ausgabe merken, es sollte meiner Ansicht nach jedoch auch mit dem Lag funktionieren)

 

Herzlichen Dank für Hinweise dazu,

Michael

 

p.s.: der Editor hier stellt meinen Code leider nicht mit den gewünschten Einrückungen dar - pardon dafür.

p.s.2: habe mir eine Frage schon selbst beantworten können 😉

AndreasMenrath
Pyrite | Level 9
Hallo Michael,
ich selbst benutze LAG nur höchst ungern, da es in Verbindung mit konditionalen Abfragen zu unerwarteten Effekten führt.
Vielleicht hilft dir dieses Whitepaper unter http://support.sas.com/resources/papers/proceedings09/055-2009.pdf weiter.

Grüße,
Andreas
mfab
Quartz | Level 8

Hallo Andreas,

 

toller Hinweis, vielen Dank.

 

Dann macht das lag ja genau das, was es in diesem Fall soll und sollte hier auch performanter arbeiten, als wenn jede verarbeitete Nummer zwischengespeichert wird. Smiley (überglücklich)

 

So sieht der Code doch gar nicht so schlecht aus (lasse mich gerne von anderen Lösungen überraschen)

DATA _null_;
  length findme $20.;
  start_number = 18999999900;
  end_number = 99999999999;

  DO n = start_number TO end_number;
    findme = INPUT(n,$20.);
	quersumme = 0;
    
         DO i = 1 TO length(findme);
           quersumme = quersumme + (substr(findme,i,1)); /* scheint ohne explizite Typkonvertierung mit "INT()" um den substr minimal performanter zu laufen */
         END;

		 /* Test: durch 10 teilbar? */
         IF MOD(quersumme,10) EQ 0 THEN DO;
		     findlag = lag(findme);

		   /* Quersumme der vorherigen Zahl auch durch 10 teilbar? */
		   IF (PUT(findlag,20.) + 1) EQ PUT(findme,20.) THEN DO;
               PUT "Ergebnis: " findlag " und " findme;
               STOP;
           END;
		 END;
  END;
RUN;

Beste Grüße

Michael

jakarman
Barite | Level 11

Andreas das stimmt met unerwartete resultate. Die richtigen name für die LAG function (Oracle is using it with SQL) sollte abe queue sein https://en.wikipedia.org/wiki/Queue_(abstract_data_type) .   Wenn es eine falschen name hat ist die falschen benutzen zu erwarten. 

---->-- ja karman --<-----
Andreas
Fluorite | Level 6
data _null_;
   do i=18990000000 to 20000000000;
      testvalue=i;
      link cross_sum;
      if mod(cs,10) ne 0 then continue; 
      testvalue=i+1;
      link cross_sum;
      if mod(cs,10) = 0 then do; 
         i2 = i+1;
         put i= i2=;
         stop; 
      end; 
   end; 
stop; 

cross_sum:
   cvalue = compress(put(testvalue,12.));
   cs=0;
   do j=1 to length(cvalue);
      cs = cs + substr (cvalue, j, 1);
   end;
return;
 
run; 
Heide
Calcite | Level 5

hallo zusammen,

 

ich habe jede einzelne Stelle der Zahl in eine Arrayvariable gelesen und die Summe per lag() mit dem Vorgänger verglichen: 

 
data _null_;
   array a{0:10} a0 - a10;
 
   do i=18999999900 to 99999999999;
      do j=0 to 10;
         a(j) = mod(int(i / 10**j),10);
      end;
      if mod(sum(of a0-a10),10)=0 and lag(mod(sum(of a0-a10),10))=0 then do;
         i=i-1;
         put i= commax15.0; 
         stop;
      end;
   end;
run;

 

 

 viele Grüße. Heide Tribius

 

 

 

 

Heide
Calcite | Level 5

hallo zusammen,

 

es hat sich gerade gezeigt, dass die String-Funktionen zum separieren der Zahlen deutlich schneller sind und das will ich Euch natürlich nicht vorenthalten 😉

 

 
data _null_;
   array a{11} a1 - a11;
 
   do i=18990000000 to 99999999999;
      c = put(i,best.);
      do j=1 to 11;
         a(j) = ifn(length(c)>=j, input(substr(c,j,1),best.), .);
      end;
      if mod(sum(of a0-a10),10)=0 and lag(mod(sum(of a0-a10),10))=0 then do;
         i=i-1;
         put i= commax15.0; 
         stop;
      end;
   end;
run;

 

ein schönes Wochenende! Heide

FreelanceReinh
Jade | Level 19

Hallo zusammen,

 

nachdem schon so starke Datastep-Lösungen ins Rennen geschickt worden waren, wollte ich eigentlich etwas ganz anderes versuchen. Jedoch war die Performance einer reinen Makro-Lösung noch viel schlechter als befürchtet und auch ein Ansatz mit PROC FCMP (zur Berechnung der Quersumme und Prüfung ihrer Teilbarkeit durch 10) enttäuschte mit seiner Laufzeit. Daher bin ich doch beim reinen Datastep geblieben und habe versucht, ihn durch eine windschnittige Pfeilform schneller zu machen. Smiley (fröhlich)

 

data _null_;
array z[0:10];
do z1 = 0 to 9;
  do z2 = 0 to 9;
    do z3 = 0 to 9;
      do z4 = 0 to 9;
        do z5 = 0 to 9;
          do z6 = 0 to 9;
            do z7 = 0 to 9;
              do z8 = 0 to 9;
                do z9 = 0 to 9;
                  do z10= 0 to 9;
                    do z11= 0 to 9;
                      if ~init then do; z1=1; z2=8; z3=9; z4=9; init=1; end; /* nur zum Testen */
                      qsm=mod(sum(of z[*]), 10);
                      if qsm=lag(qsm) then do;
                        if ~qsm then do;
                          n=input(cats(of z[*]), 11.);
                          v=n-1;
                          put 'Lösung: ' v +(-1) ', ' n;
                          stop;
                        end;
                      end;
                    end;
                  end;
                end;
              end;
            end;
          end;
        end;
      end;
    end;
  end;
end;
run;

Die Zeile "if ~init ..." würde für einen kompletten Lauf ab 0 natürlich entfernt.

 

Viele Grüße und schönes WE

 

Reinhard

 

AndreasMenrath
Pyrite | Level 9

Vielen Dank schon einmal für alle eingereichten Lösungen. Ich bin immer wieder faziniert auf wie viele unterschiedlichen Wegen sich das gleiche Problem lösen lässt und wie stark die einzelnen Lösungen untereinander abweichen.

 

Bei der ein oder anderen Lösung wäre ich auch froh, wenn ich nicht die Wartung für das Programm übernehmen müsste Smiley (zwinkernd)

Auch zieren die meisten Lösungen das SAS Log mit Typkonvertierungsnotes, da wohl an der ein oder anderen Stelle ein PUT/INPUT vergessen wurde.

 

Ich versuche mich daher einmal an einer "sauberen" Implementierung. Hier also mein Programm:

/* Parameters for program */
%let start_number = 1.89999e10; /* %let start_number = 1; */
%let end_number = 1.91e10; /* %let end_number = 2e10; */
%let divisor = 10;

/* define view with sum of digits */
data sum_of_digits_view/ view=sum_of_digits_view;

  attrib number        length=8 format=commax15. 
         sum_of_digits length=8;
  keep number 
       sum_of_digits;

  do number=&start_number. to &end_number.;
    sum_of_digits = 0;
    tmp_number = number;

    do while(tmp_number ne 0);
      sum_of_digits = sum_of_digits + mod(tmp_number, 10);
      tmp_number = floor(tmp_number / 10);
    end;

    output;
  end;
run;

/* data processing logic */
data _null_;
  set sum_of_digits_view;

  /* filter */
  if (mod(sum_of_digits,&divisor.) eq 0);

  length previous_number current_number 8;
  retain previous_number 0;

  /* check condition */
  current_number = number;
  if ( (current_number - previous_number) eq 1) then do;
    put "NOTE: Zahlenpaar gefunden:";
    put "NOTE- Zahl:" previous_number;
    put "NOTE- Nachfolger:" current_number;
    stop;
  end;
  previous_number = number;

  /* report progress */
  if (mod(_n_, 1000000) eq 0) then do;
    progress = (current_number - &start_number.) / ( &end_number. - &start_number. );
    rc = dosubl(cats('SYSECHO "progress:', put(progress, percent10.2), '";'));
  end;
run;

Ich habe mein Programm logisch in zwei Teile geteilt. Im ersten Teil erzeuge ich eine Data View, die mir alle Zahlen im Suchraum sowie ihre Quersumme berechnet. Dieses Zwischenergebnis lässt sich auch schnell und einfach visuell "debuggen".

Im zweiten Teil wird im DATA _NULL_ Schritt die View verarbeitet und die Regeln der "Business Logik" geprüft.

Da bei einer vollständigen Suche ab der Zahl 1 die Verarbeitung relativ lange dauert, habe ich mir hier noch einenTrick abgeschaut: innerhalb des Datasteps melde ich noch an Enterprise Guide zurück, wie weit der aktuelle Verarbeitungsstand ist.

 

Viele Grüße,

Andreas

 

mfab
Quartz | Level 8

Hallo zusammen,

 

klasse, wieviel man hierbei lernen kann!

 

  • Falls jemand die Typkonvertierungs-Notes aus meinem Code entfernen kann - ich bin für Hinweise dankbar. Gerade sehe ich nicht, wo das Problem ist.
  • @Heide: den zweiten Code kann ich leider nicht ausführen. Mich würde interessieren, welche Funktion das "length(c)>=j" erfüllt. Ist das nicht immer "true"?
  • @Reinhard: Die Pfeiform hat schon was ;). Was bewirkt denn das "~init". Das kenne ich nicht und kann auch online nichts dazu finden.
  • @Andreas: Wieso ist denn Deine Lösung so dermaßen performant? Liegt das an der Berechnung der Quersumme? Hier hätte ich vermutet, dass die Verarbeitung per Substring in etwa genauso lange dauert, wie das Errechnen über Mod. Gibt es denn generell einen Weg bei SAS die Performanz zu prüfen? Fullstimer habe ich schon aktiviert, aber das scheint mir nicht ausreichend präzise zu sein. Ich würde in meinem Code vermuten, dass das Weglassen der Variablen start_number und end_number den Code performanter macht, weil die beiden Variablen im PDV aufgebaut werden. Das kann ich im Log aber nicht sinnvoll nachvollziehen.

Gibt es diese Code Katas regelmäßig? Ich finde das sehr spannend und freue mich über den Austausch und das Lernpotential!

 

Herzliche Grüße

Michael

HeideTribius
Fluorite | Level 6

hallo Michael,

 

das ist aber schade, dass Du den Code nicht ausführen kannst.

Dann kannst Du leider auch nicht sehen, wie unglaublich schnell er ist Smiley (zwinkernd)

 

Du hast Recht, die Bedingung ist im Moment immer true. Aber ich hoffe doch, dass sich am Ende einer findet, der die Codes (von der Zahl 1 beginnend) gegeneinander laufen lässt? Wir wollen schließlich wissen, wer gewonnen hat Smiley (zwinkernd)

 

viele Grüße. Heide

FreelanceReinh
Jade | Level 19

Hallo, Michael,

 

Dein Code verursacht zwei Typkonvertierungs-Notes:

 

1. Numeric to character
Das passiert in der Definition von FINDME. Hier wird das Character-Informat $20. auf die numerische Variable N angewandt. Passender wäre hier ein PUT-Statement mit einem numerischen Format.
Vorschlag: findme = PUT(n, 11.-l);
(Das -l sorgt für Linksbündigkeit, was im weiteren Verlauf wichtig wird, falls START_NUMBER nicht schon 11-stellig ist.)

 

2. Character to numeric
Das passiert an drei Stellen:
a) Die SUBSTR-Funktion liefert ein Character-Ergebnis, das in einer numerischen Addition verwendet wird.

Abhilfe: quersumme = quersumme + input(substr(findme,i,1), 1.);
b) SAS ist schon kulant, dass es die Anwendung des numerischen Formats 20. auf die Character-Variable FINDLAG kommentarlos akzeptiert. Die PUT-Funktion liefert aber ein Character-Ergebnis, zu dem dann die Zahl 1 addiert wird. Vorschlag: s. u.
c) Bei PUT(findme,20.) greift wieder die Kulanz, aber der Vergleich des resultierenden Strings mit dem zuvor in eine Zahl umgewandelten Wert (PUT(findlag,20.) + 1) erfordert dann doch die Konvertierung des Strings in eine Zahl.

Vorschlag für Punkte b und c: IF INPUT(findlag,11.) + 1 EQ INPUT(findme,11.) THEN DO;

 

Im Sinne eines ganz "sauberen" Logs wäre es noch schön, die Note "Missing values were generated ..." zu eliminieren. Die kommt zustande, weil der erste Wert, den FINDLAG von der LAG-Funktion erhält, ein Leerzeichen ist, zu dem nach Umwandlung in ein numerisches Missing die Zahl 1 addiert wird.

Daher modifizierter Vorschlag für 2.b und c: IF SUM(INPUT(findlag,11.),1) EQ INPUT(findme,11.) THEN DO;

Die Laufzeit verlängert sich allerdings durch die Verschönerungen ein wenig (insg. um ca. 1 - 3 %?).


Zur Frage nach meinem Code: Das INIT ist nur eine numerische Variable, die ich so genannt habe, weil sie als "Flag" dafür dient, ob die betreffende Codezeile schon einmal ausgeführt wurde. Ist dies noch nicht geschehen, ist die Variable noch nicht initialisiert, also missing. Die Bedingung ~init (also NOT init) ist dann erfüllt und die Schleifenvariablen werden von 0 auf die zu Testzwecken gewünschten Startwerte hochgesetzt. Da INIT sodann auf 1 initialisiert wird, ist ~init im weiteren Verlauf nie wieder erfüllt.


Was Laufzeitmessungen angeht, hätte ich eigentlich auf die (FULL)STIMER-Angaben vertraut. Hast Du schon unglaubwürdige Zeitangaben beobachtet? Alternativ (insb. wenn die Gesamtlaufzeit mehrerer Steps interessiert) kann man freilich auch vor und nach dem betreffenden Programmteil mit %put %sysfunc(datetime(), datetime.); Timestamps ins Log schreiben oder mit wenig mehr Aufwand sogar die Zeitdifferenz zwischen den beiden Timestamps ausrechnen lassen.

 

@HeideTribius: Den Performance-Test kann ich gern auf meinem Rechner laufen lassen, aber überzeugender fände ich es, wenn die Laufzeiten nicht von einem der teilnehmenden "Läufer" selbst gemessen würden.

 

Viele Grüße

 

Reinhard

AndreasMenrath
Pyrite | Level 9

@mfab: Berechnungen mit Fließkommazahlen sind aus meiner Erfahrung immer schneller als Stringoperationen. Außerdem hast du danach dann auch wieder die Typkonvertierung von z.B. Text "1" in die Ziffer 1. Das kostet auch noch einmal etwas Performance.

 

Bei dir sehe ich auch noch diese Zeile als potenziell problematisch an:

DO i = 1 TO length(findme);

Für jede berechnete Quersumme gehst du bei einer 10stelligen Zahl zehn Mal durch diesen Abschnitt und rufst damit 10 mal die LENGTH Funktion auf. Bei 1.000 berechneten Quersummen rufst du also 10.000 mal LENGTH auf.

 

Etwas besseres als FULLSTIMER kenne ich für DATA _NULL_ Steps auch nicht. Leider kann man nicht sehen an welchen Stellen innerhalb eines Datasteps die typischen Performancekiller (wie IO, CPU Zeit, usw.) auftreten.

 

Die Code Katas finden übrigens mehr oder weniger regelmäßig statt. Immer wenn ich ein passendes Problem finde stelle ich es ein und markiere es mit dem entsprechenden Tag. Über die Seite Code Kata Tag findest du leicht die älteren Beiträge.

Weitere Anregungen zu Code Katas sind immer willkommen.

 

Grüße,

Andreas

HeideTribius
Fluorite | Level 6

hallo zusammen,

 

Michael hat Recht - der zweite Code funktioniert so nicht. Was hab ich da nur kopiert?! Sorry!

 

 
data _null_;
   array a{1:11} a1 - a11;
 
   do i=18999000000 to 99999999999;
      c = put(i,11.);
      do j=1 to 11;
         a(j) = ifn(length(c)>=j, input(substr(c,j,1),best.), .);
      end;
      if mod(sum(of a1-a11),10)=0 and lag(mod(sum(of a1-a11),10))=0 then do;
         i=i-1;
         put i= commax15.0; 
         stop;
      end;
   end;
run;
 

sas-innovate-2024.png

Join us for SAS Innovate April 16-19 at the Aria in Las Vegas. Bring the team and save big with our group pricing for a limited time only.

Pre-conference courses and tutorials are filling up fast and are always a sellout. Register today to reserve your seat.

 

Register now!

Diskussionsstatistiken
  • 19 Antworten
  • 3460 Aufrufe
  • 5 Kudos
  • 7 in Unterhaltung