Где-то год назад от нечего делать решил покапаться в исходниках mysql||postgresql. Сразу же увидел, что такая базовая вещь, как поиск подстроки в обеих реализациях написаны бруте-форсем(причем, в mysql умудрились написать с помощью goto :) ).
На моей старенькой машинке (pIII-500) mysql компилилась порядка 1 часа, на ноуте почему-то отказалась, postgres же на старой - 20 мин, на ноуте - 7. Поэтому я решил исправить этот недочет в postgres-е. Где-то дня за два (с учетом понимания того, как это надо компилировать и немного тестировать) реализовал стандартный КМП и отправил им на коммит. Там сразу же сказали, "нафига нам это нужно, это лишь усложнение кода и текущий квадрат нас устраивает". Потом, через несколько постов (по времени, где-то месяц) все-таки добавили в TODO лист, что неплохо бы реализовать БМ.
Сейчас, выйдя в отпуск, я решил "добить" задачку. Начал качать актуальные исходники и обнаружил, что проблему уже решили месяц назад ("[D] - marks changes that are done, and will appear in the next release."). Испытываю смешанные чувства: с одной стороны я чем-то помог, создал проблему, с другой стороны не я ее решил. Хотел в отпуске попрограммировать для души... Ладно, что нибудь другое попишу.
Все таки алгоритмы идут в массы. Где-то видел, что в oracle реализован КМП; где-то в ядре linux-а есть настройки, какой алгоритм (среди списка есть БМ) использовать для "сопоставления сетевых пакетов" (что-то подобное). Вот и в postgres-е появилось(-ится). А казалось бы, такая очевидная вещь... не использовать бруте-форсе. Интересно, а до суффиксных массивов еще далеко?
PS. После того как увидел Reflector для .net, обнаружил что системных библиотеках qsort реализован с использованием стандартной выборки "среднего" элемента (а именно, средний элемент). Сразу же "повесил" до квадрата. Кстати, если использовать random при выборе "среднего" элемента и суметь перехватить randSeed, то все-равно можно сгенерить анти-кусорт чуть ли не за (n * log n).
Сообщения
