Source code for benchmark on unordered dictionary data structures. See this page for the result.
My C++ template library. Note that I have shifted my focus on C macro library and the template library is not actively maintained. You can easily find good implementations in SGI STL. However, from the benchmarks you can see that my library still has some advantages. If you like to use the template library and find bugs or require more features, please feel free to contact with me.
Sort template library: sort.hh (HTML) and sort_test.cc (HTML). This library includes high-performance iterative introsort (i.e. improved quicksort), iterative bottom-up mergesort and binary heapsort. See also this post.
GNU sort for string-number mixed comparison: sort-1.22a.tar.bz2. This version also includes some performance enhancement. See also this post.
Numerical algorithms
Normal and Gamma random generator: genran.h and genran.c (HTML). Adapted from GSL.
Hooke-Jeeves’ method for derivative-free nonlinear programming: min.hh (HTML). This is a C++ template function. See also this post.
NEWUOA method for derivative-free nonlinear programming: newuoa.hh (HTML). C++ template function. Adapted from Powell’s Fortran program. A benchmark on this method is available here. See also this post.
hermano perdona que te escriba en español, mi ingles es suficiente para leer, tengo una implemetacion de avl, que modifique para trabajar con el como si fuera una lista, ademas que permitiera elementos repetidos, “me encanto” tu comparacion del b-tree con los los binarios, voy a usar tu implementacion del b-tree en mi trabajo(por supuesto, le voy a dar difusion a tu sitio, y incluir en la bibliografia), ahora la pregunta es, cual es la mejor implementacion que conoces de AVL?, tienes alguna tuya…?, estoy desarrollando un libreria evolutiva paralela, y la poblacion pienso almacenarla en arboles, por la rapides de insercion y busqueda, como te dije modifique un AVL, pero como explicas puede existir situaciones en las que sea mejor usar un AVL y otras donde sea mejor usar un b-tree, mira disculpa la charla pero, este tema me es realmente interesante, estuve buscando implemetaciones de las demas versiones de b-tree, b+tree, b*tree, dancing b*tree, pero de estas me encontre pocas tan elegante y sobre todo rapidas que el kbtree, mis felicitaciones y agradecimiento, espero con expectativas tu respuesta. Saludos Leander.
I do not speak Spanish, but I can use google translate. Hope the translation honestly reflects what you mean to say.
There are few good AVL implementations, but there are a lot of good Red-black tree libraries. In my benchmark (“Another look at my old benchmark”), AVL and RB tree have quite similar performance in terms of both speed and memory. And therefore, if you like to use binary search tree (BST), you might want to use RB tree instead. For C++ programmers, STL’s implemention is nearly the best. For C programmers, I recommend tree.h from FreeBSD. See my post (“Comparison of binary search trees (BSTs)”) for more details.
Although in my benchmark, B-tree marginally outperforms RB tree, in other applications, RB/AVL tree may be faster. More advanced implementation of RB may also use less memory than my B-tree. But this all depends on the type of data in the BST/B-tree.
I have not tested other B-tree (B*/B+) implementations. But if you want to use an on-disk B-tree for large data set, I would highly recommend SQLite. It is faster than another B-tree library and is much more flexible.
hermano perdona que te escriba en español, mi ingles es suficiente para leer, tengo una implemetacion de avl, que modifique para trabajar con el como si fuera una lista, ademas que permitiera elementos repetidos, “me encanto” tu comparacion del b-tree con los los binarios, voy a usar tu implementacion del b-tree en mi trabajo(por supuesto, le voy a dar difusion a tu sitio, y incluir en la bibliografia), ahora la pregunta es, cual es la mejor implementacion que conoces de AVL?, tienes alguna tuya…?, estoy desarrollando un libreria evolutiva paralela, y la poblacion pienso almacenarla en arboles, por la rapides de insercion y busqueda, como te dije modifique un AVL, pero como explicas puede existir situaciones en las que sea mejor usar un AVL y otras donde sea mejor usar un b-tree, mira disculpa la charla pero, este tema me es realmente interesante, estuve buscando implemetaciones de las demas versiones de b-tree, b+tree, b*tree, dancing b*tree, pero de estas me encontre pocas tan elegante y sobre todo rapidas que el kbtree, mis felicitaciones y agradecimiento, espero con expectativas tu respuesta. Saludos Leander.
@leander
I do not speak Spanish, but I can use google translate. Hope the translation honestly reflects what you mean to say.
There are few good AVL implementations, but there are a lot of good Red-black tree libraries. In my benchmark (“Another look at my old benchmark”), AVL and RB tree have quite similar performance in terms of both speed and memory. And therefore, if you like to use binary search tree (BST), you might want to use RB tree instead. For C++ programmers, STL’s implemention is nearly the best. For C programmers, I recommend tree.h from FreeBSD. See my post (“Comparison of binary search trees (BSTs)”) for more details.
Although in my benchmark, B-tree marginally outperforms RB tree, in other applications, RB/AVL tree may be faster. More advanced implementation of RB may also use less memory than my B-tree. But this all depends on the type of data in the BST/B-tree.
I have not tested other B-tree (B*/B+) implementations. But if you want to use an on-disk B-tree for large data set, I would highly recommend SQLite. It is faster than another B-tree library and is much more flexible.
thank so much.
why don’t a document to know how use yours libraries? Is hard read and understand all code for use it
Hey, really nice posts!
If only every numerical algorithm paper included a C or C++ 1-header implementation. It would be a better world.