給定一個大正整數的十進制字串表示，什么是找到整數位長度的快速方法？使用int()然后bit_length()很慢。這個具有一百萬位數字的示例需要 5 秒以上才能告訴我它有 3321926 位：
s = '1234567890' * 10**5
print(int(s).bit_length())
結果應該是準確的，至少對于記憶體中實際可以擁有的所有字串（所以我們說多達 1000 億個十進制數字）。
uj5u.com熱心網友回復：
如果存盤空間不是問題并且您不介意預先花費時間，（并且您希望有一個不依賴于浮點精度的解決方案，即使它在其他方面不切實際）您幾乎可以解決任何問題更多記憶體的速度問題。建立一個字串表示的查找表2**n。設定一個字典，將字串長度鍵入（該長度的字串，對應的 n 值）對的串列。要測驗輸入，請查找適當的串列，然后使用普通字串比較來確定它屬于哪個位長類別。
uj5u.com熱心網友回復：
我認為這對于數十億位數字應該是準確的。只需按位數計算 100000...00000 的確切結果，然后添加前 10 位的對數。
import math
s = '1234567890' * 10**5
dper = math.log(10)/math.log(2)
base= (len(s)-10)*dper
extra = math.log(int(s[:10]))/math.log(2)
print(int(base extra 0.99))
uj5u.com熱心網友回復：
這將在大約 0.15 秒、'1234567890' * 10**6大約 2 秒和'1234567890' * 10**7大約 20 秒內完成該示例。首先我用對數近似位長，然后我用它decimal.Decimal來調整直到精確。該類使用基數 10，因此不需要昂貴的基數轉換。
位長 b 覆寫區間 [2**(b-1), 2**b)。所以我們想要比數字大的 2 的最小冪（的指數）。
在線嘗試！
from time import time
from math import log2
from decimal import *
setcontext(Context(prec=MAX_PREC, Emax=MAX_EMAX, Emin=MIN_EMIN))
def bit_length(s):
if len(s) <= 20:
return int(s).bit_length()
head_bits = log2(int(s[:20]))
tail_bits = (len(s) - 20) * log2(10)
b = int(head_bits tail_bits)
n = Decimal(s)
power = Decimal(2) ** b
while power > n:
b -= 1
power //= 2
while power <= n:
b = 1
power *= 2
return b
s = '1234567890' * 10**5
start = time()
print(bit_length(s))
print(time() - start, 'seconds')
uj5u.com熱心網友回復：
此方法計算給定示例的時間約為0.03-0.04 秒，而約 5.2 秒（因此快約173 倍）。因為'1234567890' * 10**6它是 ~0.4 秒，'1234567890' * 10**7它需要 ~4 秒。'1234567890' * 10**8在我的機器上花了大約 41 秒。
int我沒有轉換成超慢的，而是轉換成然后Decimal只是做了基本的log操作來獲得位數：
import time
from decimal import Decimal
from math import floor
start = time.time_ns()
s = '1234567890' * 10**5
num_bits = 1 floor(Decimal(s).log10() / Decimal(2).log10())
end = time.time_ns()
duration = end - start
print(f'Duration: {duration} ns. ({duration/1e9} s)')
print(f'{num_bits} bits')
輸出：
Duration: 40003700 ns. (0.0400037 s)
3321926 bits
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/477170.html
上一篇：在python中將矩陣轉換為梯形