Results 1 to 2 of 2
  1. #1
    azalea is offline Member
    Join Date
    Oct 2011
    Posts
    12
    Rep Power
    0

    Default 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 03:01 PM.

  2. #2
    azalea is offline Member
    Join Date
    Oct 2011
    Posts
    12
    Rep Power
    0

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

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

Similar Threads

  1. Tree data structure
    By Nacao in forum New To Java
    Replies: 18
    Last Post: 08-23-2011, 06:26 PM
  2. Which data structure to use?
    By malaguena in forum New To Java
    Replies: 4
    Last Post: 04-05-2011, 04:41 PM
  3. Which data structure to choose ?
    By lumpy in forum New To Java
    Replies: 2
    Last Post: 02-20-2010, 04:43 AM
  4. data structure and data base??
    By ahmed13 in forum Advanced Java
    Replies: 8
    Last Post: 03-27-2009, 05:48 AM
  5. Queue data structure
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-14-2008, 08:35 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
  •