Reading a file randomly to find the value in given range

[Man4ish]

I have one pblm for reading a file randomly for searching the value with in given range.
e.g.
offset allele id
19 G/T 2066803
20 C/T 2066804
13 A/G 2066805
12 A/G 2066927

In the above file i have to search all the records which are in range (10,15). If i read whole file sequentially it will consume lot of time since data file is around 1GB. So I am planning to read it randomly for searching the offset with in the given range. I know that by using seekg() and tellg(), we can find the exact value randomly but how it is possible to find within range?
Thanks in advance.

Manish

[donbock]

I am skeptical about performing a random search. There is no predictability in a random algorithm. Two successive searches for the same key will have markedly different response times.

Search efficiency is significantly improved if the file is sorted by the same key that you intend to search by. In your example, what is the search key? Do you need to support searching by different keys at different times?

My age is showing, but I can't think of a better reference for sorting and searching algorithms than the classic "The Art of Computer Programming . Vol 3: Sorting and Searching" by Donald Knuth.

[Man4ish]

@donbock
My Data is sorted the first column (id) is key.
offset allele id

12 A/G 2066927
13 A/G 2066805
19 G/T 2066803
20 C/T 2066804

Then How all the records within range (10 ,15) can be retrieved?

Regards
Manish

[donbock]

Is your file amenable to binary search? The typical criteria is whether or not the records are fixed-size.

Suppose each record is 16 bytes; your 1GB file contains 64M records. Binary search of this many records takes at most 26 comparisons.

If your ranges are generally pretty small then you could use a brute force strategy: search for the smallest limit of the range; if you don't find it then repeat the search for the next value in the range until you either find a match or exhaust the range. If you find a match, then read each successive record until you find a value outside the range.

You can improve on brute force if you retain and take advantage of the search trajectory of the previous [unmatched] value.

[Man4ish]

@donbock
My Key may range from 1 to billiion. so records will be like
432423 A/T 4789321
4314441 G/T 4787654
47893217 C/T 7487489

other fields will be of fixed range.My range of searching may vary from 1 to billion also.Then still can we use the brute force algorithm.

[gpraghuram]

I think You posted a similar thread for retreiving record based on a key?
Is it related to that or this is new?

Raghu

[Man4ish]

@gpraghuram
It is similar but i don't want to read the whole file i just want to access the data randomly so that i can reduce the time. I have used the method as suggested. It it is working fine for small file upto 1 MB but when i am trying the same method on 1GB file it is taking 4s which is to much i want it should be in .5 seconds.Please suggest if there is any other method or same method with better performance related to it.

Regards
Manish

[weaknessforcats]

Random accesses are not going to work.

You say your file is sorted by key and that you have a lot of keys?

I sadio earlier that you need to create an index of this file. That requires reading the entire file to build he index. I also said you probably need a multimap<> of pair<> objects as your index structure.

Once the index is built you can reuse it without re-indexing.

All large databases are not read from beginning to end to locate items wirthin a range. They all use indexes.

Here is where you should get a book on database design.

OR....

Consider using SQL rather than work with the file yourself. Access is available as is MySQL, SQL Server, Oracle, etc... Plus there are database SDKs that let you use alreqady written database access code.

Unless this is a home work assignment, no one writes this code from scratch any more.