• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Experimental algorithms >Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure
【24h】

Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure

机译：不相交集数据结构的联合查找算法实验

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The disjoint-set data structure is used to maintain a collection of non-overlapping sets of elements from a finite universe. Algorithms that operate on this data structure are often referred to as Union-Find algorithms. They are used in numerous practical applications and are also available in several software libraries. This paper presents an extensive experimental study comparing the time required to execute 55 variations of Union-Find algorithms. The study includes all the classical algorithms, several recently suggested enhancements, and also different combinations and optimizations of these. Our results clearly show that a somewhat forgotten simple algorithm developed by Rem in 1976 is the fastest, in spite of the fact that its worst-case time complexity is inferior to that of the commonly accepted "best" algorithms.
机译：不相交集数据结构用于维护有限宇宙中元素的不重叠集合的集合。在此数据结构上运行的算法通常称为联合查找算法。它们被用于许多实际应用中，并且还可以在多个软件库中获得。本文提供了一项广泛的实验研究，比较了执行55种Union-Find算法所需的时间。该研究包括所有经典算法，最近建议的一些增强功能，以及这些算法的不同组合和优化。我们的结果清楚地表明，尽管Rem在最坏情况下的时间复杂度低于公认的“最佳”算法，但它在1976年开发的某种被遗忘的简单算法是最快的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号