I need some help creating a non-binary tree (or some other data structure that will better solve my problem)

Question

I have about ten lists of numbers and some strings. Each list has about <= 30K lines. Each line on a list has a distinct number.

I need to build an efficient way of finding all the lines in each list that has the same 'control' number (or key for dB guys) and comparing what is in their string parts. I am writing this in Java.

Let me give an actual example of what I am trying to do..... I have ten lists each containing about 30K records. Each record looks like 901234(key)- 1.0987(float)-kadfnfj(Description String)-01/01/01(date) and all lists have similar records some keys may be available in some lists but not guaranteed!.. I want to find a way to search through all lists for one particular key and compare the attendant float value. Due to the size of the lists, i am worried about the memory usage and due to the number of records, I am worried about the efficiency of the data structure used.

I have thought about using trees but my brain cells are about burnt now. I need some help.

Answer 1

Ideally a database would be used. You let the database handle the look up of the value quickly. If you have a small, light database (mysql and similar) accessible, use it.

Failing having a table that you can wrangle from a DBA for doing this, there are other database solutions. The one that I am most familiar with is BDB (Berkeley DataBase).

Using the sleepycat licensed version, this is free. BDB stores its data on disk and you don't store its entirety in memory at once.

The trickiest part in this design would be the data that is stored for each key (to an extent, thats the problem for anything).

---

If you are willing to spend disk space, a consideration would be to use the filesystem itself as a database. For the data 901234(key)- 1.0987(float)-kadfnfj(Description String)-01/01/01(date), you would write a file in the directory .../9/0/1/2/3/4/901234/ with the information you are storing. Accessing the filesystem is not bad and also makes it trivial for other applications to access the data.

For that matter, if you are familiar with other "scripting" languages (perl, python, etc...) these may be more suited to the task (working with strings and the file system) of simply breaking up the large files into their component lines.

Answer 2

First, write something that works. You can just split the line to hold the key and the float and put it in Map; separate Map for each 30K-list. So you will have a few Maps from integer keys to float values. Or something that simple.

If it will work, measure if it is too slow, and then try to find better data structures/algortihms. I'd say for 30K records, a Map holding data in memory would be sufficient enough.

Answer 3

The ideal method for accessing a given key would be direct access where you use the key to give you the address. In Java you don't have direct memory addresses however you do get indexed arrays so you could use the array index as the memory address. This should be far faster than any traversal method.