Dezimalzahlen in Binärdarstellung - Meine Idee

[ne0h]

Hallo sehbaer,

dabei handelt es sich um eine sogen. "Bitverschiebung".

Code: Alles auswählen

n >> 1

bedeutet in diesem Fall, dass der Inhalt von "n" um eine Bitstelle nach rechts verschoben wird.

So zumindest kenne ich diese Schreibweise.

Man korrigiere mich bitte, falls ich es falsch erklärt habe.


ne0h

[sehbaer]

Danke! Hatte ich schon ein wenig vermutet und nun auch gefunden:
http://docs.python.org/ref/shifting.html
Nach solchen Zeichen ist leider immer ganz übel zu suchen...

[ne0h]

Hm... könnte mir Jemand diese Lösung von "sma" Schritt für Schritt erläutern?

Code: Alles auswählen

def d2b(n):
  return d2b(n / 2) + "01"[n % 2] if n else ""

Ich komme damit nicht ganz zurecht, auch wenn es einwandfrei läuft. Irgendwie fehlt mir da das Verständnis, warum ich auf das "return" diese Addition durchführe bzw. warum überhaupt eine Addition und dann mit diesem Ausdruck:

Code: Alles auswählen

+ "01"[n % 2]

ne0h

[sehbaer]

Ich versuche mich da mal: Das ist eher eine Concatenation als eine Addition. Da wird eine Zeichenkette zusammengetüdelt. Aus der Zeichenkette "01" wird abhängig davon, ob n gerade oder ungerade ist eine "0" oder "1" "herausindiziert" und solange aneindandergetüdelt, bis n = 0 (False) ist. Ich finde Rekursionen immer so schlimm zu beschreiben und hoffe ich habe mich da einigermaßen verständlich ausgedrückt.

[audax]

Code: Alles auswählen

"01"[n % 2] 

das entspricht:

Code: Alles auswählen

if n % 2 == 0:
    return '0'
else:
    return '1'

Es wird also n % 2 als Index für den String "01" benutzt.

[ne0h]

Danke Euch beiden,

das habe ich jetzt verstanden.

Aber trotzdem verstehe ich das nun syntaktisch noch nicht so ganz.

Wie genau wird denn aus dieser Zeichenkette "01" die 0 oder die 1 gefiltert bzw. errechnet, dahinter ist doch ein Ausdruck in einer Liste, oder?

Also das n % 2 steht doch in der Liste []. Wie ist da genau der Bezug zu dem String "01", welcher direkt davor steht?

Ich "sehe" da einfach nicht, wie die Berechnung der Liste auf den String einwirkt.

Hoffe, man versteht, was ich meine.

Gruß

ne0h

[EyDu]

Das ist keine Liste, das ist ein Index. Ein Blick ins Tutorial würde vielleicht helfen

[sehbaer]

gehste in den Interpreter und machste 'huhu'[3] oder so. Dann wird es klar, denke ich.

[Zap]

Du kannst ja per Index auf einen String zugreifen und das wird hier gemacht,
erst wird der Modulo ausgerechnet und dieser als Index genutzt

Code: Alles auswählen

>>>3 % 2
1
>>>4 % 2
0
>>>"AB"[0]
"A"
>>>"AB"[1]
"B"

[Trundle]

Das ist einfach die Indizierung eines Strings. Siehe auch Tutorial (3.1.2 Strings).

Code: Alles auswählen

In [23]: "Spam"[0]
Out[23]: 'S'

In [24]: "Spam"[1]
Out[24]: 'p'

etc.

Edit: einhändig ist man eben doch viel zu lahm.

[ne0h]

Ok, alles klar. Ich starre heute schon zu lange auf den Bildschirm und habe gerade die ganze Zeit wie ein Vollidiot darüber nachgedacht, wie die Liste da hinter dem String was damit zu tun hat.

Jetzt seh ichs auch, nach Euren Hinweisen, dass da einfach nur der Index des Strings berechnet wird.

Manchmal verrene ich mich echt in so komplizierte Gedanken, wie, was, warum, dass ich das offensichtlichste garnicht mehr erkenne.


Danke, ich geh ins Bett.


ne0h

[Leonidas]

Also diese rekursiven Aufrufe will ich jetzt gleich mal angehen.

Ja, uhm, Rekursion ist ein nicht ganz triviales Problem, weil es eben doch recht ungewohnt ist.

Was genau ist das für eine Sprache, in der Deine verlinkten Beispiele sind? Bzw.: Was hat das Ganze mit den von Dir gerade geschriebenen Beispielen zu tun?

Die Beispiele sind in Scheme einer Sprache von der Python viele Konzepte geerbt hat und die ich grad lerne. Ich wollte eben sehen wie so ein Binärkonverter in Scheme aussieht die ich die Sprache auch erst lerne und mich nach Beispielen umsehe, die ich mir zutrauen kann, so ähnlich wie du in Python. Außerdem starten hier manchmal kleine spontane Wettbewerbe, irgendwelche Probleme in allen möglichen Sprachen zu Lösen und sie dann mit der Python-Lösung zu vergleichen.

Übrigens: ``(number->string 21 2)`` wäre natürlich die naheliegendste Lösung gewesen

[ne0h]

Hallo,

Ok, Scheme sagt mir was (nur vom Namen her ). Sieht mir grade aber etwas zu "geklammert" aus.


Ähm, dieses Beispiel hier:

(number->string 21 2)

stammt ja von der ertsen Seite. Läuft das denn nun intern per Rekursion oder greift dies auf Bitverschiebungen zurück. Oder besser gefragt:

Welche Variante ist denn nun effizienter in der Ausführungsgeschwindigkeit? (Nicht dass es wirklich von Bedeutung für mich wäre im Moment, aber es interessiert mich nun doch.).


Gruß


ne0h

[BlackJack]

@ne0h: In Python, zumindest in CPython, dürften iterative Lösungen immer schneller sein, als Rekursive. Weil Funktionsaufrufe in CPython relativ teuer sind und keine Tail-Call-Optimization gemacht wird.

Wenn es sich um Endrekursion handelt, kann man von einem Scheme-Compiler erwarten, das der das als effiziente Schleife in Maschinensprache übersetzt. Wobei es in Scheme selbst auch gar keine iterativen Schleifen gibt, da *muss* man also Rekursion als Ausdrucksmittel wählen.

[Leonidas]

Welche Variante ist denn nun effizienter in der Ausführungsgeschwindigkeit? (Nicht dass es wirklich von Bedeutung für mich wäre im Moment, aber es interessiert mich nun doch.).

Also, die Codes die ich teste:

Code: Alles auswählen

def d2b(n):
  d = ""
  while n:
    d += "01"[n & 1]
    n >>= 1
  return d[::-1]

print d2b(21)

und

Code: Alles auswählen

(display (string-append (number->string 21 2) "\n"))

Simpler, synthetischer Benchmark mit 100 Wiederholungen:

Code: Alles auswählen

$ time eval 'i=0; while [ $i -lt 100 ]; do python2.5 d2.py > /dev/null ; i=$(($i + 1)); done'
real	0m1.301s
user	0m0.944s
sys	0m0.424s
$ time eval 'i=0; while [ $i -lt 100 ]; do mzscheme -r d2.scm > /dev/null ; i=$(($i + 1)); done'
real	0m3.010s
user	0m2.596s
sys	0m0.400s

Python läuft schneller, allerdings läuft der Scheme-Code auch im Interpreter (und PLT-Scheme ist nicht wirklich schnell). Kompiliert siehts wohl anders aus, die zahlen liefere ich nach.

Eine rekursive Python-Lösung wäre sicherlich langsamer, als die iterative. Allerdings ist ``number->string`` in PLT auch in C interpretiert, also eigentlich genauso iterativ.

[Leonidas]

Hier noch die Ergebnisse auf einem anderen Computer. Die Python-Version ist die selbe, das MzScheme ist etwas älter und der letzte Test ist ein kompiliertes Programm mittels Checken (SCM -> C -> Binary).

Code: Alles auswählen

$ time eval 'i=0; while [ $i -lt 100 ]; do python2.5 d2.py > /dev/null ; i=$(($i + 1)); done'

real	0m1.369s
user	0m0.916s
sys	0m0.468s
$ time eval 'i=0; while [ $i -lt 100 ]; do mzscheme -r d2.scm > /dev/null ; i=$(($i + 1)); done'

real	0m3.988s
user	0m3.500s
sys	0m0.504s
 $ time eval 'i=0; while [ $i -lt 100 ]; do ./d2 > /dev/null ; i=$(($i + 1)); done'

real	0m0.439s
user	0m0.288s
sys	0m0.276s