Suche mathematische Funktion, um Platzverbrauch zu zählen.

[akis.kapo]

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]

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)

[akis.kapo]

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.)

[akis.kapo]

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

[akis.kapo]

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.

[birkenfeld]

Andere Möglichkeit:

Code: Alles auswählen

def n_of_q(x):
    i = 0
    while x:
        i += 1
        x >>= 64
    return i

[sma]

Andere Möglichkeit: [...]

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

Stefan

[birkenfeld]

Ui, da muss dann wohl noch ein abs() hinein

[akis.kapo]

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.