在研究Python和C++之间的性能折衷时,我设计了一个小示例,该示例主要侧重于哑子字符串匹配。
这是相关的C++:
using std::string;
std::vector<string> matches;
std::copy_if(patterns.cbegin(), patterns.cend(), back_inserter(matches),
[&fileContents] (const string &pattern) { return fileContents.find(pattern) != string::npos; } );
上面是用-O3构建的。
这是Python:
def getMatchingPatterns(patterns, text):
return filter(text.__contains__, patterns)
它们都采用大量模式和输入文件,并使用哑子串搜索将模式列表过滤为文件中找到的模式。
这些版本是:
令我惊讶的是性能。我在低规格的Ubuntu上都运行过,Python的运行速度提高了约20%。在具有cygwin的中端规格PC上相同-Python快两倍。
Profiler显示99%+的周期用于字符串匹配(字符串复制和列表理解无关紧要)。
显然,Python实现是本机C,我希望它与C++大致相同,但没有想到它会这么快。
与gcc相比,对CPython相关优化的任何见解都将受到欢迎。
供参考,这里是完整的示例。输入仅采用一组50K HTLM(在每次测试中均从磁盘读取,无特殊缓存):
python :
import sys
def getMatchingPatterns(patterns, text):
return filter(text.__contains__, patterns)
def serialScan(filenames, patterns):
return zip(filenames, [getMatchingPatterns(patterns, open(filename).read()) for filename in filenames])
if __name__ == "__main__":
with open(sys.argv[1]) as filenamesListFile:
filenames = filenamesListFile.read().split()
with open(sys.argv[2]) as patternsFile:
patterns = patternsFile.read().split()
resultTuple = serialScan(filenames, patterns)
for filename, patterns in resultTuple:
print ': '.join([filename, ','.join(patterns)])
C++:
#include <iostream>
#include <iterator>
#include <fstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
using MatchResult = unordered_map<string, vector<string>>;
static const size_t PATTERN_RESERVE_DEFAULT_SIZE = 5000;
MatchResult serialMatch(const vector<string> &filenames, const vector<string> &patterns)
{
MatchResult res;
for (auto &filename : filenames)
{
ifstream file(filename);
const string fileContents((istreambuf_iterator<char>(file)),
istreambuf_iterator<char>());
vector<string> matches;
std::copy_if(patterns.cbegin(), patterns.cend(), back_inserter(matches),
[&fileContents] (const string &pattern) { return fileContents.find(pattern) != string::npos; } );
res.insert(make_pair(filename, std::move(matches)));
}
return res;
}
int main(int argc, char **argv)
{
vector<string> filenames;
ifstream filenamesListFile(argv[1]);
std::copy(istream_iterator<string>(filenamesListFile), istream_iterator<string>(),
back_inserter(filenames));
vector<string> patterns;
patterns.reserve(PATTERN_RESERVE_DEFAULT_SIZE);
ifstream patternsFile(argv[2]);
std::copy(istream_iterator<string>(patternsFile), istream_iterator<string>(),
back_inserter(patterns));
auto matchResult = serialMatch(filenames, patterns);
for (const auto &matchItem : matchResult)
{
cout << matchItem.first << ": ";
for (const auto &matchString : matchItem.second)
cout << matchString << ",";
cout << endl;
}
}
参考方案
python 3.4代码b'abc' in b'abcabc'
(或您的示例中的b'abcabc'.__contains__(b'abc')
)执行 bytes_contains
方法,该方法又调用内联函数 stringlib_find
;将搜索委托给 FASTSEARCH
。
然后,FASTSEARCH
函数使用简化的Boyer-Moore搜索算法(Boyer-Moore-Horspool):
快速的搜索/计数实现,基于boyer-
摩尔和霍尔斯普尔,顶部还有一些钟声和口哨声。
有关更多背景信息,请参见:http://effbot.org/zone/stringlib.htm
如评论所述,也有一些修改:
注意:快速搜索可能会访问s[n]
,这在使用时没有问题
Python的普通字符串类型,但是如果您使用
在其他情况下使用此代码。同样,计数模式返回-1
如果目标字符串中不能匹配,则0
它实际上已经检查了匹配项,但没有找到任何匹配项。来电者
谨防!
GNU C++ Standard Library basic_string<T>::find()
实现尽可能通用(且愚蠢)。它只是在每个连续的字符位置尝试哑匹配模式,直到找到匹配为止。
TL; DR :C++标准库之所以与Python相比如此之慢的原因是,它试图在std::basic_string<char>
之上执行通用算法,但在更有趣的情况下却无法有效地做到这一点;而在Python中,程序员可以根据情况免费获得最高效的算法。
尝试从nyc Wiki页面中的高中列表中获取所有高中名称。我已经写了足够多的脚本,可以让我获取包含在高中,学业和入学条件列表的表的<tr>标记中的所有信息-但是我如何才能缩小到我认为的范围内在td[0]内休息(会弹出KeyError)-只是学校的名称?到目前为止我写的代码:from bs4 import BeautifulSoup from ur…
Python numpy数据指针地址无需更改即可更改 - python编辑经过一些摆弄之后,到目前为止,我已经隔离了以下状态:一维数组在直接输入变量时提供两个不同的地址,而在使用print()时仅提供一个地址2D数组(或矩阵)在直接输入变量时提供三个不同的地址,在使用print()时提供两个地址3D数组在直接输入变量时提供两个不同的地址,而在使用print()时仅给出一个(显然与一维数组相同)像这样:>>> …
Python Pandas导出数据 - python我正在使用python pandas处理一些数据。我已使用以下代码将数据导出到excel文件。writer = pd.ExcelWriter('Data.xlsx'); wrong_data.to_excel(writer,"Names which are wrong", index = False); writer.…
Python 3运算符>>打印到文件 - python我有以下Python代码编写项目的依赖文件。它可以在Python 2.x上正常工作,但是在使用Python 3进行测试时会报告错误。depend = None if not nmake: depend = open(".depend", "a") dependmak = open(".depend.mak…
Python ElementTree:在循环中替换元素 - python我正在尝试创建一个脚本,该脚本循环创建一个xml文件,并为两个元素增加值。 (使用netaddr的IP地址,以及递增的tag / member元素,tag01-tag10)from netaddr import IPNetwork import xml.dom.minidom import lxml.etree as etree import xml.etr…