я сразу на «сути» не выкладывал линки, так как если кому понадобится, то в Buzz можно оставить вопрос или комментарий. А «сути» таких возможностей не содержат :)
альтернатива собственного производства: profiles.google.com/DMitskevich/posts/NnWhTNT91C9
чтобы не держать компьютер в рабочем состоянии, я его просто «усыпляю». как только я подключаюсь к нему по туннелю, он «просыпается». (видимо срабатывает Wake on LAN :)
1) а) если вы считаете, что первый алгоритм, это алгоритм с «откатами», тогда у меня нет претензий.
Единственное что хочется заметить, что из этого алгоритма легко вытекает сложность О(nm): у нас два вложенных цикла, один длиной n, другой — m. А вот сложность для второго алгоритма не так тривиальна. Поэтому мне показалось. что вы говорили именно о втором алгоритме, объясняя что из-за возможных «откатов» мы получаем О(nm).
б) >>… а так даже если вторая буква из пятисот не совпала, вы все-равно все пятьсот шерстите.
Посмотрите алгоритм ещё раз внимательнее. Алгоритм выходит сразу после нахождения несовпадения. Кстати использованный прием рекомендуется для избежания break-переходов.
2) рекуррентное соотношение не имеет ничего общего с рекурсией. Числа Фибоначчи, факториал — это все рекуррентные соотношения. А обычный способ вычисления рекуррентного соотношения — это не рекурсия, а динамическое программирование.
3) хорошо, теперь буду знать, что «лес деревьев» == «бор» :)
1) в Решении «в лоб» по моему вы намудрили с «откатами». Вот оно решение в лоб:
for (int i=0; i<str.length-s.lenght; i++) {
if (str[i]==s[0]) {
boolean f = true;
for (int j=1; j<s.length && f; j++) {
f = str[i+j]==s[j];
}
if (f) return i;
}
}
return -1;
а теперь попробуем реализовать алгоритм с «откатом». Получится что-то типа:
int f = 0;
for (int i=0; i<str.length; i++) {
if (str[i]!=s[i-f]) {
i -= i-f; // "откат"
f = i+1;
}
else if (i-f+1==s.length) {
return f;
}
}
return -1;
не очень тривиально, как вам кажется?
2) вычисление Z-функции и Алгоритм Кнута-Морриса-Пратта (КМП) по видимо можно записать в виде рекуррентного соотношения и вычислить при помощи динамического программирования.
Запись рекуррентного соотношения займет всего несколько строк, и заменит страницу текста с (не очень понятными) объяснениями и рисунками.
3) вопрос по термину «бор (trie)». Никогда не слышал о таком. Может быть вы имели ввиду «лес деревьев»?
А у меня следующий вопрос — как Sphinx берет данные для индексирования? Он с каким то интервалом проходит весь view catalog? Или может тригеры какие нибудь вешает в базу на изменения данных? view catalog в конечном счете может оказаться очень большим. И в каком режиме Sphinx читает view catalog — dirty read? Или он лочит все таблицы?
Если используется словарь «en-ru(yo)» (или «en-ru(ie)»), то Firefox определяет его и показывает в списке, как просто «English» (стандартный только-английский словарь там обозначен «English / United States») — может, в этом дело?
Если использовать словарь «en-ru», то в меню он будет обозначен «English / Russian Federation» —
(ini-файл c названием использует только Опера)
Так ведь именно это такой словарь и даёт (особенно если учесть, что алфавиты не пересекаются). Единственный (теоретический) недостаток в том, что работать такой «комбинированный» словарь может медленнее, чем два раздельных словаря с предварительным определением языка. Но кажется мне, что если это «определение» делать более-менее универсальным (а не ограничиваться только русским и английским), то и скорость работы вполне может отличаться в другую сторону.
чтобы не держать компьютер в рабочем состоянии, я его просто «усыпляю». как только я подключаюсь к нему по туннелю, он «просыпается». (видимо срабатывает Wake on LAN :)
можно подписаться на RSS или получать нотификации по почте
Единственное что хочется заметить, что из этого алгоритма легко вытекает сложность О(nm): у нас два вложенных цикла, один длиной n, другой — m. А вот сложность для второго алгоритма не так тривиальна. Поэтому мне показалось. что вы говорили именно о втором алгоритме, объясняя что из-за возможных «откатов» мы получаем О(nm).
б) >>… а так даже если вторая буква из пятисот не совпала, вы все-равно все пятьсот шерстите.
Посмотрите алгоритм ещё раз внимательнее. Алгоритм выходит сразу после нахождения несовпадения. Кстати использованный прием рекомендуется для избежания break-переходов.
2) рекуррентное соотношение не имеет ничего общего с рекурсией. Числа Фибоначчи, факториал — это все рекуррентные соотношения. А обычный способ вычисления рекуррентного соотношения — это не рекурсия, а динамическое программирование.
3) хорошо, теперь буду знать, что «лес деревьев» == «бор» :)
for (int i=0; i<str.length-s.lenght; i++) { if (str[i]==s[0]) { boolean f = true; for (int j=1; j<s.length && f; j++) { f = str[i+j]==s[j]; } if (f) return i; } } return -1;а теперь попробуем реализовать алгоритм с «откатом». Получится что-то типа:
int f = 0; for (int i=0; i<str.length; i++) { if (str[i]!=s[i-f]) { i -= i-f; // "откат" f = i+1; } else if (i-f+1==s.length) { return f; } } return -1;не очень тривиально, как вам кажется?
2) вычисление Z-функции и Алгоритм Кнута-Морриса-Пратта (КМП) по видимо можно записать в виде рекуррентного соотношения и вычислить при помощи динамического программирования.
Запись рекуррентного соотношения займет всего несколько строк, и заменит страницу текста с (не очень понятными) объяснениями и рисунками.
3) вопрос по термину «бор (trie)». Никогда не слышал о таком. Может быть вы имели ввиду «лес деревьев»?
Условие на уникальность элементов можно снять следующим способом:
if (A[i]<A[tid] || A[i]==A[tid] && i<tid)
K_tid++; //позиция в результате
en-ru(yo).zip (746.71 KB)
www.multiupload.com/8659DNM7GU
en-ru.zip (777.5 KB)
www.multiupload.com/AUW7DVWTL0
Если использовать словарь «en-ru», то в меню он будет обозначен «English / Russian Federation» —
(ini-файл c названием использует только Опера)