检索结果-内蒙古大学图书馆

ram-Efficient External Memory Sorting

ALGORITHMICA 2015年第4期73卷 623-636页

作者： Arge, Lars Thorup, Mikkel Aarhus Univ Dept Comp Sci Ctr Mass Data Algorithm MADALGO DK-8000 Aarhus Denmark Univ Copenhagen Dept Comp Sci Copenhagen Denmark

In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we initiate a study of algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the ram model of computation. For sorting the conventional wisdom is to use merging base algorithms in external memory but we describe how this leads to suboptimal ram performance. However, by using a splitting based algorithm in combination with existing ram sorting techniques we obtain a sorting algorithm that is both I/O and ram model efficient. Furthermore, we design an I/O- and ram-efficient priority queue. Finally, we prove a sorting lower bound that shows that in most cases our results are optimal both in terms of I/O and internal computation.

关键词： I/O algorithms ram algorithms External memory algorithms Sorting Priority queue

来源：评论

学校读者我要写书评

暂无评论

ram-Efficient External Memory Sorting

RAM-Efficient External Memory Sorting

引用

24th International Symposium on algorithms and Computation

作者： Arge, Lars Thorup, Mikkel Aarhus Univ Dept Comp Sci Ctr Mass Data Algorithm MADALGO DK-8000 Aarhus Denmark Univ Copenhagen Dept Comp Sci Copenhagen Denmark

ISBN: (纸本)9783642450297

关键词： I/O algorithms ram algorithms External memory algorithms Sorting Priority queue

来源：评论

学校读者我要写书评

暂无评论

Undirected single-source shortest paths with positive integer weights in linear time

引用

JOURNAL OF THE ACM 1999年第3期46卷 362-394页

作者： Thorup, M AT&T Bell Labs Florham Park NJ 07932 USA

The single-source shortest paths problem (SSSP) is one of the classic problems in algorithmic graph theory: given a positively weighted graph G with a source vertexs, find the shortest path from s to all other vertices in the graph. Since 1959, all theoretical developments in SSSP for general directed and undirected graphs have been based on Dijkstra's algorithm, visiting the vertices in order of increasing distance from s, Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from s, However, we do not know how to sort in linear time, Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights, The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.

关键词： ram algorithms shortest paths

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：