Преобразование чисел в виде потоковой операции - PullRequest
Новая
       14

Преобразование чисел в виде потоковой операции

7 голосов
/ 19 мая 2009

Есть ли способ в постоянном рабочем пространстве для выполнения произвольных размеров и произвольных базовых преобразований. То есть, чтобы преобразовать последовательность чисел n в диапазоне [1,m] в последовательность чисел ceiling(n*log(m)/log(p)) в диапазоне [1,p], используя отображение 1-к-1, которое ( предпочтительно , но не обязательно) сохраняет лексикографический порядок и дает последовательные результаты?

Я особенно заинтересован в решениях, которые являются жизнеспособными в качестве функции конвейера, т.е. способны обрабатывать больший набор данных, чем может храниться в оперативной памяти.

Я нашел ряд решений, которые требуют «рабочего пространства», пропорционального размеру входного сигнала, но ни одно еще не может обойтись без постоянного «рабочего пространства».

Имеет ли какое-либо значение удаление последовательного ограничения? То есть: позволить лексикографически последовательным входам приводить к не лексикографически последовательным выходам: 

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 является наименьшим общим множителем)

Ответы [ 3 ]

6 голосов
/ 19 мая 2009

Я не думаю, что это возможно в общем случае. Если m является степенью p (или наоборот), или если они обе являются степенями общей базы, вы можете сделать это, поскольку каждая группа журнала m ( p) тогда не зависит. Однако в общем случае предположим, что вы конвертируете число a1 a2 a3 ... an. Эквивалентное число в базе p равно

sum(ai * mi-1 для i in 1..n)

Если мы обработали первые i цифр, то у нас есть i th частичная сумма. Чтобы вычислить i+1 'частичную сумму, нам нужно добавить ai+1 * mi. В общем случае это число будет иметь ненулевые цифры в большинстве мест, поэтому нам нужно изменить все цифры, которые мы обработали до сих пор. Другими словами, нам нужно обработать все входных цифр, прежде чем мы узнаем, какими будут конечные выходные цифры.

В особом случае, когда m являются степенями общего основания, или эквивалентно, если log m (p) является рациональным числом, тогда mi будет иметь только несколько ненулевых цифр в базе p в передней части, поэтому мы можем безопасно вывести большинство цифр, которые мы вычислили до сих пор.

2 голосов
/ 20 мая 2009

Я думаю, что есть способ сделать радикальное преобразование ориентированным на поток способом в лексикографическом порядке. Однако того, что я придумал, недостаточно для того, чтобы на самом деле это сделать, и у него есть пара предположений:

  1. Длина позиционных чисел уже известна.
  2. Числа, описанные являются целыми числами. Я не учел, что происходит с математическими и живыми индексами.

У нас есть последовательность значений a длины p , где каждое значение находится в диапазоне [0, m -1]. Нам нужна последовательность значений b длины q в диапазоне [0, n -1]. Мы можем вычислить k -й разряд нашей выходной последовательности b из a следующим образом:

b k = этаж [сумма (a i * m i для i от 0 до p-1) / n k ] мод n

Позволяет переставить эту сумму на две части, разделив ее в произвольной точке z

b k = этаж [(сумма (a i * m i для i в z до p-1) + сумма (a i * м i для i от 0 до z-1)) / n k ] mod n

Предположим, что мы еще не знаем значений между [0, z-1] и не можем вычислить второй член суммы. Нам осталось иметь дело с диапазонами. Но это все же дает нам информацию о b k .

Минимальное значение b k может быть:

b k > = этаж [сумма (a i * m i для i в z до p-1) / n k ] мод н

и максимальное значение b k может быть равно:

b k <= этаж [(сумма (a <sub>i * m i для i в z до p-1) + m z - 1) / n k ] мод n

Мы должны быть в состоянии выполнить такой процесс:

  1. Инициализировать z как p . Мы будем отсчитывать от p по мере получения каждого символа a .
  2. Инициализируйте k индексом самого значимого значения в b . Если мой мозг все еще работает, ceil [log n (m p )].
  3. Считать значение a . Decrement z .
  4. Вычислить минимальное и максимальное значение для b k .
  5. Если min и max совпадают, выведите b k и уменьшите k. Перейти к 4. (Возможно, у нас уже достаточно значений для нескольких последовательных значений b k )
  6. Если z ! = 0, то мы ожидаем больше значений a . Перейти к 3.
  7. Надеюсь, на этом мы закончили.

Я еще не думал, как эффективно вычислить значения диапазона, но я достаточно уверен, что вычисление суммы из входящих символов a может быть сделано гораздо более разумно, чем сохранение всех а . Хотя, без математики, я не буду предъявлять никаких претензий!

0 голосов
/ 24 мая 2017

Да, это возможно

Для каждого I символа, который вы прочитали, вы запишите O символов на основе потолка (длина * log (вход) / log (выход)).

Выделите достаточно места 

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.

...