February 2nd, 2010

moose, transparent

параметрический поиск

(эта запись будет интересна скорее всего лишь программистам и сочувствующим)

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

Параметрический поиск - метод, разработанный Нимродом Мегиддо в конце 70-х - начале 80-х. Особенно часто он подходит к проблемам в вычислительной геометрии.

Рассмотрим следующую задачу. Даны уравнения n прямых на плоскости, и для простоты предположим, что они находятся в общем положении: то есть, любые две из них пересекаются, и нет трех, пересекающихся в одной точке. У этих прямых есть n(n-1)/2 = O(n2) точек пересечения, которые можно отсортировать по их x-координатам слева направо - опять же для простоты положим, что все x-координаты разные. Проблема: найти k-ю слева точку пересечения, где 1≤k≤n(n-1)/2.

Наивное решение: отсортируем точки пересечения, и возьмем k-ю. Т.к. точек O(n2), это займет примерно O(n2logn) времени. Метод, который я опишу, решает задачу за O(n*log3n) времени. Учитывая то, что сам аргумент k двигается в пределах от 1 до n(n-1)/2, это впечатляет. Метод состоит из трех частей: процедура сравнения, собственно сам параметрический поиск, и его параллелизация.
Collapse )
moose, transparent

како падоша силнии посреде брани (компьютерное)

$ telnet www.sun.com 80
Trying 72.5.124.61...
Connected to www.sun.com (72.5.124.61).
Escape character is '^]'.
GET / HTTP/1.1
Host: www.sun.org

HTTP/1.1 301 Moved Permanently
Server: Sun-Java-System-Web-Server/7.0
Date: Tue, 02 Feb 2010 10:22:31 GMT
P3p: policyref="http://www.sun.com/p3p/Sun_P3P_Policy.xml", CP="CAO DSP COR CUR ADMa DEVa TAIa PSAa PSDa CONi TELi OUR SAMi PUBi IND PHY ONL PUR COM NAV INT DEM CNT STA POL PRE GOV"
Location: http://www.oracle.com
Content-length: 0

Connection closed by foreign host.
moose, transparent

немного английской путаницы

С выражением "if not" произошла такая досадная штука, что его можно понимать двумя способами, почти противоположными по смыслу.

"A, if not B" может означать как "A, но все-таки не B", так и "A, а может даже и B". Какое из двух прочтений верно, иногда ясно из контекста. А иногда неясно, и приходится гадать.

He considered George an acquaintance, if not a friend. Кем был для него Джордж - знакомым, но не другом? Или знакомым, а пожалуй даже и другом?

I found him cold, if not hostile. Каким он мне показался - холодным, но не враждебным? Или холодным, а то и враждебным?

Чаще бывает верной первая из перечисленных альтернатив. Но в зависимости от контекста, верным прочтением может быть второе, а может быть просто непонятно.


Сегодня мне попалось любопытное предложение в "Александрийском квартете" Даррелла; я никак не могу решить, странное оно или мне просто кажется.

"...Maskelyne was anything but a convivial soul and could seldom talk of anything but the work in hand."

Меня поразило то, что тут совсем рядом фраза "anything but X" употребляется дважды в разных, собственно противоположных смыслах. Но так ли это на самом деле?

В "was anything but a convivial soul" говорится, что он не был "convivial soul"; а в "could seldom talk of anything but the work in hand" говорится, что он почти все время говорил о "the work in hand". Т.е. в первом "anything but X" заключено "что угодно, кроме X", а во втором - "именно X".

Но этот анализ неверен, потому что он игнорирует "отрицательное" по смыслу слово seldom. Если учесть то, что оно "переворачивает" смысл, то противоречие как бы исчезает. Можно сравнить почти совсем одинаковые отрывки:

I can talk of anything but X. Я могу говорить о чем угодно, кроме X.
I can't talk of anything but X. Я не могу говорить ни о чем, кроме X.

Казалось бы, все нормально. И все же меня не оставляет ощущение парадоксальности, "неправильности". Я только не могу его как следует объяснить. Может, дело вот в чем. "anything but X" имеет само по себе отдельный смысл: "что угодно, кроме X". И этот смысл хорошо укладывается в первое предложение, присоединяясь естественным образом к "я могу говорить". А во втором предложении - не так; в нем есть особая связь между can't и anything, в которой целое больше суммы составных частей. Это та же связь, что и в обычном "I can't do anything", которое ведь не значит "Я не могу делать что угодно".

Видимо, я пытаюсь сказать следующее. В первом предложении я бы расставил скобки так: I can talk of (anything but X). А во втором так не получается: I can't talk of (anything but X) выходит бессмыслица. Но и другой способ расставления скобок, "(I can't talk of anything) but X" тоже подозрителен, потому что "but X" не относится все же ко всему вместе, что ему предшествует, а только к anything. Так что я окончательно запутался насчет моих попыток (наивно) проанализировать второе предложение; а ощущение "неправильности" вызвано, видимо, тем, что оно не распадается на части так же удобно, как первое.