Programming

Hello,
Attached is my very simple C++ code to remove any substrings (DNA sequence) of each other, i.e. any redundant sequence is removed to get unique sequences. Similar to sort | uniq command except there is reverse-complementary for DNA sequence. The program runs well with small dataset, but when I increase the data size to ~1,000 entries (some maybe 100,000bp long), it took about 2 hours to finish.
My question is: How to improve the performance of my code?
It seems memory issue can be excluded as 256GB RAM is available.
1) What are the room for coding techniques based on my current algorithms, which is a simple "sorting---looping---comparing" with complexity n^2 ?
2) What are the better algorithms, for sure there are many?

Either of the two questions is too complicate for myself, but I am wondering if anybody can give me some help to increase the performance of the program. Thanks a lot!

You need to reformat that code - I'm seeing it all as one line.

You can save time by keeping it always sorted. That would mean that you'd be able to check for duplicates every time you try and add a line, not afterwards.

I don't mean that you should call sort() every loop, I mean you should find the spot in the container where it belongs and insert there. This would be easier and faster with a list<> than a vector<>.

achenle, I do not know what happened, but it is fine with my vim/gedit, and good viewed with cat/more/less/head etc on my Linux console: ubuntu/Mint 17.0.

corona688, can I make sure the difference between list<> and vector <> can be hours? I am aware the data is kind of big (~6MB, for 300 entries with 166,000bp in total), but it's nothing compared with ~10GB file with ~100 millions of entries. I did not try ~10BG file yet, which would be forever!! I must have missed something big for my code.

It is UNIX text, not Windows text.

Vector is not "fast" and list is not "slow".

If you try to insert in arbitrary places anywhere inside a vector, it will be slow.

If you try to use a list for random access, it will be slow.

What I have suggested is better suited for lists than vectors.

You are comparing every element to every other element. If you have 300 elements, that's 90,000 comparisons. If you have 3000 elements, that's 9 million comparisons. Any sequence you remove early means 300 fewer loops later.

You are also searching for strings inside strings without using any sort of index, but that would be complicated.

Your reply reminds me of two ideas that bug me a lot, or I have been trying to catch to handle fasta files. 1) Use some sort of index (hashing? FM-index?); 2) use suffix array, tree or trie to do the job. I'm trying to get example code by starting from what I have.