我試圖在 C 標準中找到不同的搜索演算法。
我的實驗表明它在 MSVC 實作中要快一些，但仍然比 慢得多strstr，因為它strstr是矢量化的。使用編譯器資源管理器上的 gcc，它比默認值慢，而且strstr速度更快：https : //godbolt.org/z/zW3o87j8T
因此，如果我不太關心性能，我使用 default std::search，如果我關心，我使用strstror 手動矢量化演算法。而且 Boyer–Moore 演算法似乎不是可矢量化的，因為它執行單個字符的大表查找。
哪里std::boyer_moore_searcher有足夠廣泛的應用領域使其標準化？
這是我的測驗程式和測驗資料：
#include <chrono>
#include <cstring>
#include <iostream>
#include <functional>
#include <random>
#include <search.h>
#include <string>
const std::string haystack =
R"(Lorem ipsum dolor sit amet, consectetur adipiscing elit. Pellentesque hendrerit quam vel dui scelerisque vehicula. Suspendisse ipsum felis,
mattis vitae tortor at, rutrum semper nibh. Suspendisse dui ante, maximus sit amet lorem in, tempor ornare massa. Sed eget interdum mauris.
Vivamus iaculis ante odio, quis gravida libero aliquet ut. Orci varius natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus.
Fusce egestas, felis et sagittis luctus, nisl lacus pretium tortor, sed vestibulum arcu odio nec dolor. Quisque scelerisque diam ac facilisis placerat.
Cras et ante non nunc ornare ultricies. Pellentesque in feugiat nibh. Etiam tincidunt finibus pharetra. Proin ornare mollis elit, in pretium turpis.
Aenean pharetra ipsum enim, ultrices iaculis odio interdum eget. Proin ullamcorper ullamcorper eros, ullamcorper condimentum dolor rhoncus eget.
Fusce ligula velit, posuere quis fermentum id, faucibus ac ipsum.
Aliquam quis metus eget neque vestibulum malesuada. Suspendisse et fermentum turpis. Phasellus egestas metus quis lacinia pellentesque. Orci varius
natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. In fringilla justo vitae massa laoreet rutrum. Donec accumsan sem velit,
quis fermentum mi egestas sit amet. Suspendisse potenti. Vestibulum semper lacinia urna volutpat laoreet. Vestibulum scelerisque libero nunc, vitae
tincidunt nulla accumsan id. Sed non nisl nec nisi varius viverra nec consectetur augue. Duis lectus eros, mollis eget lectus eget, euismod bibendum
tortor. Ut pharetra euismod metus.
Morbi suscipit urna turpis, nec blandit lacus lobortis a. Donec purus nunc, elementum sit amet massa ac, dapibus pharetra enim. Mauris bibendum tempor
orci rutrum auctor. Donec sed maximus erat, porttitor interdum sapien. Donec at est id nunc pulvinar molestie. Praesent sed facilisis orci, a congue
tellus. Nulla venenatis at dolor vitae sagittis. Morbi eget dapibus diam. Ut a eros eros. Cras at augue tortor. Nam ac dictum leo, eget placerat urna.
Etiam non elit vel neque efficitur bibendum in nec nisi. Maecenas massa mi, placerat in efficitur vel, vehicula non nisi. Pellentesque vitae est velit.
Nam faucibus nibh ex, vitae fringilla odio dignissim eu. Curabitur eu dui at lectus luctus auctor sit amet sed quam. Nam volutpat, nunc dignissim
posuere aliquam, dui diam tristique quam, at mollis ex urna in nunc. Donec in dui gravida, varius elit vel, facilisis felis. Vivamus diam enim, commodo
eget porta ac, aliquet at justo. Duis in augue ac ligula malesuada vehicula eget euismod ipsum. Quisque placerat est sit amet ante elementum,
quis laoreet est auctor.
Morbi eleifend gravida dui quis dignissim. Integer sit amet iaculis turpis. Duis metus urna, imperdiet at auctor eget, lacinia sagittis magna.
Ut vestibulum justo at purus egestas, vitae gravida dui semper. Integer mattis facilisis pulvinar. Mauris vitae finibus nunc. In lacinia hendrerit diam,
et egestas tellus imperdiet quis. In vulputate fringilla tellus nec blandit. Cras dictum consequat neque, nec laoreet nibh dictum et. Praesent venenatis
enim sed rhoncus elementum. Nunc in magna in erat pretium volutpat aliquet eget purus. Maecenas porttitor velit a hendrerit dignissim. Mauris ullamcorper
mauris et magna aliquet fermentum. Ut imperdiet porta erat.)";
const std::string needle = "sed quam";
const void* volatile discard;
int main()
{
constexpr int N = 1'000'000;
auto t1 = std::chrono::steady_clock::now();
for (int i = 0; i < N; i) {
discard = std::strstr(haystack.c_str(), needle.c_str());
}
auto t2 = std::chrono::steady_clock::now();
std::default_searcher s1{ needle.begin(), needle.end() };
for (int i = 0; i < N; i) {
discard = &*std::search(haystack.begin(), haystack.end(), s1);
}
auto t3 = std::chrono::steady_clock::now();
std::boyer_moore_searcher s2{ needle.begin(), needle.end() };
for (int i = 0; i < N; i) {
discard = &*std::search(haystack.begin(), haystack.end(), s2);
}
auto t4 = std::chrono::steady_clock::now();
std::boyer_moore_horspool_searcher s3{ needle.begin(), needle.end() };
for (int i = 0; i < N; i) {
discard = &*std::search(haystack.begin(), haystack.end(), s2);
}
auto t5 = std::chrono::steady_clock::now();
std::cout
<< "strstr " << std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1) << "\n"
<< "default " << std::chrono::duration_cast<std::chrono::duration<double>>(t3 - t2) << "\n"
<< "BM " << std::chrono::duration_cast<std::chrono::duration<double>>(t4 - t3) << "\n"
<< "BMH " << std::chrono::duration_cast<std::chrono::duration<double>>(t5 - t4) << "\n";
}
uj5u.com熱心網友回復：
這取決于輸入尺寸和圖案尺寸。
我的基準測驗的圖案尺寸太小。
我從這里嘗試了作者的資料：https : //github.com/mclow/sea??rch-library。我無法快速構建基準程式，因此我將那里的資料用于我的基準程式。它表明，對于~100 位元組的模式strstr更好，但對于~8 KB 的模式，BM 和 BMH 更好。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/404908.html
標籤：
上一篇：在C 中快速列印出bitset