avva | тони хоар r.i.p.

На прошлой неделе умер Тони Хоар, ученый, исследователь алгоритмов и языков программирования. Его самым известным и популярным изобретением остается алгоритм quicksort. От имени всех программистов, которые знают quicksort и когда-то сами его писали, салютую памяти Тони Хоара.

Оказывается, в конце 50-х годов 25-летний Хоар сначала выучил русский язык, а потом по культурному обмену провел год в аспирантуре МГУ, изучая теорию вероятностей "на факультете А.Н.Колмогорова". Там он заинтересовался проблематикой машинного перевода, и первой публикацией Хоара была статья, которую он написал по-русски и опубликовал в сборнике "Машинный перевод и прикладная лингвистика" (1961, вып. 6).

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

Эта необходимость привела Хоара к задаче быстрой сортировки слов в алфавитном порядке (а затем любых данных), и для этого он изобрел Quicksort, а опубликовал статью о нем после возвращения в Англию, в 1962-м. Все это выглядит немного как первоапрельская фантазия, но тем не менее правда.