What data structure should I use for this pricing table

Question

I have a JTable that has 50,000 rows. Each row contains 3 columns. The middle column contains a double (price), and reads like this.

 col1  col2      col3
       1.0031
       1.0032
       1.0033
       1.0034
       1.0035

I then have a constantly updating array of about 10-20 prices that gets updated every 20ms.

Im currently iterating over that array, and checking it against the 50,000 rows to find the row it should belong to, and inserting it.

Then on the next update, Im clearing those columns, and repeating.

This is extremely costly though, as each update, I have to iterate over 20 prices, that then each iterate 50,000 times to find the value of the row they should belong to.

Theres gotta be a better way to do this... I really want to be able to just insert the price at a certain row, based on the price. (so each p rice is mapped to an index) if price = 1.0035 insert into row X

Instead I have to do something like If price is in one of 50,000 values, find the value index and insert.

Any ideas as the best way to achieve this?? Hashtable?? quadtree for localized search? Anything faster, because the way Im doing it is far to slow, for the application needs.

"to find the row it should belong to, and inserting it", what should belong to what, and what is inserted where ? — mangusta, Jul 22 '15 at 05:09
" I really want to be able to just insert the price at a certain row, based on the price" - (O,o) — mangusta, Jul 22 '15 at 05:17

score 2 · Accepted Answer · edited May 23 '17 at 12:06

2

It sounds like you could let your TableModel manage a SortedMap, such as TreeMap<Double, …>, which "provides guaranteed log(n) time cost for the containsKey, get, put and remove operations." This related example manages a Map<String, String>.

edited May 23 '17 at 12:06

Community

1
1

answered Jul 22 '15 at 05:24

trashgod

203,806
29
246
1,045

Thanks, I think this is exactly what I need – Kylie Jul 22 '15 at 05:53

score 0 · Answer 2 · answered Jul 22 '15 at 05:12

A tree seems like the most logical data structure to me, however if your values are in a known range you could have an index that corresponds to each possible price, with a flag to show if the price is present. Your searches would then be and updates would be O(1) for each entry, the drawback being increased memory footprint. In essence this is a hashtable, although your hashing function could be very simple.

As for a tree, you would have to do some experimentation (or calculation) to determine the number of values in each node for your needs.

What data structure should I use for this pricing table

2 Answers2