申请试用
HOT
登录
注册
 
重新审视现代处理器的合并和排序

重新审视现代处理器的合并和排序

Andy
/
发布于
/
2938
人观看
The vast quantities of log-based data appearing in data centers has generated an interest in sorting almost-sorted datasets. We revisit the problem of sorting and merging data in main memory, and show that a long-forgotten technique called Patience Sort can, with some key modifications, be made competitive with today’s best comparison-based sorting techniques for both random and almost sorted data. Patience sort consists of two phases: the creation of sorted runs, and the merging of these runs. Through a combination of algorithmic and architectural innovations, we dramatically improve Patience sort for both random and almost-ordered data. Of particular interest is a new technique called ping-pong merge for merging sorted runs in main memory.
12 点赞
3 收藏
7下载
相关文档
确认
3秒后跳转登录页面
去登陆