Nat*_*oos 1 sorting algorithm parallel-processing multicore data-structures
我遇到一个问题,我有一个大量的信息列表(287,843项)必须排序显示.哪个更有效,使用自组织的红黑二叉树来保持它们排序或构建一个数组然后排序？我的钥匙是字符串,如果这有帮助的话.该算法应该使用多个处理器核心.
谢谢!
这实际上取决于您的设置细节.如果你有一台多核机器,你可以使用并行版本的quicksort非常快速地对字符串进行排序,其中每个递归调用与其他调用并行执行.对于许多内核,这可以采用已经很快的快速排序并使其速度更快.其他排序算法(如合并排序)也可以并行化,但并行快速排序具有需要更少额外内存的优势.既然您知道要对字符串进行排序,那么您可能还需要查看并行基数排序,这可能非常快.
大多数二叉搜索树不容易被多线程化,因为重新平衡操作通常需要一次更改树的多个部分,因此平衡的红/黑树可能不是这里的最佳方法.但是,您可能希望查看并发跳转列表,这是一种可以并行有效工作的数据结构.有一些较新的二元搜索树设计用于并行性,有时甚至超过了跳过列表(这里是一个这样的数据结构),尽管我预计现有的实现和讨论将会更少.
如果元素没有经常更改,或者您只需要排序一次,那么只需使用并行快速排序进行一次排序可能是最好的选择.如果元素频繁变化,那么像并行跳转列表这样的并发数据结构可能是更好的选择.
希望这可以帮助!