Stefan wrote:
Hello, I am Stefan and this is my first year at GSoC as it's the first time I'm eligible to participate as a student. Since I have been using C++ and the Boost libraries for quite some time, I would be thrilled to be able to code for Boost. I have quite a few ideas, and I was wondering which ones you consider to benefit the most, therefore I'm awaiting for your feedback. Also, please let me know if any of these ideas are already implemented in any of the libraries. Here we go:
* Selection algorithm (find the kth smallest element in a container, O(n) worst-case, very easy to implement)
* Optimize Boost String Algorithm finders to use an efficient substring matching algorithm as opposed to the naive algorithm. Most likely because of the fact that boost has implemented the finders for strings as generic algorithms, they haven't used efficient algorithms such as KMP, Boyer-Moore, Rabin-Karp etc. \see boost/algorithm/string/detail/finder.hpp The idea is to implement efficient algorithms such as the ones mentioned above to replace the current naive implementation. Note: it may be difficult to find nth matching substring position using some of these algorithms. Difficulty: easy-medium
* Implement a string algorithm for generating the suffix array. The suffix array, after being precomputed on a certain string, allows for very efficient substring searches in the future. This is useful when the string doesn't change too often but there are plenty of substring to search against.
* Yet another efficient associative data structure, skip lists?
* Space partitioning data structures? kd-trees? quadtrees? octtrees? collision detectors? closest neighbors?
* A parser capable of evaluating mathematical expressions which contains operands,operators,function calls,variable names and constant names (also considering priority of operators): 1. a list of valid operators described by: a) number of operands (unary/binary/ternary?); b) allowed operand types; c) the precedence (priority of the operator) 2. a list of existent functions described by: a) function name; b) number of parameters; c) type of each parameter and return type; d) a callback (maybe just automatically deduce type based on the callback's type if possible) 3. a list of constants 4. a list of allowed variable names and types
Here's a pseudo-C++ code sample on how it should look like: namespace m = boost::math_expressions_parser; m::parser p; p.add_operators() ('+', 1, ret<int32_t>(_1+_2)) // binary +, precedence 1 ('*', 2, ret<int32_t>(_1*_2)) // binary -, precedence 2 ('+', 3, ret<int32_t>(_1)) // unary +, precedence 3 ('-', 3, ret<int32_t>(-_1)); // unary - (also a funny face), precedence 3 p.add_functions() ("sin", ret<int32_t>(sin(_1))); p.add_constants() ("PI", 3); p.add_allowed_variables() (allowed_var<int32_t>("x"));
m::expression E("1 + 3*sin(PI*x)", p); // evaluates mathematical expression E against parser p if (!E.valid()) { /* ... */ } else { std::cout << E.evaluate( ("x", 3) ); // evaluate this expression by letting x=3 E.let() ("x",4); std::cout << E.evaluate(); } //Maybe an optimization so only the parts that depend on the changed variable will be recalculated every time?. E.g.: for expression f(x)+y, f(x) is recomputed only when x is changed. This may cause problems for functions that do not always yield the same results for the same input. Maybe make this optimization optional, only if the user marks the function/operator as "volatile" or something Difficulty: hard-very hard
* Someone suggested on this ml earlier that a crypto suite would be useful for boost. Maybe, but it would take a lot of time and dedication to implement. I believe that we should at least add some Cryptographic hash functions (such as md5, sha1, sha256 etc.). No one wants to install Crypto++ or something similar just to be able to compute the SHA1 sum of a file. It is a common necessity to want to compute a hash function of a string. Difficulty: very easy if you copy the implementation and just create a boost-ish interface
* In-place radix sort? Radix sort is a very efficient algorithm which performs better than std::sort (my implementation) (also asymptotically better) for some particular types such as: uint8_t, uint16_t, uint32_t, unsigned char, unsigned char[2], unsigned char[4] etc. Radix sorting takes linear time, but unfortunately, linear memory. It is very useful for sorting very large amounts of numbers tho (or genetic codes and maybe some other stuff).
I am able to implement some of these stuff and I'm waiting for your opinion in what would be most useful to be part of boost. Let me know if you believe that none will have any use.
Yours sincerely, Stefan
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Here are my ideas before submitting a proposal: * Selection algorithm (quick implementation, useful for efficiently finding kth smallest number in a container offering random access iterators) * In the String algorithms library, add optimal algorithms for searching a substring in a string: Rabin-Karp, Knuth-Morris-Pratt, Boyer-Moore, possibly Boyer-Moore-Horspool and suffix arrays. As has been previously discussed in the mailing lists, these algorithms can offer significant improvements to the current substring searching implementation in boost::string::find_*(). Some of these algorithms perform better when the string changes less often, others perform better when substring changes less often and their efficiency is quite dependent on the input data. I believe it would be a good idea to perform benchmarks on these algorithms using various types of input data: random strings and substrings, strings and substrings taken from the English language, substrings that occur often in the strings, substrings that occur only partly in the strings, very long substrings, very short substrings, searches with very small alphabets (such as DNA) etc. It is also my belief that it would be a good idea to add such benchmarks to the documentation pages so that the users of these algorithms will know which one will be the most suitable, having additional information about the input. * Extend the bindings to Python of Boost.Graph or write the topology generators (whichever you consider more important or of a higher priority). Personally, I would prefer doing the bindings to python, because Python is one of my favorite programming languages and I've never done something similar before. This would be beneficial for me, as I'm sure I can do it and I will also have the chance of learning something new (i.e. improve my python and my boost.graph skills) Can you please review my list of ideas and let me know what you think? Regards, Stefan