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

У меня есть пара недавних примеров, которые могут дать представление об этом опыте.

Приложение, над которым я работаю, по разным причинам иногда должно иметь возможность взять идентификатор блока переписи - строку из 15 символов - и сопоставить его с идентификатором избирательного округа, который его включает - 9–12 символьная строка. Отдел переписи населения публикует эту информацию и размещает ее в свободном доступе на своем веб-сайте. Мы импортировали эту информацию и сохранили ее, вероятно, в самом простом представлении JSON / JavaScript, которое вы можете себе представить - просто объект с идентификаторами блоков в качестве ключей и идентификатором избирательного округа в качестве значений. Обработка, необходимая для сопоставления, должна загрузить файл JSON, а затем просто использовать объект для сопоставления от ключа к значению.

Эти файлы хранятся по штатам, поэтому в худшем случае в Техасе почти один миллион блоков переписи, и эта структура составляет почти 30 мегабайт при хранении на диске. В памяти он расширяется до 50 МБ. JSON (нотация объектов JavaScript - способ взять объект JavaScript и передать его в виде строки или сохранить в файле) может быть довольно многословным, поэтому иногда он может уменьшаться при импорте, но в этом случае файл в основном представляет собой просто строки, поэтому на самом деле расширяется после анализа и сохранения в памяти.

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

Теперь снова посмотрев на Техас, этот файл JSON размером 30 МБ на самом деле был всего 4 МБ при сжатии, как он хранился и передавался. Сжатие - это хороший быстрый способ получить некоторую интуицию о том, что такое «реальное» информационное содержание некоторого блока данных. Сжатая форма может быть не лучшей для обработки, но она дает вам представление о том, насколько избыточны данные. В этом случае имеется тонна избыточности. Эта избыточность довольно очевидна, если подумать о содержании. Каждый избирательный округ состоит из примерно 65 переписных блоков, поэтому каждое значение (идентификатор избирательного округа от 9 до 12 знаков) повторяется в среднем 65 раз. Идентификаторы блоков на самом деле находятся в очень структурированной форме, где первые 2 символа - это идентификатор штата (так же они одинаковы для всех значений в файле, организованном по штатам), следующие 3 символа - это идентификатор округа, затем переписной участок, группа блоков переписи. и, наконец, индивидуальный номер блока.

Учитывая всю эту избыточность, мне казалось вероятным, что мы сможем придумать гораздо более плотную структуру данных, которую можно было бы хранить, передавать, загружать и использовать непосредственно в этом плотном представлении без необходимости взрывать его в памяти. Недавно я увлекся программированием на JavaScript, когда мне нужно было что-то ускорить или уменьшить использование памяти (часто одно и то же), чтобы определить, где наивное представление данных JavaScript излишне раздуто, и вместо этого использовать компактное двоичное представление. Может быть, дело в моих корнях C / C ++.

В этом случае у меня было две области, на которых нужно было сосредоточиться: как хранить значения и как хранить ключи. Поскольку я знал, что значения дублируются в среднем 65 раз, тривиальным решением было бы просто сохранить копию всех уникальных строк и сохранить ссылку на уникальную строку, а не на буквальную строку (компиляторы и языки часто делают это автоматически внутри для некоторых части вашей программы). Я подумал, что мог бы сделать немного лучше, поскольку значения также имеют тонну внутренней избыточности - многие значения имеют одну и ту же первую часть, а затем многие значения имеют одни и те же последние несколько отличительных символов. Простым решением было просто разбить строки на две части (динамически) и найти разбиения, которые минимизировали хранилище строк. По сути, это приближение к тому, что делает общий алгоритм сжатия (поиск общих общих последовательностей и затем компактных ссылок на них).

Для ключей, когда у вас есть большая избыточность в вашем ключевом пространстве, trie - хороший выбор. Кодирование было в основном связано с проектированием того, как упаковать его в единый блок данных, используя смещения от начала буфера, а не указатели для обхода структуры данных. Как обычно, когда вы начинаете экспериментировать с памятью хитрыми способами, для этого потребовалось немного тестирования и отладки, чтобы начать работать.

Я был очень доволен окончательными результатами. Этот техасский файл оказался компактным буфером размером 2,7 МБ, который можно было напрямую загрузить в память в виде одного блока и использовать без дальнейшего преобразования. Он был сжат до менее 1 МБ для хранения и передачи (что утверждало, что в моем решении было еще больше возможностей для улучшения). Но у меня уже было 20-кратное улучшение использования памяти и значительные улучшения в хранении и передаче данных, поэтому я остановился на этом.

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

Я скажу, что общая проблема «компактных словарей» (которые были частным случаем) - настолько хорошо изученная проблема, что я чувствовал себя немного виноватым, когда писал что-то с нуля. Наверняка есть что-нибудь, что я мог бы схватить с полки? Поиск ничего не дал, поэтому я был на пенсии; Я мог подавить чувство вины и просто получать удовольствие, решая проблему.

Мой второй пример немного отличается. В данном случае было весело узнать что-то новое и затем эффективно использовать.

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

Самый простой способ повысить производительность - взять формы с высоким разрешением, предоставленные отделом переписи, и упростить их, удалив точки. Это помогает везде (при использовании памяти и на каждом этапе обработки), поэтому это очевидная вещь, на которой нужно сосредоточиться. Дополнительные очки либо не имеют визуального значения при отображении на экране компьютера, либо не имеют никакого значения, потому что они не меняют способ взаимодействия пользователя с приложением. Основные формы переписи должны различать, находится ли отдельный дом в одном переписном блоке или в другом, но для наших целей это хорошо работает, поскольку никакие другие наши данные (перепись и выборы) не доступны в этом разрешении.

Итак, упрощение формы - наша первая проблема.

Вторая проблема заключается в том, как объединить набор фигур в одну форму или, в более общем смысле, «объединение многоугольников». Основная проблема, с которой мы столкнулись, - это взять набор форм избирательных округов и объединить их в единую форму Конгресса (или законодательного органа штата). Объединение полигонов - это хорошо изученная проблема в компьютерной графике, но общее решение связано с интенсивным использованием как памяти, так и обработки, и когда мы интегрировали решение с открытым исходным кодом в наше приложение, это оказало значительную нагрузку на интерактивную производительность приложения. Мне пришлось построить на его основе сложный асинхронный механизм разделения работы, чтобы он не блокировал наше приложение на несколько секунд.

Третья проблема заключалась в том, как определить, являются ли две фигуры смежными. Это основа того, как мы анализируем план перераспределения границ. В нашем приложении это происходит «в автономном режиме» для построения графа смежности. Это не должно было быть особенно быстрым, но изначально было решено с помощью набора инструментов, которые были отделены от нашего основного набора инструментов, поэтому у нас была мотивация попытаться унифицировать это.

Есть много алгоритмов упрощения на выбор, но дополнительная проблема в нашем случае заключается в том, что у нас есть набор фигур, которые мы вместе рисуем на поверхности. Фигуры покрывают поверхность, и когда вы упрощаете, вы можете столкнуться с двумя связанными проблемами, если вы примете разные решения по упрощению для двух фигур, лежащих рядом друг с другом. Принятие различных решений происходит легко, потому что одна фигура может иметь одну непрерывную линию, в то время как на другой стороне может быть несколько фигур, граничащих с этой линией. Сохранение целостности этих меньших форм означает сохранение большего количества точек, в то время как большая форма может упростить и удалить эти точки. Когда вы принимаете различные решения по упрощению, вы либо оставляете дыры на карте, когда рисуете смежные фигуры, либо у вас есть перекрывающиеся фигуры, и это вызывает визуальные аномалии при заливке фигур с частичной непрозрачностью (потому что перекрывающиеся области прорисовываются дважды и выглядят темнее ).

Пробелы также вызывают проблемы, когда вы хотите объединить формы (проблема объединения многоугольников, о которой я упоминал выше), потому что вы в конечном итоге генерируете формы с множеством маленьких аномальных отверстий, которых на самом деле нет в реальных данных. Это как удорожает обработку, так и вносит визуальные и аналитические аномалии.

Исследуя это, я наткнулся на библиотеки TopoJSON, написанные Майком Бостоком. Майк довольно хорошо известен в сообществе специалистов по визуализации, ранее занимался новаторской работой в New York Times и соавтором важной библиотеки визуализации с открытым исходным кодом, d3.js. Изучая это, я узнал что-то новое.

Библиотеки TopoJSON используют другой подход к проблемам, с которыми я столкнулся. Основная идея заключается в том, что когда у вас есть набор форм, таких как очертания штатов США или избирательных округов штата, эти формы на самом деле обладают важной характеристикой разделения поверхности - они не перекрываются и полностью покрывают часть поверхности, которая вам небезразлична. У вас действительно есть топология (отсюда и название пакета), а многоугольники разделяют линейные сегменты или дуги этой топологии.

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

Эта модель прорыва часто повторяется. У вас есть некоторая общая проблема, которая является «теоретически сложной», но, определив ключевой момент, вы можете решить другую, более простую проблему, таким образом, чтобы преодолеть сложность с гораздо большей производительностью.

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

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

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

Проблема профсоюзов становится еще проще. Учитывая набор многоугольников, описанных как набор дуг, вы просто удаляете все дуги, на которые ссылается более одного многоугольника. Оставшиеся дуги описывают границу объединенной формы (есть несколько тонкостей, чтобы иметь дело с непересекающимися формами и отверстиями при восстановлении окончательной формы).

Проблема смежности в этом представлении также тривиальна - две фигуры являются смежными, если они имеют общую дугу.

Еще одна вещь, которую я обнаружил примечательной, заключалась в том, что вся эта функциональность (и другие функции, которые я пропустил) были реализованы в нескольких сотнях строк кода. Очень аккуратная работа. Я больше знаком с кодовыми базами, такими как Microsoft Office, где у вас могут быть сотни из тысяч строк кода, просто имеющих дело с копированием / вставкой (что, честно говоря, действительно является семантически сложной проблемой - позвольте мне рассказать вам о копировании и вставке в HTML таблицы некоторое время).

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

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

Проблемы с упрощением были в основном противоположны упрощению с детализацией многоугольников. Такое же решение по упрощению принимается для двух полигонов, имеющих общую кромку, но могут быть приняты противоречивые решения для отдельных кромок одного и того же многоугольника. Результатом будет многоугольник, который пересекает сам себя. Обычно это происходило только для узких извилистых форм, например, для переписного квартала, который был нарисован таким образом, чтобы перекрывать путь реки или ручья. К сожалению, результатом этих самопересекающихся полигонов были именно те визуальные аномалии и аномалии обработки, которых я пытался избежать в первую очередь!

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

Я использовал итеративный подход. Я знал, что если я сохраню все точки, у меня будет набор правильно сформированных форм. Итак, я запускал процесс упрощения, определял неправильные формы и поэтапно искусственно увеличивал «вес» точек вдоль дуг, на которые ссылались эти вырожденные многоугольники. Это было возможно и достаточно эффективно, потому что веса были явно представлены как результат первого этапа процесса упрощения. Вначале я не был уверен, что это приведет к достаточному упрощению, но на практике это сработало очень хорошо. Тот факт, что библиотека раскрыла этот промежуточный этап, а не рассматривала весь процесс как черный ящик, сделал это достаточно простым.

В процессе разработки было несколько перипетий. Я обрабатывал десятки миллионов фигур, покрывающих США, и несколько сотен в конечном итоге доставили мне проблемы. Что особенного в этих формах? Итак, я отправился в место вдоль Бостонской гавани, где у почти прямоугольной формы был длинный тонкий палец, прикрывавший причал. Или набор фигур в Колорадо, тщательно нарисованный географом, чтобы покрыть узкий извилистый ручей. В Миннесоту, которая использует гораздо больше форм, чем можно было ожидать, тщательно обведена вокруг всех ее водоемов. Земля десяти тысяч озер. Мне пришлось преследовать общую ошибку с алгоритмом слияния TopoJSON при работе с полигонами с самокасающимися отверстиями (представьте себе восьмерку). Почему это происходит всего несколько десятков раз на всю территорию США? А потом я вижу ряд отверстий - нитку жемчуга - аккуратно начерченную вокруг линии островов посреди реки.

Вторая проблема заключалась в том, что представление TopoJSON, используемое для точек и последовательностей линий, согласовывалось с другими пакетами JavaScript и форматами для географической обработки (по сути, точка была представлена ​​двухэлементным массивом, а линейная последовательность была представлена ​​как массив точек), но была ужасно неэффективная память. Программист на C считает массив, возможно, самой простой и компактной структурой данных, но JavaScript рассматривает массивы как особую форму общего объекта или хеш-таблицы, только со специальными строковыми ключами вида «0», «1» и т. Д. В результате простое представление последовательности точек / линий использовало тонны памяти и фактически доминировало в нашем использовании памяти. Это было правдой, несмотря на то, что TopoJSON начал с большой победы почти на 50% по сравнению с форматами, организованными по многоугольнику, за счет однократного кодирования точек на общем ребре.

Ранее я придумал упакованное представление, которое по сути хранило все точки для сложного набора фигур в одном двоичном буфере, что дало мне на два порядка улучшения использования памяти (я люблю JavaScript, но меня просто шокировало, насколько плохо наивное представление было). Я искал, могу ли я применить такое же улучшение к пакету TopoJSON.

Здесь действительно помогли небольшой общий размер пакета (в строках кода), а также его чистый дизайн. Мне удалось интегрировать упакованный формат всего с несколькими десятками дополнительных строк кода (а существующий код нужно было изменить только в паре мест). Более того, основная обработка, которую мне нужно было выполнить с помощью библиотеки TopoJSON, слияние, могла быть выполнена непосредственно из упакованного представления. В предыдущем подходе полигоны сохранялись упакованными, но требовалось распаковать координаты, чтобы передать их в библиотеку, которую мы использовали для объединения полигонов.

После окончательной интеграции завершенная работа сократила использование памяти нашими приложениями на 100 мегабайт и по существу устранила как проблему наиболее ресурсоемкую часть нашего интерактивного приложения, требующую больших вычислительных ресурсов и памяти. По пути я узнал об интересной технологии и исследовал некоторые странности географии США. Как весело!