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

17th International Symposium on Haskell (Haskell)

作者： van Brugge, Jan Heriot Watt Univ Edinburgh Midlothian Scotland

ISBN: (纸本)9798400711022

Formal reasoning about the time complexity of algorithms and data structures is usually done in interactive theorem provers like Isabelle/HOL [16]. This includes reasoning about amortized time complexity which looks at the worst case performance over a series of operations. However, most programs are not written within a theorem prover and thus use the data structures of the production language. To verify the correctness it is necessary to translate the data structures from the production language into the language of the prover. Such a translation step could introduce errors, for example due to a mismatch in features between the two languages. We show how to prove amortized complexity of data structures directly in Haskell using Liquid-Haskell [18]. Besides skipping the translation step, our approach can also provide a didactic advantage. Learners do not have to learn an additional language for proofs and can focus on the new concepts only. For this paper, we do not assume prior knowledge of amortized complexity as we explain the concepts and apply them in our first case study, a simple stack with multipop. Moving to more complicated (and useful) data structures, we show that the same technique works for binomial heaps which can be used to implement a priority queue. We also prove amortized complexity bounds for Claessen's version of the finger tree [3], a sequence-like data structure with constant-time cons/uncons on either end. Finally we discuss the current limitations of LiquidHaskell that made certain versions of the data structures not feasible.

关键词： datastructures LiquidHaskell amortized complexity finger trees theorem proving functional pearl

来源：评论

学校读者我要写书评

暂无评论

Long-lived counters with polylogarithmic amortized step complexity

引用

DISTRIBUTED COMPUTING 2023年第1期36卷 29-43页

作者： Baig, Mirza Ahad Hendler, Danny Milani, Alessia Travers, Corentin IST Austria Klosterneuburg Austria Ben Gurion Univ Negev Beer Sheva Israel Marseille Univ Marseille France

A shared-memory counter is a widely-used and well-studied concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. In Jayanti et al (SIAM J Comput, 30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read-write registers, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this work, we address this gap. We show that n-process, wait-free and linearizable counters can be implemented from read-write registers with O(log(2) n) amortized step complexity. This is the first counter algorithm from read-write registers that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is within a logarithmic factor of the optimal. The worst-case step complexity of the construction remains linear, which is optimal. This is obtained thanks to a new max register construction with O(log n) amortized step complexity in executions of arbitrary length in which the value stored in the register does not grow too quickly. We then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel [1] in which we "plug" our max register implementation to show that it remains linearizable while achieving O(log(2) n) amortized step complexity.

关键词： Shared memory Wait-freedom Counter amortized complexity Concurrent objects

来源：评论

学校读者我要写书评

暂无评论

amortized complexity Verified

引用

JOURNAL OF AUTOMATED REASONING 2019年第3期62卷 367-391页

作者： Nipkow, Tobias Brinkop, Hauke Tech Univ Munich Munich Germany

A framework for the analysis of the amortized complexity of functional data structures is formalized in the proof assistant Isabelle/HOL and applied to a number of standard examples and to the following non-trivial ones: skew heaps, splay trees, splay heaps and pairing heaps. The proofs are completely algebraic and are presented in some detail.

关键词： amortized complexity Interactive verification Functional Programming

来源：评论

学校读者我要写书评

暂无评论

amortized Circuit complexity, Formal complexity Measures, and Catalytic Algorithms 62

Amortized Circuit Complexity, Formal Complexity Measures, an...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Robere, Robert Zuiddam, Jeroen McGill Univ Sch Comp Sci Montreal PQ Canada Univ Amsterdam Korteweg De Vries Inst Math Amsterdam Netherlands

ISBN: (纸本)9781665420556

We study the amortized circuit complexity of boolean functions. Given a circuit model F and a boolean function f : {0, 1}(n) -> {0, 1}, the F-amortized circuit complexity is defined to be the size of the smallest circuit that outputs m copies of f (evaluated on the same input), divided by m, as m -> infinity. We prove a general duality theorem that characterizes the amortized circuit complexity in terms of "formal complexity measures". More precisely, we prove that the amortized circuit complexity in any circuit model composed out of gates from a finite set is equal to the pointwise maximum of the family of "formal complexity measures" associated with F. Our duality theorem captures many of the formal complexity measures that have been previously studied in the literature for proving lower bounds (such as formula complexity measures, submodular complexity measures, and branching program complexity measures), and thus gives a characterization of formal complexity measures in terms of circuit complexity. We also introduce and investigate a related notion of catalytic circuit complexity, which we show is "intermediate" between amortized circuit complexity and standard circuit complexity, and which we also characterize (now, as the best integer solution to a linear program). Finally, using our new duality theorem as a guide, we strengthen the known upper bounds for non-uniform catalytic space, introduced by Buhrman et. al [1] (this is related to, but not the same as, our notion of catalytic circuit size). Potechin [2] proved that for any boolean function f : {0, 1}(n) -> {0, 1}, there is a catalytic branching program computing m = 2(2n-1) copies of f with total size O(mn) - that is, linear size per copy - refuting a conjecture of Girard, Koucky and McKenzie [3]. Potechin then asked if the number of copies m can be reduced while retaining the amortized upper bound. We make progress on this question by showing that if f has degree d when represented as polynomial over F-2

关键词： amortized complexity Branching Programs Catalytic Computation Comparator Circuits Direct Sum Duality Formal complexity Measures Submodular

来源：评论

学校读者我要写书评

暂无评论

Finger Trees Explained Anew, and Slightly Simplified (Functional Pearl) 13

Finger Trees Explained Anew, and Slightly Simplified (Functi...

引用

13th International Symposium on Haskell (Haskell)

作者： Claessen, Koen Chalmers Univ Technol Gothenburg Sweden

We explicitly motivate the subtle intricacies of Hinze and Paterson's Finger Tree datastructure, by step-wise refining a naive implementation. The result is a new explanation of how Finger Trees work and why they ... 详细信息

ISBN: (纸本)9781450380508

关键词： datastructures finger trees amortized complexity functional pearl

来源：评论

学校读者我要写书评

暂无评论

Lock-free Concurrent Search

Lock-free Concurrent Search

引用

作者： BAPI CHATTERJEE Chalmers University of Technology

学位级别：博士

The contemporary computers typically consist of multiple computing cores with high compute power. Such computers make excellent concurrent asyn- chronous shared memory system. On the other hand, though many celebrated books on data structure and algorithm provide a comprehensive study of se- quential search data structures, unfortunately, we do not have such a luxury if concurrency comes in the setting. The present dissertation aims to address this paucity. We describe novel lock-free algorithms for concurrent data structures that target a variety of search problems. (i) Point search (membership query, predecessor query, nearest neighbour query) for 1-dimensional data: Lock-free linked-list; lock-free internal and external binary search trees (BST). (ii) Range search for 1-dimensional data: A range search method for lock- free ordered set data structures - linked-list, skip-list and BST. (iii) Point search for multi-dimensional data: Lock-free kD-tree, specially, a generic method for nearest neighbour search. We prove that the presented algorithms are linearizable i. e. the concurrent data structure operations intuitively display their sequential behaviour to an ob- server of the concurrent system. The lock-freedom in the introduced algorithms guarantee overall progress in an asynchronous shared memory system. We present the amortized analysis of lock-free data structures to show their efficiency. Moreover, we provide sample implementations of the algorithms and test them over extensive micro-benchmarks. Our experiments demonstrate that the implementations are scalable and perform well when compared to related existing alternative implementations on common multi-core computers. Our focus is on propounding the generic methodologies for efficient lock- free concurrent search. In this direction, we present the notion of help-optimality, which captures the optimization of amortized step complexity of the operations. In addition to that, we explore the language-portable

关键词： Data Structure Search Range Search Nearest Neighbour Search Concurrent Concurrency Lock-free Lock-based Blocking Non-blocking Wait-free Linearizable Linearizability Binary Search Tree Linked-list kD-tree Lock-free-kD-tree amortized complexity Help-aware Help-optimal Language-portable Synchronization

来源：评论

学校读者我要写书评

暂无评论

Communication complexity of Functions Related to Set Intersection

Communication Complexity of Functions Related to Set Interse...

引用

Information Theory and Applications Workshop

作者： Tamm, Ulrich Univ Bielefeld Bielefeld Germany

The amortized communication complexity of functions f : {0, 1, . . . , m - 1} x {0, 1, . . . , m - 1} having an allzero row and and an all-zero column in their function matrix is determined. For m = 2 this yields the ... 详细信息

ISBN: (纸本)9781509025299

关键词： communication complexity amortized complexity information complexity data compression

来源：评论

学校读者我要写书评

暂无评论

Deletion Without Rebalancing in Binary Search Trees

引用

ACM TRANSACTIONS ON ALGORITHMS 2016年第4期12卷 57-57页

作者： Sen, Siddhartha Tarjan, Robert E. Kim, David Hong Kyun Microsoft Res New York NY 10011 USA Princeton Univ Dept Comp Sci 35 Olden St Princeton NJ 08540 USA Intertrust Technol 920 Stewart Dr Sunnyvale CA 94085 USA Univ Chicago Dept Comp Sci 1100 East 58th St Chicago IL 60637 USA

We address the vexing issue of deletions in balanced trees. Rebalancing after a deletion is generally more complicated than rebalancing after an insertion. Textbooks neglect deletion rebalancing, and many B-tree-based database systems do not do it. We describe a relaxation of AVL trees in which rebalancing is done after insertions but not after deletions, yet worst-case access time remains logarithmic in the number of insertions. For any application of balanced trees in which the number of updates is polynomial in the tree size, our structure offers performance competitive with that of classical balanced trees. With the addition of periodic rebuilding, the performance of our structure is theoretically superior to that of many, if not all, classic balanced tree structures. Our structure needs lg lgm + 1 bits of balance information per node, where m is the number of insertions and lg is the base-two logarithm, or lg lgn + O(1) with periodic rebuilding, where n is the number of nodes. An insertion takes up to two rotations and O(1) amortized time, not counting the time to find the insertion position. This is the same as in standard AVL trees. Using an analysis that relies on an exponential potential function, we show that rebalancing steps occur with a frequency that is exponentially small in the height of the affected node. Our techniques apply to other types of balanced trees, notably B-trees, as we show in a companion article, and particularly red-black trees, which can be viewed as a special case of B-trees.

关键词： Balanced trees database access methods exponential potential function amortized complexity data structure algorithm

来源：评论

学校读者我要写书评

暂无评论

Automatic amortized Analysis 15

Automatic Amortized Analysis

引用

17th International Symposium on Principles and Practice of Declarative Programming (PPDP)

作者： Hofmann, Martin

We summarise the state of the art in automatic amortized resource analysis. We then focus on some recent applications to term rewriting with G. Moser and conclude with open problems and questions.

ISBN: (纸本)9781450335164

We summarise the state of the art in automatic amortized resource analysis. We then focus on some recent applications to term rewriting with G. Moser and conclude with open problems and questions.

关键词： Resource analysis runtime analysis amortized complexity type systems functional programming

来源：评论

学校读者我要写书评

暂无评论

Rank-Balanced Trees

引用

ACM TRANSACTIONS ON ALGORITHMS 2015年第4期11卷 30-30页

作者： Haeupler, Bernhard Sen, Siddhartha Tarjan, Robert E. Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA Microsoft Res New York City New York NY 10011 USA Princeton Univ Dept Comp Sci Princeton NJ 08540 USA Intertrust Technol Sunnyvale CA 94085 USA

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the design space of balanced trees has not been fully explored. We continue the exploration. Our contributions are three: We systematically study the use of ranks and rank differences to define height-based balance in binary trees. Different invariants on rank differences yield AVL trees, red-black trees, and other kinds of balanced trees. By relaxing AVL trees, we obtain a new kind of balanced binary tree, the weak AVL tree (wavl tree), whose properties we develop. Bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and at most two rotations, improving the three or more rotations per deletion needed in all other kinds of balanced trees of which we are aware. The height bound of a wavl tree degrades gracefully from that of an AVL tree as the number of deletions increases and is never worse than that of a red-black tree. Wavl trees also support top-down, fixed look-ahead rebalancing in O(1) amortized time. Finally, we use exponential potential functions to prove that in wavl trees rebalancing steps occur exponentially infrequently in rank. Thus, most of the rebalancing is at the bottom of the tree, which is crucial in concurrent applications and in those in which rotations take time that depends on the subtree size.

关键词： Algorithms Theory Balanced binary trees exponential potential function amortized complexity AVL trees red-black trees search trees data structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：