ADPfusion alternatives and similar packages
Based on the "Algorithms" category.
Alternatively, view ADPfusion alternatives based on common mentions on social networks and blogs.
-
lca
Improves the known complexity of online lowest common ancestor search to O(log h) persistently, and without preprocessing -
-
-
-
-
edit-distance-linear
Levenshtein edit distance in linear memory (also turns out to be faster than C++)
CodeRabbit: AI Code Reviews for Developers
* Code Quality Rankings and insights are calculated and provided by Lumnify.
They vary from L1 to L5 with "L5" being the highest.
Do you think we are missing an alternative of ADPfusion or a related project?
README
ADPfusion
generalized Algebraic Dynamic Programming Homepage
Ideas implemented here are described in a couple of papers:
- Christian Hoener zu Siederdissen
Sneaking Around ConcatMap: Efficient Combinators for Dynamic Programming
2012, Proceedings of the 17th ACM SIGPLAN international conference on Functional programming
paper preprint - Andrew Farmer, Christian Höner zu Siederdissen, and Andy Gill.
The HERMIT in the stream: fusing stream fusion’s concatMap
2014, Proceedings of the ACM SIGPLAN 2014 workshop on Partial evaluation and program manipulation.
paper - Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.
Product Grammars for Alignment and Folding
2014, IEEE/ACM Transactions on Computational Biology and Bioinformatics. 99
paper - Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler
Algebraic Dynamic Programming over General Data Structures
2015, BMC Bioinformatics
preprint - Maik Riechert, Christian Höner zu Siederdissen, and Peter F. Stadler
Algebraic dynamic programming for multiple context-free languages
2016, Theoretical Computer Science
preprint
Introduction
ADPfusion combines stream-fusion (using the stream interface provided by the vector library) and type-level programming to provide highly efficient dynamic programming combinators.
From the programmers' viewpoint, ADPfusion behaves very much like the original ADP implementation http://bibiserv.techfak.uni-bielefeld.de/adp/ developed by Robert Giegerich and colleagues, though both combinator semantics and backtracking are different.
The library internals, however, are designed not only to speed up ADP by a large margin (which this library does), but also to provide further runtime improvements by allowing the programmer to switch over to other kinds of data structures with better time and space behaviour. Most importantly, dynamic programming tables can be strict, removing indirections present in lazy, boxed tables.
As an example, even rather complex ADP code tends to be completely optimized to loops that use only unboxed variables (Int# and others, indexIntArray# and others).
Completely novel (compared to ADP), is the idea of allowing efficient monadic combinators. This facilitates writing code that performs backtracking, or samples structures stochastically, among others things.
Installation
Follow the gADP examples.
Implementors Notes (if you want to extend ADPfusion)
These have been moved to HACKING.md.
Contact
Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany
[email protected]
http://www.bioinf.uni-leipzig.de/~choener/