6

Имеется суффиксный автомат. Необходимо найти самую длинную пoдстpoку (oбщyю).

Автомат реализован на основе данной статьи: Суффиксный автомат.

(если с суффиксным автоматом не знакомы или статью не смотрели, дальше можно не читать)

Работает быстрее Хорспула. Но при работе с длинными строками скорости всё равно недостаточно.

Может кто-нибудь работал с подобной структурой и знает, как её можно ускорить?

10
  • Не совсем понятно что за спец. символы. У вас просто строки или какой - то шаблон? Слышал что можно строить автомат на хэшах. В каких то случаях даст прирост производительности.
    – Dith
    25 фев 2013 в 1:08
  • @Артём Девятов понял, посыпаю голову пеплом. Судя по описанию вполне себе ленивая динамика. Может приведете код, суммарную длину строк и их количество? Суффиксный автомат вещь быстрая, с маленькой скрытой константой в ассимптотике.
    – Dith
    25 фев 2013 в 9:05
  • @Артём Девятов, если правильно понял 4-5 секунд выполняется 500000 вызовов в каждом ищется общая подстрока 5 строк. И каждый раз это разные 5 строк по 1000 символов (кстати ascii (байт) или что?). Так? А распараллелить вызовы на количество ядер (или гипертредов) не пробовали?
    – avp
    25 фев 2013 в 20:18
  • @Артём Девятов что делает State::operator+ ? Суммирует длины путей?
    – Dith
    26 фев 2013 в 1:22
  • @Артём Девятов вы решаете реальную задачу, или с какого нибудь тестирующего сервера а-ля ACM? В замер времени входит ввод/вывод или другие действия?
    – Dith
    26 фев 2013 в 1:55

1 ответ 1

4

Из известных сейчас данных можно сделать вывод, что асимптотически улучшить ничего нельзя, 500000 тысяч раз выполнять O(5*1000) с маленькой скрытой константой даст таки 4-5 секунд.
Остается попробовать уменьшить эту константу.
1)

if (state.next[DELIM_FIRST + i] != 0)
...
for (int i = 0; i < ALPHABET; i++)
{
    if (state.next[CHAR_FIRST + i] != 0)
    {

так делать не совсем верно в плане быстродействия. map::operator[] вставляет элемент при его отсутствии, а значит появятся пустые переходы, в которых нет необходимости. Нужно что то такое:

if (state.next.find(DELIM_FIRST + i) != state.next.end())

а тут просто перебор:

for (std::map<char, int>::const_iterator i = state.next.begin(); i!= state.next.end(); ++i)
{
    ...

Так немного ускорим обработку, убрав заранее ненужные операции.

2) Раз строк для поиска всего 5, state::result можно сделать std::bitset или свою битовую маску на базе char/int.

3) В реализации из оригинальной статьи используется std::map для хранения переходов. Это дает экономию памяти и быстрый перебор, но требует логарифмическое время на нахождение перехода. Переходы эти можно сделать обычным массивом, это даст честную константу на поиске, но придется перебирать отсутствующие переходы при переборе (в старой версии статьи об этом было написано, не знаю почему убрали)

struct state {
    int len, link;
    int next[ALPHABET_SIZE];
};

На деле в столь маленькой std::map будет больше оверхэда (на поддержание дерева), и она будет работать помедленнее массива. Имеет смысл поменять и посмотреть (Если сделать так, совет #1 будет неверен).
Еще можно поменять на хэш-таблицу.

Не исключены также оптимизации исходящие из структуры входных данных.


UPD.
4) Присваивание лучше конечно убрать, вместо оператора суммы для состояния сделать operator | (это семантически вернее отражает действие), внутри битовый OR для маски.

2
  • @Dith, там комментарии закончились, отвечаю здесь: Задача будет решаться с тестирующего сервера. Если бы время на ввод и вывод учитывалось, то решить остальные задачи было бы просто невозможно, так что вряд ли 26 фев 2013 в 2:07
  • @Артём Девятов сильно ускорилось? Вы ведь релиз с оптимизацией запускаете? (глупый вопрос, ну а вдруг? бывает же) Мне тут пришел в голову алгоритм O(сумма длин строк) - сливать суффиксные деревья ^^.
    – Dith
    28 фев 2013 в 8:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.