Здравствуйте, Mab, Вы писали:
Mab>Вот довольно популярный анализ практической эффективности:
Большое спасибо, с интересом сейчас изучаю. Очень ценно. Уже подивился, с какой лихостью они приводят скорости работы алгоритмов, ведь ясно, что на деле эти цифры могут отличаться наверное минимум на порядок в зависимости от среднего lcp и размера алфавита, не говоря уже про нестабильность некоторых алгоритмов (bzip, к примеру, виснет на длинных прогонах ababab...). Но все-таки это позволило мне осознать, что на практике разница между характеристиками алгоритмов в log n и аналогичные функции ничего не означает — константы при O элементарно их перевешивают. Был несколько удивлен этим обстоятельством. Буду привыкать.
Mab>Недавно рецензировал статью на FOCS08, там народ предлагает еще один алгоритм с линейным временем работы, который на практике еще быстрее существующих. Естественно, выигрыш не асимптотический, а измеряется в десятках процентов.
Я тоже, признаться, тоже этим грешу. Вот как-то придумал, как можно уменьшить объем работы в алгоритме Sadakane-Larsson так, чтобы применять технику удвоения только к части суффиксов (примерно 1/7), а остальное за гарантированное O(n log n) время отсортировать более быстрым способом с Induced Copying. Надо бы как-то попробовать это реализовать и посмотреть, что получится, но не знаю, когда у меня дойдут до этого руки.
And if you listen very hard the alg will come to you at last.
Здравствуйте, R.K., Вы писали:
RK>По памяти для массивов на каждый символ используется 4 байта, для деревьев — 16.
Для деревьев все сильно зависит от того, как именно хранить дуги. А это, в свою очередь, дает memory-time tradeoff.
RK>По времени построения массивы не сильно быстрее деревьев.
Ну разница легко может быть в разы. Кому сильно, кому не сильно.
RK>Сложность построения suffix tree на PATRICIA не зависит от алфавита ни по времени, ни по памяти. Ибо фактически используется бинарный алфавит.
Тогда просто длина строки возрастает в log A раз, казалось бы.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, R.K., Вы писали:
RK>>По памяти для массивов на каждый символ используется 4 байта, для деревьев — 16. Mab>Для деревьев все сильно зависит от того, как именно хранить дуги. А это, в свою очередь, дает memory-time tradeoff.
Дуги можно хранить по-разному, это да. Но в реализации PATL
я предпочел постоянный 16-ти байтный (по 4 байта: длина префикса, парент и два дочерних) размер узла, так намного удобнее, чем городить структуры переменной длины.
Вообще для полноценной замены дерева необходимо совместно с массивами для разных применений вычислять дополнительные структуры, которые также тянут время и память. Конкретный пример: enhanced suffix array в Seqan. А дерево — более универсальная структура и сразу предоставляет большинство своих возможностей. Вот и получается такой довольно нетривиальный трейдофф: все в одном, красиво и достаточно быстро vs экономно, ограниченно и всегда по-разному.
RK>>По времени построения массивы не сильно быстрее деревьев. Mab>Ну разница легко может быть в разы. Кому сильно, кому не сильно.
Таки надо сделать забег Seqan против PATL
RK>>Сложность построения suffix tree на PATRICIA не зависит от алфавита ни по времени, ни по памяти. Ибо фактически используется бинарный алфавит. Mab>Тогда просто длина строки возрастает в log A раз, казалось бы.
Как это? Нет, длина строки, как и размер дерева, линейны от индексируемого объема.
Здравствуйте, R.K., Вы писали:
Mab>>Тогда просто длина строки возрастает в log A раз, казалось бы. RK>Как это? Нет, длина строки, как и размер дерева, линейны от индексируемого объема.
Это я как-то не понимаю. Мы рассматриваем вставляемые строки как последовательности бит? Или что-то иное?
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, R.K., Вы писали:
Mab>>>Тогда просто длина строки возрастает в log A раз, казалось бы. RK>>Как это? Нет, длина строки, как и размер дерева, линейны от индексируемого объема.
Mab>Это я как-то не понимаю. Мы рассматриваем вставляемые строки как последовательности бит? Или что-то иное?
Да, именно "рассматриваем вставляемые строки как последовательности бит", но с каких это пор представление увеличивает длину?
Здравствуйте, R.K., Вы писали:
RK>Да, именно "рассматриваем вставляемые строки как последовательности бит", но с каких это пор представление увеличивает длину?
Ну очевидно как. Размер дерева становится линеен по битовой длине строки, а она как раз в log A раз больше, чем символьная.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, R.K., Вы писали:
RK>>Да, именно "рассматриваем вставляемые строки как последовательности бит", но с каких это пор представление увеличивает длину?
Mab>Ну очевидно как. Размер дерева становится линеен по битовой длине строки, а она как раз в log A раз больше, чем символьная.
Т.е., имеется в виду, что А = log(8 * sizeof(symbol_type))? Ну что ж, таков коэффициент линейной сложности. С точки зрения теории O(N) остается той же, а на практике возможные тормоза прояснятся как сами по себе, так и из сравнения с реализацией через массивы. Isn't it?
Здравствуйте, R.K., Вы писали:
RK>Т.е., имеется в виду, что А = log(8 * sizeof(symbol_type))?
Имелось в виду, что log A = число бит на символ, и этот множитель пролезает в оценку.
RK>Ну что ж, таков коэффициент линейной сложности. С точки зрения теории O(N) остается той же, а на практике возможные тормоза прояснятся как сами по себе, так и из сравнения с реализацией через массивы. Isn't it?
C теоретической точки зрения алгоритм оказыватеся alphabet-dependent. Я лишь это и хотел отметить, ничего более.
Конечно, на практике алфавит фиксирован, поэтому надо сравнивать с другими реализациями на осмысленных практических тестах.
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, R.K., Вы писали:
RK>>Ну что ж, таков коэффициент линейной сложности. С точки зрения теории O(N) остается той же, а на практике возможные тормоза прояснятся как сами по себе, так и из сравнения с реализацией через массивы. Isn't it? Mab>C теоретической точки зрения алгоритм оказыватеся alphabet-dependent. Я лишь это и хотел отметить, ничего более.
Возможно, возможно... Но вот что я подразумеваю под независимостью от алфавита: с увеличением размера в битах каждого символа уменьшается кол-во символов в некотором ограниченном объеме памяти. Вот линейную зависимость от индексируемого объема памяти я и подразумевал. Право, не знаю, как это выразить через O(N).
Mab>Конечно, на практике алфавит фиксирован, поэтому надо сравнивать с другими реализациями на осмысленных практических тестах.
Здравствуйте, Mab, Вы писали:
Mab>Какая разница, что с ней делается? Если сливать в лоб, создавая новую очередь за время, равное сумме размеров старых, то время работы будет как минимум квадратичным. И никакой n log n его не перекроет.
Mab>Или имелось в виду, что мы применяем "ранговую эвристику" -- добавляем элементы меньшей кучи в большую? Хорошо, пусть исходно есть n^{1/2} куч по n^{1/2} элементов. И пусть там надо слить их в одну кучу из n элементов по турнирной системе. Решение с meldable heaps c ценой слияния O(log n) работает за O(n^{1/2} (общее число слияний) * log n (время слияния)) = O(n^{1/2} log n).
Mab>А решение без medlable heaps требует порядка n * log^2 n времени.
Кстати, а почему это мы добавляем элементы из одной кучи в другую по одному? Есть более эффективный способ слияния хипов примерно одного размера — свалить в одну кучу и выстроить, делается за O(n). Сливая по турнирной системе описанные выше кучи таким способом мы получаем итоговую сложность O(n log n), что вполне аналогично времени на вытаскивание этих элементов из результирующей кучи (тоже O(n log n)). Если же брать маленькие кучи и большие, до для них нельзя организовать турнирную систему, а в нетурнирной сложность поэлементной вставки опять O(n log n).
Итого вывод — использование биномиальных куч не улучшает общей асипмтотики времени работы алгоритма, который правильно реализован на бинарных кучах, если только этот алгоритм не оставляет невычерпанными существенное количество элементов в создаваемых им очередях. А есть такие алгоритмы?
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>Итого вывод — использование биномиальных куч не улучшает общей асипмтотики времени работы алгоритма, который правильно реализован на бинарных кучах, если только этот алгоритм не оставляет невычерпанными существенное количество элементов в создаваемых им очередях. А есть такие алгоритмы?
Вот как-то придумал, как можно уменьшить объем работы в алгоритме Sadakane-Larsson так, чтобы применять технику удвоения только к части суффиксов (примерно 1/7), а остальное за гарантированное O(n log n) время отсортировать более быстрым способом с Induced Copying. Надо бы как-то попробовать это реализовать и посмотреть, что получится, но не знаю, когда у меня дойдут до этого руки.
