C ++ 11 정규식은 파이썬보다 느립니다.
안녕하세요 정규식을 사용하여 분할 문자열 분할을 수행하는 다음 코드가 왜 이해하고 싶습니다
#include<regex>
#include<vector>
#include<string>
std::vector<std::string> split(const std::string &s){
static const std::regex rsplit(" +");
auto rit = std::sregex_token_iterator(s.begin(), s.end(), rsplit, -1);
auto rend = std::sregex_token_iterator();
auto res = std::vector<std::string>(rit, rend);
return res;
}
int main(){
for(auto i=0; i< 10000; ++i)
split("a b c", " ");
return 0;
}
다음 파이썬 코드보다 느립니다.
import re
for i in range(10000):
re.split(' +', 'a b c')
여기에
> python test.py 0.05s user 0.01s system 94% cpu 0.070 total
./test 0.26s user 0.00s system 99% cpu 0.296 total
나는 osx에서 clang ++를 사용하고 있습니다.
-O3로 컴파일하면 0.09s user 0.00s system 99% cpu 0.109 total
주의
이 답변도 참조하십시오 : https://stackoverflow.com/a/21708215 여기 하단 의 EDIT 2 의 기반이었습니다 .
더 나은 타이밍 측정을 위해 루프를 1000000으로 늘 렸습니다.
이것은 내 Python 타이밍입니다.
real 0m2.038s
user 0m2.009s
sys 0m0.024s
다음은 귀하의 코드에 해당하는 것입니다.
#include <regex>
#include <vector>
#include <string>
std::vector<std::string> split(const std::string &s, const std::regex &r)
{
return {
std::sregex_token_iterator(s.begin(), s.end(), r, -1),
std::sregex_token_iterator()
};
}
int main()
{
const std::regex r(" +");
for(auto i=0; i < 1000000; ++i)
split("a b c", r);
return 0;
}
타이밍:
real 0m5.786s
user 0m5.779s
sys 0m0.005s
이것은 벡터 및 문자열 객체의 생성 / 할당을 피하기위한 최적화입니다.
#include <regex>
#include <vector>
#include <string>
void split(const std::string &s, const std::regex &r, std::vector<std::string> &v)
{
auto rit = std::sregex_token_iterator(s.begin(), s.end(), r, -1);
auto rend = std::sregex_token_iterator();
v.clear();
while(rit != rend)
{
v.push_back(*rit);
++rit;
}
}
int main()
{
const std::regex r(" +");
std::vector<std::string> v;
for(auto i=0; i < 1000000; ++i)
split("a b c", r, v);
return 0;
}
타이밍:
real 0m3.034s
user 0m3.029s
sys 0m0.004s
이는 거의 100 % 성능 향상입니다.
벡터는 루프 전에 생성되며 첫 번째 반복에서 메모리를 늘릴 수 있습니다. 이후에는에 의한 메모리 할당 해제가 없으며 clear()벡터는 메모리를 유지하고 제자리에 문자열 을 구성 합니다.
또 다른 성능 향상은 생성 / 파괴를 std::string완전히 피하여 개체의 할당 / 할당 을 피하는 것 입니다.
이것은이 방향에서 잠정적 인 것입니다.
#include <regex>
#include <vector>
#include <string>
void split(const char *s, const std::regex &r, std::vector<std::string> &v)
{
auto rit = std::cregex_token_iterator(s, s + std::strlen(s), r, -1);
auto rend = std::cregex_token_iterator();
v.clear();
while(rit != rend)
{
v.push_back(*rit);
++rit;
}
}
타이밍:
real 0m2.509s
user 0m2.503s
sys 0m0.004s
궁극적 인 개선은 각 char 포인터가 원래 c 문자열 자체 내부의 하위 문자열을 가리키는 반환 값 으로 std::vectorof const char *를 갖는 것입니다. 문제는 각각이 null로 종료되지 않기 때문에 그렇게 할 수 없다는 것입니다 (이에 대해서는 이후 샘플에서 C ++ 1y 사용 참조 ).s string_ref
이 마지막 개선은 다음과 같이 달성 할 수도 있습니다.
#include <regex>
#include <vector>
#include <string>
void split(const std::string &s, const std::regex &r, std::vector<std::string> &v)
{
auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
auto rend = std::cregex_token_iterator();
v.clear();
while(rit != rend)
{
v.push_back(*rit);
++rit;
}
}
int main()
{
const std::regex r(" +");
std::vector<std::string> v;
for(auto i=0; i < 1000000; ++i)
split("a b c", r, v); // the constant string("a b c") should be optimized
// by the compiler. I got the same performance as
// if it was an object outside the loop
return 0;
}
-O3를 사용하여 clang 3.3 (트렁크에서)으로 샘플을 빌드했습니다. 다른 정규식 라이브러리가 더 나은 성능을 발휘할 수 있지만 어쨌든 할당 / 할당 해제는 종종 성능 저하입니다.
Boost.Regex
다음은 c 문자열 인수 샘플 의 boost::regex타이밍입니다 .
real 0m1.284s
user 0m1.278s
sys 0m0.005s
이 샘플의 동일한 코드 boost::regex와 std::regex인터페이스는 동일하며 네임 스페이스를 변경하고 포함하는 데만 필요합니다.
시간이 지남에 따라 더 나아지기를 바라는 C ++ stdlib 정규식 구현은 초기 단계입니다.
편집하다
완성을 위해 나는 이것을 시도했고 (위에서 언급 한 "궁극적 인 개선"제안) std::vector<std::string> &v어떤 것에서도 동등한 버전의 성능을 향상시키지 않았습니다 .
#include <regex>
#include <vector>
#include <string>
template<typename Iterator> class intrusive_substring
{
private:
Iterator begin_, end_;
public:
intrusive_substring(Iterator begin, Iterator end) : begin_(begin), end_(end) {}
Iterator begin() {return begin_;}
Iterator end() {return end_;}
};
using intrusive_char_substring = intrusive_substring<const char *>;
void split(const std::string &s, const std::regex &r, std::vector<intrusive_char_substring> &v)
{
auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
auto rend = std::cregex_token_iterator();
v.clear(); // This can potentially be optimized away by the compiler because
// the intrusive_char_substring destructor does nothing, so
// resetting the internal size is the only thing to be done.
// Formerly allocated memory is maintained.
while(rit != rend)
{
v.emplace_back(rit->first, rit->second);
++rit;
}
}
int main()
{
const std::regex r(" +");
std::vector<intrusive_char_substring> v;
for(auto i=0; i < 1000000; ++i)
split("a b c", r, v);
return 0;
}
이것은 array_ref 및 string_ref 제안과 관련이 있습니다. 다음은이를 사용하는 샘플 코드입니다.
#include <regex>
#include <vector>
#include <string>
#include <string_ref>
void split(const std::string &s, const std::regex &r, std::vector<std::string_ref> &v)
{
auto rit = std::cregex_token_iterator(s.data(), s.data() + s.length(), r, -1);
auto rend = std::cregex_token_iterator();
v.clear();
while(rit != rend)
{
v.emplace_back(rit->first, rit->length());
++rit;
}
}
int main()
{
const std::regex r(" +");
std::vector<std::string_ref> v;
for(auto i=0; i < 1000000; ++i)
split("a b c", r, v);
return 0;
}
with vector return 의 경우 복사본 string_ref보다 벡터를 반환하는 것이 더 저렴합니다 .stringsplit
2 편집
이 새로운 솔루션은 반환으로 출력을 얻을 수 있습니다. 마샬 Clow의 사용했다 string_view( string_ref이름이 변경되었다)의 libc ++ 구현에서 찾을 https://github.com/mclow/string_view .
#include <string>
#include <string_view>
#include <boost/regex.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/iterator/transform_iterator.hpp>
using namespace std;
using namespace std::experimental;
using namespace boost;
string_view stringfier(const cregex_token_iterator::value_type &match) {
return {match.first, static_cast<size_t>(match.length())};
}
using string_view_iterator =
transform_iterator<decltype(&stringfier), cregex_token_iterator>;
iterator_range<string_view_iterator> split(string_view s, const regex &r) {
return {
string_view_iterator(
cregex_token_iterator(s.begin(), s.end(), r, -1),
stringfier
),
string_view_iterator()
};
}
int main() {
const regex r(" +");
for (size_t i = 0; i < 1000000; ++i) {
split("a b c", r);
}
}
타이밍:
real 0m0.385s
user 0m0.385s
sys 0m0.000s
이것이 이전 결과에 비해 얼마나 빠른지 주목하십시오. 물론 vector루프 내부를 채우는 것은 아니지만 (아마도 사전에 아무것도 일치하지 않음) 범위를 얻습니다. 범위 기반으로 범위 for를 지정하거나 vector.
원본 (또는 null로 끝나는 문자열 ) 에 대해 iterator_range생성 범위를 지정하면 매우 가벼워지고 불필요한 문자열 할당이 생성되지 않습니다.string_viewstring
이 split구현을 사용하여 비교 하지만 실제로 채우 려면 다음과 같이 vector할 수 있습니다.
int main() {
const regex r(" +");
vector<string_view> v;
v.reserve(10);
for (size_t i = 0; i < 1000000; ++i) {
copy(split("a b c", r), back_inserter(v));
v.clear();
}
}
이것은 부스트 범위 복사 알고리즘을 사용하여 각 반복에서 벡터를 채 웁니다. 타이밍은 다음과 같습니다.
real 0m1.002s
user 0m0.997s
sys 0m0.004s
보시다시피 최적화 된 string_view출력 매개 변수 버전 과 비교할 때 큰 차이가 없습니다 .
이와 같이 작동 하는에 대한 제안std::split 도 있습니다 .
최적화의 경우 일반적으로 다음 두 가지를 피해야합니다.
- 불필요한 물건을 위해 CPU 사이클을 태우다
- 어떤 일이 일어나기를 유휴 대기 (메모리 읽기, 디스크 읽기, 네트워크 읽기, ...)
이 둘은 때로는 메모리에 모든 것을 캐싱하는 것보다 더 빠르게 계산하기 때문에 반의적일 수 있습니다. 그래서 균형의 게임입니다.
코드를 분석해 보겠습니다.
std::vector<std::string> split(const std::string &s){
static const std::regex rsplit(" +"); // only computed once
// search for first occurrence of rsplit
auto rit = std::sregex_token_iterator(s.begin(), s.end(), rsplit, -1);
auto rend = std::sregex_token_iterator();
// simultaneously:
// - parses "s" from the second to the past the last occurrence
// - allocates one `std::string` for each match... at least! (there may be a copy)
// - allocates space in the `std::vector`, possibly multiple times
auto res = std::vector<std::string>(rit, rend);
return res;
}
우리가 더 잘할 수 있습니까? 음, 메모리 할당 및 할당 해제를 유지하는 대신 기존 스토리지를 재사용 할 수 있다면 상당한 개선을 볼 수 있습니다 [1].
// Overwrites 'result' with the matches, returns the number of matches
// (note: 'result' is never shrunk, but may be grown as necessary)
size_t split(std::string const& s, std::vector<std::string>& result){
static const std::regex rsplit(" +"); // only computed once
auto rit = std::cregex_token_iterator(s.begin(), s.end(), rsplit, -1);
auto rend = std::cregex_token_iterator();
size_t pos = 0;
// As long as possible, reuse the existing strings (in place)
for (size_t max = result.size();
rit != rend && pos != max;
++rit, ++pos)
{
result[pos].assign(rit->first, rit->second);
}
// When more matches than existing strings, extend capacity
for (; rit != rend; ++rit, ++pos) {
result.emplace_back(rit->first, rit->second);
}
return pos;
} // split
수행하는 테스트에서 하위 일치 수가 반복에서 일정하게 유지되는 경우이 버전은 이길 가능성이 적습니다. 첫 번째 실행 ( rsplit및에 대해 모두 result) 에서만 메모리를 할당 한 다음 기존 메모리를 계속 재사용합니다.
[1] : 면책 조항, 저는이 코드가 정확하다는 것을 증명했을뿐입니다 (Donald Knuth가 말했듯이).
이 버전은 어때? 정규식은 아니지만 분할을 꽤 빨리 해결합니다 ...
#include <vector>
#include <string>
#include <algorithm>
size_t split2(const std::string& s, std::vector<std::string>& result)
{
size_t count = 0;
result.clear();
std::string::const_iterator p1 = s.cbegin();
std::string::const_iterator p2 = p1;
bool run = true;
do
{
p2 = std::find(p1, s.cend(), ' ');
result.push_back(std::string(p1, p2));
++count;
if (p2 != s.cend())
{
p1 = std::find_if(p2, s.cend(), [](char c) -> bool
{
return c != ' ';
});
}
else run = false;
} while (run);
return count;
}
int main()
{
std::vector<std::string> v;
std::string s = "a b c";
for (auto i = 0; i < 100000; ++i)
split2(s, v);
return 0;
}
$ 시간 splittest.exe
실제 0m0.132s 사용자 0m0.000s sys 0m0.109s
I would say C++11 regex is much slower than perl and possibly than python.
To measure properly the performance it is better to do the tests using some not trivial expression or else you are measuring everything but the regex itself.
For example, to compare C++11 and perl
C++11 test code
#include <iostream>
#include <string>
#include <regex>
#include <chrono>
int main ()
{
int veces = 10000;
int count = 0;
std::regex expres ("([^-]*)-([^-]*)-(\\d\\d\\d:\\d\\d)---(.*)");
std::string text ("some-random-text-453:10--- etc etc blah");
std::smatch macha;
auto start = std::chrono::system_clock::now();
for (int ii = 0; ii < veces; ii ++)
count += std::regex_search (text, macha, expres);
auto milli = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - start).count();
std::cout << count << "/" << veces << " matches " << milli << " ms --> " << (milli / (float) veces) << " ms per regex_search" << std::endl;
return 0;
}
in my computer compiling with gcc 4.9.3 I get the ouput
10000/10000 matches 1704 ms --> 0.1704 ms per regex_search
perl test code
use Time::HiRes qw/ time sleep /;
my $veces = 1000000;
my $conta = 0;
my $phrase = "some-random-text-453:10--- etc etc blah";
my $start = time;
for (my $ii = 0; $ii < $veces; $ii++)
{
if ($phrase =~ m/([^-]*)-([^-]*)-(\d\d\d:\d\d)---(.*)/)
{
$conta = $conta + 1;
}
}
my $elapsed = (time - $start) * 1000.0;
print $conta . "/" . $veces . " matches " . $elapsed . " ms --> " . ($elapsed / $veces) . " ms per regex\n";
using perl v5.8.8 again in my computer
1000000/1000000 matches 2929.55303192139 ms --> 0.00292955303192139 ms per regex
So in this test the ratio C++11 / perl is
0.1704 / 0.002929 = 58.17 times slower than perl
in real scenarios I get ratios about 100 to 200 times slower. So, for example parsing a big file with a million of lines takes about a second for perl while it can take more minutes(!) for a C++11 program using regex.
참고URL : https://stackoverflow.com/questions/14205096/c11-regex-slower-than-python
'development' 카테고리의 다른 글
| Android에서 콤보 박스를 표시하려면 어떻게해야합니까? (0) | 2020.10.27 |
|---|---|
| 파이썬에 불변 목록이 있습니까? (0) | 2020.10.27 |
| TypeScript 맵 파일이란 무엇입니까? (0) | 2020.10.27 |
| / etc / hosts에 와일드 카드 항목을 넣는 방법은 무엇입니까? (0) | 2020.10.27 |
| 만드는 방법 (0) | 2020.10.27 |