s**********l
发帖数: 8966 | 1 For a 256 byte size class, each class will have a double value's member.
Please write a pseudo-code to sort out 1,000,000 size of this class array quickly.
Assume you have 8 CPU can do this thing. Please use all resources. Please mark
what is your big concern for this case?
我的思路是利用快速排序，首先任选一个CPU。先随机选择一个class(ｎ) ，一次快速
排序后所有小于n的数字都在前面，所有大于n的数字都在后面。这样一百个class array
被分成(A1,n1,A2)
然后第二次利用两个CPU对A1,A2进行两次快速排序，假设选出两个值n2，n3，快速排序
, 这样原始数组被分成，（A11,n2,A12,n1,A21,n3,A22).
然后第三次利用四个CPU对A11,A12,A21,A22快速排 | w***g
发帖数: 5958 | 2 256 byte有用。如果你把所有的浮点数取出来放到一个8M的数组中排序，cache命中率
会有显著提高。事实上为了提高cache命中率和平衡的任务分配，我觉得最好的做法是
把所有数据平均分成8*N块进行归并排序(每一块用一个CPU做快速排序),N根据cache大
小决定。
quickly.
Please mark
array
【在 s**********l 的大作中提到】
: For a 256 byte size class, each class will have a double value's member.
: Please write a pseudo-code to sort out 1,000,000 size of this class array quickly.
: Assume you have 8 CPU can do this thing. Please use all resources. Please mark
: what is your big concern for this case?
: 我的思路是利用快速排序，首先任选一个CPU。先随机选择一个class(ｎ) ，一次快速
: 排序后所有小于n的数字都在前面，所有大于n的数字都在后面。这样一百个class array
: 被分成(A1,n1,A2)
: 然后第二次利用两个CPU对A1,A2进行两次快速排序，假设选出两个值n2，n3，快速排序
: , 这样原始数组被分成，（A11,n2,A12,n1,A21,n3,A22).
: 然后第三次利用四个CPU对A11,A12,A21,A22快速排
| s**********l
发帖数: 8966 | 3 感谢回答，你的意思是把所有数据平均分到8个CPU分别做快速排序，然后用归并排序得
出总体的结果是吧。
那256 byte还是没用啊，你那个8M怎么出来的呢？Cache命中率提高体现在哪里？
【在 w***g 的大作中提到】
: 256 byte有用。如果你把所有的浮点数取出来放到一个8M的数组中排序，cache命中率
: 会有显著提高。事实上为了提高cache命中率和平衡的任务分配，我觉得最好的做法是
: 把所有数据平均分成8*N块进行归并排序(每一块用一个CPU做快速排序),N根据cache大
: 小决定。
:
: quickly.
: Please mark
: array
| w***g
发帖数: 5958 | 4 把每个struct里面那个8byte的浮点数单独拷贝出来进行排序。8M确实是不对的。每个
浮点数得外带一个指向原来结构的ID，得用上4byte。拍完后再根据排序结果对运来的
256M进行排序。
【在 s**********l 的大作中提到】
: 感谢回答，你的意思是把所有数据平均分到8个CPU分别做快速排序，然后用归并排序得
: 出总体的结果是吧。
: 那256 byte还是没用啊，你那个8M怎么出来的呢？Cache命中率提高体现在哪里？
| s**********l
发帖数: 8966 | 5 那concern是什么呢？cache大小？这个没给应该不会是条件吧。排完了根据结果对原来
的排序用到256 byte了么？
【在 w***g 的大作中提到】
: 把每个struct里面那个8byte的浮点数单独拷贝出来进行排序。8M确实是不对的。每个
: 浮点数得外带一个指向原来结构的ID，得用上4byte。拍完后再根据排序结果对运来的
: 256M进行排序。
|
|
