# Thread: need some advice on my choice of data-structure ...

1. Member
Join Date
Oct 2011
Posts
12
Rep Power
0

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

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:
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:
Java Code:
`private Map<Integer, Seq> seqs;`
It has a function that allows for the indexth sequence of the arraylist of sequences to be updated.
Java Code:
`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:
Java Code:
`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.
Last edited by azalea; 11-03-2011 at 04:01 PM.

2. Member
Join Date
Oct 2011
Posts
12
Rep Power
0

## Re: need some advice on my choice of data-structure ...

anyone??? :P
Last edited by azalea; 11-03-2011 at 08:28 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•