Настройки поиска (Страница 6 из 15)

Эм, там в статье несколько опущен случай неориентированного графа (добавил себе в TODO).

Вообще для неор графа надо немножко изменить алгоритм: навесить одну доп. проверку. А именно, в функцию dfs передавать вершину p - это номер вершины, по которой мы попали в v. Тогда внутри dfs в цикле перед всеми остальными проверками надо дописать проверку:

if (to == p)  continue;

Тем самым мы избежим этой проблемы, которую вы описали: мы никогда не будем пытаться пройти по только что пройденному ребру в обратную сторону.

Соответственно, при вызове dfs (to) мы теперь ещё передаём вершину p, т.е. вместо этого пишем dfs (to, v). В основной программе вызывать надо dfs (i, -1).

Ой, как много ошибок... Спасибо.

В целом, к концу года удалось обуздать нагрузку на сервер.

• Ужесточил ограничение на нагрузку сервера с одного IP. Т.е. если вы начинаете долбить сайт своим wget'ом (и, например, это дало нагрузку в несколько процентов серверного процессора), то спустя несколько минут Вам перестанет показываться сам сайт, а будет выдаваться табличка "Сайт вызвал перегрузку процессора и закрыт". Для всех остальных людей в это время сайт будет по-прежнему доступен. Этот вид блокировки включается, если нагрузка с IP превысила 1% от мощности процессора.

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

• Добавил кеширование в Википедии. Там есть магические настройки кеширования, про которые точно никто не может сказать, насколько сильно они помогают, но кеширование APC + файловое кеширование для анонимусов привело к тому, что нагрузка на сервер упала раза в 2-3. В общем, как я и предполагал, самое тормозное звено на сайте - MediaWiki.

• А форум и код самого сайта даже не пришлось трогать - эта нагрузка оказалась не критической. Хотя вот думаю всё же реализовать файловое кеширование и на самом сайте, на всякий случай

Всё правильно, вы как раз заметили два связанных факта

Почему при нахождении ответа мы просто берём x[ i ] = d[ i ]? Потому что в моей реализации все c[ i ][ i ] = 1.

Почему они равны единице? Потому что я каждый раз сокращаю на c[ i ][ i ] всю строку, что вы и отметили вторым куском кода. Более логично было бы ещё дописать осле этого цикла a[ i ][ i ] = 1, но я этого не написал, просто потому что эти значения вообще больше нигде не будут использоваться.

Но, если угодно, можно убрать цикл сокращения, но тогда надо будет при нахождении ответа сделать деление на a[ i ][ i ], и ещё в самом гауссе при отнимании одной строки от другой надо будет текущую строку делить на a[ i ][ i ].

Да, никак руки не дойдут. А старый LCP, который у меня описан, прибить надо

Это деление v на 2 по модулю n (где n нечётно).
Если число v - и так чётное, то результат деления - просто v/2.
Если v - нечётное, то результатом будет (v+n)/2.

Хотя это, наверное, странная уловка - ведь с точки зрения скрытой константы более информативно написать "log M"

Вроде всё правильно. Массив P - содержит все степени заданного числа-основания хеша (P[ i ] - это константа P в степени i).

Речь там о том, что если мы подсчитаем хеши от всех префиксов H[ i ], то разность двух таких префиксных хешей H[ j ] - H[ i-1 ] даст хеш от подстроки S[i..j], но умноженный на P в степени i.

Я правильно понял, что елей одного сорта можем сажать сколько угодно?

Мне кажется, решать можно так: динамика d[ i ][ j ], где i - текущая рассматриваемая клумба, j - номер последней клумбы, в которую посадили ель. Тогда есть два перехода: мы либо не сажаем в i никакую ель - тогда переходим в d[ i+1 ][ j ] с тем же значением, либо пытаемся посадить какую-нибудь ель в i - тогда перебираем номер k сорта ели, проверяем, что так мы не бросим тень на клумбу с номером j, и переходим в состояние d[ next ][ i ], где next - номер первой клумбы после правого конца тени текущей ели.

Улучшил статью, - теперь сказано и про размер макс. парсоча (с наметками док-ва), и про нахождение самого паросочетания (хотя по-прежнему за не очень крутую асимптотику).