首頁>Program>source

為什麼C ++實現了 string::find() 不会使用KMP演算法(並且不会在 O(N + M) )並在 O(N * M)中執行 ? 在C ++ 0x中可以纠正吗? 如果当前查詢的複雜性不是 O(N * M) ,那是什麼?

PS: 對不起,我是說 string::find()

那麼在gcc中實現了什麼演算法? 那是KMP吗? 如果没有,為什麼? 我已经測試過了,執行時間表明它可以在 O(N * M)中執行

最新回復
  • 5月前
    1 #

    Why the c++'s implemented string::substr() doesn't use the KMP algorithm (and doesn't run in O(N + M)) and runs in O(N * M)?

    我假設你是說 find() ,而不是 substr() 不需要搜尋,應该線上性時間內執行(並且仅因為它必须將結果複製到新字元串中)。

    C ++標準未指定實現细节,仅在某些情况下指定了複雜性要求. std::string上唯一的複雜性要求 操作是那 size()max_size()operator[]swap()c_str()data() 都是固定的時間.其他任何事物的複雜性都取決於實現您所使用的庫的人的選擇。

    選擇類似KMP之類的簡單搜尋的最可能原因是避免需要額外的儲存空間.除非要找到的字元串非常长,並且要搜尋的字元串包含很多部分匹配項,否則分配和釋放所花费的時間可能要比額外的複雜性花费更多。

    Is that corrected in c++0x?

    否,C ++ 11並未向 std::string添加任何複雜性要求 ,当然也不会添加任何強製性的實施细节。

    If the complexity of current substr is not O(N * M), what is that?

    当要搜尋的字元串包含很多长的部分匹配項時,這是最壞的情况.如果字元分佈合理合理,則平均複雜度將接近 O(N) .因此,通過選擇具有更好的最壞情况複雜度的演算法,您可能会使更典型的情况變慢得多。

  • 5月前
    2 #

    您从何處获得的印象 不使用線性演算法? 實際上,我什至無法想象如何以您所引用的複雜性来實現.而且,没有太多演算法涉及:是否有可能您认為此函式除了執行其他操作之外? std::string::substr() 只需建立一个新字元串,它从第一个引數開始,並使用第二个引數指定的字元數或直到字元串末尾的字元。

    您可能是指 std::string::substr() 没有任何複雜性要求或 std::string::find() 確實可以进行O(n * m)比较.但是,這使實現者可以在理論上具有最佳複雜性的演算法与不需要額外記憶體的演算法之間自由選擇.由於除非明確要求,否則通常不希望分配任意數量的記憶體,所以這似乎是一件合理的事情。

  • 5月前
    3 #

    FyI, gcc / libstdc ++和llvm / libcxx中的string :: find都很慢.在某些情况下,它已被顯着提高了20倍.您可能要檢查新的實現:

    GCC:PR66414優化std :: string :: find https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65

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

  • 5月前
    4 #

    C ++標準不規定 std::search()的效能特征 (或许多其他部分,包括 substr 您最有可能指的是 find 複雜性)。

    它主要決定了語言的功能方面(但有一些例外,例如非傳統的 M*N 功能)。

    實施甚至免费實施 sort 作為泡沫排序(但仅当他们希望被嘲笑並可能倒闭時)。

    例如,在 qsort部分中只有七个(非常小的)子點 C ++ 11的代碼,而其中的none都没有指定效能引數。

  • 5月前
    5 #

    让我们来看看CLRS书.在第三版的989頁上,我们进行以下练习:

    21.4.7.2 basic_string::find

    Suppose that pattern P and text T are randomly chosen strings of length m and n, respectively, from the d-ary alphabet Ʃd= {0; 1; ...; d}, where d >= 2. Show that the expected number of character-to-character comparisons made by the implicit loop in line 4 of the naive algorithm is enter image description here
    over all executions of this loop. (Assume that the naive algorithm stops comparing characters for a given shift once it finds a mismatch or matches the entire pattern.)

    Thus, for randomly chosen strings, the
      naive algorithm is quite efficient
    

    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

    我们希望一次轮班執行 Proof: 比较.現在使用求和公式並乘以有效班次數,即 1 + 1/d + ... + 1/d^{m-1} . □

    n - m + 1

  • javascript:為什麼documentGetElementById返迴null
  • java:Spring-Data-Jpa儲存庫-實體列名稱下划線