?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Entries by category: литература

binary search
nyaload
_winnie
В книге "жемчужины программирования" сообщается, что невозможно написать binary search с первого раза.

На самом деле его невозможно написать с первого раза, если не осознаешь что такое инвариант цикла. Если осознаёшь - то скорее всего запросто напишешь (я вот уже в третий раз за год написал).

Если не осознаёшь инвариант цикла, то с большой вероятностью будет одна из ошибок:

* mid = (lo+hi)/2 или hi/2+lo/2 ? (и нет, дело не в overflow, эти формулы просто разные (1+3)/2 != 1/2 + 3/2 ).Read more...Collapse )

Как писать двоичный поиск чтобы он не бажил:
* Выбрать инвариант "если искомый элемент существует, то он в [lo, hi)", изначально выбрать lo,hi = 0, N.
* mid = lo+(hi-lo)/2 (при этом для кода верно утверждение "промежуток длиннее 1 всегда укоротится").
* Если ищем первый среди равных - то сравнение выглядит как key<=array[mid-1], если последний - key<array[mid]
* в зависимости от сравнения присваиваем mid в lo или hi (в любом случае, не mid-1).



Двоичный поиск для равномерно распределённых ключей (хешей) ускоряется простым хаком "для каждого из 65536 двубайтовых префиксов запомнить, где он начинается", это убирает 16 начальных итераций.Read more...Collapse )
Tags:

Температура возгорания бумаги - 230°C (451° по Фаренгейту)
nyaload
_winnie
Сейчас я вам представлю доказательства того, что температура самовоспламенения бумаги - 230 градусов (или 451° по Фаренгейту), плюс-минус 10°.

ссылка 1) Информация с английской вики: http://en.wikipedia.org/wiki/Autoignition_temperature#cite_note-8
Скриншот: http://dobrokot.ru/pics/i2014-07-08__01-52-26_27kb.png

ссылка 2) А. Я. Корольченко, Д. А. Корольченко Пожаровзрывоопасность веществ и материалов и средства их тушения
Книга - http://dwg.ru/dnl/9002 , скриншот нужной страницы http://dobrokot.ru/pics/i2014-07-08__01-51-02_133kb.png

ссылка 3)
http://www.tcforensic.com.au/docs/article10.html#2.1 — Австралийский журнал «Firepoint». Physical constants for investigators, см. "paper"

Поверили? Справочники и английская вики - надёжный источник? На название романа я не ссылаюсь, это художественная литература. А вот справочники и википедия врать не должны.

Update: у меня духовка греет только до 250°C (правда, не знаю как это проверить). У кого-нибудь есть, которая греет сильней чем 250, но заведомо меньше 400?

fuzzy search grep своими руками
nyaload
_winnie
Если нужно провести неточный поиск слова по большому файлу (напр. по дампу википедии), то самое простое - это сгенерить регулярное выражение со всеми нужными вариантами опечаток, и сунуть в хорошую библиотеку регулярных выражений ( стандартный grep - OK, PCRE/python.re - NOT OK ).

Например, слово WORD превращается в регулярку:
.ORD|ORD|W.RD|WRD|W.ORD|WO.D|WOD|WO.RD|WOR.|WOR|WOR.D

Если нужен поиск по UTF-8 файлу - то можно ускорить поиск, используя вместо точки и UTF8-локали - "[^\x80-\xbf][\x80-\xbf]*" и C-локаль.

Если нужен case-insensitive поиск - то при генерации регулярки вместо СЛОВО писать (С|с)(Л|л)(О|о)(В|в)(О|о). И вы сами определяете, что вы хотите - [iI] или [Iiı], ẞ или (ß|ẞ|SS|S-S|ss|SSS|SZ), ё или (е|ё).

Пример генератора, который генерирует регулярку для всех вариантов на расстоянии 1 по Левенштейну: https://gist.github.com/dobrokot/6150988
Tags:

почему зеркало меняет право и лево, а верх и низ нет
nyaload
_winnie
Совершил диверсию: предложил коллегам на кухне задачку "почему зеркало меняет право-лево, но не верх и низ".

Мои мысли по этому поводу: фотки прилагаются!Collapse )
Tags: , ,

Геометрические Алгоритмы. Пересечение двух отрезков на плоскости.
nyaload
_winnie
Пусть есть два отрезка A,B и C,D. Надо понять, пересекаются ли они, и если да, то где именно. Во всех исходниках и книжках, которые я смотрел, это было сделано с кучей ненужного мусора, не смотря на то, что вроде бы очень простая и распространённая задача. Read more...Collapse )

Смотри ещё: • Угол между двумя векторами
Смотри ещё: • Проверка точки внутри многоугольника

Как обменять значениями две переменные (swap)?
nyaload
_winnie
9½.

1) Предположим, мы пишем некий абстрактный алгоритм, шаблонной функцией. Сортировку, например. И нам надо в нем поменять значения пары переменных(например, из сортируемого массива). Неизветсного типа. Как это сделать, причём желательно использовать специализированный и оптимизированный для данного типа swap?
2) Как нам безопасней всего определить функцию swap для для своего класса?

Read more...Collapse )
Tags: ,