Какой самый быстрый метод для вычисления подстроки

Question

У меня есть огромная «двоичная» строка, например: 1110 0010 1000 1111 0000 1100 1010 0111 ....

Его длина равна 0 по модулю 4 и может достигать 500 000.

У меня также есть соответствующий массив: { 14 , 2, 8 , 15, 0 , 12, 10 , 7 , ...}

(каждое число в массиве соответствует 4 битам в строке)

Учитывая эту строку, этот массив и число N, мне нужно вычислить следующую подстроку string.substr(4*N, 4), т. Е .:

для N=0 результат должен быть 1110

для N=1 результат должен быть 0010

Мне нужно выполнить эту задачу много раз, и мой вопрос: какой самый быстрый способ вычислить эту подстроку?

Один из методов - вычислить подстроку прямо: string.substr(4*N, 4). Боюсь, что этот не эффективен для таких огромных строк.

Другой метод - использовать array[N].toString(2), а затем обернуть результат нулями, если необходимо. Я не уверен, как быстро это.

Может быть, у вас есть другие идеи?

Answer 1

Откуда взялась строка? Почему бы не представить строку не как двоичный файл, а как шестнадцатеричный, и тогда вы можете хранить каждый раздел из четырех двоичных цифр как один символ? (Очевидно, вы могли бы упаковать его вдвое плотнее, если хотите, или, собственно, сейчас, когда я об этом думаю, 4 раза, поскольку строки Javascript - это 16-битный Unicode). Тогда поиск одной группы будет одним вызовом «charAt ()», и вам просто нужно будет перейти к двоичной форме с помощью таблицы поиска.

изменить & mdash; да ладно, у тебя уже есть массив. В этом случае не выполняйте подстроку вообще; это безумие. Просто возьмите элемент массива и переведите его через массив поиска в строку из 4 двоичных цифр.

Answer 2

Массив уже содержит именно то, что вам нужно, не так ли, за исключением того, что вам нужно распечатать его в двоичном формате. К счастью, sprintf для javascript доступен.

Answer 3

Если вы хотите, чтобы он был дополнен, вы можете сделать это:

var elem = array[N]
var str = "" + ((elem>>3)&1) + ((elem>>2)&1) + ((elem>>1)&1) + (elem&1);

Answer 4

Вы можете представить свою огромную строку в виде Rope структуры данных. Веревка - это в основном бинарное дерево, листья которого представляют собой массивы символов. У узла в дереве есть левый и правый дочерние элементы, левый дочерний элемент - первая часть строки, а правый - конечная часть

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