我正在寻找C#中的并行化(多线程)排序算法的简单实现,它可以在List<T>Arrays上运行,也可能使用Parallel Extensions,但这部分并不是绝对必要的.
编辑:Frank Krueger提供了一个很好的答案,但我希望将该示例转换为不使用LINQ的示例.还要注意,Parallel.Do()似乎已被取代了Parallel.Invoke().
谢谢.
我有一行代码,占用了我应用程序运行时的25% - 30%.它是std :: set的小于比较器(该集合用红黑树实现).它在28秒内被称为大约1.8亿次.
struct Entry {
const float _cost;
const long _id;
// some other vars
Entry(float cost, float id) : _cost(cost), _id(id) {
}
};
template<class T>
struct lt_entry: public binary_function <T, T, bool>
{
bool operator()(const T &l, const T &r) const
{
// Most readable shape
if(l._cost != r._cost) {
return r._cost < l._cost;
} else {
return l._id < r._id;
}
}
};
条目应按成本排序,如果成本与其ID相同.每次提取最小值时都会有很多插入.我想过使用Fibonacci-Heaps,但我被告知它们理论上很好,但是它们受到高常数的影响并且实现起来非常复杂.并且由于insert在O(log(n))中,运行时增加几乎是恒定的,大n.所以我认为可以坚持下去.
为了提高性能,我尝试用不同的形状表达它:
return l._cost < r._cost || r._cost > l._cost || …我现在正在查看我的旧学校作业,并希望找到问题的解决方案.
哪种排序方法最适合并行处理？
我想快速排序(或合并排序？)就是答案.
我对么？
当数据不适合内存时,网上有很多关于在Unix上对大文件进行排序的讨论.通常使用mergesort和variants.
Hoewever,如果假设有足够的内存来容纳整个数据,那么最有效/最快的排序方式是什么？csv文件大约为50 GB(> 10亿行),并且有足够的内存(数据大小的5倍)来保存整个数据.
我可以使用Unix排序,但仍然需要> 1小时.我可以使用任何必要的语言,但我主要寻找的是速度.我知道我们可以将数据加载到一个柱状类型的db表和排序中,但这是一次性的努力,所以寻找更灵活的东西......
提前致谢.
tl; dr:对uint8x16_t进行排序的最快方法是什么？
我需要对许多正好16个无符号字节的数组进行排序(按降序排列,当然这无关紧要),我正在尝试通过ARM NEON向量化优化排序.
而且我发现这是一个非常奇特的谜题,因为似乎"必须"存在一个NEON指令的短组合(例如vmax/vpmax/vmin/vpmin,vzip/vuzp),它们可靠地产生一个排序的数组.
例如,如果我们将两个8字节数组的对(A,B)转换为(vpmax(A,B),vpmin(A,B)),我们就会以不同的顺序获得相同的16个值.如果我们重复这个操作四次,我们可靠地确定第一个单元格中的数组最大值,并且最后一个单元格中的数组最小; 但我们无法确定中间元素.
另一个例子:如果我们先做(C,D)=(vmax(A,B),vmin(A,B)),那么我们做(E,F)=(vpmax(C,D),vpmin(C, D)),然后我们做(G,H)= vzip(E,F),然后我们将我们的数组分成四个字节的四个部分,在每个部分我们已经知道最大的元素和最小的元素.可能下一个天真的步骤是将这个数组解交织到阵列开头的前四个字节(这不一定是数组的前四个元素,只是它们各自组的顶部字节)并重复,但还不确定最后它在哪里领先.
是否存在针对此特定问题或其他类似问题的已知方法(针对不同的阵列大小或其他类型)？任何想法都赞赏:)
我需要对存储在结构数组中的数据块进行排序.结构没有指针.每个块都有一个计数器编号和一个数组中等于结构块的数组的位置坐标.例如,如果我们有一个数据数组,我们可以划分为4个NxN块,我们在结构块的索引数组中有4个结构块,每个结构块在数据数组中有自己的数字和位置,借助我们可以计算使用索引块的数据数组中块的指针.应该使用比较器来进行排序,该比较器以这样的方式比较两个块,使得两个块中的至少两个具有最少的第i个数据.例如比较器:
for( i = 0; i < N * N; ++i )
{
if( a[i] < b[i] ) return -1;
if( a[i] > b[i] ) return 1;
}
where a和b是指向数据数组的指针,由于索引数组和数据数组开始的指针,我们可以得到它们.排序不应该排序数据数组而是排序索引数组.所以问题是:我可以使用哪种并行算法(除了框架,库,我需要完全算法或标准语言工具包,如pthread或qt libs,或c/c ++标准库)以避免同步错误？代码或伪代码也会有所帮助.