在Python中交织两个十进制数字

Question

我对所谓的“交错函数”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 中有效地实现此映射以保持其一对一的关系？

Answer 1

为了实现高效的实现，需要确保实现两件事：大 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 precision0.12345678901234567737>>> print(f"Float:  {interleave_float(a, b):.50}")Float:  0.91827364554637280757987127799424342811107635498047使用小数克服精度问题的常见方法是使用decimal.Decimal ，即定点十进制算术的python实现：from decimal import Decimal, getcontextgetcontext().prec = 50  # increase number precisiondef 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...但是我们可以对生成的字符串做什么呢？也许再次将其转换为十进制？取决于您想如何使用结果。