Можете ли вы ускорить этот алгоритм? C#/C++

Question

Эй, я время от времени работал над чем-то, и теперь он стал относительно большим (и медленным). Однако мне удалось точно определить узкое место после тщательного измерения производительности в зависимости от времени.

Скажем, я хочу «переставить» строку «ABC». То, что я имею в виду под «перестановочны» не совсем перестановка, а непрерывный набор подстрока следуя схеме:

A 
AB 
ABC 

B 
BC 

C 

я должен проверить для каждой подстроки, если она содержится в другой строке S2, так что я сделал некоторые Quick'n грязного буквального выполнения следующим образом:

for (int i = 0; i <= strlen1; i++) 
{ 
    for (int j = 0; j <= strlen2- i; j++) 
    { 
     sub = str1.Substring(i, j); 
     if (str2.Contains(sub)) {do stuff} 
     else break; 

Это было очень медленным, но сначала, как только я понял, что если первая часть оленьей кожа существует, нет необходимости проверять для последующего это означает, что если саб не содержащийся в str2, я могу вызвать break во внутреннем цикле.

Хорошо, это дало быстрые результаты, но, вычисляя сложность моего алгоритма, я понял, что в худшем случае это будет N^4? Я забыл, что str.contains() и str.substr() имеют свои собственные сложности (N или N^2, я забыл, что).

Тот факт, что у меня есть огромное количество вызовов для тех, кто находится внутри цикла 2-го цикла, заставляет его выполнять, а .. ну N^4 ~ сказал достаточно.

Однако я вычислил среднее время выполнения этого математически с использованием теории вероятностей для оценки вероятности роста подстроки в пуле случайно сгенерированных строк (это была моя базовая линия), измеряя, когда вероятность стала> 0,5 (50%)

Это показало экспоненциальную зависимость между количеством различных символов и длиной строки (примерно), что означает, что в сценарии я использую свой алгоритм длину string1 обыкновение (наиболее вероятно) никогда не превышает 7

Таким образом, средняя сложность будет ~ O (N * M), где N - длина строки1, а M - длина строки 2. Из-за того, что я протестировал N в functio n константы M, я получил линейный рост ~ O (N) (неплохо противостоял N^4 eh?)

Я проверил время и построил график, который показал почти идеальный линейный рост, поэтому я получил свой фактические результаты, соответствующие моим математическим предсказаниям (yay!)

Однако это НЕ принималось во внимание стоимость string.contains() и string.substring(), которая заставляла меня задаться вопросом, можно ли еще оптимизировать ее?

Я также думал о том, чтобы сделать это на C++, потому что мне нужен материал с низким уровнем знаний? Ребята, что вы думаете? Я положил время на анализ этой надежды, я разработал все достаточно ясно :)!

Answer 1

Ваш вопрос отмечен как C++, так и C#.

В C++ оптимальным решением будет использование итераторов и std::search. Исходные строки остаются неизмененными, и промежуточные объекты не создаются. Совсем не будет эквивалента вашей Substring(), поэтому это устраняет эту часть служебных данных.

Это должно обеспечить теоретически наилучшую производительность: поиск грубой силы, тестирование всех перестановок без создания или уничтожения промежуточных объектов, кроме самих итераторов, которые просто заменяют ваши переменные индекса int.Я не могу придумать более быстрый способ реализации этого базового алгоритма.

Answer 2

Вы тестируете одну строку на одну строку? Если вы тестируете связку строк против другой группы строк, это совершенно другая история. Даже если у вас есть лучший алгоритм для сравнения одной строки с другой O(X), это не значит, что она повторяется M * N раз. Вы получите лучший алгоритм для обработки строк M против N.

Когда я сделал что-то знакомое, я построил словарь всех подстрок всех N строк

Dictionary<string, List<int>> 

string подстрока и int является индекс строки, которая содержит, что подстроки. Затем я проверил все подстроки всех строк M против него. Скорость была внезапно не O(M*N*X), но O(max(M,N)*S), где S - количество подстрок одной строки. В зависимости от M, N, X, S, которые могут быть быстрее. Я не говорю, что словарь подстрок - лучший подход, я просто хочу указать, что вы всегда должны пытаться увидеть всю картину.