我對(duì)所謂的“交錯(cuò)函數(shù)”f 的高效 Python 實(shí)現(xiàn)感興趣，該函數(shù)接受 (0,1) 中的兩個(gè)數(shù)字 a、b 并交錯(cuò)它們的十進(jìn)制數(shù)字，即f(a,b) := 0.a1 b1 a2 b2 a3 b3 ... 其中 a = 0.a1 a2 a3... 和 b = 0.b1 b2 b3... 是 a,b 的十進(jìn)制表示形式。從數(shù)學(xué)上來(lái)說(shuō)，函數(shù) f 是從 (0,1)x(0.1) 到 (0,1) 的一對(duì)一映射。您能否建議如何在 Python 中有效地實(shí)現(xiàn)此映射以保持其一對(duì)一的關(guān)系？
1 回答
收到一只叮咚
TA貢獻(xiàn)1821條經(jīng)驗(yàn) 獲得超5個(gè)贊
為了實(shí)現(xiàn)高效的實(shí)現(xiàn)，需要確保實(shí)現(xiàn)兩件事：大 O 表示法的漸近復(fù)雜度最小化和高效的計(jì)算運(yùn)算符，避免重復(fù)或其他不必要的計(jì)算。
考慮到這個(gè)問題，不太可能用與輸入數(shù)字的長(zhǎng)度不呈線性關(guān)系的算法來(lái)解決它。就運(yùn)算符而言，考慮到我們使用十進(jìn)制格式，我們很難從一些按位（二進(jìn)制）計(jì)算中受益。因此，我們可能最擅長(zhǎng)一般的數(shù)學(xué)運(yùn)算。
使用浮動(dòng)
第一個(gè)簡(jiǎn)單的實(shí)現(xiàn)將嘗試對(duì)浮點(diǎn)數(shù)執(zhí)行該函數(shù)：
def interleave_float(a: float, b: float) -> float:
? ? a_rest = a
? ? b_rest = b
? ? result = 0
? ? dst_pos = 1.0? # position of written digit
? ? while a_rest != 0 or b_rest != 0:
? ? ? ? dst_pos /= 10? # move decimal point of write
? ? ? ? a_rest *= 10? # move decimal point of read
? ? ? ? result += a_rest // 1 * dst_pos
? ? ? ? a_rest %= 1? # remove current digit
? ? ? ? dst_pos /= 10
? ? ? ? b_rest *= 10
? ? ? ? result += dst_pos * (b_rest // 1)
? ? ? ? b_rest %= 1
? ? return result
然而，一個(gè)簡(jiǎn)單的測(cè)試顯示了一個(gè)問題 -浮點(diǎn)運(yùn)算的精度固有地有限，它在浮點(diǎn)后的第 16-17 位數(shù)字處已經(jīng)失真：
>>> a = 0.987654321
>>> b = 0.1234567890123456789
>>> print(a)
0.987654321
>>> print(f"{b:.20}")? # formatted to show higher precision
0.12345678901234567737
>>> print(f"Float:? {interleave_float(a, b):.50}")
Float:? 0.91827364554637280757987127799424342811107635498047
使用小數(shù)
克服精度問題的常見方法是使用decimal.Decimal ，即定點(diǎn)十進(jìn)制算術(shù)的python實(shí)現(xiàn)：
from decimal import Decimal, getcontext
getcontext().prec = 50? # increase number precision
def interleave_fixed(a: Decimal, b: Decimal) -> Decimal:
? ? a_rest = a
? ? b_rest = b
? ? result = 0
? ? dst_pos = Decimal(1)
? ? while a_rest != 0 or b_rest != 0:
? ? ? ? dst_pos *= Decimal(0.1)
? ? ? ? a_rest *= 10? # move decimal point
? ? ? ? result += a_rest // 1 * dst_pos
? ? ? ? a_rest %= 1? # remove current digit
? ? ? ? dst_pos *= Decimal(0.1)
? ? ? ? b_rest *= 10
? ? ? ? result += dst_pos * (b_rest // 1)
? ? ? ? b_rest %= 1
? ? return result
這似乎對(duì)b效果更好，但不幸的是，它也會(huì)導(dǎo)致結(jié)果中大約相同數(shù)字的不精確。計(jì)算后上下文中的Inexact標(biāo)志也表明了這種不精確性：
>>> print(getcontext())
Context(prec=50, rounding=ROUND_HALF_EVEN, Emin=-999999, Emax=999999, capitals=1, clamp=0, flags=[], traps=[InvalidOperation, DivisionByZero, Overflow])
>>> a = Decimal(".987654321")
>>> b = Decimal(".1234567890123456789")
>>> print(a)
0.987654321
>>> print(b)
0.1234567890123456789
>>> print(f"Fixed:? {interleave_fixed(a, b)}")
Fixed:? 0.91827364554637287146771953200668367263491993253785
>>> print(getcontext())
Context(prec=50, rounding=ROUND_HALF_EVEN, Emin=-999999, Emax=999999, capitals=1, clamp=0, flags=[Inexact, FloatOperation, Rounded], traps=[InvalidOperation, DivisionByZero, Overflow])
使用 str
另一種不應(yīng)由于精度而施加限制的方法（并且您自己提出了這種方法）是對(duì)字符串進(jìn)行語(yǔ)法處理：
def interleave_str(a: str, b: str) -> str:
? ? result = "0."
? ? src_pos = 2? # position of read digit
? ? while len(a) > src_pos or len(b) > src_pos:
? ? ? ? result += a[src_pos] if len(a) > src_pos else "0"
? ? ? ? result += b[src_pos] if len(b) > src_pos else "0"
? ? ? ? src_pos += 1
? ? return result[:-1] if result.endswith("0") else result
刪除 traling 0（如果存在）
該算法不進(jìn)行驗(yàn)證，因此您可以決定要添加什么。然而，測(cè)試它給出了所需的精度：
>>> a = "0.987654321"
>>> b = "0.1234567890123456789"
>>> print(a)
0.987654321
>>> print(b)
0.1234567890123456789
>>> print(f"String: {interleave_str(a, b)}")
String: 0.91827364554637281900010203040506070809
...但是我們可以對(duì)生成的字符串做什么呢？也許再次將其轉(zhuǎn)換為十進(jìn)制？取決于您想如何使用結(jié)果。
添加回答
舉報(bào)
0/150
提交
取消