Saturday, February 27, 2010

Упрощение списка координат

Иногда нужно упростить список координат, например вывод kml(kmz) на маленьких уровнях увеличения - большая точность отображения не нужна, зато скорость очень важна.
Наиболее популярным вариантом в этом случае является Douglas-Peucker Algorithm дающим хорошую для человека результирующую траекторию. Но он является достаточно алгоритмически сложным, так как для удаления лишних точек удаляя определяя точки с минимальным векторный расстоянием между точками. 

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

Более хорошая версия - проход по точкам и высчитывается минимальное растояние между точками, если оно слишком мало, то увеличиваем его до минимально допустимого.
Затем запускается цикл по точкам и добавляются только те точки, которые располагаются на расстоянии от последней добавленной точки больше, чем минимально допустимое полученное на предыдущим шаге. Эту операцию повторяют пока количество точек не станет меньше максимально допустимого (вычисляется в общем-то на глаз, до тех пор пока время пересчета допустимо по времени ожидания и дефекты в контурах карт еще мало заметны). Также итерации могут продолжаться пока в контуре более 3 точек и площадь полигона больше допустимого для отображения, меньше можно просто отбрасывать(можно считать, что площадь линейно зависима от произведения минимального расстояния на количество точек, что, конечно, геометрически не всегда верно). Для упрощения математической сложности модно считать что расстояние равно не квадрату различий между точками((x1-x2)^2 + (y1-y2)^2 ), а сумме расстояний по координатам по модулю(|(x1-x2)| + |(y1-y2)|), что опять таки не всегда верно, но зато быстро.   

3D в linux

После обновления ядра до 2.6.33 и обновления Ubuntu до 10.04 (запуск обновления: update-manager -d ) с установленными обновлениями из xorg-edgers появилась достаточно быстрый рендеринг 3d и kms. Правда - с стандартным ядром у меня система не загрузилось,  на этапе создания splash screen  экран погас и на переключение консолей не реагировал, возможно причина в уже установленных обновлениях mesa. Без обновления до 10.04 33 ядро грузилось с поддержкой KMS, но без поддержки 3d. Сейчас есть только один артефакт - неправильное отображение воды в Cube2. 

Осталось  подождать поддержки Hybrid graphics и стабилизации версии mesa.

Sunday, February 21, 2010

Erlang

Не бывает достоинств без недостатков.
Достоинства:
  • функциональный язык с простым синтаксисом;
  • удобный синтаксис для записи математических функций;
  • ленивое исполнение;
  • событие ориентированный;
  • замыкания;
  • обширная библиотека OTP;
  • легковесные потоки;
  • удобная система фильтрации в условных операторах и разбора данных  по шаблону.
Недостатки, если смотреть излишне критично, вытекают из достоинств:
  • необычный синтаксис; 
  • никогда во время исполнения не чистит память, очистка вызываться только после завершения N-количества потоков;
  • во время очистки блокируется полностью вся виртуальная машина;
  • только недавно появилась поддержка многоядерных процессоров;
  • изначально написан для телефонных станций (ориентация на необычную специфичную сферу деятельности);
  • легковесные потоки - миф - при появлении ожидания  сообщения переключается на другой поток и при появлении новых сообщений ставим в очередь (возможно ее переполнение);
  • полностью функциональный язык со всеми неудобствами - нужно реализовывать большинство алгоритмов полностью рекурсивно (и кто его знает сколько оно будет думать?) и не использовать переопределение значений переменных(непривычно и иногда неудобно);
  • сложные вещи реализуется просто, простые очень сложно;
  • строки представлены списками, где используется не экономный формат данных для хранения 1 байта используется 8;
  • базы данные мнезье - все хорошо пока у вас памяти больше, чем данных, а потом или все читаем с диска или ядро убьет вас(не умеет оптимально кешировать запросы используя достоинства обоих типов хранения данных);
  • сложение строк дает разные значения в зависимости перемены мест слагаемых.

Риторические вопросы:
  • хотим чтобы не не использовали небезопасное выделение памяти и глобальные переменные - может стоит объяснить людям почему это плохо или дать удобный интерфейс для использования, а не полностью запрещать в синтаксисе?
  • ленивое выполнение - а вы всегда уверены когда это все выполниться и не зависнет ли? Как посчитать время исполнения? И все современные компиляторы стараются в месте с суперскалярной архитектурой (внеочередное выполнение, параллельное исполнение нескольких участков с применением уже рассчитанных результатов при благоприятном стечении условий) пытаются оптимизировать поток выполнения. И не стоить заменять логику надеждой - среда исполнения сама разберется  что уже не нужно исполнять дотянув реальное выполнения до последнего момента;
  • замыкания - если вы боитесь за стек включите оптимизации в компиляторе он давно умеет это избегать(в gcc - уже есть оптимизация при которой для рекурсивного выполнения стек если это возможно не растет).
  • если так уж хотим выделяться - берем гугловсий Go и получаем все тоже, но компилируемое... Не хотим? Есть куча библиотек по контролю за памятью и обменам сообщениями, все равно он преобразует в байткод исполняемый в виртуальной машине написанной на с, и если немного подумать можно сделать возможно и лучше и быстрее.

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

Wednesday, February 17, 2010

Прогресс развития

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

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

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

ReactOs - тоже сильно продвинулись, решились обьеденить свои наработки по реализации win32 и проекта wine, а не переписывать все как в windows. Надеюсь вскоре ее можно будет использовать как запускалку Windows игр, там где Wine не подходит.

Sunday, February 7, 2010

Прогресс с поддержкой 3d в linux

Или до обновлялся теперь 3d работает быстрее, но появились очень интересные особенности: в QuakeII мигает отображение, в кубе втором отсутствуют стены и пол. В общем еще немного подождать и все будет работать. Надеюсь ждать осталось недолго.
P.S.S.: При отключении эффектов рабочего стола QuakeII не мигает и нагрузка не процессор значительно меньше(сейчас любое 3d приложение сильно нагружает процессор).

Hybrid graphics on linux

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

Если судить по информации, что я имею:
  • эта технология нормально работает только в Vistе - есть нормальные драйвера и поддержка производителей ноутбуков;
  • для XP отсутствует поддержка в графической системе переключения;
  • Seven - есть только сентябрьский драйвер находящийся в вечной бете - хотя вполне рабочий, но вечно удаляемый системой, так она считает его устаревшим и без вопросов удаляет. И работает только самая слабая видеокарта и на второй стоит отметина проблемы инициализации. И если в биосе переключить нельзя - то никак уже не подключишь.
P.S. Hybrid graphics(оно же: PowerXpress(ATI), HybridPower(Nvidia)) - это когда системе присутствует более одной видеокарты и при смене нагрузки или питания происходит переключение видеокарты: при низкой нагрузке работает интегрированная видеокарта с низким потреблении энергии, если нужна большая производительность или дополнительные выходы(HDMI например, хотя для основных они могут кросится и сами, работает мощная, но вывод идет через выходы более слабой) включается более мощная.

symfony

  • Получить в форме значение поля - работает в обоих случаях для нового объекта установили значение по умолчанию (через setDefault) и в случае редактирования существующего объекта: $form['имя поля']->getValue();
  • Если нужно получить значение от select с установленным multiple нужно чтобы имя заканчивалось [] иначе получим только первое значение вместо списка.