Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от e-maxx
Убрал эту статью, т.к. по всей видимости это не очень полезный метод. Так получилось, что когда я не знал про метод Гаусса, то разобрал первый попавшийся метод, и оказался он методом Краута 
Сейчас я уже не помню сути этого метода, но внешних преимуществ у него нет никаких: ни во времени работы, ни в возможности ухода от дробных чисел.
В общем, статья скрыта из оглавления и из книги, хотя и будет по-прежнему доступна по прямой ссылке.
Книга становится всё лучше и лучше!
Оказалось, что Adobe Acrobat 8 менее глючный и более функциональный своего последователя, поэтому благодаря деградации до 8-ой версии удалось сделать разрыв страницы перед началом каждой статьи, кроме того, качество сжатия формул снова стало хорошим, - соответственно, и PDF потяжелела до 6 Мб обратно.
Страницы Acrobat повернул в альбомный формат, и я подумал - и правда, хорошая идея! Так гораздо лучше читается с экрана, и почти все программные коды теперь помещаются в одну строчку.
Хотя непонятно, как это может быть связано с рантаймами - вы же не локально их внутри рекурсивной функции выделяли? Если использовали итераторы, и при этом меняли списки - неаккуратная работа с итераторами может привести к рантайму.
Лист быстрее только при вставке/удалении в начало/середину. В остальном он и медленнее, и больше памяти выделяет (потому что каждый элемент - отдельно выделяемая структура, в которой приходится хранить указатель на следующий элемент в списке, отсюда тормоза и при добавлении (куча выделений памяти), и при проходе (скачки по памяти туда-сюда происходят, вместо линейного упорядоченного просмотра)).
PDF-версия книги, расположенная по постоянному адресу, и так постоянно обновляется, но сегодня произошло большое изменение: по совету Дениса prog-r я сумел выполнить конвертирование через Adobe Acrobat, в результате получилась вполне адекватная книга, с работающими внутренними ссылками. Нельзя сказать, что всё выглядит идеально, но, видимо, это лучший возможный вариант в случае PDF.
Книга получилась в 2 раза легче (3 мб из 300 страниц) за счёт того, что Acrobat сильнее сжимает изображения.
Для этого достаточно для каждой вершины хранить указатель на её структуру в декартовом дереве, и ещё в каждой вершине деревьев поддерживать указатель на вершину-предка.
Тогда, чтобы определить, в каком дереве вершина и какая по счёту, надо просто идти от выбранной вершины по предкам до корня. Корень и будет уникальным идентификатором декартова дерева, по корням мы можем определять, находятся две вершины в одной компоненте связности или нет.
Теперь осталось определить номер вершины. Но здесь всё просто - вот когда мы поднимались по предкам, - можно заметить, что если мы переходим к предку и являемся его правым сыном, то к ответу надо прибавить количество вершин в левом поддереве этого предка. Ещё вначале надо прибавить число вершин в левом поддереве текущей вершины. В итоге получится число вершин, меньших текущей, что в нашем понимании и есть номер вершины в компоненте связности.
Храним каждую компоненту связности (цепь или цикл) в виде отдельного декартова дерева. Тогда чтобы найти кратчайший путь между двумя какими-то вершинами, надо просто найти, какие они по счёту в их декартовом дереве (т.е. найти, сколько элементов стояло до них). Если компонента - путь, то ответом будет просто модуль разности между найденными величинами, а если цикл - то минимум из этого модуля и длины цикла минус этот модуль.
А ты, кстати, что запускал? Одну функцию, которая всю работу делает сама? Она, может быть, плохие константы использует для тупого алгоритма trial-division, и из-за него может быть тормоза?
Ок, добавлю и такой вариант, хотя мне он не кажется логичным Один иф по сравнению с временем работы умножения мало что меняет, но лучше, конечно, привести и более оптимизированный вариант. Спасибо за фидбэк.
После последнего Петрозаводска у меня закрались сомнения, не палево ли у меня там написано, особенно в алгоритмах Полларда
Кто-нибудь может авторитетно заявить, что да, полное палево? 
Алгоритм, находящийся по адресу http://e-maxx.ru/algo/minimal_triangle, по всей видимости, безнадёжно неверен, и потому он временно скрыт из общего списка. Этот алгоритм когда-то давно прошёл на задаче одного контеста, но, похоже, это было вызвано слабостью тестов.
Я видел решение cmd этой задачи, оно имеет ту же асимптотику, но основано на другой идее (угловые события), и как раз оно, видимо, и верно. Осталось восстановить этот алгоритм, реализовать, и переписать статью А пока статья будет скрыта...
Рабочая CHM-версия книги.
С Microsoft HTML Help Compiler пришлось немного подолбаться, но на текущий момент это выглядит самым удобным вариантом книги, потому что все внутренние гиперссылки работают.
Известные проблемы:
Очень медленное открытие книги, потому что она состоит из одной сплошной страницы, что сильно напрягает IE.
Пофиксил Флойда. Просмотрите, пожалуйста, а то у меня, как обычно, глаз замылен, мог ляпов насажать...
Какие будут комментарии, пожелания форматов?
Проблема с ссылками PDF, видимо, не скоро будет решена, потому что имеющиеся программы конвертации настолько тупы, что либо вообще некорректно конвертят HTML, либо не поддерживают эти внутренние ссылки на якоря, либо всё это поддерживают, но жёстко тормозят и вылетают с ошибкой при запуске на большом файле. Связался с автором самой адекватной программы, возможно, он как-нибудь доделает своё детище.
Рабочая MHT-версия книги.
Ой да, во Флойде у меня ужас какой-то написан Сейчас что ли переписать эту статью...
Про палиндромы - круто, не знал. Значит, авторство Сергея Назарова придётся удалить
Это рабочая PDF-версия книги.
Известные проблемы:
внутри PDF не работает внутренняя навигация (ссылки на алгоритмы) - система якорей некорректно обрабатывается программой-конвертером
каждый алгоритм начинается не с новой страницы, а отступает от предыдущего на несколько строчек
Наконец дошли руки заняться этим безусловно полезным делом: создать в виде единственного файла книгу - архив всех алгоритмов с раздела /algo.
Исправил статью. Кстати, в Вики эта статья уже содержала исправленный вариант.
Понял ошибку, сейчас делаю фикс в описании.
Проблема была в том, что когда есть несколько одинаковых блоков на каком-то уровне k, то при вычислении LCP на уровне k+1 мы берём с предыдущего уровня не тот LCP:
lcpn[i] = lcp[pos[a]];Фикс идейно несложный: для каждого класса эквивалентности надо запоминать самую последнюю в перестановке строку из этого класса.
Да-да, но кажется, что аналогичная ситуация может быть не только с корнем цветка, а с любой четной его вершиной.
Хм. Этот код, по идее, где-то проходил тестирование... Что же, under investigation
Неправильная оценка, наверное, да.
Ох, много работы предстоит по пересмотру старых статей, написанных в незапамятные времена...
Лекции Котова В.М. по динамическому программированию.
MAXimal :: φορυμ » Сообщения от e-maxx