14
edits
User:Dspies: Difference between revisions
Jump to navigation
Jump to search
→E: Coding experience
| (6 intermediate revisions by the same user not shown) | |||
| Line 30: | Line 30: | ||
'''C++'''<br /> | '''C++'''<br /> | ||
I've programmed somewhat on and off in C++, but I've never worked on a project with a group or intended for public consumption. A couple years ago I wrote a Quadratic Number Field Sieve using gmp and that was the first significant piece of code I wrote in C++. A couple months ago I wrote a preprocessor for grounded Answer Set Programs that does something analogous to forward-checking to infer binary constraints. During this project I read "Effective C++" and some of "C++ Templates: The Complete Guide". I did extensive online browsing to understand C++-11 rvalue references and perfect forwarding (although I realize Octave doesn't use C++-11 so those won't be available). I also posted a lot of questions on Stack Overflow.<br /> | I've programmed somewhat on and off in C++, but I've never worked on a project with a group or intended for public consumption. A couple years ago I wrote a Quadratic Number Field Sieve using gmp and that was the first significant piece of code I wrote in C++. A couple months ago I wrote a preprocessor for grounded Answer Set Programs that does something analogous to forward-checking to infer binary constraints. During this project I read "Effective C++" and some of "C++ Templates: The Complete Guide". I did extensive online browsing to understand C++-11 rvalue references and perfect forwarding (although I realize Octave doesn't use C++-11 so those won't be available). I also posted a lot of questions on Stack Overflow.<br /> | ||
Here's a recent C++ project of mine: | |||
https://sourceforge.net/projects/aspmutexpreprocessor/files/?source=navbar <br /> | |||
'''Octave m-scripts'''<br /> | '''Octave m-scripts'''<br /> | ||
I use Octave a lot for minor tasks that come up in research. It's a wonderful tool and I love coming up with sneaky ways to vectorize bits of code. Sometimes I go on StackOverflow to look for "how do you vectorize x" questions just so I can answer them. Most of them are for Matlab though. I don't know why Octave isn't a more popular alternative.<br /> | I use Octave a lot for minor tasks that come up in research. It's a wonderful tool and I love coming up with sneaky ways to vectorize bits of code. Sometimes I go on StackOverflow to look for "how do you vectorize x" questions just so I can answer them. Most of them are for Matlab though. I don't know why Octave isn't a more popular alternative.<br /> | ||
| Line 45: | Line 47: | ||
On the one hand, I confess my documentation was absolutely terrible where it existed at all (today I believe I could do much better, I've had practice explaining things more completely and simply as a TA for CMPUT 101 and tend to get fairly positive reviews), but also these students were almost always freshman who had only just taken their first CS class. My approach to indexing game-states relied heavily on dynamic programming as well as results from combinatorics and generating functions and most of these students had just taken freshman calculus and hadn't expected to be doing any math. | On the one hand, I confess my documentation was absolutely terrible where it existed at all (today I believe I could do much better, I've had practice explaining things more completely and simply as a TA for CMPUT 101 and tend to get fairly positive reviews), but also these students were almost always freshman who had only just taken their first CS class. My approach to indexing game-states relied heavily on dynamic programming as well as results from combinatorics and generating functions and most of these students had just taken freshman calculus and hadn't expected to be doing any math. | ||
* Please state the commits and patches you already contributed to Octave. | * Please state the commits and patches you already contributed to Octave. | ||
I made a minor change to the m-script for the issymmetric function. I also created a significant patch to the find-function which consolidates all the many implementations into one templatized function. This fixes a couple separate bugs/matlab incompatibilities (find(sparse(0,0)), find(sparse(0,1)) etc. all work the same, six or more return values doesn't cause Octave to crash). Additionally, I added a fourth parameter for specifying the desired dimension of the output vector: http://savannah.gnu.org/patch/?8386 | I made a minor change to the m-script for the issymmetric function: http://savannah.gnu.org/bugs/?41426. I also created a significant patch to the find-function which consolidates all the many implementations into one templatized function. This fixes a couple separate bugs/matlab incompatibilities (find(sparse(0,0)), find(sparse(0,1)) etc. all work the same, six or more return values doesn't cause Octave to crash). Additionally, I added a fourth parameter for specifying the desired dimension of the output vector: http://savannah.gnu.org/patch/?8386 | ||
I've reported many bugs relating to sparse matrices. | I've reported many bugs relating to sparse matrices. | ||
| Line 110: | Line 112: | ||
== Y: Your task == | == Y: Your task == | ||
* Did you select a task from our list of proposals and ideas? | * Did you select a task from our list of proposals and ideas? | ||
Yes | |||
** If yes, what task did you choose? Please describe what part of it you especially want to focus on if you can already provide this information. | ** If yes, what task did you choose? Please describe what part of it you especially want to focus on if you can already provide this information. | ||
The Sparse Matrices Project: http://wiki.octave.org/Projects#Sparse_Matrices | The Sparse Matrices Project: http://wiki.octave.org/Projects#Sparse_Matrices | ||
I want to help improve Sparse Matrix support. | I want to help improve Sparse Matrix support. | ||
Particularly, I wanted to build a sparse matrix library tuned towards graph operations. I think that people often underestimate how many complex graph operations are possible with sparse matrices. In many cases, doing something like a breadth-first search can be equivalent to an operation which is almost just a matrix multiply.<br /> | |||
Particularly, I | |||
On the mailing list, I gave an example of a program that takes an undirected graph and finds the set of all maximal cliques. As I've mentioned, I've done a lot with this sort of thing, but constantly find myself working around gaps or bugs. I want to try to fill those gaps and build this graph library on top of it. <br/> | On the mailing list, I gave an example of a program that takes an undirected graph and finds the set of all maximal cliques. As I've mentioned, I've done a lot with this sort of thing, but constantly find myself working around gaps or bugs. I want to try to fill those gaps and build this graph library on top of it. <br/> | ||
UPDATE: After some discussion on the mailing list, one project | UPDATE: After some discussion on the mailing list, one project Jordi suggested was just to get Octave Sparse-Matrix indexing working properly. This seems feasible since sparse column arrays are already stored in compressed format (and indexing generally requires converting back and forth between matrix and column format, but there shouldn't be any need to use row vectors). My first thought for how to approach this is simply to change the way sparse matrix dimensions are represented so that the vertical dimension is an unsigned long long int. If this turns out to be infeasible, I'll look at other possibilities. | ||
* Please provide a rough estimated timeline for your work on the task. | * Please provide a rough estimated timeline for your work on the task. | ||
I | Honestly, the sparse-indexing problem doesn't sound like something that will take up three full months to complete, but I acknowledge that I haven't done much work on the Octave source yet, and can't properly judge this. If it doesn't, there are certainly many other sparse matrix features that have yet to be implemented which I would enjoy working on. | ||
[[Category: Summer of Code]] | [[Category: Summer of Code]] | ||
== Codebase Consolidation == | |||
This is a list of things which I think need to be consolidated and cleaned up in the Octave codebase. Before embarking on my project, I'd feel obliged to handle each of these. | |||
* Permutation Matrices are not index vectors. They shouldn't subclass Array<octave_idx_type>. They should instead contain a private instance of Array<octave_idx_type>. Right now element_type and xelem are both wrong, and elem, checkelem, operator() all return octave_idx_type when they should return bool (for logical correctness) or double (for Matlab compatibility) | |||
* Diagonal matrices, permutation matrices and compressed column sparse matrices are all different types of sparse matrices. There needs to be an AbstractSparse class which is the base of DiagMatrix, PermMatrix and Sparse. In particular, all three types should have an nz_iter which iterates over its non-zero elements in column-major order. | |||
* Permuation Matrices should always be column-major. Every other matrix type in the entire code-base is. This bool _colp just adds unnecessary complication without granting any measurable performance boost except in extremely contrived situations. | |||
* <p> The cumulative forms of max, min, all, any, sum, and product (and there should also probably be some sort of cum_xor) should all call the same function internally. They all are forms of reduce with a different binary operation. Right now, the implementations miss a lot of cases. Ex try:<br /> | |||
max(sprand(1000000000, 20, 0.000001), [], 2);<br /> | |||
This fails with an OOM because it wasn't considered when writing max <br /> | |||
This sort of aggregate function (over the rows) can be done in O(min(h+nnz, nnz*log(w))) time, but one would have to implement the algorithm for each of the above-mentioned 7 functions. By consolidating these into one templated function, it'll make it worth the effort to implement.</p> | |||
* There has to be a standard way to take an octave_value argument and call the proper template instantiation of a function based on its type. I started doing this with https://savannah.gnu.org/patch/?8417 , but diagonoal matrices still need to be added. The fact that the original implementer of find neglected to handle diagonal matrices should be evidence enough that the ad-hoc approach doesn't work. | |||