Theory and Practice of Chunked Sequences

Umut A. Acar 1, 2 Arthur Charguéraud 3, 4 Mike Rainey 1
4 TOCCATA - Certified Programs, Certified Tools, Certified Floating-Point Computations
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Sequence data structures, i.e., data structures that provide operations on an ordered set of items, are heavily used by many applications. For sequence data structures to be efficient in practice, it is important to amortize expensive data-structural operations by chunking a relatively small, constant number of items together, and representing them by using a simple but fast (at least in the small scale) sequence data structure, such as an array or a ring buffer. In this paper, we present chunking techniques, one direct and one based on bootstrapping, that can reduce the practical overheads of sophisticated sequence data structures, such as finger trees, making them competitive in practice with special-purpose data structures. We prove amortized bounds showing that our chunking techniques reduce runtime by amortizing expensive operations over a user-defined chunk-capacity parameter. We implement our techniques and show that they perform well in practice by conducting an empirical evaluation. Our evaluation features comparisons with other carefully engineered and optimized implementations.
Type de document :
Communication dans un congrès
Schulz, AndreasS. and Wagner, Dorothea. European Symposium on Algorithms, Sep 2014, Wrocław, Poland. Springer Berlin Heidelberg, Algorithms - ESA 2014, pp.25 - 36, 2014, Lecture Notes in Computer Science. <10.1007/978-3-662-44777-2_3>
Liste complète des métadonnées

https://hal.inria.fr/hal-01087245
Contributeur : Arthur Charguéraud <>
Soumis le : mardi 25 novembre 2014 - 16:08:18
Dernière modification le : jeudi 9 février 2017 - 15:52:58
Document(s) archivé(s) le : jeudi 26 février 2015 - 12:06:01

Fichier

chunkedseq.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Umut A. Acar, Arthur Charguéraud, Mike Rainey. Theory and Practice of Chunked Sequences. Schulz, AndreasS. and Wagner, Dorothea. European Symposium on Algorithms, Sep 2014, Wrocław, Poland. Springer Berlin Heidelberg, Algorithms - ESA 2014, pp.25 - 36, 2014, Lecture Notes in Computer Science. <10.1007/978-3-662-44777-2_3>. <hal-01087245>

Partager

Métriques

Consultations de
la notice

295

Téléchargements du document

136