8

有没有办法在恒定工作空间中进行任意大小和任意基本转换。也就是说，要使用 1 对 1 映射（最好但不一定）保留字典顺序并给出顺序结果，将范围内的n数字序列转换为范围内[1,m]的ceiling(n*log(m)/log(p))数字序列？[1,p]

我对作为管道功能可行的解决方案特别感兴趣，ei 能够处理比存储在 RAM 中更大的数据集。

我发现了许多需要与输入大小成比例的“工作空间”的解决方案，但还没有一个解决方案可以摆脱恒定的“工作空间”。

放弃顺序约束有什么不同吗？即：允许按字典顺序输入导致非按字典顺序输出：

F(1,2,6,4,3,7,8) -> (5,6,3,2,1,3,5,2,4,3)
F(1,2,6,4,3,7,9) -> (5,6,3,2,1,3,5,2,4,5)

一些想法：

这可能有用吗？

streamBase n -> convert( n, lcm(n,p)) -> convert( lcm(n,p), p) -> streamBase p

（lcm最小公倍数在哪里）

4

3 回答 3

6

我认为在一般情况下这是不可能的。如果m是p（或反之亦然）的幂，或者如果它们都是共同基的幂，则可以这样做，因为每组 log m( p) 都是独立的。但是，在一般情况下，假设您要转换 number 。基数中的等价数是a1 a2 a3 ... anp

sum(ai * mi-1对于i在1..n)

如果我们已经处理了第一个i数字，那么我们就有了i第 th 个部分和。要计算i+1'th 部分和，我们需要添加。在一般情况下，这个数字在大多数地方都是非零数字，所以我们需要修改到目前为止我们已经处理的所有数字。换句话说，我们必须先处理所有输入数字，然后才能知道最终输出数字是什么。ai+1 * mi

m在一个公共底数的幂的特殊情况下，或者等效地如果 log m( p) 是一个有理数，那么在靠近前面mi的底数中只会有几个非零数字p，所以我们可以安全地输出我们的大部分数字到目前为止已经计算过了。

于 2009-05-19T19:42:10.093 回答
2

我认为有一种方法可以按字典顺序以面向流的方式进行基数转换。然而，我想出的还不足以真正做到这一点，它有几个假设：

  1. 位置编号的长度是已知的。
  2. 所描述的数字是整数。我没有考虑过 maths 和 -ive 索引会发生什么。

我们有一系列长度为p的值a，其中每个值都在 [0, m -1] 范围内。我们想要一个长度为q在 [0, n -1]范围内的值b序列。我们可以从a中计算出输出序列b的第k个数字，如下所示：

b k = floor[ sum(a i * m i for i in 0 to p-1) / n k ] mod n

让我们将总和重新排列为两部分，将其拆分为任意点z

b k = floor[ ( sum(a i * m i for i in z to p-1) + sum(a i * m i for i in 0 to z-1) ) / n k ] mod n

假设我们还不知道 [0,z-1] 之间的 a 的值并且无法计算第二个和项。我们不得不处理范围。但这仍然为我们提供了有关b k的信息。

b k的最小值可以是：

b k >= floor[ sum(a i * m i for i in z to p-1) / n k ] mod n

b k的最大值可以是：

b k <= floor[ ( sum(a i * m i for i in z to p-1) + m z - 1 ) / n k ] mod n

我们应该能够做这样的过程：

  1. 将z初始化为p。当我们收到a 的每个字符时，我们将从p开始倒计时。
  2. 将k初始化为b中最重要值的索引。如果我的大脑还在工作，ceil[log n (m p ) ]。
  3. 读取a的值。递减z。
  4. 计算b k的最小值和最大值。
  5. 如果最小值和最大值相同，则输出b k并递减 k。转到 4。（可能我们已经为b k的几个连续值提供了足够的值）
  6. 如果z !=0 那么我们期望a 有更多的值。转到 3。
  7. 希望，在这一点上我们已经完成了。

我还没有考虑如何有效地计算范围值，但我有理由相信从 a 的传入字符计算总和比存储所有a更合理。虽然不做数学，但我不会对此提出任何硬性要求！

于 2009-05-20T04:19:32.487 回答
0

对的，这是可能的

对于您读入的每个 I 个字符，您将根据 Ceiling(Length * log(In) / log(Out)) 写出 O 个字符。

分配足够的空间

Set x to 1
Loop over digits from end to beginning # Horner's method
    Set a to x * digit
    Set t to O - 1
    Loop while a > 0 and t >= 0
        Set a to a + out digit
        Set out digit at position t to a mod to base
    Set a to a / to base
Set x to x * from base
Return converted digit(s)

因此，对于基数 16 到 2（这很容易），使用“192FE”我们读取 '1' 并将其转换，然后重复 '9'，然后是 '2'，依此类推，得到 '0001'，'1001'， “0010”、“1111”和“1110”。请注意，对于不是普通幂的碱基，例如从 17 到 2 的底数意味着读取 1 个字符并写入 5 个字符。

于 2017-05-24T02:57:07.753 回答