Защо внедреният c++ string::find() не използва KMP алгоритъм (и не работи в O(N + M)) и работи в O(N * M)? Това коригирано ли е в C++0x? Ако сложността на текущото намиране не е O(N * M), какво е това?
така че какъв алгоритъм е внедрен в gcc? това KMP ли е? ако не, защо? Тествах това и времето за работа показва, че работи в O(N * M)
Защо внедреният низ::substr() на c++ не използва алгоритъма KMP (и не работи в O(N + M)), а работи в O(N * M)?
Предполагам, че имате предвид find(), а не substr(), което не се нуждае от търсене и трябва да работи в линейно време (и само защото трябва да копира резултата в нов низ).
Стандартът C++ не уточнява подробности за изпълнението и уточнява само изискванията за сложност в някои случаи. Единствените изисквания за сложност на std::string операциите са, че size(), max_size(), operator[], swap(), c_str() и data() са с постоянно време. Сложността на всичко останало зависи от избора, направен от този, който е внедрил библиотеката, която използвате.
Най-вероятната причина да изберете просто търсене пред нещо като KMP е да избегнете нуждата от допълнително място за съхранение. Освен ако низът, който трябва да бъде намерен, е много дълъг и низът за търсене съдържа много частични съвпадения, времето, необходимо за разпределяне и освобождаване, вероятно ще бъде много повече от цената на допълнителната сложност.
Това коригирано ли е в c++0x?
Не, C++11 не добавя никакви изисквания за сложност към std::string и със сигурност не добавя никакви задължителни подробности за изпълнението.
Ако сложността на текущия substr не е O(N * M), какво е това?
Това е сложността в най-лошия случай, когато низът за търсене съдържа много дълги частични съвпадения. Ако знаците имат разумно равномерно разпределение, тогава средната сложност ще бъде по-близо до O(N). Така че, като изберете алгоритъм с по-добра сложност в най-лошия случай, можете да направите по-типичните случаи много по-бавни.
O(N * M) за малки Ns и KMP за големи Ns. Той също така изисква O(N) памет, така че общият ред на паметта не се променя.
- person Farzam; 15.01.2012
M и N. Надеждното оценяване кой алгоритъм би бил по-бърз би било също толкова сложно, колкото извършването на самото търсене и не мисля, че усложняването на алгоритъма с ненадеждна оценка би било от полза за някого. Но, разбира се, не съм изучавал това толкова много, колкото тези, които внедриха библиотеките, така че не мога да коментирам точно защо поне някои от тях избраха проста реализация, извън наблюденията, които вече направих.
- person Mike Seymour; 15.01.2012
std::search() и е по-добре да инвестирате време в подобряване на други алгоритми (чувствам, че звуча като PJ!), 3. за очакваните случаи на употреба O(n * m) изглежда има по-добра или поне приемлива производителност. Наистина обаче не съм внедрил KMP, за да го тествам.
- person Dietmar Kühl; 15.01.2012
std::search(): докато std::search() се поддържа от предни итератори KMP търсенето използва масиви доста силно и все още не виждам как да избегна напредналите итератори (добре , версията, която имам в момента, дори не опитвам: тя изисква итератори с произволен достъп), въпреки че мисля, че получената сложност все още трябва да е линейна (обаче не съм се убедил напълно в това).
- person Dietmar Kühl; 16.01.2012
FYI, низът::find както в gcc/libstdc++, така и в llvm/libcxx беше много бавен. Подобрих и двата доста значително (с ~ 20x в някои случаи). Може да искате да проверите новата реализация:
GCC: PR66414 optimize std::string::find https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65
LLVM: https://reviews.llvm.org/D27068
Новият алгоритъм е по-прост и използва ръчно оптимизирани асемблиращи функции на memchr и memcmp.
Откъде имате впечатлението, че std::string::substr() не използва линеен алгоритъм? Всъщност дори не мога да си представя как да внедря по начин, който има сложността, която цитирахте. Освен това не е включен много алгоритъм: възможно ли е да смятате, че тази функция прави нещо друго, отколкото? std::string::substr() просто създава нов низ, започвайки от първия си аргумент и използвайки или броя знаци, посочени от втория параметър, или знаците до края на низа.
Може да имате предвид std::string::find(), който няма никакви изисквания за сложност или std::search(), който наистина има право да прави O(n * m) сравнения. Това обаче дава на изпълнителите свободата да избират между алгоритъм, който има най-добрата теоретична сложност, срещу алгоритъм, който не се нуждае от допълнителна памет. Тъй като разпределянето на произволни количества памет обикновено е нежелателно, освен ако не е изрично поискано, това изглежда разумно нещо.
Стандартът C++ не диктува характеристиките на производителността на substr (или много други части, включително find, за който най-вероятно имате предвид със сложност M*N).
Той диктува най-вече функционалните аспекти на езика (с някои изключения като ненаследените sort функции, например).
Реализациите дори са свободни да внедрят qsort като балонно сортиране (но само ако искат да бъдат осмивани и евентуално да излязат от бизнеса).
Например, има само седем (много малки) подточки в раздел 21.4.7.2 basic_string::find на C++11 и нито една от тях не посочва параметри за производителност.
qsort(), но std::sort() трябва да има сложност O(n * ln(n)) в C++2011. В C++2003 беше позволено да има сложност O(n * n), за да има бързо сортиране да бъде жизнеспособен избор за алгоритъм, но беше показано, че можете да получите подобна нормална производителност с introsort както бихте получили за бързо сортиране, докато имате сложност в най-лошия случай O(n * ln(n)). Изпълнителят е свободен да използва различен алгоритъм със същата сложност в най-лошия случай.
- person Dietmar Kühl; 15.01.2012
qsort няма такива изисквания, той е чисто функционален, както в C. По-важното е, че докато някои части на C++ имат такива изисквания, substr и find не са част от това подмножество. Но повдигнахте добра гледна точка относно нещата за сортиране без наследство, така че добавих това към отговора.
- person paxdiablo; 15.01.2012
Нека да разгледаме книгата CLRS. На страница 989 от третото издание имаме следното упражнение:
Да предположим, че шаблон P и текст T са произволно избрани низове с дължина m и n, съответно, от d-арната азбука Ʃd = {0; 1; ...; d}, където d >= 2. Покажете, че очакваният брой сравнения между символи, направени от неявния цикъл в ред 4 на простия алгоритъм, е
над всички изпълнения на този цикъл. (Да приемем, че наивният алгоритъм спира да сравнява знаци за дадена промяна, след като открие несъответствие или съвпадне с целия шаблон.) По този начин, за произволно избрани низове, наивният алгоритъм е доста ефективен.
NAIVE-STRING-MATCHER(T,P)
1 n = T:length
2 m = P:length
3 for s = 0 to n - m
4 if P[1..m] == T[s+1..s+m]
5 print “Pattern occurs with shift” s
Доказателство:
За една смяна се очаква да извършим 1 + 1/d + ... + 1/d^{m-1} сравнения. Сега използвайте формулата за сумиране и умножете по броя на валидните смени, което е n - m + 1. □
Откъде получавате информация за C++ библиотеката? Ако наистина имате предвид string::search и той наистина не използва алгоритъма KMP, предполагам, че това е така, защото този алгоритъм обикновено не е по-бърз от обикновено линейно търсене поради необходимостта да се изгради таблица за частично съвпадение, преди търсенето да може да продължи.
Ако ще търсите един и същ модел в множество текстове. Алгоритъмът на BoyerMoore е добър избор, тъй като таблиците с шаблони трябва да бъдат изчислени само веднъж, но се използват многократно при търсене на множество текстове. Ако обаче ще търсите шаблон само веднъж в 1 текст, режийните разходи за изчисляване на таблиците заедно с режийните разходи за разпределяне на памет ви забавят твърде много и std::string.find(....) ще ви победи тъй като не разпределя никаква памет и няма допълнителни разходи. Boost има множество алгоритми за търсене на низове. Открих, че BM е с порядък по-бавен в случай на търсене на единичен шаблон в 1 текст, отколкото std::string.find(). За моите случаи BoyerMoore рядко беше по-бърз от std::string.find() дори при търсене на множество текстове със същия модел. Ето връзката към BoyerMoore BoyerMoore
string::find, вижте публикацията ми: stackoverflow.com/questions/19506571/ - person Peter Lee schedule 25.10.2013(std::string(n-1,'a')+"b"+std::string(n,'a')).find(std::string(n,'a'))е O(n^2) или по-лошо. напр. за n = 1 милион отнема 21 секунди на моя компютър, но би трябвало да е мигновено (може би няколко милисекунди). - person Don Hatch schedule 12.04.2020