C ++ string :: encontrar complexidade

Por que a string::find() implementada do c ++ string::find() não usa o algoritmo KMP (e não roda em O(N + M) ) e roda em O(N * M) ? Isso é corrigido em C ++ 0x? Se a complexidade da descoberta atual não é O(N * M) , o que é isso?

PS: Desculpe quer dizer string::find()

Então, qual algoritmo é implementado no gcc? é esse KMP? se não, por quê? Eu testei isso e o tempo de execução mostra que ele é executado em O(N * M)

Por que o string :: substr () implementado pelo c ++ não usa o algoritmo KMP (e não roda em O (N + M)) e roda em O (N * M)?

Eu suponho que você quer dizer find() , ao invés de substr() que não precisa procurar e deve ser executado em tempo linear (e só porque ele tem que copiar o resultado em uma nova string).

O padrão C ++ não especifica detalhes de implementação e apenas especifica requisitos de complexidade em alguns casos. Os únicos requisitos de complexidade em operações std::string são que size() , max_size() , operator[] , swap() , c_str() e data() são todos constantes. A complexidade de qualquer outra coisa depende das escolhas feitas por quem implementou a biblioteca que você está usando.

O motivo mais provável para escolher uma pesquisa simples sobre algo como o KMP é evitar a necessidade de armazenamento extra. A menos que a string a ser encontrada seja muito longa, e a string a ser pesquisada contenha muitas correspondências parciais, o tempo gasto para alocar e liberar isso provavelmente será muito mais do que o custo da complexidade extra.

Isso é corrigido em c ++ 0x?

Não, o C ++ 11 não adiciona nenhum requisito de complexidade ao std::string , e certamente não adiciona detalhes de implementação obrigatórios.

Se a complexidade do substr atual não é O (N * M), o que é isso?

Essa é a complexidade do pior caso, quando a string para pesquisa contém muitas correspondências parciais longas. Se os caracteres tiverem uma distribuição razoavelmente uniforme, então a complexidade média estaria mais próxima de O(N) . Então, escolhendo um algoritmo com maior complexidade de pior caso, você pode tornar os casos mais comuns muito mais lentos.

De onde você tira a impressão de que std::string::substr() não usa um algoritmo linear? Na verdade, não consigo nem imaginar como implementar de uma forma que tenha a complexidade que você citou. Além disso, não há muito de um algoritmo envolvido: é possível que você pense que essa function faz algo mais do que faz? std::string::substr() apenas cria uma nova string começando em seu primeiro argumento e usando o número de caracteres especificado pelo segundo parâmetro ou os caracteres até o final da string.

Você pode estar se referindo a std::string::find() que não possui nenhum requerimento de complexidade ou std::search() que é de fato permitido fazer comparações O (n * m). No entanto, este é um dar implementadores a liberdade de escolher entre um algoritmo que tem a melhor complexidade teórica vs. um que não precisa de memory adicional. Uma vez que a alocação de quantidades arbitrárias de memory é geralmente indesejável, a menos que especificamente solicitada, isso parece uma coisa razoável a ser feita.

FYI, A string :: find em ambos os gcc / libstdc ++ e llvm / libcxx eram muito lentos. Ele foi melhorado significativamente em 20x em alguns casos. Você pode querer verificar a nova implementação:

GCC: PR66414 otimizar std :: string :: ache https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65

LLVM: https://reviews.llvm.org/D27068

O padrão C ++ não dita as características de desempenho do substr (ou muitas outras partes, incluindo o find você provavelmente está se referindo com uma complexidade M*N ).

Ele dita principalmente aspectos funcionais da linguagem (com algumas exceções, como as funções de sort não legadas, por exemplo).

As implementações são mesmo gratuitas para implementar o qsort como um tipo de bolha (mas apenas se eles querem ser ridicularizados e possivelmente saírem do negócio).

Por exemplo, existem apenas sete sub-pontos (muito pequenos) na seção 21.4.7.2 basic_string::find de C ++ 11, e nenhum deles especifica parâmetros de desempenho.

Vamos dar uma olhada no livro do CLRS. Na página 989 da terceira edição, temos o seguinte exercício:

Suponha que o padrão P e o texto T sejam seqüências de comprimento aleatoriamente escolhidas m e n, respectivamente, do alfabeto d-ário dƩ {0; 1; …; d}, onde d> = 2. Mostre que o número esperado de comparações de caractere para caractere feitas pelo loop implícito na linha 4 do algoritmo ingênuo é insira a descrição da imagem aqui
sobre todas as execuções desse loop. (Suponha que o algoritmo ingênuo pare de comparar caracteres para um determinado deslocamento, uma vez que ele encontre uma incompatibilidade ou corresponda a todo o padrão.) Assim, para seqüências de caracteres escolhidas aleatoriamente, o algoritmo ingênuo é bastante eficiente .

 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 

Prova:

Para um único turno, esperamos realizar comparações 1 + 1/d + ... + 1/d^{m-1} . Agora use a fórmula de sum e multiplique pelo número de turnos válidos, que é n - m + 1 . □

Onde você obtém suas informações sobre a biblioteca C ++? Se você quer dizer string::search e realmente não usa o algoritmo KMP então eu sugiro que é porque esse algoritmo não é geralmente mais rápido que uma busca linear simples devido a ter que construir uma tabela de correspondência parcial antes que a pesquisa possa prosseguir.