k***g
发帖数: 166 | 1 一大堆数，要按照第一位拷贝到不同的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，看起来貌似就不需要锁了，不知道是否够快
还有更好的办法吗？ |
t**r
发帖数: 3428 | 2 数据 特别大 可以考虑mapreduce.
否则就你说的地二种方法不錯阿 |
k***g
发帖数: 166 | 3 又想到一个办法。还是把数组分成8等份，用8个线程同时做，和第一种方法的区别是它
们把数据放到自己的小桶里面。都完成之后，再把这些小桶连接起来。
这个要用C++实现，传进来的是一个vector。还没想好桶用什么数据结构
如果也用vector或者list，感觉会慢，因为要在堆上分配大量的内存才行 |
h*******e
发帖数: 1377 | 4 vector 的push_back 不是thread safe么原子操作吗？ |
a*****s
发帖数: 1121 | 5 并行计算需要考虑两个因素，数据依赖和流程依赖，你这个例子有数据依赖，没有流程
依赖。
简单来讲，避免多对多的通信，可以用数据复制来减少通信，每个thread有一份所有数
据的拷贝，第一个thread做数组1，第二个thread座数组2，以此类推，最后大家各自输
出各自的；performance瓶颈在你的最慢的thread上
如果不在乎通信，那就分数据，每个thread编号，每个进程都计算出自己的总结果，一
号负责收集最后的数组1，二号thread负责收集数组2，以此类推，bottleneck在最慢的
thread和最慢的网络，两者去最大值。这个就是mapreduce的做法。 |
a*****s
发帖数: 1121 | 6 再复杂的话，只有这两个基本解法的融合，根据你自己系统的硬件条件来决定，因为计
算量不大，不需要GPU，如果算法复杂度大的话，可以在二级并行上使用GPU。
【在 a*****s 的大作中提到】
: 并行计算需要考虑两个因素，数据依赖和流程依赖，你这个例子有数据依赖，没有流程
: 依赖。
: 简单来讲，避免多对多的通信，可以用数据复制来减少通信，每个thread有一份所有数
: 据的拷贝，第一个thread做数组1，第二个thread座数组2，以此类推，最后大家各自输
: 出各自的；performance瓶颈在你的最慢的thread上
: 如果不在乎通信，那就分数据，每个thread编号，每个进程都计算出自己的总结果，一
: 号负责收集最后的数组1，二号thread负责收集数组2，以此类推，bottleneck在最慢的
: thread和最慢的网络，两者去最大值。这个就是mapreduce的做法。
|
h*******e
发帖数: 1377 | 7 为啥要lock 数字入哪个 bucket 不会错啊， 可能出错的是入bucket 的顺序， 可是那
个重要吗， 线程本来就不能guarentee顺序啊。
【在 k***g 的大作中提到】
: 一大堆数，要按照第一位拷贝到不同的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]
: 考虑用多线程来提高效率
: 想了两个办法：
|
l********6
发帖数: 129 | 8 thread safe? sure?
【在 h*******e 的大作中提到】
: vector 的push_back 不是thread safe么原子操作吗？
|
h*******e
发帖数: 1377 | 9 python append 是原子操作。 那 c++ stl push_back 可能不是吧。 |
k**l
发帖数: 2966 | 10 如果方法1的话，可以用 compare and swap 实现 vector 添加的原子操作。
【在 k***g 的大作中提到】
: 一大堆数，要按照第一位拷贝到不同的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]
: 考虑用多线程来提高效率
: 想了两个办法：
|
k**l
发帖数: 2966 | 11 python 有多线程么，我好久不用了
【在 h*******e 的大作中提到】
: python append 是原子操作。 那 c++ stl push_back 可能不是吧。
|
a*******o
发帖数: 129 | 12 为啥要lock，读操作不需要锁，而且每个数只能归类到一个bucket，怎么都用不上锁呀。
如果数组很长，应该可以把它分成很多块，9个线程work一个块，那样就会更快了。
这样理解对吗？ |
