Оптимизация длинных списков логических значений на JavaScript

Очень часто в веб-разработке (и в программировании вообще) необходимо сохранить длинный список логических значений (yes/no, true/false, checked/unchecked и подобные) в виде строк. К примеру, вы захотите записать такие данные с помощью localStorage, в cookie, или отправить их в теле HTTP запроса. У меня возникала такая необходимость сотни раз.

Использование массива

У нас есть два разумных способа организации логических данных в массиве. Первый — хранить значения true/false:

[false, true, true, false, false, true, true]

Второй — хранить массив нулей и единиц:

[0, 1, 1, 0, 0, 1, 1]

Какой бы способ мы не выбрали, нам в любом случае придется конвертировать такой массив в строку, и затем конвертировать эту строку обратно в массив при чтении данных. Для этого мы можем воспользоваться старыми методами Array#join() (или Array#toString()) и String#split(), или же более изящными JSON.stringify() и JSON.parse().

Если мы пойдем по пути JSON, то код будет немного короче, хотя использовать в данном случае JSON — все равно что резать хлеб бензопилой. В некоторых браузерах будет заметно влияние такого подхода на производительность, также это немного ухудшит поддержку старых браузеров.

Основным недостатком использования строк на основе массивов является их размер в байтах. Если выбрать вариант с хранением массива нулей и единиц, то придется использовать 2 символа на значение (или, если быть точным, 2n-1, по одному разделителю после каждого значения, кроме последнего):

[0, 1, 1, 0, 0, 1, 1].toString().length // 13 символов для 7 значений

Таким образом, для 512 значений необходимо 1023 символа или 2 КБ, потому что JavaScript использует UTF-16.

Если мы будем хранить массив значений true/false, то все становится еще хуже:

[false, true, true, false, false, true, true].toString().length // 37 символов для 7 значений

Это 5 или 6 символов на значение, от 2560 до 3072 символов на 512 значений (от 5 до 6 КБ).

JSON.stringify() расходует еще по 2 символа в каждом случае на открытие и закрытие скобок, но его преимущество в том, что в результате JSON.parse() мы получим исходные типы значений вместо строк.

Использование строки

Строка позволяет сэкономить символы, т. к. нет необходимости использовать разделители. Например, если мы выбрали цифровой подход и храним строку '01001101010111', то мы используем один символ на значение, что гораздо лучше подхода с использованием массивов. Поместить наши значения в массив можно с помощью String#split():

'01001101010111'.split(''); // ['0','1','0','0','1','1','0','1','0','1','0','1','1','1']

Также, можно просто перебрать символы в строке с помощью цикла, используя string.charAt(i) или даже строковые индексы (string[i]), если не нужно заботиться о поддержке старых браузеров.

Использование битовых полей

Вы тоже подумали о двоичном коде, рассматривая предыдущий пример? Концепция битовых полей достаточно популярна в других языках программирования, но не в JavaScript. В двух словах, битовые поля используются для упаковки множества логических значений в биты логического представления числа. К примеру, у нас есть 8 значений (true, false, false, true, false, true, true, false). В двоичном коде это будет 10010110, 150 в десятичном и 96 в шестнадцатеричном. Таким образом, используется 2 символа вместо 8, экономия 75%. Одно число в шестнадцатеричном представлении точно соответствует 4 битам. (Потому что 16 = 24. В системе счисления с основанием 2n, можно упаковать n битов в каждое число.)

Таким образом, вместо хранения целой строки и использования одного символа на значение, мы можем пойти более умным путем и сконвертировать такую строку в шестнадцатеричное число. Как это сделать? Вот так:

parseInt('10010110', 2).toString(16); // возвращает '96'

Как вернуть данные в читабельный вид? Проще некуда:

parseInt('96', 16).toString(2); // возвращает '10010110'

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

Можно ли сделать еще лучше?

На самом деле можно! Зачем конвертировать в шестнадцатеричную систему счисления, которая использует только 6 букв латинского алфавита из 26? Метод Number#toString() позволяет использовать base 36 – систему счисления с основанием 36 (при >= 37 получаем RangeError), которая эффективно использует все буквы из латинского алфавита. Таким образом, мы можем сжать 32 значения в 6 символов, что означает экономию в 81.25% по сравнению с методом использования простой строки. Код по-прежнему остается простым:

parseInt( '1001011000', 2).toString(36); // возвращает 'go' (вместо '258' в шестнадцатеричном варианте)

parseInt('go', 36).toString(2); // возвращает '1001011000'

Многие на этом и остановятся. Но более любознательные скажут: «У нас же еще есть заглавные буквы и другие символы, мы до сих пор не используем весь потенциал!» И они будут правы. Неспроста при открытии бинарного файла в текстовом редакторе, вы видите на экране странные символы, перемешанные с цифрами и буквами — заглавными и строчными. Каждый символ в кодировке UTF-16 занимает 2 байта (16 бит), это означает, что при использовании верного алгоритма сжатия, мы сможем получить экономию в 93,75%.

Проблема в том, что в JavaScript нет встроенного функционала для использования такого алгоритма, поэтому код становится несколько сложнее.

Упаковка 16 значений в один символ

Нам понадобится метод String.fromCharCode. Он принимает численное значение до 65535 и возвращает символ (а при значениях больше 65535, возвращает пустую строку).

Разделим нашу строку на фрагменты по 16 символов каждый. Можно сделать это с помощью .match(/.{1,16}/g). Весь код будет выглядеть так:

function pack(/* string */ values) {

var chunks = values.match(/.{1,16}/g), packed = '';

for (var i=0; i < chunks.length; i++) {

packed += String.fromCharCode(parseInt(chunks[i], 2));

}

return packed;

}

function unpack(/* string */ packed) {

var values = '';

for (var i=0; i < packed.length; i++) {

values += packed.charCodeAt(i).toString(2);

}

return values;

}

Не так уж и сложно, правда? Эти несколько строк кода позволяют упаковать вышеупомянутые 512 значений в (барабанная дробь) 32 символа (64 байта)! Гораздо лучше изначальных 2 КБ (с хранением в простом массиве), не так ли?

Ограничения

У чисел в JavaScript есть свои границы. Для методов, описанных здесь, которые включают промежуточные преобразования в числа, предел устанавливается на 1023 логических значениях, потому что parseInt('1111…1111', 2) вернет Infinity при большем количестве. Это ограничение не накладывается на последний способ, потому что мы преобразуем блоки битов вместо всей строки. И, разумеется, это ограничение не накладывается на первые два способа (массив и строка) потому что они вообще не включают в себя упаковки значений.

«Мне кажется, мы зашли слишком далеко»

Да, в некоторых случаях такая оптимизация может быть излишней. Но если необходимо сохранить кучу логических значений в ограниченном месте, которое поддерживает только строки, указанные способы окажутся очень кстати. И оптимизация чего-либо, что с большой частотой передается по проводам, никогда не лишняя. Например, cookie передаются почти в каждом запросе, поэтому они должны быть настолько малыми, насколько возможно. Другой пример — многопользовательские онлайн игры, для которых реакция сервера должна быть молниеносной, иначе играть в такую игру будет совсем не весело.

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

Перевод. Оригинал (en): Optimizing Long Lists Of Yes/No Values With JavaScript

Комментарии:

1. У нас есть огромная колбаса, состоящая из «1010001010010101010...»

Если стоИт задача перевести всё это в строку, то «стандартным» способом является нарезать эту колбасу на дольки по 6 бит и затем испольовать полученное число как индекс в массиве. Примерно так:

base64array = ['A','B','C'...];

kolbasa = '1010001010010101010...';

out = "";

for(i=0; i<kolbasa.length;i+=6) {

out += base64array[ parseInt( kolbasa.substring(i,i+7), 2) ];

}

на выходе получается примерно такое

«TWFuIGlzIGRpc3Rpbmd1aXNoZWQsIG5vdCBvbmx5IGJ»

2. Проверяем:

parseInt('001', 2).toString(16)

облом: «1»

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