Sunday, June 01, 2014

vim to ubuntu 14.04: youcompleteme :-)

I just found out that "youcompleteme" was added as a package in Ubuntu 14.04 LTS.
Now, vim fans like me can have the amazing IDE-like experience by simply doing the few easy steps below:
apt-get install vim apt-get install vim-youcompleteme apt-get install vim-addon-manager vam install youcompleteme
The screen shots (C++ and Python) below work out of the box!


Monday, February 24, 2014

Value Semantics, Concepts Based Polymorphism and Composite Pattern

Not long ago, I watched Sean Parent's Value Semantics and Concepts Based Polymorphism.
In the presentation, Sean showed a sample code that manipulates "document type".

Yesterday, while flipping over an old book on my book shelf, Pattern Hatching: Design Patterns Applied, by John Vlissides, I came across his example of using the Composite Pattern to illustrate a simplified file system structure with class Node, class File and class Directory.  There it uses the classical way of inheritance.
I couldn't help but notice the similarity between the simplified file system recursive structure of the Composite Pattern with Sean's example of the document inside document.

So, I just play around with concepts based polymorphism a bit.
Note that the code may not be optimize or anything, as it is a quick copy-and-modify.

Here is node.h:
#ifndef NODE_H #define NODE_H #include #include #include #include class node_t { struct concept_t { virtual ~concept_t() = default; virtual size_t total_size() const = 0; virtual void print(std::ostream& out) = 0; virtual concept_t* copy() = 0; }; struct file_model_t : concept_t { file_model_t(size_t x) : total_size_(x) {} size_t total_size() const { return total_size_; } void print(std::ostream& out) { out << total_size_; } concept_t* copy() { return new file_model_t(*this); } size_t total_size_; }; struct dir_model_t : concept_t { dir_model_t(std::initializer_list l) : children_(l) {} size_t total_size() const { size_t total_size = 0; for (const auto& c : children_) total_size += c.total_size(); return total_size; } virtual void print(std::ostream& out) { out << "("; auto i = children_.begin(); out << *i; ++i; while (i != children_.end()) { out << ","; out << *i; ++i; } out << ")"; } concept_t* copy() { return new dir_model_t(*this); } std::vector children_; }; std::unique_ptr p_; public: node_t(size_t value) : p_(new file_model_t(value)) { /*std::cout << "ctor file" << std::endl;*/ } node_t(std::initializer_list l) : p_(new dir_model_t(l)) { /*std::cout << "ctor dir" << std::endl;*/ } node_t(const node_t& x) : p_(x.p_->copy()) { /*std::cout << "copy" << std::endl;*/ } node_t& operator=(node_t x) { //std::cout << "assign" << std::endl; p_ = std::move(x.p_); return *this; } size_t total_size() const { return p_->total_size(); } friend std::ostream& operator<<(std::ostream& out, const node_t& n) { n.p_->print(out); return out; } }; using file_t = node_t; using directory_t = node_t; #endif //NODE_H
And here is the client code:
#include #include #include "node.h" int main() { file_t f1 ( 10 ); std::cout << "f1: " << f1.total_size() << std::endl; file_t f2 ( 20 ); std::cout << "f2: " << f2.total_size() << std::endl; directory_t d1 { f1, f2 }; std::cout << "d1: " << d1.total_size() << std::endl; file_t f3 ( 30 ); std::cout << "f3: " << f3.total_size() << std::endl; directory_t d2 { f3, d1 }; std::cout << "d2: " << d2.total_size() << std::endl; std::cout << d2 << std::endl; }
And this is the output:
f1: 10 f2: 20 d1: 30 f3: 30 d2: 60 (30,(10,20))

Note how the directory nests the subdirectory.
More importantly, the value semantics of the client code, polymorphism without reference or pointer, cool!

Admittedly, I'm quite new to this concepts-based polymorphism technique, and may also not be paying too much attention to other aspect of the C++ code in general. If you find any mistake, feedback and advice are appreciated.

Tuesday, December 31, 2013

Discrete Fourier Transform and Nested For Loops

This will be my last post for this year, 2013. Hehe, what a way to spend my new year countdown.
A while ago, Discrete Fourier Transform gave me a feeling of "I understand the intuition but the equation...".
So, I spent some time understanding the math behind.
After some reading, I kinda think that it would be easier for programmer to understand it if we spell it out as nested for loops, instead of equation that Capital Sigma notation. So, here is a post that I try to code it out in Python (originally to convince myself, but hopefully it can help others too).
First, we import NumPy and Matplotlib, so that we can plot the output to help with the understanding.
import numpy import matplotlib.pyplot
Next, we create a couple sine, cosine, with different (multiple) frequencies.
N = 44 time = numpy.arange(N) sine = numpy.sin(2 * numpy.pi * (1.0/N) * time) cosine = numpy.cos(2 * numpy.pi * (1.0/N) * time) legend_sine_real, = matplotlib.pyplot.plot(sine.real, marker='o') legend_sine_imag, = matplotlib.pyplot.plot(sine.imag, marker='o') matplotlib.pyplot.legend([legend_sine_real, legend_sine_imag], ["sine real", "sine imag"]) matplotlib.pyplot.title("time domain sine") matplotlib.pyplot.savefig("time_domain_sine.png") matplotlib.pyplot.clf() # # sine2a and sine2b should be equivalent sine2a = numpy.sin(2 * numpy.pi * (2.0/N) * time) sine2b = numpy.array([sine[n*2 % N] for n in time]) legend_sine2b_real, = matplotlib.pyplot.plot(sine2b.real, marker='o') legend_sine2b_imag, = matplotlib.pyplot.plot(sine2b.imag, marker='o') matplotlib.pyplot.legend([legend_sine2b_real, legend_sine2b_imag], ["sine2b real", "sine2b imag"]) matplotlib.pyplot.title("time domain sine2b") matplotlib.pyplot.savefig("time_domain_sine2b.png") matplotlib.pyplot.clf() # sine4 = numpy.sin(2 * numpy.pi * (4.0/N) * time) legend_sine4_real, = matplotlib.pyplot.plot(sine4.real, marker='o') legend_sine4_imag, = matplotlib.pyplot.plot(sine4.imag, marker='o') matplotlib.pyplot.legend([legend_sine4_real, legend_sine4_imag], ["sine4 real", "sine4 imag"]) matplotlib.pyplot.title("time domain sine4") matplotlib.pyplot.savefig("time_domain_sine4.png") matplotlib.pyplot.clf() #
The wave forms we get are like:
Then, we add up the wave forms with different frequencies to create our time domain data
data = sine + sine2b + sine4 legend_data_real, = matplotlib.pyplot.plot(data.real, marker='o') legend_data_imag, = matplotlib.pyplot.plot(data.imag, marker='o') matplotlib.pyplot.legend([legend_data_real, legend_data_imag], ["data real", "data imag"]) matplotlib.pyplot.title("time domain data") matplotlib.pyplot.savefig("time_domain_data.png") matplotlib.pyplot.clf() #
This should give us:
After that, we create the "scary" coefficient array (the one that usually appears as complex exponential of 'e')
coff = numpy.arange(N, dtype=numpy.complex) coff.real = cosine coff.imag = sine * -1.0
Finally, we perform the DFT using nested for loops.
# freq = numpy.fft.fft(data) # equivalently, we can implement DFT (which is not as efficient as FFT, since it is O(n^2)), but for learning purpose freq = numpy.arange(N, dtype=numpy.complex) for p in time: freq[p] = numpy.complex(real=0.0, imag=0.0) for q in time: freq[p] += data[q] * coff[p*q % N] legend_freq_real, = matplotlib.pyplot.plot(freq.real, marker='o') legend_freq_imag, = matplotlib.pyplot.plot(freq.imag, marker='o') matplotlib.pyplot.legend([legend_freq_real, legend_freq_imag], ["freq real", "freq imag"]) matplotlib.pyplot.title("freq domain spectrum") matplotlib.pyplot.savefig("freq_domain_spectrum.png") matplotlib.pyplot.clf() #
And here is the plot for the DFT (you can enable the line that uses numpy.fft.fft to verify and see if the result is identical):
Yeah, I know, it is probably too lame for those who already understand it. But hopefully, for some who find it easier to read source code (and loops) compare to mathematical symbol, this can be helpful. By the way, if you find that I have coded/explained something inaccurately, feel free to let me know, I will appreciate it and update it accordingly. Happy New Year 2014! :)