Соответствие строк: gcc и CPython

Изучая компромисс между производительностью 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) 

Оба они берут многообразный набор шаблонов и входной файл и фильтруют список шаблонов к тем, которые находятся в файле, используя поиск поддельной подстроки.

Версии:

  • gcc – 4.8.2 (Ubuntu) и 4.9.2 (cygwin)
  • python – 2.7.6 (Ubuntu) и 2.7.8 (cygwin)

Для меня было неожиданностью. Я запустил оба с низким уровнем Ubuntu, а Python был быстрее примерно на 20%. То же самое на ПК с mid-spec с cygwin – Python в два раза быстрее. Профилер показывает, что 99%% циклов расходуются на соответствие строк (строковое копирование и понимание списков несущественны).

Очевидно, что реализация Python является родной C, и я ожидал, что она будет примерно такой же, как C ++, но не ожидала ее так же быстро.

Любое понимание соответствующих оптимизаций CPython по сравнению с gcc было бы очень желанным.

Для справки, вот полные примеры. Входы просто берут набор 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; } } 

One Solution collect form web for “Соответствие строк: gcc и CPython”

Код python 3.4 b'abc' in b'abcabc' (или b'abcabc'.__contains__(b'abc') как в вашем примере) выполняет метод bytes_contains , который, в свою очередь, вызывает встроенную функцию stringlib_find; который делегирует поиск FASTSEARCH .

Затем функция FASTSEARCH использует модифицированный алгоритм поиска Boyer-Moore :

быстрая реализация поиска / подсчета, основанная на сочетании между болотом и хорвалом, с еще несколькими колокольчиками и свистами на вершине. для получения дополнительной информации см .: http://effbot.org/zone/stringlib.htm

Есть также некоторые изменения, о которых свидетельствуют комментарии:

note: fastsearch может получить доступ к s[n] , что не является проблемой при использовании обычных типов строк Python, но может вызвать проблемы, если вы используете этот код в других контекстах. также, режим count возвращает -1 если в целевой строке невозможно совпадение, а 0 если он действительно проверял совпадения, но не нашел. абоненты остерегайтесь!


Стандартная библиотека GNU C ++ basic_string<T>::find() является как можно более универсальной (и немой); он просто пытается тупо сопоставить шаблон в каждой позиции подряд, пока не найдет совпадение.


TL; DR : причина, по которой стандартная библиотека C ++ настолько медленна по сравнению с Python, состоит в том, что она пытается сделать общий алгоритм поверх std::basic_string<char> , но не делает это эффективно для более интересных случаев; в то время как в Python программист получает наиболее эффективные алгоритмы в каждом конкретном случае бесплатно.

Python - лучший язык программирования в мире.