最近、あるインタビューでスレッドを使った文字列反転機能の実装を依頼されました。以下のソリューションの大部分を思いつきました。選ばれるかどうかは別の話です:-)。Windows 8 コンシューマー プレビューを実行している自宅の PC で、以下のソリューションを実行しようとしました。コンパイラは VC11 Beta です。
問題は、マルチスレッド コードが常にシーケンシャル コードと同じか、1 ミリ秒遅いかということです。私が与えた入力は、サイズが 32.4 MB のテキスト ファイルです。マルチスレッド コードを高速化する方法はありますか? それとも、与えられた入力が少なすぎて違いがないのでしょうか?
編集
インタビューでは方法void Reverse(char* str, int beg, int end, int rbegin, int rend);と方法だけを書きました。
void CustomReverse(char* str);他のすべてのコードは自宅で作成されます。
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);
}