Week 11: Start Working in Mothur Code Integration

[azmfaridee]

Related Issues: #3, #14, #15, #16, #17, #19, #20

This is weeks task is pretty straight forward. Begin working on porting the python code to C++ with mothur integration.

We've already some some initial R&D on mothur's framework in issue #4, #5, #6 and #7. Continuing from those investigation, we need to port our current algorithm to work with mothur.

[azmfaridee]

Here is a quick list of what might be the issues with transferring python code to C++

• We need to perform random shuffling of a list, we do this in python using radom.shuffle(list) function. In C++ this can be easily done by using random_shuffle(vector.begin(), vector.end())
• Python uses Mersenne Twister in generating hight quality random numbers particularly random.randint(upperLimit) which we've been using so far. ISO C++ does not have a Mersenne Twister implementation but rand() function could be used here without much problem. The point is further discussed in Issue #18
• Which would be the better way to handing data? Do we usevector< vector <int> > for the matrix representation (which is automatically memory managed?) or use dynamic allocated array to do this (which is a lot faster)
• Matrix transpose is an operation that we need very frequently, while this is a trivial issue (creating a copied transpose matrix in C++ is a 2-3 line code), I wonder is there any built in operation already to do that which is of course a lot faster
• The functions in python implementation can return multiple values, this can be easily mimicked by passing references to the C++ function
• Writing proper copy constructors for complex classes so that to ensure deep copy is also a major issue in the implementation
• It would be easier if we mock implement the template of the classify.shared command then implement the rest centered around that.

[kdiverson]

As mentioned in issue #18, I think rand() is fine for now. If there's time at the end you can spend time implementing the mersenne twister algo.

A vector of vectors should be fine although if you're not doing a lot of manipulation a 2d array is pretty easy to implement array[width * height] and array[width * row + col] = x

I don't think there's a built in matrix transpose. It's probably easiest to just write a for-loop.

[azmfaridee]

I don't think there's a built in matrix transpose. It's probably easiest to just write a for-loop.

I know matrix transpose is a simple problem, well it might be the simplest problem that is given to freshers. The reason I'm concerned about this is that we are talking about huge amount of data. In these cases (consider a matrix of 4000x400 or even bigger), efficient implementation becomes a important factor, even for the simplest of operations.

Check these three links, and you'll understand why I'm concerned about this:

• http://stackoverflow.com/questions/2884304/how-can-i-transpose-an-image-in-assembly
• http://stackoverflow.com/questions/5200338/a-cache-efficient-matrix-transpose-program
• http://en.wikipedia.org/wiki/Cache-oblivious_algorithm

We'll at this point, this may sound like overkill, but I'd definitely want to implement a faster implementation of matrix transpose than a 2-3 liner nested for, if I can get some spare time later :)