我對所謂的“交錯函數”f 的高效 Python 實現感興趣，該函數接受 (0,1) 中的兩個數字 a、b 并交錯它們的十進制數字，即f(a,b) := 0.a1 b1 a2 b2 a3 b3 ... 其中 a = 0.a1 a2 a3... 和 b = 0.b1 b2 b3... 是 a,b 的十進制表示形式。從數學上來說，函數 f 是從 (0,1)x(0.1) 到 (0,1) 的一對一映射。您能否建議如何在 Python 中有效地實現此映射以保持其一對一的關系？
1 回答
收到一只叮咚
TA貢獻1821條經驗 獲得超5個贊
為了實現高效的實現，需要確保實現兩件事：大 O 表示法的漸近復雜度最小化和高效的計算運算符，避免重復或其他不必要的計算。
考慮到這個問題，不太可能用與輸入數字的長度不呈線性關系的算法來解決它。就運算符而言，考慮到我們使用十進制格式，我們很難從一些按位（二進制）計算中受益。因此，我們可能最擅長一般的數學運算。
使用浮動
第一個簡單的實現將嘗試對浮點數執行該函數：
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
然而，一個簡單的測試顯示了一個問題 -浮點運算的精度固有地有限，它在浮點后的第 16-17 位數字處已經失真：
>>> 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
使用小數
克服精度問題的常見方法是使用decimal.Decimal ，即定點十進制算術的python實現：
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
這似乎對b效果更好，但不幸的是，它也會導致結果中大約相同數字的不精確。計算后上下文中的Inexact標志也表明了這種不精確性：
>>> 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
另一種不應由于精度而施加限制的方法（并且您自己提出了這種方法）是對字符串進行語法處理：
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（如果存在）
該算法不進行驗證，因此您可以決定要添加什么。然而，測試它給出了所需的精度：
>>> a = "0.987654321"
>>> b = "0.1234567890123456789"
>>> print(a)
0.987654321
>>> print(b)
0.1234567890123456789
>>> print(f"String: {interleave_str(a, b)}")
String: 0.91827364554637281900010203040506070809
...但是我們可以對生成的字符串做什么呢？也許再次將其轉換為十進制？取決于您想如何使用結果。
添加回答
舉報
0/150
提交
取消