Compact Fenwick trees for dynamic ranking and selection (2019)
The paper presents Compact Fenwick trees, enhancing array storage and operations efficiency. It introduces optimized variants for faster searches and reduced space usage, aiming to create a dynamic bit vector with logarithmic time complexity. Additionally, it proposes solutions to leverage CPU cache structures for enhanced performance.
Read original article
The paper discusses Compact Fenwick trees, a data structure that efficiently stores arrays and supports operations like modifying elements, accessing elements, computing prefix sums, and predecessor searches in logarithmic time. The authors introduce variants that improve the classical implementation by reducing size when an upper bound on array elements is known and enabling faster predecessor searches. They aim to use these variants to create an efficient dynamic bit vector that can perform updates, ranking, and selection in logarithmic time with minimal space overhead. The study also addresses the interaction between the arithmetic of Fenwick trees and CPU cache structures, proposing solutions to enhance performance. The work outperforms existing data structures with similar functionalities, offering a compact solution with improved efficiency.
Related
Own Constant Folder in C/C++
Neil Henning discusses precision issues in clang when using the sqrtps intrinsic with -ffast-math, suggesting inline assembly for instruction selection. He introduces a workaround using __builtin_constant_p for constant folding optimization, enhancing code efficiency.
B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
B-trees require fewer comparisons than balanced binary search trees due to better access locality. Larger k values in B-trees lead to tighter bounds, outperforming AVL trees for k>=8, offering practical advantages.
Optimizing the Roc parser/compiler with data-oriented design
The blog post explores optimizing a parser/compiler with data-oriented design (DoD), comparing Array of Structs and Struct of Arrays for improved performance through memory efficiency and cache utilization. Restructuring data in the Roc compiler showcases enhanced efficiency and performance gains.
Matters Computational [pdf]
The FXT page hosts a library of efficient algorithms, complemented by the fxtbook "Matters Computational." Authored by Jörg Arndt, it offers free downloads, demo programs, and comprehensive documentation on various computational topics.
Modeling B-Trees in TLA+
Lorin Hochstein explores B-trees using TLA+, modeling operations like key-value retrieval and insertion. He emphasizes historical outputs and node structures, offering insights into B-tree functionality in databases.
3 commentsI had pretty much this same task as the second hardest challenge in a 2-hour competitive programming contest, and plenty of people came up with the solution on the spot. Try an implementation yourself if you're up for it here: https://csacademy.com/contest/archive/task/light-count/
large bit vectors as in 10^6..10^10 bit bit veczors
Related
Own Constant Folder in C/C++
Neil Henning discusses precision issues in clang when using the sqrtps intrinsic with -ffast-math, suggesting inline assembly for instruction selection. He introduces a workaround using __builtin_constant_p for constant folding optimization, enhancing code efficiency.
B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees
B-trees require fewer comparisons than balanced binary search trees due to better access locality. Larger k values in B-trees lead to tighter bounds, outperforming AVL trees for k>=8, offering practical advantages.
Optimizing the Roc parser/compiler with data-oriented design
The blog post explores optimizing a parser/compiler with data-oriented design (DoD), comparing Array of Structs and Struct of Arrays for improved performance through memory efficiency and cache utilization. Restructuring data in the Roc compiler showcases enhanced efficiency and performance gains.
Matters Computational [pdf]
The FXT page hosts a library of efficient algorithms, complemented by the fxtbook "Matters Computational." Authored by Jörg Arndt, it offers free downloads, demo programs, and comprehensive documentation on various computational topics.
Modeling B-Trees in TLA+
Lorin Hochstein explores B-trees using TLA+, modeling operations like key-value retrieval and insertion. He emphasizes historical outputs and node structures, offering insights into B-tree functionality in databases.