|
|
|
November 4th, 2011
09:46 pm - HolyHell
HolyHell - Prophecy
HolyHell - Rising Force
Разве Мария Бреон не богиня?
Current Music: Dio - Heaven and Hell
|
November 2nd, 2011
03:51 am - Наблюдение
Одно наблюдение.
Возмем какую-нибудь толстую книжку. Например, Кормена (1300 страниц). С одной стороны это достаточно узкоспециализированная книжка. Ну действительно, она рассказывает про Computer Science, который является достаточно специализированным разделом математики. Который, кстати, ещё и достаточно молодой. Он появился, ну, грубо говоря, 60 лет назад. До этого это просто не было никому интересно. (не будем вспоминать диофантовы уравнения и перечислимые множества)
С другой стороны, Кормен очень обзорная книжка. Например, в нем есть глава "Вычислительная геометрия" на 40 страниц (самое-самое простое).
По вычислительной геометрии есть книжки на 1500 страниц (Handbook of Discrete and Computational Geometry). При этом там глава "Robust geometric computation" — ну в ней нет почти ничего. И по этой теме сейчас пишется отдельная толстая книжка.
Вопрос. Предположим, мы бы писали книжку "Математика" с достаточно детальным уровнем изложения. Сколько страниц была бы эта книжка?
Current Music: Halford - Made in Hell
|
03:02 am - What Every Programmer Should Know About Memory
За последние много лет скорость компьютеров выросла очень сильно. Но скорость работы разных частей росла с разной скоростью. В результате, сейчас мы имеем достаточно странные вещи.
Современные процессоры умеют складывать/умножать числа с огромной скоростью. Ну, вы сами знаете, какие это молотилки. При этом один branch misprediction будет вам стоить как 20-30 умножений, а один cache-miss как >200. Так было не всегда.
С течением времени разница между скоростью работы процессора и памяти растет. Ну, по крайней мере, она росла до настоящего времени. Ребята из Sony в одной из своих презентаций сделали достаточно интересный вывод: если мы хотим писать быстрые программы, нам необходимо правильно располагать наши данные в памяти. То, как данные расположены в памяти, оказывает все большее и большее влияние на производительность.
Вчера я случайно нашел хорошую статью на эту тему. Она называется What Every Programmer Should Know About Memory. Её написал небезызвестный Ulrich Drepper (ментейнер glibc).
Всё что там написано, это такие, достаточно общеизвестные факты. Хорошо, что они все собраны в одном месте, поскольку получился неплохой обзор. Немножко про то, как работает память, немножко про то, как работает кеш процессора, немножко про то, как обеспечивает когерентность кеша между ядрами, немножко про то, что программист может делать/не делать, чтобы использовать память более эффективно, немножко про то, какие проблемы получаются, когда у нас многопоточность.
Я точно знаю, что у чуваков из glibc любимое занятие это писать какой-нибудь супер заоптимизированный memcpy. Так что эта статья написана специалистом мирового уровня в том, как писать "супер заоптимизированный memcpy".
Current Music: Manowar - Revelation
|
October 29th, 2011
01:52 am - Лифт
Ура! У нас сделали лифт. Теперь мне не нужно ходить пешком на девятый этаж, перепрыгивая через заблеванные ступеньки и нюхая мусоропровод каждый второй этаж.
Что характерно, снаружи лифта написано "350кг, 4 человека", внутри — "375кг, 5 человек".
Очень важно, что предыдущий лифт вовремя заменили. У него была одна интересная особенность работы: когда в него заходишь, он проваливается. Достаточно сильно — сантиметра на 2. Это хорошо заметно и это вызывает беспокойство. Как-то ко мне заходил знакомый, говорит: "что-то у вас лифт кажется каким-то ненадежным" — "да, мне, тоже, было сыкотно на нем кататься первое время".
Current Music: Manowar - Bridge of Death
|
October 22nd, 2011
05:02 pm - Устойчивая реализация алгоритмов вычислительной геометрии
Завтра в Computer Science клубе в ПОМИ пройдет лекция Антона Ковалева «Устойчивая реализация алгоритмов вычислительной геометрии».
Алгоритмы вычислительной геометрии сложны в реализации. Не только потому что некоторые из них сложны алгоритмически. Дело в том, что, во-первых, в опубликованных алгоритмах часто опускают вырожденные случаи, рассмотрение которых бывает сложнее самого алгоритма. Во-вторых, алгоритмы вычислительной геометрии формулируют в предположении, что у нас есть вычислительная машина, которая хранит в ячейках памяти вещественные числа и может выполнять над ними арифметические операции за O(1). Т.е. таких машин просто не существует.
Если первая проблема решается с помощью "посидеть-подумать" для каждого конкретного алгоритма индивидуально. То что делать со второй проблемой не совсем очевидно.
Самое простое что мы можем сделать, это забить на то, алгоритм создавался в предположении, что свойства вещественных чисел выполняются и вместо них использовать числа с плавающей точкой. Переходя к числам с плавающей точкой мы теряем кучу свойств: ассоциативность сложения и умножения, дистрибутивность умножения относительно сложения, но часть свойств остается (коммутативность сложения и умножения).
Что происходит с алгоритмом, когда эти свойства нарушаются? Примерно тоже, что происходит с бинарным деревом поиска, когда ему передают не транзитивный компаратор: он не работает. Программа может отработать корректно, может выдать неправильный результат, может упасть где-нибудь внутри, может войти в бесконечный цикл, может упасть на бесконечной рекурсии. Всё что угодно. Общая закономерность, что чем сложнее алгоритм, тем более разнообразные спецэффекты можно наблюдать.
Почему это вообще так? Простой пример, как нарушение этих свойств ломает алгоритм. Одна из самых часто используемых операций в вычгеоме, orientation, возвращает с какой стороны от прямой лежит точка (просто знак векторного произведения). При нарушении этих свойств перестает выполняться orientation(a, b, c) = orientation(b, c, a) = orientation(c, a, b), а также orientation(a, a, b) = 0. Все алгоритмы нахождения выпуклой оболочки опираются на эти свойства. Когда они перестают выполняться, что делают эти алгоритмы вообще не понятно.
В качестве примера приведу картинки из статьи Classroom Examples of Robustness Problems in Geometric Computations (ребята из CGAL). Функцию orientation вычислили (в числах с одинарной точностью) для всех точек вблизи некоторой прямой и каждую точку покрасили в соответствие с тем, что выдала эта функция:
Результат немного более хитрого вычисления (вычисление с расширенной точностью и округление до двойной точности перед сравнением):
Что с этим делать? Существует два наивных подхода. Первый — использовать эпсилоны. Если мы при вычислении ориентации, посчитали векторное произведение и оно оказалось близко к нулю, давайте считать, что оно ноль. Ясно, что при таком подходе все свойства orientation продолжают не выполняться и алгоритм остается некорректным, но часто это позволяет ему работать на более широком классе входных данных.
Недостатком этого подхода является то, что для сложных алгоритмов сложно подобрать эпсилон. Кроме того часто одного эпсилона бывает недостаточно и в разных местах приходится использовать разные эпсилоны. В нашем straight skeleton'е их в какой-то момент стало 8.
Второй подход основан на использовании длинной арифметики т.е. давайте все считать с абсолютной точностью. При таком подходе алгоритм действительно становится корректным. Проблема в том, что длинная арифметика работает в десятки (сотни) раз медленнее чисел с плавающей точкой. Там где программа во флотах работает час, программа с длинной арифметикой работает несколько суток. Наш straight skeleton, кроме своих 8 эпсилонов, некоторые особо проблемные вещи считает в длинной арифметике.
На практике ни тот ни другой (ни их комбинация) подход не работает. На своей лекции Антон расскажет о том какие существуют более продвинутые подходы. В частности, как производить вычисления с абсолютной точностью в числах с плавающей точкой, подходы, которые называются Adaptive Precision Floating-Point Arithmetic (APFPA), Exact Sign of a Sum Algorithm (ESSA). В процессе лекции я думаю станет понятно почему реализация даже самых простых алгоритмов вычислительной геометрии, например, алгоритм Бентли—Оттмана является очень не тривиальной задачей.
Перед лекцией стоит обязательно прочитать (если вы ещё не читали): David Goldberg "What Every Computer Scientist Should Know About Floating-Point Arithmetic" и Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap "Classroom Examples of Robustness Problems in Geometric Computations".
После лекции, чтобы более детально ознакомиться с предметом, можно почитать Jonathan Richard Shewchuk "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates".
Current Music: HolyHell - Gates of Hell
|
September 9th, 2011
01:37 am - Типичный log ядра
История изменений ядра ветвится очень сильно. Всегда было интересно, как разработчики что-то в ней понимают.
(обратите внимание, что список немножко отсколен вправо, целиком дерево на экране не помещается)
|
April 16th, 2011
01:39 am - Перевод Ubuntu
Криворукая и дурная команда переводчиков Ubuntu сеет хаос и разрушение.
Обычно перевод программы развивается вместе с её кодом и лежит под контролем версий. Но только не в Убунту. Я не знаю почему, но эти ребята игнорируют оригинальный перевод программ и делают свой. Причем делают очень интересным способом. Переводы можно менять прямо у них на сайте. Это означает, что буквально любая обезьяна может зайти и начать менять переводы. Без контекста, без всего. Они тебе слово — ты им перевод.
Была одна очень гадкая ошибка перевода в Синаптике. Мне потребовалось каждому в рассылке персонально объяснить, что каждый из них козёл, и дословный перевод здесь делать нельзя. Тогда я их убедил. Перевод поправили. Сейчас, спустя полгода, его опять изменили на дословный!
Вот ещё по теме:
Для тех, кто ещё не знает, что Ubuntu делает свои корявые переводы, а претензии отправляются настоящим переводчикам проекта KDE.
Current Music: HolyHell - Resurrection
|
April 4th, 2011
12:20 am - qasmixer
Говорят, что опердень вся глючная и тормозная. Это совсем не так. Опердень бывает разная.
Как я выяснил источником всех моих проблем со звуком был pulseaudio. Который загадочным образом мешал работать даже тем программам, которые используют alsa напрямую. Наверное сейчас, это первый раз, когда у меня на компьютере всё программы работают. Точнее может быть какие-то не работают, но я про это не знаю.
После удаления pulseaudio всерьез встал вопрос о том, как крутить громкость алсы. После недолгих поисков я нашел замечательную программу qasmixer:
Эта программа выглядит по-человечески (по крайней мере по сравнению с остальными alsa-микшерами, которые я видел). Если пошарить по менюшкам, пишет много интересного об алсе. Написана на православных C++ и Qt. Не тянет лишних зависимостей. Если бы все программы были такие, мир бы был намного лучше.
Если кто захочет себе установить, но не хочет связываться с Mercurial'ом, я отзеркалил их репозиторий в git: https://github.com/sorokin/qasmixer.
На сайте программы есть больше красивых скриншотов: http://xwmw.org/qasmixer/media.html.
Current Music: Godgory - Conspiracy Of Silence
|
April 2nd, 2011
02:10 pm - Цитата
The traffic rules committee was at an impasse: half wanted the rule to be “drive on the right hand side of the road”, the other half wanted it to be the left hand side.
So of course they split the difference, and required driving in the middle of the road. — George Kangas
|
March 27th, 2011
04:30 am - Письмо писателей-копирастов
"Великие" писатели-домохозяйки собрались и решили написать президенту, о том, как мало они зарабатывают, как плохо им живется и что во всём виноваты электронные библиотеки: xttp://daiyan-19.livejournal.com/129456.html?style=mine
Вообще, я собирался насрать прям там в коментах, но там модерастия. Огородились. Ну и ладно.
"Несчастный автор получает 15000руб при реализационной выручке от тиража под миллион(5000экз х 200руб), но виноват, конечно, интернет". Правда жизни в том, что если вы работаете с издателями, то миллионерами вы не станете. Издатель — станет, а вы — нет. Собственно они уже и так. Очень показательная история Феномен Аманды Хокинг.
И вообще, если вы считаете, что писатели так мало зарабатывают, то почему вы всё ещё пишете? Вам мало платят? Не пишите. Вам нифига не платят, а вас всё больше и больше.
Самый хороший способ, что ваши произведения не "украли" — не писать их. Или писать, но никому не давать читать.
Ссылки по теме:
http://semiurg.livejournal.com/514568.html — мужик хорошо пишет. От себя добавлю, что не верен посыл, что запретив электронные библиотеки, люди побегут в мазагин. Не побегут.
http://cd-riper.livejournal.com/302433.html — Творчество vs $$
Current Music: Ария - Рабство Иллюзий
|
|
|
![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=91.7){kind=small}
ivansorokin's journal
