Что самый быстрый метод должен вычислить подстроку
У меня есть огромная "двоичная" строка, как: 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) и затем перенесите результат с нулями в случае необходимости. Я не уверен, как быстро это.
Можно ли быть, имеют какие-либо другие идеи?
4 ответа
Откуда взялась строка? Почему бы не представить строку не как двоичную, а как шестнадцатеричную, и тогда вы можете сохранить каждую секцию из четырех двоичных цифр как один символ? (Вы могли бы, очевидно, упаковать его вдвое плотнее, если хотите, или, на самом деле, теперь, когда я думаю об этом, 4 раза, поскольку строки Javascript - это 16-битный Unicode). Тогда для поиска одной группы будет достаточно одного вызова «charAt ()», и вам просто нужно будет развернуть ее до двоичной формы с помощью таблицы поиска.
править - да ладно, у вас уже есть массив. В этом случае вообще не выполняйте работу с подстрокой; это безумие. Просто возьмите элемент массива и преобразуйте его через поисковый массив в строку из 4-х двоичных цифр.
Можно рассмотреть возможность представления вашей огромной строки в виде структуры данных Rope. Веревка - это двоичное дерево, листья которого представляют собой массивы символов. Узел в дереве имеет левого и правого ребенка, причем левый ребенок является первой частью строки, а правый - последней.
Благодаря использованию веревки, операции с подстроками становятся логарифмически сложными, а не линейными, как для обычных строк.
Массив уже содержит именно то, что вам нужно, не так ли, за исключением того, что вам нужно вывести его в двоичном формате. К счастью, существует sprintf для javascript.
Если вам нужна прокладка, вы можете сделать так:
var elem = array[N]
var str = "" + ((elem>>3)&1) + ((elem>>2)&1) + ((elem>>1)&1) + (elem&1);