Programming

If you want to run faster,

1. Insert data in a way that it's always sorted, as Corona688 has already noted.
2. Don't use new/delete in a loop.
3. Don't use C++ I/O routines - use C open/read/close or other low-level routines.

---------- Post updated at 04:34 PM ---------- Previous update was at 04:34 PM ----------

I don't always have access to a Unix box.

You say you have a lot of memory so I think you would be best using a hash table. Store both each entry and it's reverse-complementary.

My problem is the implementation. I want to try programming using some available "libraries". I appreciate any code example on top of mine. This sounds lazy, but I'm self-learning by practice. Of course googled a while, but did not get any similar example. Thanks a lot!

I would agree to achenles 1(Corona688) and 3 points.


On top of that I would just use simple dynamic array with pointer to next element, something like :

Code:

typedef struct _sList _sList;
struct _sList{
    _sList    *next;
    int       SEQ_size;
    SEQ       *element;
};

when reading elements from file on complete element just start comparing SEQ_size from start of list, until point where element_size from file equals or smaller to element in list, then in case of smaller - add element to list (unique one). If equal memcmp(list_elemen, file_element, SEQ_size) until list element is greater, equal or SEQ_size of file element is greater, if equal delete - its equal, if greater add to list before greater element.
P.S. this is case when sorting from small to big.

This way you will fast forward to elements of same length, and then will compare only until you will find equal element or storing spot.

In the end you will have sorted list of unique elements.

Need even faster then make more difficult structures from which you could build graph(data tree). In this area only your imagination and content of element will stop from optimizing even more. Usually more complex structures will pay off when having bigger amount of data.

"hash table" isn't exactly a library, it's different enough from other data structures it's often hand-rolled. Generalizing it too much would run the risk of poor performance, you need to pick the right algorithms for your application. It has a lot of restrictions as well (hard to iterate, deletion can cause something like fragmentation, and it can't be sorted). I've seen a few attempts at building a library for it, but nothing I ever liked very much.

In the end it's not that complicated. It's a big array with strict rules about what data gets put in what element. I'd suggest "open chaining" for your table -- basically an array full of lists -- with an index that's not really hashed at all, just converted from ACGT into boolean. Four letters would be 8 bits, for an array 256 long for example. Then you could just look up the first four letters of your sequence, find that list, and speedily check every possible thing which might contain your sequence without having to brute-force it.