Recherche regex en arrière C ++

Je n’ai pas assez de réputation pour commenter XD. Je ne vois pas ce qui suit comme une réponse, mais plutôt une alternative. Néanmoins, je dois répondre, sinon je ne vous atteindrai pas.

Je suppose que vous ne trouverez pas d’astuce pour rendre la performance indépendante de la position (devinez qu’elle va linéaire pour une regex aussi simple ou autre).

Une solution très simple consiste à remplacer cette horrible lib regex par, par exemple, le posix regex.h (old but gold;) ou à regex boost.

Voici un exemple:

 #include  #include  #include  #include  #include  inline auto now = std::chrono::steady_clock::now; inline auto toMs = [](auto &&x){ return std::chrono::duration_cast(x).count(); }; void cregex(std::ssortingng const&s, std::ssortingng const&p) { auto start = now(); regex_t r; regcomp(&r,p.data(),REG_EXTENDED); std::vector m(r.re_nsub+1); regexec(&r,s.data(),m.size(),m.data(),0); regfree(&r); std::cout << toMs(now()-start) << "ms " << std::string{s.cbegin()+m[1].rm_so,s.cbegin()+m[1].rm_eo} << std::endl; } void cxxregex(std::string const&s, std::string const&p) { using namespace std; auto start = now(); regex r(p.data(),regex::extended); smatch m; regex_search(s.begin(),s.end(),m,r); std::cout << toMs(now()-start) << "ms " << m[1] << std::endl; } void boostregex(std::string const&s, std::string const&p) { using namespace boost; auto start = now(); regex r(p.data(),regex::extended); smatch m; regex_search(s.begin(),s.end(),m,r); std::cout << toMs(now()-start) << "ms " << m[1] << std::endl; } int main() { std::string s(100000000,'x'); std::string s1 = "yolo" + s; std::string s2 = s + "yolo"; std::cout << "yolo + ... -> cregex "; cregex(s1,"^(yolo)"); std::cout << "yolo + ... -> cxxregex "; cxxregex(s1,"^(yolo)"); std::cout << "yolo + ... -> boostregex "; boostregex(s1,"^(yolo)"); std::cout << "... + yolo -> cregex "; cregex(s2,"(yolo)$"); std::cout << "... + yolo -> cxxregex "; cxxregex(s2,"(yolo)$"); std::cout << "... + yolo -> boostregex "; boostregex(s2,"(yolo)$"); } 

Donne:

 yolo + ... -> cregex 5ms yolo yolo + ... -> cxxregex 0ms yolo yolo + ... -> boostregex 0ms yolo ... + yolo -> cregex 69ms yolo ... + yolo -> cxxregex 2594ms yolo ... + yolo -> boostregex 62ms yolo 

Je viens de me rendre compte…

Que mes solutions proposées ci-dessous ne fonctionnent pas. Eh bien, au moins s’il y a plusieurs “yolo” dans le texte. Il ne renvoie pas la “première instance trouvée dans la chaîne”, mais la “première instance trouvée dans une sous-chaîne de la chaîne”. Donc, si vous avez 4 processeurs, la chaîne est divisée en 4 sous-chaînes. Le premier à revenir “yolo” ‘gagne’. Cela peut être correct si vous voulez uniquement savoir si “yolo” figure n’importe où dans le texte, mais pas si vous souhaitez obtenir la position de la première instance.

Ancienne réponse

En me basant sur la réponse d’OZ, j’ai écrit une version parallèle. edit: utilise maintenant les sémaphores pour finir plus tôt.

 #include  #include  std::mutex g_mtx; std::condition_variable g_cv; int g_found_at = -1; void thread( int id, std::ssortingng::const_iterator begin, std::ssortingng::const_iterator end, const boost::regex& r, boost::smatch* const m) { boost::smatch m_i; if (regex_search(begin, end, m_i, r)) { *m = m_i; std::unique_lock lk(g_mtx); g_found_at = id; lk.unlock(); g_cv.notify_one(); } } #include  #include  #include  #include  #include  using namespace std::chrono_literals; void boostparregex(std::ssortingng const &s, std::ssortingng const &p) { { std::unique_lock lk(g_mtx); g_found_at = -1; } auto nrOfCpus = std::thread::hardware_concurrency() / 2; std::cout << "(Nr of CPUs: " << nrOfCpus << ") "; auto start = steady_clock::now(); boost::regex r(p.data(), boost::regex::extended); std::vector> m; m.reserve(nrOfCpus); std::generate_n(std::back_inserter(m), nrOfCpus, []() { return std::make_shared(); }); std::vector t; t.reserve(nrOfCpus); auto sizePerThread = s.length() / nrOfCpus; for (size_t tId = 0; tId < nrOfCpus; tId++) { auto begin = s.begin() + (tId * sizePerThread); auto end = tId == nrOfCpus - 1 ? s.end() : s.begin() + ((tId + 1) * sizePerThread) - 1; t.push_back(std::thread(thread, (int)tId, begin, end, r, m[tId].get())); } { std::unique_lock lk(g_mtx); g_cv.wait_for(lk, 10s, []() { return g_found_at >= 0; }); } { std::unique_lock lk(g_mtx); if (g_found_at < 0) std::cout << "Not found! "; else std::cout << m[g_found_at]->str() << " "; } std::cout << toMs(steady_clock::now() - start) << "ms " << std::endl; for (auto& thr : t) thr.join(); } 

Ce qui me donne cette sortie (ne pas avoir posix sous vs2017)

 yolo + ... -> cxxregex 0ms yolo yolo + ... -> boostregex 1ms yolo yolo + ... -> boostparregex (Nr of CPUs: 4) yolo 13ms ... + yolo -> cxxregex 5014ms yolo ... + yolo -> boostregex 837ms yolo ... + yolo -> boostparregex (Nr of CPUs: 4) yolo 222ms 

Je reçois une accélération jusqu'à 4 fois plus rapide sur 4 processeurs. Il y a des frais généraux pour démarrer les threads

ps ceci est mon premier programme de threads C ++ et ma première expression rationnelle, il pourrait donc y avoir quelques optimisations possibles.