Java + ассемблер

Сначала думал написать тут короткую заметку про то, как подружить Java и ассемблер, но потом решил написать об этом пост на Хабре, и не зря — получил инвайт.
Статья: http://habrahabr.ru/post/145804/

В общем, этим я занимался вчера, а сегодня я успел сделать еще кое-что, на еще один пост на Хабре не тянет, так что напишу здесь. Для понимания того, что я делаю, рекомендуется прочесть эту статью.

Читать далее…


Чиним установку сторонних модулей Python в Windows 7

Данный пост, как следует из названия,  будет интересен только тем, кто использует операционную систему Windows 7 (вроде как, в 32-битных версиях все нормально, и проблема есть только в x64), программирующим на Python’е. Суть такова: если при установке некоторого стороннего модуля воспользоваться .exe-установщиком, то он будет жаловаться на отсутствие в реестре информации, необходимой для установки.
Если этой информации нет, значит, надо ее туда добавить:

Windows Registry Editor Version 5.00

[HKEY_CURRENT_USER\Software\Python]

[HKEY_CURRENT_USER\Software\Python\Pythoncore]

[HKEY_CURRENT_USER\Software\Python\Pythoncore\2.7]

[HKEY_CURRENT_USER\Software\Python\Pythoncore\2.7\InstallPath]
@="C:\\Program Files (x86)\\Python 2.7"

[HKEY_CURRENT_USER\Software\Python\Pythoncore\2.7\PythonPath]
@="C:\\Program Files (x86)\\Python 2.7;C:\\Program Files (x86)\\Python 2.7\\Lib\\;C:\\Program Files (x86)\\Python 2.7\\DLLs\\"

Естественно, корневую директорию Python и его версию можно поменять.


Онлайн-курсы Стэнфорда и MIT

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

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


Radix Sort

Некоторая полезная информация о поразрядной сортировке: http://codercorner.com/RadixSortRevisited.htm


ТЫРПРАЙЗНО

Писал я, значит, лабораторную работу по дискретной математике и решал задачу о поиске минимального остовного дерева в полном геометрическом графе, который был задан расположением своих вершин на плоскости. Мое решение получало Time Limit Exceeded на девятом тесте, который, если верить интуиции, должен быть не очень крупным. Я несколько раз тщательно сверил свой код с разными источниками и не нашел в нем ничего слишком медлительного. По крайней мере, асимптотика была верной.

Убедившись, что проблема не в алгоритме, я решил посмотреть подробнее, что же настолько тормозит мою программу. Первый вариант работал на максимальном (порядка 5000 вершин) тесте примерно 21 секунду. Я не буду описывать здесь все мои попытки оптимизации, так как это не имеет значения, скажу только, что расстояние между двумя точками я считал как Math.hypot(x[i] — x[j], y[i] — y[j]), и улучшить время работы до чего-то меньшего, чем 3 секунды, мне не удалось. На каком-то этапе у меня появилась мысль: может, надо быть проще и написать, как в старые добрые времена, квадратный корень из суммы квадратов? Конечно же, это никак не должно повлиять на производительность, ведь адекватные люди именно так и реализовали бы hypot(), подумал я, но все же попробовал. Результат был удивителен: время работы программы теперь составляло 332 миллисекунды!

Что, что можно делать в этом методе настолько долго? Проверять особые случаи по 100 раз? Вычислять результат десятью разными способами? Линчевать негров? Строить планы захвата галактики? К сожалению, добраться до определения метода hypot() мне не удалось, он native’ный. Надо бы все же найти его где-нибудь и посмотреть, что же там такое происходит.

P.S.: До этого дня я думал, что самая смешная sqrt/hypot-функция была в одной из версий Borland Delphi. Реализация содержала около 30 строчек delphi-кода сомнительного качества, который затем был закомментирован. Вместо него были написаны другой(тоже закомментированный, но уже хороший) код и ассемблерная вставка.

P.P.S: а вот и разгадка.