Suche mathematische Funktion, um Platzverbrauch zu zählen.

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.
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Suche mathematische Funktion, um Platzverbrauch zu zählen.

Beitragvon akis.kapo » Freitag 18. Januar 2008, 16:19

Hallo alle.

Python kennt ja keine Grenzen und auch keine Grösse für seine Integer.

Code: Alles auswählen

>>> zahl = 18382838243
>>> zahl
18382838243L
>>> len(zahl)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: object of type 'long' has no len()


Ich möchte aber so eine Zahl verpacken können per struct.pack() im 'Q' Format (unsigned long long := 64 bit Integer).

Aber da Python Integers keine Obergrenze haben, muss ich deswegen vorher ganz genau wissen, wieviele Q's, sprich wieviele 64 bit Blöcke, hintereinander ich benötige, um das Pyhton Integer n abzubilden.

Je grösser die Zahl desto mehr 64 bit (8 byte) Blöcke brauche ich.

Anders gesprochen, ich muss einen String aus 8 byte Vielfachen bauen und dann die Zahl "reinladen", gesucht ist aber zu jeder Zahl N das dazugehörige 8 byte Vielfache X.

Das "reinladen" ist etwas kompliziert, es geht nicht direkt, aber stellt auch nicht wirklich das Problem dar.

Was ich suche ist eine Funktion, die mir zu jedem N das richtige X zurückgibt.

Beispiel:

0 < N <= 2**64 -----> X = 1 (* 8 byte)
2**64 < N <= 2**128 -----> X = 2 (* 8 byte)
2**128 < N <= 2**192 -----> X = 3 (* 8 byte)
... usw. ...

NB: Ich fange bei 1 an zu zählen, nicht bei Null, daher auch 0 < N <= 2**64 und nicht N von 0 bis 2**64-1.

Ich hab schon mit math.log() und math.ceil() etwas rumgespielt, aber irgendwie kommt da nicht das raus, was ich vermutete.

Code: Alles auswählen

>>> from math import log
>>> log(1,2**64)
0.0
>>> log(2,2**64)
0.015625
>>> log(2**64,2**64)
1.0
>>> log(2**64+1,2**64)
1.0
>>> log(2**64+2,2**64)
1.0
>>> log(2**65,2**64)
1.015625
>>> log(2**128,2**64)
2.0


Wie ihr sehen könnt, braucht man laut log() 0 (Null) mal 64 bit, um bis eins zählen zu können. [FALSCH]
Um bis 2 zählen zu können, braucht man dann einige 64 bit (sprich mindestens 1 64 bit Block). [RICHTIG]
Um bis 2**64 zählen zu können, muss schon 1 mal 64 bit vorhanden sein. [RICHTIG]
Um bis 2**64 + 1 oder +2 zählen zu können, reichen 64 bit immer noch aus. [FALSCH]
Für 2**128 braucht man genau 2 x 64 bit Blöcke. [RICHTIG]

Ihr seht das reimt sich vorne und hinten nicht ganz mit der Logik.

Wie berechne ich die Anzahl der 64 bit Blöcke korrekt?
(Mathe ist schon so lange her gewesen bei mir... :( )
BlackJack

Beitragvon BlackJack » Freitag 18. Januar 2008, 16:31

Ist schon fast richtig, Du musst das Ergebnis mit `math.ceil()` aufrunden und die 0 als Sonderfall behandeln, weil man ja mindestens einmal 8 Bytes braucht, auch wenn man die Zahl theoretisch mit weniger Bytes/Bits kodieren könnte.

Code: Alles auswählen

nr_of_longs = max(int(ceil(log(zahl, 2**64))), 1)
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Beitragvon akis.kapo » Freitag 18. Januar 2008, 16:34

AHA!

Das mit int(ceil(log(foo, bar))), soweit war ich schon...

Aber nochmal nen max() drumrum zu bauen, darauf wäre ich jetzt von alleine nicht gekommen.

1000 Dank an dir.
Als Belohnung darfst du in Zukunft in meinem myfindduplicates.py Programm beliebig lange Dateien einlesen.
(Limit liegt dann beim OS, nicht bei Python. Dann gibts auch keine Probs, mit Dateien, die zufällig genau ein Vielfaches von 2**64 byte gross sind.) :)
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Beitragvon akis.kapo » Freitag 18. Januar 2008, 16:37

Zu früh gefreut.

Ich vermute Rundungsfehler sind die Ursache für:

Code: Alles auswählen

>>> max(int(ceil(log(2**64+1,2**64))),1)
1
>>> max(int(ceil(log(2**64+2,2**64))),1)
1
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Beitragvon akis.kapo » Freitag 18. Januar 2008, 21:40

Diese Funktion habe ich gesucht:

Code: Alles auswählen

def get_numberofQs(fsize):
   numberofQs = 1
   while (max(fsize-1,1) / (2**(numberofQs*64))) > 0:
      numberofQs += 1
   return numberofQs


Ok jetzt kanns weitergehn.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Beitragvon birkenfeld » Samstag 19. Januar 2008, 11:57

Andere Möglichkeit:

Code: Alles auswählen

def n_of_q(x):
    i = 0
    while x:
        i += 1
        x >>= 64
    return i
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Samstag 19. Januar 2008, 12:06

birkenfeld hat geschrieben:Andere Möglichkeit: [...]

Versuch mal `n_of_q(-1)` Diese Zahl ist deinem Algorithmus nach GROSS :)

Stefan
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Beitragvon birkenfeld » Samstag 19. Januar 2008, 12:11

Ui, da muss dann wohl noch ein abs() hinein ;)
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Beitragvon akis.kapo » Samstag 19. Januar 2008, 19:01

Danke für den Hinweis.

Hätte ich selber drauf kommen können einfach zu shiften, statt zu dividieren, aber da fehlt mir einfach die Erfahrung, solche "Tricks" zu verwenden.

Das wäre der resultierende Algorithmus:

Code: Alles auswählen

>>> def getnq(x):
...     i = 1
...     while max(x-1,1) >> (i*64):
...             i += 1
...     return i
...
>>>
>>> getnq(0)
1
>>> getnq(2**64-1)
1
>>> getnq(2**64)
1
>>> getnq(2**64+1)
2
>>> getnq(2**128-1)
2
>>> getnq(2**128)
2
>>> getnq(2**128+1)
3
>>>


Der Hintergrund ist, dass x eine Dateigrösse darstellt, diese ist immer positiv, also braucht man für praktische Zwecke nicht so tiefgründig mathematisch denken, und kann somit das abs() ignorieren.

Danke auch euch.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder