воскресенье, 27 июня 2010 г.

ускорение

В годы моего спортивного участия разница между программкой на C и Pascal (да, было время когда в спорте писали на этом, причем большинство) составляла порядка 20-30% скорости в пользу С.

В Pascal еще можно было выставить оптимизирующие опции компилятору ({$O+, R-} или что-то подобное), что давало 10-20 % скорости.

Была одна техническая задачка: найти транзитивное замыкание для графа n = 1000. Понятно дело, что чистый куб не проходит, быстро умножать матрицы никто не умеет, поэтому надо уменьшать константу (переходить на битовые представления, и всякие линейные оптимизации). Мы еще сконденсировали сильно связные, получили ацикличный, и на нем... В общем работало, но ТЛ на каком-то. И за 2-3 минуты до конца вспомнили об опциях компилятору - прошло. Это был последний АС среди всех :) .

Сейчас я пишу нечто алгоритмическое, и выжимаю константу. Наконец-то вспомнил про debug/release. Переключил в release и получил 3-х (!!!) кратное ускорение. Даже боюсь представить, что будет когда я перейду с С# на чистый C без всяких виртуальных методов. Но этого я делать пока не буду.

Update[29.06.10]
Как мне пояснили, в debug без оптимизации вставляется куча nop-ов после каждой строчки кода. Что бы можно было просто дебажить (в т.ч. условные breakpoint) и модифицировать код без перекомпиляции. То есть все jmp остаются нетронутыми при возможной обработке. В общем не забывайте про release.

Это лучше, чем вызывать asm int 3 :) .

среда, 23 июня 2010 г.

shift

Так получилось, что я живу в городе, в котором есть как минимум 60 (с хвостом) п*в депутатов; в стране с не очень адекватным президентом.

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

Первоначально президентом была сказана фраза, "давайте посчитаем, потом подумаем". В реальности, считать уже никто не умеет, думать - тем более. В итоге получили.

Сейчас половина десятого вечера, 23 июня 2010 года (вчера/позавчера был самый продолжительный световой день) - солнце за горизонтом.

Уже стабильно повторяется ситуация, что я еще не ложился спать, а на улице уже светает (я довольно часто ложусь около 2). В 4-5 уже светло. Я когда утром выхожу побегать, на улице уже жарко.

И это все для того, что бы москва (жаль, что первую букву нельзя сделать еще меньше) как-то лучше смогла нами управлять. Большая часть москвы на работу приходит не ранее 10. Может проще было президенту сказать, чтобы они сами вставали пораньше?

Тут сдвиг не часового пояса, а по фазе.

ЗЫ. У меня предложение, давайте отнесем регион к Уральскому ФО, и тогда у нас будет +2.

вторник, 22 июня 2010 г.

Языки

Как я уже говорил, я никогда не повторяюсь.
(с) некто

Как я уже говорил, языки мне нравятся, но только не естественные. Английский довольно (относительного русского) прост своей грамматикой. Но в нем есть такая гадость, что нельзя синтаксически отличить существительного от глагола и существительное от прилагательного.

Вот тут есть лекции Охотина в csclub про формальные грамматики (советую посмотреть, ибо про булевы грамматики вы вряд ли где найдете), где упоминается классический пример:

Time flies like an arrow.

Fruit flies like a banana.

Время летит как стрела.
Временные мухи любят стрелы.

Фруктовые мухи любят бананы.
Фрукт летит как банан.

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

Слов мало, а терминов много. Проблемы.

Если же перейти к языкам программирования, то тут стоит напомнить цитату из "1984" Оруэлла : "новояз - единственный на свете язык, чей словарь с каждым годом сокращается".

В реальности все наоборот. Только чистые языки стабильны, остальное превращается в непонятно_во_что. Вы когда-нибудь писали на С++ ? (провокационный вопрос :) ). А знаете хотя бы одного человека, который бы мог сказать, что знает С++? Советую найти спецификацию языка и сосчитать количество страниц спецификации, которые вы использовали. Если будет более 5%, то вы гуру.

Пожалуй, только функциональщина за счет \lambda-абстракции может не расширяться. И в этом ее прелесть.

update (01.08.10).
Хотя вот немного пошлый пример на русском, показывающий проблему с глаголом/существительным:

Мужик на огороде врезается в сук дерева и хочет его спилить. Спрашивает у жены:
- где пила?
- нигде не пила.
- где пила?
- с чего ты взял? нигде не пила.
- в последний раз спрашиваю, где пила?
- ну, у соседа пила.
- а зачем дала?
- ну выпила, и дала.

понедельник, 21 июня 2010 г.

abracadabra, квайн

В теории строк в качестве примеров исторически используют только три слова: "banana", "mississippi", "abracadabra". Слова содержат малое число различных букв, довольно регулярны (есть повторы подстрок).

Переписываю некоторые вещи, прогоняю тесты. Упало на сабже, смотрю на результат. Нулевая мысль - "Мда, и в самом деле херня какая-то".

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

воскресенье, 20 июня 2010 г.

Постановка, исходник, комментарий

Покажем, что постановка задачи оторвана от исходника, точнее в другую сторону (исходник от задачи).

В cs есть такая теорема Райса (Райса-Шапиро, в некоторых вариациях встречается фамилия Успенского, но может быть это уже оффтопик). По исходному коду нельзя понять никакие нетривиальные свойства вычисляемого алгоритма. "Как же так ?" - спросит читатель. Вот исходник, сейчас почешу голову и пойму как оно все там работает.

Перейдем к примерам. Вот, например, некий код (уж извините, императивщина):

Pair[int, int] Some(int a, int b)
{
 int p;
 p = b;
 while (a > p)
 {
  p *= 2;
 }
 int q = 0;
 while (p != b)
 {
  p /= 2;
  q *= 2;
  if (a > p)
  {
   a -= p;
   q++;
  }
 }

 return [q, a];
}

Делается ли здесь что-либо полезное?

Some(56, 8) = [6, 8]

Фиг его знает. Я не фиг, я не знаю (странный логический вывод). Если вы найдете смысл в этой программе - сообщите мне (подумайте с полчаса).

Можно ли сказать, что исходник бессмыслен или неправилен? Конечно... нет. Любой исходник туп по своей сути, формальная система лишь исполняет команды. Смысл находится вне системы.

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

Давайте рандомом поменяем два символа в исходнике.

Pair[int, int] Some1(int a, int b)
{
 int p;
 p = b;
 while (a >= p)
 {
  p *= 2;
 }
 int q = 0;
 while (p != b)
 {
  p /= 2;
  q *= 2;
  if (a >= p)
  {
   a -= p;
   q++;
  }
 }

 return [q, a];
}

Найдите два отличия (даже три) :) .

А сейчас есть ли смысл у программы? Еще раз - конечно, нет. Есть ли смысл у мясорубки? Она тупо делает фарш из всего, что ей подадут на вход. И из мяса, и из хлеба, и из карандашей (если их подать на вход). Так и программа - тупо исполняет то, что в ней написано.

Но приведем несколько тестов
Some(56, 8) = [7, 0]
Some(25, 4) = [6, 1]
Тут уже можно заметить закономерность. Внезапно, программа начала делить нацело числа! Подумайте с полчаса, как же это работает.

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

А вот если бы у нас была постановка задачи ранее исходников, то кое что можно было бы сказать. Заметим, что вторая программа не идеальна: деление на 0, деление только натуральных, возможен глюк при переполнении p (p *= 2;)

Так вот, из исходного кода получить постановку (Райс-Шапиро - нельзя) (я - трудновато :) ). То есть желательно двигаться от постановки задачи к исходнику. А это уже синтез программ, и тут лет на n*10 пока глуховато.

Итого, мы пришли что двигаться от программы к постановке (смыслу?) очень трудно.

Перейдем к комментариям. Тут та же фигня. Комментарий может вообще никак не быть привязан к коду, а тем более к постановке. Хуже кривого кода может быть только неадекватные комментарии.

Не могу сказать, что полностью понял идею Кнутовского грамотного программирования (literate programing); а вот контрактное программирование (Мейера, Eiffel) близко к пред/пост-условиям, и мне по душе. Текущее состояние с текстовыми комментариями, да еще в часто изменяемом коде, выглядит страшновато. Заметим, что все быстрые agile методологии предпочитают тесты вместо комментариев.

В итоге мы получили три основные сущности (постановка, код, комментарий), которые никак друг с другом не связаны.

пятница, 18 июня 2010 г.

Четверть

Пытался сегодня побаловаться с виртуализацией на старой машинке (ибо кроме mercurial-а там сейчас ничего полезного для меня нету). После ревизии железяк оказалось, что есть только 1 (из 4) рабочий ДВД. Но приложенице настоятельно требует 64-bit CPU, а это опять четверть моего парка, на котором я не готов экспериментировать. Так что эксперименты отложены на непонятное будущее.

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

вторник, 15 июня 2010 г.

Что-то среднее

Патологоанатомы утверждают, что слухи о внутренней красоте человека сильно преувеличины.

Д

П

Не существующие люди. Сгенерено при помощи. Имхо, среднее получилось поболее любой части.

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

Ранее мужской эталон красоты был тупо-сильно-прокачен => большее количество мамонтов сможет загасить. Сейчас же тупо-на-фоне-лексуса. Хотя если вы будете брать себе охранника, то выбирайте тупо-сильно-прокачен.

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

Основная проблема, чтобы оценить внутренность одного взгляда не достаточно.

С программами иногда проще, если есть исходники или можно залезть рефлектором.

Проще всего с конфетами, их не так много, ошибиться сложно и некритично.

ЗЫ. Выяснилось, что резюме 3/4 девушек присылает с фотокарточками, с другой стороны тождественный нуль. Факт.