Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
2  
So... what is you can't use a binary tree? Have you already tried and run into problems of some sort? –  FrustratedWithFormsDesigner Oct 31 '12 at 14:50
    
Have you considered a set? –  Ben Oct 31 '12 at 14:58
    
Does this analysis need to happen just once, or often? –  Mike Partridge Oct 31 '12 at 17:24

3 Answers 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.

share|improve this answer
    
@FrustratedWithFormsDesigner..... I have not tried to use a binary tree.... reason being that the data I am trying to store does not have the binary outlay(IMO).. –  EDO Oct 31 '12 at 16:11
    
@Ben.. I have not tried to use a set... I will research sets now and see if it fits.... –  EDO Oct 31 '12 at 16:12
    
Lists...... not sure..... –  EDO Oct 31 '12 at 16:13
    
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. –  EDO Oct 31 '12 at 16:21
2  
-1: ArrayList in Java is NOT a linked list... –  Thomas Eding Oct 31 '12 at 16:54

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.

share|improve this answer

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.

share|improve this answer
    
Updated to edits in original question. –  herby Oct 31 '12 at 17:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.