Нередко случается, что какие-то данные программа загружает в память и оставляет их там надолго (а то и до конца работы) в неизменном виде. При этом используются структуры данных, оптимизированные как для чтения, так и для записи. Например, вы вычитываете из базы Ensembl список идентификаторов всех генов человека (включая всякие микроРНК и т. д. — всего чуть больше 50000). Если их прочитать в стандартный ArrayList, то на 32-битной HotSpot вы потратите чуть больше 4 мегабайт. Можно ли сэкономить память, зная, что коллекция больше не будет меняться?
Читать полностью »
Рубрика «строки» - 4
Строковые коллекции только для чтения: экономим на спичках
2012-06-04 в 14:11, admin, рубрики: java, read-only, коллекции, оптимизация памяти, списки, строки, метки: java, read-only, коллекции, оптимизация памяти, списки, строкиRopes — быстрые строки
2012-05-29 в 7:59, admin, рубрики: rope string, Алгоритмы, строки, строки на деревьях, метки: rope string, строки, строки на деревьях Здравствуй.
Большинство из нас так или иначе работает со строками. Этого не избежать — если ты пишешь код, ты обречен каждый день складывать строки, разбивать их на составные части и обращаться к отдельным символам по индексу. Мы давно привыкли что строки — это массивы символов фиксированной длины, а это влечет за собой соответствующие ограничения в работе с ними.
Так, мы не можем быстро объединить две строки — для этого нам потребуется сначала выделить необходимое количество памяти, а потом скопировать туда данные из конкатенируемых строк. Очевидно, что такая операция имеет сложность порядка О(n), где n — суммарная длина строк.
Именно поэтому код
string s = "";
for (int i = 0; i < 100000; i++) s += "a";работает так медленно.
Хочешь выполнять конкатенацию гигантских строк быстро? Не нравится, что строка требует для хранения непрерывную область памяти? Надоело использовать буферы для построения строк?
Полиномиальные хеши и их применение
2012-04-23 в 19:37, admin, рубрики: Алгоритмы, олимпиадные задачи, поиск подстроки в строке, сравнение строк, строки, хеширование, метки: Алгоритмы, олимпиадные задачи, поиск подстроки в строке, сравнение строк, строки, хешированиеЗдравствуй. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.
Введение
Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p2s2 +… + pn-1sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).
Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Читать полностью »