问题描述
最近，有人问我在采访中实现一个字符串反向使用功能的线程。我想出了以下解决方案的大部分。选定了与否是一个不同的故事:-)。我试图运行下面的解决方案，我家的电脑运行Windows 8消费者preVIEW上。编译器是VC11 Beta版。
的问题是，在多线程code是始终无论是作为快或比顺序code 1毫秒慢。输入我给的大小32.4 MB的文本文件。有没有一种方法，使多线程code更快？抑或是给定的输入过少什么区别？
修改
我只写了 void反转（字符*海峡，诠释求，诠释年底，INT rbegin，INT雷德）; 和
无效CustomReverse（字符*海峡）; 方法的采访。所有其他code被写入在家里。
模板＆LT; typename的功能＆GT;
无效TimeIt（功能和安培;＆安培;乐趣，为const char *标题）
{
clock_t表示开始=时钟（）;
有趣（）;
用clock_t蜱=时钟（） - 启动;
性病::法院＆LT;＆LT;的std ::运输及工务局局长（30）＆LT;＆LT;标题＆LT;＆LT; ：＆其中;＆其中; （双）蜱/ CLOCKS_PER_SEC＆LT;＆LT; \ N的;
}
void反转（字符*海峡）
{
断言（海峡！= NULL）;
的for（int i = 0，J =的strlen（STR） - 1; I＆LT; D]; ++我，--j）
{
如果（STR [I]！=海峡[J]。）
{
的std ::交换（STR [我]，海峡[J]）;
}
}
}
void反转（字符*海峡，诠释求，诠释年底，INT rbegin，INT雷德）
{
对于（;求＆LT; =结束和放大器;＆安培; rbegin＆GT; =雷德++初学者，--rbegin）
{
如果（STR [求]！=海峡[rbegin]）
{
焦炭TEMP =海峡[求]
海峡[求] = STR [rbegin]
海峡[rbegin] =气温;
}
}
}
无效CustomReverse（字符*海峡）
{
INT LEN =的strlen（海峡）;
const int的max_threads的=的std ::螺纹:: hardware_concurrency（）;
的std ::矢量＆lt;的std ::线程＆GT;螺纹;
threads.reserve（max_threads的）;
const int的CHUNK = LEN / max_threads的＆GT; （4096）？ （4096）：LEN / max_threads的;
/ *性病::法院＆LT;＆LT; LEN：＆LT;＆LT; LEN＆LT;＆LT; \ N的;
性病::法院＆LT;＆LT; max_threads的：＆其中;＆其中; max_threads的＆LT;＆LT; \ N的;
性病::法院＆LT;＆LT; CHUNK：＆LT;＆LT; CHUNK＆LT;＆LT; \ N; * /
的for（int i = 0，J = LEN - 1; I＆LT; D];）
{
如果第（i + CHUNK＆其中; J＆安培;＆安培;的J - CHUNK I标记）
{
为（中间体K = 0; K＆其中; max_threads的＆安培;及（1 +＆CHUNK其中; J＆安培;＆安培;的J - CHUNK I标记）; ++ k）的
{
threads.push_back（STD ::线程（[=，＆安培; STR（）{反转（海峡，我，
1 + CHUNK，J，J - 分块）; }））;
I + = CHUNK + 1;
的J - = CHUNK + 1;
}
为（自动＆安培;日：螺纹）
{
th.join（）;
}
threads.clear（）;
}
其他
{
焦炭TEMP =海峡[I]
海峡[i] = STR [J]。
海峡[J] = STR [I]
我++;
j--;
}
}
}
无效写（的std :: ostream的＆放大器;＆放大器; OS，常量标准::字符串＆安培; STR）
{
OS＆LT;＆LT;海峡＆LT;＆LT; \ N的;
}
无效CustomReverseDemo（INT ARGC，字符** argv的）
{
性病:: ifstream的inpfile;
的for（int i = 0; I＆LT; ARGC; ++ I）
性病::法院＆LT;＆LT;的argv [1] - ;＆其中; \ N的;
inpfile.open（的argv [1]，标准::内部监督办公室::中）;
的std :: ostringstream OSS;
性病::串线;
如果（！inpfile.is_open（））
{
返回;
}
而（STD ::函数getline（inpfile，线））
{
OSS＆LT;＆LT;线;
}
标准::字符串序列（oss.str（））;
标准::字符串面值（oss.str（））;
性病::法院＆LT;＆LT; 现在倒车的\ n;
TimeIt（[安培] {CustomReverse（安培;票面[0]）;}，使用并行code \ N）;
TimeIt（[安培] {反向（放大器;序列[0]）;}，使用顺序code \ N）;
TimeIt（[安培] {反向（放大器;序列[0]）;}，使用顺序code \ N）;
TimeIt（[安培] {CustomReverse（安培;票面[0]）;}，使用并行code \ N）;
写（标准::的ofstream（sequential.txt），SEQ）;
写（标准::的ofstream（Parallel.txt），标准杆）;
}
INT主（INT ARGC，字符* argv的[]）
{
CustomReverseDemo（ARGC，ARGV）;
}
我试着写有相同的功能的程序：我的冲销努力使用线程字符串
我已经测试了与VC11 Beta版和MinGW（GCC 4.8）在Windows 7
2核处理器测试结果：
VC11 Beta版：
7 MB 文件：
调试
简单的反向：0.468
异步反向：0.275
发布
简单的反向：0.006
异步反向：0.014
98 MB 文件：
调试
简单的反向：5.982
异步反向：3.091
发布
简单的反向：0.063
异步反向：0.079
782 MB 文件
发布
简单的反向：0.567
异步反向：0.689
称为Mingw：
782 MB 文件
发布
简单的反向：0.583
异步反向：0.566
正如你所看到的多线程code胜仅在调试版本。但在发布编译器可以优化并使用所有内核即使在单线程code。
那么信任你的编译器=）
Recently, I was asked in a interview to implement a string reverse function using threads. I came up with most part of the solution below. Got selected or not is a different story :-). I tried to run the below solution on my home PC running Windows 8 consumer preview. The compiler is VC11 Beta.
The question is, the multi-threaded code is always either as fast or 1 millisecond slower than the sequential code. The input I gave is a text file of size 32.4 MB. Is there a way to make the multi-threaded code faster ? Or is it that the input given is too less to make any difference ?
EDIT
I only wrote void Reverse(char* str, int beg, int end, int rbegin, int rend); and
void CustomReverse(char* str); methods in the interview. All the other code is written at home.
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);
}
I tried to write the program with same functionality:My effort of "Reversing a string using threads"
I have tested that with 2 core processor with VC11 Beta and mingw(gcc 4.8) on Windows 7
Testing results:
VC11 Beta:
7 Mb file:
Debug
Simple reverse: 0.468
Async reverse : 0.275
Release
Simple reverse: 0.006
Async reverse : 0.014
98 Mb file:
Debug
Simple reverse: 5.982
Async reverse : 3.091
Release
Simple reverse: 0.063
Async reverse : 0.079
782 Mb file
Release
Simple reverse: 0.567
Async reverse : 0.689
Mingw:
782 Mb file
Release
Simple reverse: 0.583
Async reverse : 0.566
As you can see multi-threaded code wins only in debug build. But in release compiler makes optimization and uses all cores even in case of single-threaded code.
So trust your compiler =)
这篇关于扭转利用线程字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！