|
From: | Sorav Bansal |
Subject: | Re: binary search in a file |
Date: | Thu, 14 Jul 2005 11:54:56 -0700 |
User-agent: | Mozilla Thunderbird 1.0 (X11/20041206) |
Is there a utility to search for a value in a sorted file using binary search. The file was sorted using the 'sort' command.
[/snip]
Is there any reason why you want to use a binary search, except for speed?
Well, linear search on a 60GB file is likely to be many orders of magnitude slower than binary search.
Unless the lines are fixed-length, after each chop, the search program will have to find the start-of-line character. This is likely to negate any advantage gained from binary searches.
Just a little bit. Finding the start-of-line is easy and quite fast since it is an in-memory operation. The speed in such operations is usually limited by disk-I/Os
I'd sugest just sticking to grep. You can use the '-l' (ell) option -this will exit when the first matching line is found, (but not display it).
I ended up writing my own binary search utility. We are discussing if it should be made a part of gnu.coreutils.
Sorav
[Prev in Thread] | Current Thread | [Next in Thread] |