need some advice on my choice of data-structure ...

[azalea]

Hi All,

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:
s₁,s₂, ... ,
and I would like to maintain a dynamic data-structure that holds the pair-wise distances between
sequences s_i and s_j.

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:

s₀ = 1,1,0,0,0,0,1,1,
s₁ = 1,2,3,4,4,4,4,4,1,1,1,2,
s₂ = 23,14,1,1,12,0,

and I receive a new value, say '14', along with index 2, then I'll update s₂ 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, s₃ = 14.

I also need to maintain the pair-wise distance values.
Say, before receiving '14', I'd already saved
d(s₀ ,s₁ ), d(s₀ ,s₂ ), d(s₁ ,s₂ )
then once I receive '14' along with index 2, I will need to update d(s₀ ,s₂ ), and d(s₁ ,s₂ ).
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(s₀ ,s₃ ), d(s₁ ,s₃ ) and d(s₂ ,s₃ ).

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:

private Map<Integer, Seq> seqs;

It has a function that allows for the index^th sequence of the arraylist of sequences to be updated.

public void addElement(Number newSymbol, int index)

Whenever a sequence is updated, I also update the parameters I need to calculate its distance from other sequences.
Now my question is, what would be the best (most efficient) data-structure for the pair-wise distances?
I'm thinking:

List<ArrayList<Double>> dists = new ArrayList<ArrayList<Double>>();

But I wonder if there's a smarter way to model this?
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.
Thanks,

-A.

[azalea]

anyone??? :P