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

All-in-one implementation framework for binary heaps

SOFTWARE-PRACTICE & EXPERIENCE 2017年第4期47卷 523-558页

作者： Katajainen, Jyrki Univ Copenhagen Dept Comp Sci Univ Pk 5 DK-2100 Copenhagen East Denmark

Even a rough literature review reveals that there are many alternative ways of implementing a binary heap, the fundamental priority-queue structure loved by us all. Which one of these alternatives is the best in practice? The opinions of crowd-pullers and textbook authors are aligned: use an array. Of course, the correct answer is it depends'. To get from opinions to facts, a frameworka set of class templateswas written that provides a variety of customization options so it could be used to realize a large part of the proposed variants. Also, some of the derived implementations were performance benchmarked. From this work, three conclusions can be drawn: (i)It is difficult to achieve space efficiency and speed at the same time. If n denotes the current number of values in the data structure, E is a small positive real, E<1, and |V| denotes the size of the values of type V in bytes, space efficiency means (1+E)|V|n bytes of space, and speed means O(lgn) worst-case time per push and pop. (ii) If an array-based solution is sufficient, Williams' original program from 1964 is still to this day hard to beat. (iii)Sometimes a linked structure and clever programming is a viable option. If the binary-heap variant you need is not available at the software library you are using, reading this essay might save you some headaches. Copyright (c) 2016 John Wiley & Sons, Ltd.

关键词： customizable software libraries adaptable component frameworks data structures binary heaps generic programming benchmarking

来源：评论

学校读者我要写书评

暂无评论

STLlint: lifting static checking from languages to libraries

引用

SOFTWARE-PRACTICE & EXPERIENCE 2006年第3期36卷 225-254页

作者： Gregor, D Schupp, S Indiana Univ Dept Comp Sci Bloomington IN 47405 USA Chalmers Univ Technol Dept Comp Sci SE-41296 Gothenburg Sweden

Traditional static checking centers around finding bugs in programs by isolating cases where the language has been used incorrectly. These language-based checkers do not understand the semantics of software libraries, and therefore cannot be used to detect errors in the use of libraries. In this paper, we introduce STLlint, a program analysis we have implemented for the C++ Standard Template Library and similar, generic software libraries, and we present the general approach that underlies STLlint. We show that static checking of library semantics differs greatly from checking of language semantics, requiring new representations of program behavior and new algorithms. Major challenges include checking the use of generic algorithms, loop analysis for interfaces, and organizing behavioral specifications for extensibility. Copyright (c) 2005 John Wiley & Sons, Ltd.

关键词： static checking program verification interface compilation generic programming Standard Template Library

来源：评论

学校读者我要写书评

暂无评论

A generic software design for Delaunay refinement meshing

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2007年第1-2期38卷 100-110页

作者： Rineau, Laurent Yvinec, Mariette INRIA F-06902 Sophia Antipolis France

This paper describes a generic software designed to implement meshing algorithms based on the Delaunay refinement paradigm. Such a meshing algorithm is generally described through a set of rules guiding the refinement of mesh elements. The central item of the software design is a generic class, called a mesher level, that is able to handle one of the rules guiding the refinement process. Several instantiations of the mesher level class can be stacked and tied together to implement the whole refinement process. As shown in this paper, the design is flexible enough to implement all currently known mesh generation algorithms based on Delaunay refinement. In particular it can be used to generate meshes approximating smooth or piecewise smooth surfaces, as well as to mesh three dimensional domains bounded by such surfaces. It also adapts to algorithms handling small input angles and various refinement criteria. This design highly simplifies the task of implementing Delaunay refinement meshing algorithms. It has been used to implemented several meshing algorithms in the CGAL library. (c) 2007 Elsevier B.V. All rights reserved.

关键词： mesh generation Delaunay refinement generic programming

来源：评论

学校读者我要写书评

暂无评论

The density matrix renormalization group for strongly correlated electron systems: A generic implementation

引用

COMPUTER PHYSICS COMMUNICATIONS 2009年第9期180卷 1572-1578页

作者： Alvarez, G. Oak Ridge Natl Lab Div Math & Comp Sci Oak Ridge TN 37831 USA Oak Ridge Natl Lab Ctr Nanophase Mat Sci Oak Ridge TN 37831 USA

The purpose of this paper is (i) to present a generic and fully functional implementation of the density-matrix renormalization group (DMRG) algorithm, and (ii) to describe how to write additional strongly-correlated electron models and geometries by using templated classes. Besides considering general models and geometries, the code implements Hamiltonian symmetries in a generic way and parallelization over symmetry-related matrix blocks. Program summary Program title: DMRG++ Catalogue identifier: AEDJ_v1_0 Program summary URL: http://***/summaries/AEDJ_vl_*** Program obtainable from: CPC Program Library, Queen's University, Belfast, N. Ireland Licensing provisions: See file LICENSE No. of lines in distributed program, including test data, etc: 15795 No. of bytes in distributed program, including test data, etc.: 83454 Distribution format: *** programming language: C++, MPI Computer: PC, HP cluster Operating system: Any, tested on Linux Has the code been vectorized or parallelized?: Yes RAM: I GB (256 MB is enough to run included rest) Classification: 23 External routines: BLAS and LAPACK Nature of problem: Strongly correlated electrons systems, display a broad range of important phenomena, and their study is a major area of research in condensed matter physics. In this context, model Hamiltonians are used to simulate the relevant interactions of a given compound, and the relevant degrees of freedom. These studies rely on the use of tight-binding lattice models that consider electron localization, where states on one site can be labeled by spin and orbital degrees of freedom. The calculation of properties from these Hamiltonians is a computational intensive problem, since the Hilbert space over which these Hamiltonians act grows exponentially with the number of sites on the lattice. Solution method: The DMRG is a numerical variational technique to study quantum many body Hamiltonians. For one-dimensional and quasi one-dimensional systems, the DMR

关键词： Density-matrix renormalization group DMRG Strongly correlated electrons generic programming

来源：评论

学校读者我要写书评

暂无评论

A generic lazy evaluation scheme for exact geometric computations

引用

SCIENCE OF COMPUTER programming 2011年第4期76卷 307-323页

作者： Pion, Sylvain Fabri, Andreas INRIA Sophia Antipolis France GeometryFactory Grasse France

We present a generic C++ design to perform exact geometric computations efficiently using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms. Their efficiency is also important for many applications, hence the need for delaying the costly exact computations at run time until they are actually needed, if at all. Our approach is generic and extensible in the sense that it is possible to make it a library that users can apply to their own geometric objects and primitives. It involves techniques such as generic functor-adaptors, static and dynamic polymorphism, reference counting for the management of directed acyclic graphs, and exception handling for triggering exact computations when needed. It also relies on multi-precision arithmetic as well as interval arithmetic. We apply our approach to the whole geometry kernel of CGAL. (c) 2010 Elsevier B.V. All rights reserved.

关键词： Computational geometry Exact geometric computation Numerical robustness Interval arithmetic Lazy evaluation generic programming C plus CGAL

来源：评论

学校读者我要写书评

暂无评论

Design of the CGAL 3D Spherical Kernel and application to arrangements of circles on a sphere

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2009年第6-7期42卷 536-550页

作者： de Castro, Pedro M. M. Cazals, Frederic Loriot, Sebastien Teillaud, Monique INRIA F-06902 Sophia Antipolis France Univ Bourgogne IMB UFR Sci & Tech F-21078 Dijon France

This paper presents a CGAL kernel for algorithms manipulating 3D spheres, circles. and circular arcs. The paper makes three contributions. First. the mathematics underlying two non-trivial predicates are presented. Second, the design of the kernel concept is developed, and the connexion between the mathematics and this design is established. In particular, we show how two different frameworks can be combined: one for the general setting, and one dedicated to the case where all the objects handled lie on a reference sphere. Finally, an assessment about the efficacy of the 3D Spherical Kernel is made through the calculation of the exact arrangement of circles on a sphere. On average while computing arrangements with few degeneracies (on sample molecular models), it is shown that certifying the result incurs a modest factor of two with respect to calculations using a plain double arithmetic. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Robustness Curved objects generic programming Spheres Predicates Constructions Geometric kernels CGAL

来源：评论

学校读者我要写书评

暂无评论

Template metaprogramming techniques for concept-based specialization

引用

SCIENTIFIC programming 2013年第1-2期21卷 43-61页

作者： Bachelet, Bruno Mahul, Antoine Yon, Loic Univ Blaise Pascal Clermont Univ LIMOS F-63000 Clermont Ferrand France CNRS UMR 6158 LIMOS F-63171 Aubiere France Univ Blaise Pascal Clermont Univ CRRI F-63000 Clermont Ferrand France

In generic programming, software components are parameterized on types. When available, a static specialization mechanism allows selecting, for a given set of parameters, a more suitable version of a generic component than its primary version. The normal C++ template specialization mechanism is based on the type pattern of the parameters, which is not always the best way to guide the specialization process: type patterns are missing some information on types that could be relevant to define specializations. The notion of a concept, which represents a set of requirements (including syntactic and semantic aspects) for a type, is known to be an interesting approach to control template specialization. For many reasons, concepts were dropped from C++ 11 standard, this article therefore describes template metaprogramming techniques for declaring concepts, modeling relationships (meaning that a type fulfills the requirements of a concept), and refinement relationships (meaning that a concept refines the requirements of another concept). From a taxonomy of concepts and template specializations based on concepts, an automatic mechanism selects the most appropriate version of a generic component for a given instantiation. Our purely library-based solution is also open for retroactive extension: new concepts, relationships, and template specializations can be defined at any time;such additions will then be picked up by the specialization mechanism.

关键词： generic programming template specialization concept-based overloading/specialization template metaprogramming

来源：评论

学校读者我要写书评

暂无评论

Typed generic traversal with term rewriting strategies

引用

JOURNAL OF LOGIC AND ALGEBRAIC programming 2003年第1-2期54卷 1-64页

作者： Lämmel, R Free Univ Amsterdam Amsterdam Netherlands CWI NL-1009 AB Amsterdam Netherlands

A typed model of strategic term rewriting is developed. The key innovation is that generic traversal is covered. To this end, we define a typed rewriting calculus S'(gamma). The calculus employs a many-sorted type system extended by designated generic strategy types gamma. We consider two generic strategy types, namely the types of type-preserving and type-unifying strategies. S'(gamma) offers traversal combinators to construct traversals or schemes thereof from many-sorted-and generic strategies. The traversal combinators model different forms of one-step traversal, that is, they process the immediate subterms of a given term without anticipating any scheme of recursion into terms. To inhabit generic types, we need to add a fundamental combinator to lift a many-sorted strategy s to a generic type gamma. This step is called strategy extension. The semantics of the corresponding combinator states that s is only applied if the type of the term at hand fits, otherwise the extended strategy fails. This approach dictates that the semantics of strategy application must be type-dependent to a certain extent. Typed strategic term rewriting with coverage of generic term traversal is a simple but expressive model of generic programming. It has applications in program transformation and program analysis. (C) 2002 Elsevier Science Inc. All rights reserved.

关键词： term rewriting strategies generic programming traversal type systems program transformation

来源：评论

学校读者我要写书评

暂无评论

Efficient method of pixel neighborhood traversal

引用

JOURNAL OF VISUAL COMMUNICATION AND IMAGE REPRESENTATION 2012年第5期23卷 719-728页

作者： Pyatykh, Stanislav Zheng, Lei Hesser, Juergen Heidelberg Univ Univ Med Ctr Mannheim D-68167 Mannheim Germany

The processing of a pixel neighborhood is a common operation in image processing. Therefore, a flexible, computationally efficient and easy-to-use strategy for neighborhood traversal is required. In this paper, a new neighborhood traversal method and its implementation in C++ are presented. In the proposed method, the pixel neighbor access is organized without boundary checks and without image extension, which yields to significant improvements of computational efficiency. The method is based on a partition of the image domain, for which valid neighbor pixel offsets can be precomputed for each subset. The proposed C++ implementation is based on generic programming and can handle images of arbitrary dimensionality. It hides all implementation details from the user and can be extended in order to support additional boundary conditions. The evaluation demonstrates that the proposed method is considerably faster than neighborhood traversal implementations from other libraries. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Neighborhood traversal Boundary condition Image processing Image filtering Image traversal Code optimization generic programming Image processing library

来源：评论

学校读者我要写书评

暂无评论

Dynamic algorithm selection for runtime concepts

引用

SCIENCE OF COMPUTER programming 2010年第9期75卷 773-786页

作者： Pirkelbauer, Peter Parent, Sean Marcus, Mat Stroustrup, Bjarne Texas A&M Univ College Stn TX 77843 USA Adobe Syst Inc San Jose CA USA

A key benefit of generic programming is its support for producing modules with clean separation. In particular, generic algorithms are written to work with a wide variety of types without requiring modifications to them. The Runtime concept idiom extends this support by allowing unmodified concrete types to behave in a runtime polymorphic manner. In this paper, we describe one implementation of the runtime concept idiom, in the domain of the C++ standard template library (STL). We complement the runtime concept idiom with an algorithm library that considers both type and concept information to maximize performance when selecting algorithm implementations. We present two implementations, one in ISO C++ and one using an experimental language extension. We use our implementations to describe and measure the performance of runtime-polymorphic analogs of several STL algorithms. The tests demonstrate the effects of different compile-time vs. run-time algorithm selection choices. (C) 2009 Elsevier B.V. All rights reserved.

关键词： generic programming Runtime polymorphism C plus Standard template library

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：