Улучшить обозначение алгоритма Big O с O (n ^ 2) до чего-то лучшего - PullRequest
Новая
       25

Улучшить обозначение алгоритма Big O с O (n ^ 2) до чего-то лучшего

0 голосов
/ 28 июня 2018

Я ищу, чтобы улучшить алгоритм, который у меня сейчас есть, который, хотя он работает, в настоящее время имеет сложность O (n ^ 2). Я пытаюсь уменьшить эту сложность, если это возможно, или улучшить / изменить сам алгоритм для улучшения времени выполнения.

У меня есть список строк, каждая из которых содержит несколько слов, и конечная цель - найти «совпадения» между этими строками, отсортированные по процентному «сходству».

Допустим, у меня есть следующие строки:

"Конец света"
«Начало путешествия»
«Конец Времени»
«Время, когда мы покинули этот мир сегодня»

Мой алгоритм выполняет следующие шаги:

  • Перебирайте каждую строку, разбивая каждую строку на составляющие ее слова и упорядочивая эти слова в алфавитном порядке (регистр не чувствителен во всем алгоритме). (то есть «Конец света» становится «Концом света». «Время, когда мы покинули этот мир сегодня», становится «Оставленным на этот раз сегодня мы, мир» и т. д.)
  • По деловым причинам определенные слова удаляются из обработанной строки. Обычно это местоимения и другие подобные слова - то есть, и т. Д., Поэтому «Конец Света» становится «Концом Света».
  • Теперь у нас есть список строк, разбитых и собранных в алфавитном порядке из составляющих их слов с удалением определенных несущественных слов.
  • Во-первых, я могу просто посмотреть, есть ли точные дубликаты в списке. Это тривиально и позволяет мне идентифицировать те строки, которые на 100% совпадают.
  • Теперь, однако, идет самая сложная часть и самая медленная часть алгоритма. Я должен перебрать список строк, сравнивая каждую строку с каждой другой строкой в ​​списке (то есть вложенным циклом), чтобы определить, сколько слов имеет каждая строка из двух сравниваемых. при сравнении «Конец света» и «Конец времени», существует 66,6% общности, поскольку обе строки имеют два из трех общих слов. Сравнивая «Конец света» с «Оставив на этот раз сегодня мы мир», мы обнаруживаем, что между двумя строками есть только одно общее слово (так как в каждой строке разное количество слов, фактический процент в этом случае рассчитывается на основе среднее между двумя - так что примерно 22% общности).

В конечном счете, у меня остаются пары строк (каждая возможная пара всех строк в начальном списке) и процентное значение соответствия между ними. Затем я могу отменить все эти совпадения ниже некоторого порога и работать только с теми, которые выше порога. Порог определяется пользователем, и весь алгоритм служит способом «фильтрации» очень большого набора данных, позволяя человеческим глазным яблокам работать только с теми частями данных, которые в первую очередь кажутся близкими.

Как вы можете себе представить из вложенного цикла (то есть раздела O (n ^ 2)) алгоритма, это очень медленно и становится значительно медленнее с ростом размера ввода.

Есть ли способ улучшить Big O этого алгоритма или есть какие-либо изменения в алгоритме, производящие такой же вывод, который улучшит сложность среды выполнения?

1 Ответ

0 голосов
/ 30 июня 2018

Существует дополнительная сложность, если вы тянете за собой строки во всех вычислениях, что делает последнюю операцию не O (M ^ 2), а O (M ^ 2 * sizeof (предложение) * AvgLength (слово))

Посмотрим (код концепции) 

std::vector<std::set<int>> sSets;
sentenceSets.reserve(sentences.size());

for(auto& sentence : sentences) { // O(m)
  std::vector<const char *> words = SplitWord(sentence); // O(n) needs to go through all letters.
  sSet.emplace_back();
  for(auto& word: words) {
    int wordNo = LookUp(word); // table of all words, with entries of 0 for unwanted words. O(log AllWords)
    if (wordNo)
      sSet.back().insert(wordNo); // also removes duplicates. O(Log(#diff words in sentence))
  }
}

Всего O (m Log (AllWords) avgWordLen) или O (m collisionFactor avgWordLen), если вы считаете, что ваша хэш-таблица всех возможных слов работает отлично.

LookUp сохраняет коэффициент O (буквы в слове) для всех последующих сравнений. 

for(const auto& theSet : sSet) { // O(sSet.size()
  for(const auto& cmpSet : sSet) { // O(sSet.size()
    std::vector<int> intersect;
    std::set_intersection(theSet.begin(), theSet.end(),
                          cmpSet.begin(), cmpSet.end(),
                          std::back_insert<std::vector<int>>(intersect)); // O(set.size())
    StoreRes(theSet, cmpSet, intersect);
  }
}

Всего здесь O (sSet.size () ^ 2 * O (set.size ()). Может быть оптимизирован для запуска только O (sSet.size () * sSet.size () / 2), поскольку таблица симметрична.

Использование LookUp сохраняет здесь коэффициент O (размер слова).

std :: set может быть заменен некоторым flat_set для более быстрых операций в реальном мире.

...