String mit Threads umkehren
Kürzlich wurde ich in einem Interview gebeten, eine String-Reverse-Funktion mit Threads zu implementieren. Ich habe den größten Teil der folgenden Lösung gefunden. Ausgewählt zu sein oder nicht, ist eine andere Geschichte :-). Ich habe versucht, die folgende Lösung auf meinem Heim-PC mit Windows 8 Consumer Preview auszuführen. Der Compiler ist VC11 Beta.
Die Frage ist, der Multithread-Code ist immer entweder so schnell oder 1 Millisekunde langsamer als der sequentielle Code. Die Eingabe, die ich gemacht habe, ist eine Textdatei mit einer Größe von 32,4 MB. Gibt es eine Möglichkeit, den Multithread-Code schneller zu machen? Oder ist der angegebene Input zu gering, um einen Unterschied zu machen?
BEARBEITEN
Ich habe nur geschriebenvoid Reverse(char* str, int beg, int end, int rbegin, int rend);
undvoid CustomReverse(char* str);
Methoden im Interview. Der gesamte andere Code wird zu Hause geschrieben.
<code> template<typename Function> void TimeIt(Function&& fun, const char* caption) { clock_t start = clock(); fun(); clock_t ticks = clock()-start; std::cout << std::setw(30) << caption << ": " << (double)ticks/CLOCKS_PER_SEC << "\n"; } void Reverse(char* str) { assert(str != NULL); for ( int i = 0, j = strlen(str) - 1; i < j; ++i, --j) { if ( str[i] != str[j]) { std::swap(str[i], str[j]); } } } void Reverse(char* str, int beg, int end, int rbegin, int rend) { for ( ; beg <= end && rbegin >= rend; ++beg, --rbegin) { if ( str[beg] != str[rbegin]) { char temp = str[beg]; str[beg] = str[rbegin]; str[rbegin] = temp; } } } void CustomReverse(char* str) { int len = strlen(str); const int MAX_THREADS = std::thread::hardware_concurrency(); std::vector<std::thread> threads; threads.reserve(MAX_THREADS); const int CHUNK = len / MAX_THREADS > (4096) ? (4096) : len / MAX_THREADS; /*std::cout << "len:" << len << "\n"; std::cout << "MAX_THREADS:" << MAX_THREADS << "\n"; std::cout << "CHUNK:" << CHUNK << "\n";*/ for ( int i = 0, j = len - 1; i < j; ) { if (i + CHUNK < j && j - CHUNK > i ) { for ( int k = 0; k < MAX_THREADS && (i + CHUNK < j && j - CHUNK > i ); ++k) { threads.push_back( std::thread([=, &str]() { Reverse(str, i, i + CHUNK, j, j - CHUNK); })); i += CHUNK + 1; j -= CHUNK + 1; } for ( auto& th : threads) { th.join(); } threads.clear(); } else { char temp = str[i]; str[i] = str[j]; str[j] = str[i]; i++; j--; } } } void Write(std::ostream&& os, const std::string& str) { os << str << "\n"; } void CustomReverseDemo(int argc, char** argv) { std::ifstream inpfile; for ( int i = 0; i < argc; ++i) std::cout << argv[i] << "\n"; inpfile.open(argv[1], std::ios::in); std::ostringstream oss; std::string line; if (! inpfile.is_open()) { return; } while (std::getline(inpfile, line)) { oss << line; } std::string seq(oss.str()); std::string par(oss.str()); std::cout << "Reversing now\n"; TimeIt( [&] { CustomReverse(&par[0]); }, "Using parallel code\n"); TimeIt( [&] { Reverse(&seq[0]) ;}, "Using Sequential Code\n"); TimeIt( [&] { Reverse(&seq[0]) ;}, "Using Sequential Code\n"); TimeIt( [&] { CustomReverse(&par[0]); }, "Using parallel code\n"); Write(std::ofstream("sequential.txt"), seq); Write(std::ofstream("Parallel.txt"), par); } int main(int argc, char* argv[]) { CustomReverseDemo(argc, argv); } </code>