Dezimalzahlen in Binärdarstellung - Meine Idee

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
ne0h
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Montag 19. Mai 2008, 19:11

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
Benutzeravatar
sehbaer
User
Beiträge: 39
Registriert: Sonntag 30. März 2008, 17:26
Wohnort: Kölle

Montag 19. Mai 2008, 19:45

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...
...es sind ganz bestimmt mehr Nullen als Einsen.
ne0h
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Montag 19. Mai 2008, 20:22

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
Benutzeravatar
sehbaer
User
Beiträge: 39
Registriert: Sonntag 30. März 2008, 17:26
Wohnort: Kölle

Montag 19. Mai 2008, 20:46

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.
...es sind ganz bestimmt mehr Nullen als Einsen.
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Montag 19. Mai 2008, 20:46

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
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Montag 19. Mai 2008, 21:12

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
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Montag 19. Mai 2008, 21:18

Das ist keine Liste, das ist ein Index. Ein Blick ins Tutorial würde vielleicht helfen ;-)
Benutzeravatar
sehbaer
User
Beiträge: 39
Registriert: Sonntag 30. März 2008, 17:26
Wohnort: Kölle

Montag 19. Mai 2008, 21:19

gehste in den Interpreter und machste 'huhu'[3] oder so. Dann wird es klar, denke ich.
...es sind ganz bestimmt mehr Nullen als Einsen.
Zap
User
Beiträge: 533
Registriert: Freitag 13. Oktober 2006, 10:56

Montag 19. Mai 2008, 21:19

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"
Benutzeravatar
Trundle
User
Beiträge: 591
Registriert: Dienstag 3. Juli 2007, 16:45

Montag 19. Mai 2008, 21:21

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
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Montag 19. Mai 2008, 21:28

:lol:


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. :wink:


ne0h
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Montag 19. Mai 2008, 23:08

ne0h hat geschrieben: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.
ne0h hat geschrieben: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 :)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
ne0h
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Dienstag 20. Mai 2008, 16:15

Hallo,

Ok, Scheme sagt mir was (nur vom Namen her :wink: ). 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

Dienstag 20. Mai 2008, 20:10

@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
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Mittwoch 21. Mai 2008, 00:58

ne0h hat geschrieben: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.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Antworten