• Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorted table data structure with good performance

 
Miro Ricco
Ranch Hand
Posts: 40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I need a hint how to design a data structure for a table of items with good performance.

The structure must fullfil folowing requirements:

1. table is sorted by specified item attribute and sort order, which may change, but not so often
2. get item by index (used in method for getting the N-th page of items) - very often
3. add new item - very often
4. remove item by ID - very often

Item has about 15 attributes, so the table will have 15 columns.
The attributes have different data type (long, int, string, timestamp, ...).
The table will hold about 1000-10000 items.

The data structure will be implemented in java. I need only theoretical design, not the implementation, but the implementation is appreciated.

Thanks !
 
Peter Chase
Ranch Hand
Posts: 1970
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
OK, I got 1 minute before home-time, so this is just brain-dump...

Design a class for storing a row of the data (including the ID). We'll call it class A.

Create a Map (e.g. HashMap) whose keys are IDs and whose values are instances of class A.

Create a SortedSet (e.g. TreeSet) of IDs, with a custom Comparator. The Comparator will compare two IDs, by looking up their entries in the Map and comparing whatever fields are currently chosen for indexing.

When you change the index, you need to re-create the SortedSet, but not the Map.

Think that'll work for you?

NB 10000 items isn't all that many. Unless performance is really critical, it's probably not worth worrying too much about the algorithm.
 
Peter Chase
Ranch Hand
Posts: 1970
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Peter Chase:
OK, I got 1 minute before home-time, so this is just brain-dump...

Design a class for storing a row of the data (including the ID). We'll call it class A.

Create a Map (e.g. HashMap) whose keys are IDs and whose values are instances of class A.

Create a SortedSet (e.g. TreeSet) of IDs, with a custom Comparator. The Comparator will compare two IDs, by looking up their entries in the Map and comparing whatever fields are currently chosen for indexing.

When you change the index, you need to re-create the SortedSet, but not the Map.

Think that'll work for you?

NB 10000 items isn't all that many. Unless performance is really critical, it's probably not worth worrying too much about the algorithm.


Addendum. Silly me. You could just use a SortedMap.
 
Miro Ricco
Ranch Hand
Posts: 40
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for the answer.

How will I quickly get sorted elements from positions 5000-5100 from SortedMap or SortedSet ?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!