You are viewing antilamer

The limits of my language mean the limits of my world
 
[Most Recent Entries] [Calendar View] [Friends]

Below are the 20 most recent journal entries recorded in Eugene Kirpichov's LiveJournal:

    [ << Previous 20 ]
    Monday, May 25th, 2026
    10:31 pm
    Музыка
    Тут я соберу пьесы/исполнения, которые нахожу наиболее гениальными и тревожащими мой дух.
    Последнее обновление 06.11.06 22:33 (много чего)Collapse )
    Friday, July 25th, 2014
    9:30 am
    Мой второй доклад с Ulcamp
    Спасибо @r_andrey.

    Millwheel (потоки), Pregel (графы), Dremel (сверхбыстрый колоночный SQL)

    https://www.youtube.com/watch?v=ea6UKvpe9AE&feature=youtu.be
    Tuesday, July 22nd, 2014
    7:19 am
    Пол-видео с Ulcamp
    На просторах интернета найдено видео половины одного из двух моих докладов. Половина довольно-таки self-contained: пропущено введение, а то, что осталось, содержит всё техническое.

    https://www.youtube.com/watch?v=fuErd-O6rCw&feature=youtu.be
    Monday, July 21st, 2014
    12:03 am
    Ulcamp
    Закончился Ulcamp, сижу в Домодедово, сидеть еще 6 часов.
    Впечатления интересные, in no particular order.

    Девиртуализовался с немалым количеством людей, познакомился с еще бОльшим, и погулял с некоторыми из них по Ульяновску в первый день, и со многими - во второй. Сам Ульяновск мне понравился; отдает ностальгическим советским духом.

    Прочитал два доклада - про "архитектуру bigdata processing в Google" (более "популярное" изложение, со сцены) и баркемп про сущность и устройство Millwheel (потоки), Pregel (графы), Dremel (read-only сверхбыстрый SQL по protobuf-ам).

    Мой стиль изложения первого доклада был весьма необычным для меня. Обычно-то я заряжаю телегу на час-полтора с витиеватыми слайдами, а тут даже проектора не полагалось - правда, полагался бумажный флипчарт. Кроме того, незадолго до улькампа я прочитал книжку Made To Stick, которая меня очень впечатлила и, надеюсь, навеки изменила мой стиль донесения информации (а по дороге купил и прочитал еще и Talk like TED - тоже довольно полезно). Постараюсь как-нибудь написать про нее пост - но, как бы там ни было, я задался целью сделать доклад более увлекательным и доступным, чем обычно, с помощью использования историй (хоть каких-нибудь), curiosity gaps, больше конкретики, структурирования тройками, и делания очень явных акцентов на самых важных идеях, выраженных в простой форме. Целью было максимизировать не то, насколько доклад впечатлит слушателей, а то, сколько они из него запомнят.
    За пару недель до улькампа я написал подробный план доклада (это сырые заметки, по которым я готовился), вроде бы соответствующий этим целям, и я даже впервые в жизни отрепетировал доклад. Нарисовал фломастером на флипчарте слайды со смешными картинками (фоток у меня нет, флипчарт я выкинул). Вроде бы получилось прикольно; во всяком случае, мне самому понравилось. Ответил многим на много вопросов про Гугл.

    Узнал, что многие люди занимаются всякими интересными вещами - кто на clojure пишет кровавый энтерпрайз, кто прошивки к раутерам на эрланге и фильтры пакетов на хаскеле, кто видеостриминг с фонтанными кодами, кто так и вовсе суперкомпиляцию встраивает в анализатор IntelliJ IDEA. Это все освежает - а то эдак в гугле-то и зазнаться можно. Из баркемпов, на которых был, понравился доклад про суффиксные массивы от Павла Айткулова, про какую-то security сертификацию платежной системы, про ReactJS. Много других интересных баркемпов я пропустил, т.к. либо готовился к своим докладам, либо спал, либо толковал с кем-нибудь о жизни.

    Режим дня у меня сбился совершенно. Это началось еще в полете с пересадками SFO - LHR - MUC - DME - ULV: было совсем непонятно, какое сейчас время дня, и относительно какой временной зоны этот вопрос вообще следует задавать, так что я кушал по принципу "прошло много времени с предыдущей еды", не особо понимая, это у меня завтрак, обед или ужин. Потом на самом улькампе выяснилось, что многие люди любят ночью потолковать и попеть песни - в первый день я проснулся в 2 часа ночи и так и не заснул, т.к. люди продолжали толковать и петь песни (особенно "о любви"). Во второй день я предусмотрительно лег спать в 7 вечера и проснулся в 8 утра - в общем, скомпенсировал.

    Искупался в Волге разок.

    Выражаю Льву и другим организаторам большой-пребольшой респект за проявленную организаторскую доблесть и за все, что он и они для нас всех сделали.
    Saturday, June 28th, 2014
    10:07 am
    Придумал неожиданно NP-полную задачу
    Disclaimer: задача представляет чисто теоретический / развлекательный интерес. Не для интервью.

    Вы организуете событие, на котором N мест. Люди могут покупать билеты, в т.ч. билеты на несколько мест сразу (например, я могу купить билет на 4 человека).
    Допускается продажа бОльшего числа мест, чем есть. Тогда после окончания продажи билетов проводится лотерея и те, чьи билеты не "выиграли", получают деньги назад.
    Нужно провести справедливую лотерею:
    1) Билет на несколько мест атомарен - он либо "выигрывает" целиком, либо "проигрывает" целиком.
    2) Для каждого человека, который хотел пойти, вероятность пойти должна быть одинаковой.
    3) Эта вероятность должна быть максимальна (иначе можно было бы просто вернуть всем деньги).

    Пример: 8 мест; хотят пойти 12 человек: куплены билеты на 3, 4, 5.
    Одно из оптимальных решений такое: бросить монетку, и либо выбрать {3, 4}, либо {5}.
    Тогда у всех 12 человек вероятность пойти 1/2.

    Заметьте, что {5} не максимально - можно было бы добавить и {3}, но тогда нарушилось бы условие справедливости - у этих троих вероятность была бы 1, а у четверых и пятерых - 1/2.
    Wednesday, June 25th, 2014
    8:07 pm
    Google Cloud Dataflow
    Сегодня на Google IO (живое видео - http://google.com/io) анонсировали проект, над которым наша команда работала последние пару лет (смотря как считать) - Google Cloud Dataflow. Посмотрите - там очень прикольная демка. (перед этим, кстати - анонс cloud debugger и tracing для AppEngine - тоже офигенно крутые вещи).

    Это сервис, который за вас оптимизирует и гоняет ваши распределённые вычисления - и batch, и потоковые. Например, такие (фрагменты кода из демки):
    Pipeline pipeline = Pipeline.create();
    
    PCollection<Tweet> tweets = pipeline.begin()
        .apply(new InputFromPubSub())
        .apply(new TweetTransformer());
    
    tweets.apply(new CalculateSentiment());
    tweets.apply(new CorrelateKeywords());
    
    pipeline.run();
    
    public class CalculateSentiment {
     ...
     return tweets.apply(new ExtractSentiment())
                  .apply(Bucket.By(SlidingWindows.of(3, MINUTES)))
                  .apply(Mean.perKey())
                  .apply(new OutputAverageToBigQuery());
    }
    

    (за объяснением и пр. - смотрите анонс и демку; там минут 15-20, насколько я помню)

    В общем, это гибрид FlumeJava и Millwheel, доступный in the cloud. Вы пишете программу на Java, которая конструирует и просит запустить pipeline, который, например, читает что-нибудь из Cloud PubSub, всячески мурыжит, а результат складывает в BigQuery - мы его оптимизируем (некоторые из оптимизаций описаны в статье про FlumeJava), запускаем на GCE, выделяем ресурсы, распределяем, балансируем, мониторим, восстанавливаем от крахов и пр.

    MapReduce - тривиальный частный случай того, что можно делать с помощью Dataflow, выглядящий примерно как .apply(new MyMapper()).groupByKey().apply(new MyReducer()).

    В ближайшие 9 вечера по московскому времени (10 утра по тихоокеанскому) на http://google.com/io можно будет наблюдать ещё одну демку этого продукта - сессия называется "The Dawn of Fast Data".

    Моя роль в этом проекте - я один из разработчиков фреймворка, на котором держится этот продукт и другие связанные с ним внутренние инструменты обработки данных Гугла. "Клаудных" частей я не касался, но наблюдал за их разработкой, и они очень круты - удобство мониторинга, например, это чуть ли не главная selling point. Ещё одна главная selling point - auto-everything; нулевая необходимость в настройке (выборе количества машин, шардинге, упаси боже каких-нибудь размеров буферов, и пр.)

    Пока что проект в режиме private beta. Через какое-то время будет limited preview, через какое - не могу сказать.
    Saturday, June 21st, 2014
    4:30 pm
    Купил билеты на Ulcamp
    Спустя $2200, 2 зафайленных бага в Google Flight Search, 2 звонка в банк, пару регистраций на сайтах авиакомпаний, пару страниц заметок, часов 7 времени и пару унций нервных клеток...
    * Вылетаю из SFO 15го июля, лечу через DME, торчу там 6 часов, прилетаю в ULV утром 17го
    * Улетаю из ULV вечером 20го, лечу через DME, торчу там 7.5 часов, прилетаю в SFO вечером 21го
    Осталось, видимо, найти гостиницу на ночь 17-18 в Ульяновске, и купить билет собственно на сам Ulcamp.
    Sunday, June 15th, 2014
    10:15 am
    Юля написала, как к нам родители ездили.
    В апреле к нам на 3 недели приезжали родители (моя мама и Юлин папа); мы взяли по 2 недели отпуска с перехлёстом в одну, и водили их по разным местам нашего загнивающего запада.

    http://grrrl.livejournal.com/12773.html

    Показали почти всё, что тут знаем интересного (кроме мест, куда надо ехать более 2 часов - в т.ч. Йосемити, например, не показали).
    Поэтому пост может быть особенно полезен начинающим посетителям Долины для ответа на вопрос "что у вас тут интересного и куда можно съездить".
    Saturday, June 14th, 2014
    9:54 pm
    SFO <=> Ulcamp
    Кто летал из Долины на http://ulcamp.ru/ - поделитесь планом полёта?

    Momondo и Google Flights показывают какую-то сверхдорогую хрень по запросу SFO/ULV; если искать SFO/VKO и VKO/ULV отдельно, то я что-то приемлемое нашёл, но хотелось бы совета от опытных путешественников. Например, 3 часа во Внуково на то, чтобы слезть с международного рейса и залезть на российский (и наоборот) - достаточно?

    P.S. Skyscanner находит вдвое дешевле, чем Momondo и Google, но всё равно гораздо хуже, чем если искать вручную.

    P.P.S. А кто из френдов на Ulcamp едет вообще?
    10:15 am
    Global Sensitivity Analysis
    Рассказал коллегам вчера вводную презентацию про global sensitivity analysis, про который я ранее писал в ЖЖ (http://antilamer.livejournal.com/458540.html).

    Презентация на Google Slides
    Saturday, June 7th, 2014
    10:09 pm
    Две разных музыки
    Поскольку всё, что я делаю на работе, пока секретно, то вот вам музыки.

    Charles Valentin Alkan


    http://en.wikipedia.org/wiki/Charles-Valentin_Alkan

    Композитор и пианист-виртуоз из 19 века, современник и друг Листа и Шопена. Лист, утверждается, считал его более крутым пианистом, чем самого себя.

    Мне удивительно, что я о нём услышал впервые только в этом году (YouTube порекомендовал); да и то, первое знакомство было на менее интересных для меня пьесах, например Le Chemin de Fer, Le Preux. У него довольно много похожих на эти пьес - виртуозных и требующих от пианиста как минимум нечеловеческой выносливости, с довольно равномерной текстурой или в форме вариаций. Они оригинальны и уж точно я бы по ним не сказал, что они написаны во времена Шопена и Листа - кажутся более современными. Однако долго их слушать я не могу - становится скучно.

    Потом в один прекрасный момент ютуб порекомендовал какой-то другой кластер его музыки, и тут уже впечатление совсем другое. Главное произведение его жизни, как я понимаю, "12 этюдов в минорных тональностях op.39"; этюды 4-7 из них коллективно названы "Симфонией", а 8-10 - "Концертом". И то, и другое - по-моему, потрясающая музыка. Enjoy:

    Симфония (в исполнении Marc-Andre Hamelin):
    Часть 1. Allegro http://www.youtube.com/watch?v=o6Z5P1gAjyE
    Часть 2. Marche Funebre http://www.youtube.com/watch?v=9z3DRIargH0
    Часть 3. Menuet http://www.youtube.com/watch?v=FvxU-ur06V8
    Часть 4. Finale (Presto) http://www.youtube.com/watch?v=Q6qh96b2D6A

    Концерт (в исполнении Jack Gibbons):
    Часть 1. http://www.youtube.com/watch?v=6-YXdfKK4J0
    Часть 2. http://www.youtube.com/watch?v=4hQ5gJ4zrXI
    Часть 3. http://www.youtube.com/watch?v=o9XlvyU1YrI

    Не могу даже посоветовать, с чего начать, т.к. в обоих этих произведениях все части исключительно мощные. Ну, начните, наверное, с концерта (часть 1).

    Выяснилось, впрочем, что "12 этюдов в мажорных тональностях" тоже очень круты; по-моему, не хуже Шопеновских.
    Вот парочка; оба из них лучше слушать целиком:
    Номер 3 http://www.youtube.com/watch?v=t6JISkidmKo
    Номер 7 "Пожар (поджог?) в соседней деревне" http://www.youtube.com/watch?v=2XMSxnAqLJc

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

    Yellow Magic Orchestra


    And now for something completely different: _navi_ прислал ссылку на Thousand Knives of Ryuichi Sakamoto.

    Мне и так уже начинала понемногу нравиться электронщина, например альбом Daft Punk "Random access memories" мне очень даже нравится - но эти thousand knives меня просто сразили наповал. Это, по-моему, на голову выше всей остальной электронной музыки, что я пока слышал. Учитывая, что это 1978 год - просто невероятно. Потыкайте в разные места альбома, послушайте - it just keeps getting better and better. Я бы, честно говоря, поставил эту музыку в один ряд по качеству, оригинальности и частично стилю с минималистами, что ли, вроде Гласса, Райха и Райли.

    В 1978 году Sakamoto записал этот альбом, а в 1979 создал группу Yellow Magic Orchestra, и их первый альбом - на мой вкус, шедевр того же калибра.
    Cosmic Surfin'
    Tong Poo
    Весь альбом

    Мне тут интересно буквально всё - и гармония (и проскакивающие микротональные куски), и форма, и использованные выразительные средства. Поразительно, как из такого "несерьёзного" материала (на первый взгляд похоже на музыку к 8-битной приставке) получается сложная и завораживающая музыка.
    Thursday, April 24th, 2014
    8:45 am
    Об p-value
    Вопрос на mathoverflow про частые ошибки интерпретации статистики.

    Начитавшись комментариев к этому вопросу, я, наконец, просёк одну из фишек p-value; чего и вам советую:

    p-value - величина, получаемая при попытке проверить некоторую "альтернативную" гипотезу (например, "у меня рак") относительно "базовой" ("я здоров") с помощью теста (например, концентрации каких-нибудь штук в крови). Предполагается, что известно, что чем более экстремален результат теста, тем менее вероятна базовая гипотеза.

    p-value говорит, насколько вероятен был бы полученный результат теста, если бы была верна базовая гипотеза. (плюс ещё несколько предположений, которые я пока что не постиг интуитивно)
    Например, если тест на рак отверг гипотезу о здоровье на p-value=0.01, это означает, что лишь у 1% здоровых людей так много штук в крови.

    Многие неправильно интерпретируют p-value: мол, p-value - это вероятность истинности базовой гипотезы.
    Nothing could be further from the truth.

    Вот два утверждения:
    1) Лишь у 1% здоровых людей в крови так много штук
    2) Лишь 1% людей, у которых в крови так много штук, здоровы (т.е. те, у кого много штук, с вероятностью 99% больны)

    p-value говорит о первом из них. А разница между ними - такая же, как между "70% алкоголиков - мужчины" и "70% мужчин - алкоголики" (на самом деле менее 18% в США).

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

    Например, предположим, что в целом по населению частота интересующей нас формы рака - 1 на миллион.
    Тогда, если тест сказал "лишь у 1% здоровых людей так много штук, как у вас", то это значит одно из двух:
    1) я болен (т.е. я 1 человек из миллиона)
    2) я один из тех 1% здоровых людей, у которых так много штук в крови (т.е. я 1 человек из 100)

    Второе, естественно, на несколько порядков более вероятно; и вероятность моей болезни даже с учётом теста всё равно примерно 1 на миллион.

    p-value применяется и для других тестов, например, для проверки наличия связи между переменными в выборке, и т.п.

    Вот ещё статья про 12 ошибок понимания p-value, включая описанную и другие более коварные: http://www.perfendo.org/docs/BayesProbability/twelvePvaluemisconceptions.pdf - думаю, я до сих пор делаю некоторые из них.
    Saturday, February 15th, 2014
    5:44 pm
    Sunday, February 9th, 2014
    12:43 am
    Global sensitivity analysis
    Тоже тут напишу.

    http://www.amazon.com/Global-Sensitivity-Analysis-The-Primer/dp/0470059974 и моя рецензия на неё.

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

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

    Много очень красивых методов - например, FAST (Fourier Amplitude Sensitivity Test), или group sampling (поиск значимых среди 1000 параметров за менее чем 1000 измерений).

    Ну и вообще, книжка очень хорошо написана, легко читается и требует лишь минимальных знаний статистики и линейной алгебры.
    12:28 am
    Про открытие олимпиады
    Написал уже в паре других мест; соберу высказанные мысли, наконец, и тут.

    Открытие Олимпиады сразило меня наповал.

    Никогда не думал, что буду цитировать "Спутник и погром" - но, если отбросить национализм, чувак всё правильно написал. Они показали всё лучшее из культуры и истории России, чем можно гордиться и к чему хочется принадлежать - Толстой, Чайковский, Менделеев, супрематисты, Шнитке и Стравинский, "ёжик в тумане", лучшее из советской эстетики, способность к нечеловеческой работоспособности, не перечислять же всё... - и кажется, создали что-то новое: сама эстетика мероприятия показалась мне современной, оригинальной, но в то же время глубоко русской; у меня проскакивало ощущение "да, именно таким мог бы быть образ современной России" - в смысле, не образ как фотография, а образ как что-то, с чем можно себя идентифицировать и к чему стремиться.

    И главное - как выразились и "Спутник", и Эхо - показали Россию, в которой можно жить и за которую стоит умирать, без мракобесия, пропаганды, ненависти.

    Я уже довольно давно не чувствовал ни гордости, ни особой надежды по отношению к будущему России - мне казалось, что на ближайшие годы она обречена тонуть в продажных чиновниках и законодательных высерах Милоновых с Мизулиными, пусть даже и более или менее улучшая экономическое положение. А тут - собрались вместе множество талантливых людей, которым было не всё равно, и совершили чудо. Для меня было очень важно осознать, что такое сейчас вообще возможно.
    Wednesday, January 15th, 2014
    8:42 pm
    Thursday, January 2nd, 2014
    9:39 pm
    Settling debts
    Сегодня с утра подумал было, что, наверное, settle debts - хорошая задачка на интервью.

    Формулировка задачи: есть список транзакций "кто кому сколько одолжил". Надо сделать так, чтобы никто был никому не должен, за минимальное количество транзакций.
    Например, если я должен Маше 1 рубль, а Маша должна Пете 1 рубль, то я могу отдать 1 рубль Пете.

    Однако, по мере того, как я размышлял, какого, собственно, решения я ожидаю от кандидата, мне всё более и более казалось, что то ли я дурак, то ли задачка не так уж хороша для интервью.

    Казалось бы, простая задача; должно быть если не тривиальное или хотя бы жадное решение, то уж, в худшем случае, решение через какой-нибудь min-cost max-flow.

    Однако не тут-то было: задача NP-трудна (слайд 15) - тривиально сводится к KNAPSACK.
    Sunday, December 29th, 2013
    3:27 pm
    2013
    2013й был крайне спокоен и небогат на события.
    Я пилил MapReduce; сделал одну большую и клёвую фичу и несколько вещей поменьше, вот это всё.
    Несколько месяцев играли с _navi_ и еще одним гуглером гитарные трио по понедельникам, потом перестали.
    Заняли 19е место на ICFPC (10 в lightning).
    Повидали национальные парки Юты и Аризоны; Гранд Каньон даже два раза.
    Юля с октября начала работать в LinkedIn.
    Собственно, и всё. Как-то год пролетел очень быстро и совершенно незаметно. Я думаю, это скорее плохо, чем хорошо - эдак вся жисть пролетит.

    Надеюсь, 2014й будет поинтереснее. Надо, что ли, найти какие-нибудь митапы, повыступать там, или найти какое-нибудь место, куда меня пустят попреподавать.
    10:28 am
    Два подхода к random testing, или QuickCheck сбоку
    Положим, вы написали какую-нибудь хитрую структуру данных - скажем, interval heap, ну или просто heap.

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

    Есть два принципиально разных подхода в духе "нагенерировать тесткейсов":
    1) Генерировать случайные последовательности операций: Начать с пустой структуры и много раз применять к ней последовательность случайно сгенерированных операций, проверяя на каждом шаге, что семантика операции соблюдается (например, параллельно применяя те же операции к вспомогательной простой и неэффективной структуре с той же семантикой, или как-нибудь ещё).
    Альтернатива 1.1) Генерировать не много независимых последовательностей операций, а их дерево - это возможно, если структура чисто функциональная (тогда можно к одному и тому же экземпляру применить несколько операций, не делая полную копию).
    2) Генерировать случайные валидные состояния и применять к ним одну случайную операцию. В случае двоичной кучи, например - сгенерировать все возможные массивы длины N с числами от 1 до N с повторами, отфильтровать те, что являются кучами (или сгенерировать сразу только кучи - это не очень сложно), и про каждую такую кучу проверить, что применение к ней insert соблюдает семантику insert, а применение removeMax - семантику removeMax.

    Утверждается, что подход 2 сложнее в реализации, но гораздо эффективнее - намного меньше пространство перебора для достижения того же покрытия, и вот почему:
    * Для достижения каких-то "сложных" для алгоритма состояний может потребоваться большое количество операций.
    * В случае подхода 1 невозможно даже оценить, какая часть валидных состояний и комбинаций "состояние + операция" была покрыта.
    * В случае подхода 1 одни и те же состояния могут быть рассмотрены много раз - 1.1 уменьшает этот эффект, но не убирает его полностью. Можно, конечно, запоминать какие-нибудь хеши рассмотренных состояний, но на это нужна память.
    * В случае подхода 2 можно оттестировать корректность разных операций по отдельности.
    * В случае подхода 2, если найдена ошибка, то понятно, что она именно в реализации применённой операции (ну или в генераторе), а не в какой-то из ранее применённых.

    Понятно, что сама реализация подхода 2 может содержать баги, но если присыпать её assert'ами, и если она всё же намного проще тестируемого кода, то это может быть не так страшно.

    Пример реализации подхода 2: https://github.com/jkff/gkutil_java/commit/fcbecdb44a3ebb448e88713d919d65084e2e5994 [я это написал just for lulz, когда искал для stream-lib реализацию interval heap, нашёл gkutil_java и нашел в коде глазами багу, которая почему-то не ловилась имевшимися тестами - автор подтвердил наличие баги]

    Пытливый читатель разглядит, что подход 2 близок к QuickCheck или SmallCheck, правда, я редко видел сильно нетривиальные генераторы входов для QuickCheck/SmallCheck.
    Tuesday, November 26th, 2013
    9:01 am
    Задачка
    Пусть хочется хранить в памяти большое количество строк среднего размера (например, несколько миллионов строк по 10-20кб). Известно:
    0) Хочется сэкономить память и хранить каждую строку как можно более сжатой.
    1) Набор всё время меняются: добавляются новые строки, удаляются старые
    2) Каждая строка сама по себе сжимается, но не очень
    3) Многие строки очень похожи друг на друга (но есть несколько "классов эквивалентности"); при сжатии нескольких строк сразу, сжатие получилось бы в несколько раз лучше.

    Иными словами, хочется реализовать какой-то вот такой интерфейс:
    interface CompressedSet {
      Handle Add(String s);
      String Get(Handle h);
      void Release(Handle h); // Get(h) will not happen again
    }
    


    Как быть?

    Приходит в голову следующее:
    1) Хранить небольшими коллективно сжатыми группами по примерно K: Add находит неполную группу и пересжимает ее с добавлением этой строки; Get разжимает всю группу и достает из нее нужное; Release пересжимает группу без этой строки.
    2) Завести какой-нибудь shared dictionary-based компрессор, у которого dictionary с подсчётом ссылок. Есть такие?

    P.S. Задачка скорее праздная; некоторые из предположений в реальности нарушаются. Но интересно же!
[ << Previous 20 ]
Guitar Delicacies   About LiveJournal.com