need some advice on my choice of data-structure ...
This is more like a programming question, than a java-specific question.
But since I'm programming in Java, I thought I'd post it here.
As mentioned in the title, I basically need some advice on my choice of data-structure for this program.
I have a dynamic set of sequences:
s1,s2, ... ,
and I would like to maintain a dynamic data-structure that holds the pair-wise distances between
sequences si and sj.
The reason why I use the term dynamic is that this is an "online" algorithm
in the sense that I don't have the entire batch of sequences available to me all at once. The sequences are updated on the fly.
So at every time-step I receive a symbol (say an integer),
along with the index of which sequence it belongs to.
For example, say I already have the following sequences:
s0 = 1,1,0,0,0,0,1,1,
s1 = 1,2,3,4,4,4,4,4,1,1,1,2,
s2 = 23,14,1,1,12,0,
and I receive a new value, say '14', along with index 2, then I'll update s2 to 23,14,1,1,12,0,14.
I could also receive '14', along with index 3, which means I need to start a new sequence, s3 = 14.
I also need to maintain the pair-wise distance values.
Say, before receiving '14', I'd already saved
d(s0 ,s1 ), d(s0 ,s2 ), d(s1 ,s2 )
then once I receive '14' along with index 2, I will need to update d(s0 ,s2 ), and d(s1 ,s2 ).
However, if I receive '14' along with index 3, then I will have to extend whatever data-structure
is holding the pair-wise distances, to hold d(s0 ,s3 ), d(s1 ,s3 ) and d(s2 ,s3 ).
I have made a class called "Seq"; every sequence is a Seq object.
Then I have made a classed called "Sequences" which has among its other parameters:
It has a function that allows for the indexth sequence of the arraylist of sequences to be updated.
private Map<Integer, Seq> seqs;
Whenever a sequence is updated, I also update the parameters I need to calculate its distance from other sequences.
public void addElement(Number newSymbol, int index)
Now my question is, what would be the best (most efficient) data-structure for the pair-wise distances?
But I wonder if there's a smarter way to model this?
List<ArrayList<Double>> dists = new ArrayList<ArrayList<Double>>();
Do you see any advantages (in terms of complexity) in switching to HashMaps here instead of List, or to using LinkedList instead of ArrayList etc.?
I'd realllly appreciate any suggestions.
Re: need some advice on my choice of data-structure ...