当前在线人数13602
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
一个多线程的简单问题
[版面:待字闺中][首篇作者:khing] , 2015年10月19日01:32:14 ,977次阅读,11次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
khing
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: khing (^_^), 信区: JobHunting
标  题: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 01:32:14 2015, 美东)

一大堆数,要按照第一位拷贝到不同的int array里面,比如:
[37, 57, 653, 12, 52, 501, 91, ...]
->
Bucket 1: [12]
Bucket 3: [37]
Bucket 5: [57, 52, 501]
Bucket 6: [653]
Bucket 9: [91]

考虑用多线程来提高效率

想了两个办法:
1. 把数组分成8等份,用8个线程同时做。问题是写入buckets的时候会引发大量锁操作
2. 用9个线程,各自负责一个bucket,看起来貌似就不需要锁了,不知道是否够快

还有更好的办法吗?

--
※ 修改:·khing 於 Oct 19 01:32:45 2015 修改本文·[FROM: 203.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 203.]

 
taar
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: taar (taar), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 01:38:38 2015, 美东)

数据 特别大 可以考虑mapreduce.
否则就你说的地二种方法不錯阿
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 72.]

 
khing
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: khing (^_^), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 01:54:53 2015, 美东)

又想到一个办法。还是把数组分成8等份,用8个线程同时做,和第一种方法的区别是它
们把数据放到自己的小桶里面。都完成之后,再把这些小桶连接起来。

这个要用C++实现,传进来的是一个vector。还没想好桶用什么数据结构

如果也用vector或者list,感觉会慢,因为要在堆上分配大量的内存才行
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 203.]

 
henrycode
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: henrycode (双蓝), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 01:58:57 2015, 美东)

vector 的push_back 不是thread safe么原子操作吗?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
airbots
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: airbots (a叔), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 02:31:07 2015, 美东)

并行计算需要考虑两个因素,数据依赖和流程依赖,你这个例子有数据依赖,没有流程
依赖。

简单来讲,避免多对多的通信,可以用数据复制来减少通信,每个thread有一份所有数
据的拷贝,第一个thread做数组1,第二个thread座数组2,以此类推,最后大家各自输
出各自的;performance瓶颈在你的最慢的thread上

如果不在乎通信,那就分数据,每个thread编号,每个进程都计算出自己的总结果,一
号负责收集最后的数组1,二号thread负责收集数组2,以此类推,bottleneck在最慢的
thread和最慢的网络,两者去最大值。这个就是mapreduce的做法。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

 
airbots
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: airbots (a叔), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 02:35:02 2015, 美东)

再复杂的话,只有这两个基本解法的融合,根据你自己系统的硬件条件来决定,因为计
算量不大,不需要GPU,如果算法复杂度大的话,可以在二级并行上使用GPU。
【 在 airbots (a叔) 的大作中提到: 】
: 并行计算需要考虑两个因素,数据依赖和流程依赖,你这个例子有数据依赖,没有流程
: 依赖。
: 简单来讲,避免多对多的通信,可以用数据复制来减少通信,每个thread有一份所有数
: 据的拷贝,第一个thread做数组1,第二个thread座数组2,以此类推,最后大家各自输
: 出各自的;performance瓶颈在你的最慢的thread上
: 如果不在乎通信,那就分数据,每个thread编号,每个进程都计算出自己的总结果,一
: 号负责收集最后的数组1,二号thread负责收集数组2,以此类推,bottleneck在最慢的
: thread和最慢的网络,两者去最大值。这个就是mapreduce的做法。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

 
henrycode
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: henrycode (双蓝), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 03:07:18 2015, 美东)

为啥要lock 数字入哪个 bucket 不会错啊, 可能出错的是入bucket 的顺序, 可是那
个重要吗, 线程本来就不能guarentee顺序啊。 
【 在 khing (^_^) 的大作中提到: 】
: 一大堆数,要按照第一位拷贝到不同的int array里面,比如:
: [37, 57, 653, 12, 52, 501, 91, ...]
: ->
: Bucket 1: [12]
: Bucket 3: [37]
: Bucket 5: [57, 52, 501]
: Bucket 6: [653]
: Bucket 9: [91]
: 考虑用多线程来提高效率
: 想了两个办法:
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
lc19890306
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: lc19890306 (), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 03:14:45 2015, 美东)

thread safe? sure?
【 在 henrycode (双蓝) 的大作中提到: 】
: vector 的push_back 不是thread safe么原子操作吗?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 71.]

 
henrycode
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: henrycode (双蓝), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 13:39:43 2015, 美东)

python append 是原子操作。 那 c++ stl push_back 可能不是吧。
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
kjbl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: kjbl (看家本领), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 15:06:48 2015, 美东)

如果方法1的话,可以用 compare and swap 实现 vector 添加的原子操作。


【 在 khing (^_^) 的大作中提到: 】
: 一大堆数,要按照第一位拷贝到不同的int array里面,比如:
: [37, 57, 653, 12, 52, 501, 91, ...]
: ->
: Bucket 1: [12]
: Bucket 3: [37]
: Bucket 5: [57, 52, 501]
: Bucket 6: [653]
: Bucket 9: [91]
: 考虑用多线程来提高效率
: 想了两个办法:
: ...................

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
kjbl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: kjbl (看家本领), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 15:07:27 2015, 美东)

python 有多线程么,我好久不用了


【 在 henrycode (双蓝) 的大作中提到: 】
: python append 是原子操作。 那 c++ stl push_back 可能不是吧。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
ayiyahiho
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: ayiyahiho (简单生长), 信区: JobHunting
标  题: Re: 一个多线程的简单问题
发信站: BBS 未名空间站 (Mon Oct 19 15:47:18 2015, 美东)

为啥要lock,读操作不需要锁,而且每个数只能归类到一个bucket,怎么都用不上锁呀。
如果数组很长,应该可以把它分成很多块,9个线程work一个块,那样就会更快了。
这样理解对吗?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 192.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996