День: 19.07.2011

Азиятской дикости псто

На днях был в «Икее» и сподобился съесть остывших пончиков и попить чаю, кофе и всякой разной минводы в тамошней едальне. Если остывшие пончики интереса не представляют, то про разные жижи стоит рассказать подробнее.

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

Конечно, я не дошел до такой степени варварства, как приходить в «Икею» с пятилитровым жбаном и наливать туда всякие напитки, но стаканчик на всякий случай забрал с собой — а вдруг занесет туда снова?

PS Жаль, пива не наливают.

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

Алгоритмическая задача

Дано: есть матрица высот, то есть (грубо говоря) равномерная сетка точек на поверхности Земли, для каждой из которых приведена ее высота. Точек много, порядка миллиарда. Нужно построить TIN-модель (triangular irregular network), то есть сетку из треугольников с «абы где» расположенными вершинами, «похожую» на исходную матрицу высот. Треугольников должно быть много меньше — несколько десятков тысяч это максимум.

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

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

Легко понять, что функция f, выбирающая из последовательности x0, …, xn M максимальных элементов, является индуктивной, то есть f(x0, …, xn) зависит только от f(x0, …, xn-1) и xn. Можно записать это следующим образом: f(x0, …, xn) = F(f(x0, …, xn-1), xn). Индуктивная функция от последовательности длины N вычисляется за N шагов очень простым циклом, надо знать лишь значение f на пустой или одноэлементной последовательности и функцию F.

Очень просто написать функцию, находящую M «наибольших» элементов в N-элементной последовательности за O(N*M) с расходом памяти O(M) — выбранные элементы хранятся в массиве, каждый новый элемент сравнивается со всеми выбранными до этого. Если включить мозг, то можно улучшить оценку до O(N*log M) с той же оценкой расхода памяти (храним выбранные M элементов в самобалансирующемся дереве). А можно ли сделать это еще быстрее, возможно, отказавшись от подхода с индуктивными функциями? Я ответа пока что не знаю.