Ubuntu – Efficiently search sorted file

command linegreptext processing

I have a large file containing one string on each line. I would like to be able to quickly determine if a string is in the file. Ideally, this would be done using a binary chop type algorithm.

Some Googling revealed the look command with the -b flag which promises to locate and output all strings beginning with a given prefix using a binary search algorithm. Unfortunately, it doesn't seem to work correctly and returns null results for strings that I know are in the file (they are properly returned by the equivalent grep search).

Does anyone know of another utility or strategy to search this file efficiently?

Best Answer

There's an essential difference between grep and look:

Unless explicitly stated otherwise, grep will find patterns even somewhere within the lines. For look the manpage states:

look — display lines beginning with a given string

I'm not using look very often, but it did work fine on a trivial example I just tried.

Related Solutions

Ubuntu – Find out if lines of a file is sorted

#!/usr/bin/perl -w
use strict;

unless ( @ARGV == 1 && -f -r $ARGV[0] ) {
    die "Expected single file argument!\n";
}

my %cols;
my $ind = 0;

while (<>) {
    chomp;
    next if /^\s*($|#)/;
    ( @{ $cols{col1} }[$ind], @{ $cols{col2} }[$ind], @{ $cols{col3} }[$ind] ) = split;
    $ind++;
}

my @sorted1 = map { ${ $cols{col1} }[$_] } sort {
    ${ $cols{col1} }[$a] <=> ${ $cols{col1} }[$b] or
    ${ $cols{col2} }[$a] <=> ${ $cols{col2} }[$b] or
    ${ $cols{col3} }[$a] <=> ${ $cols{col3} }[$b]
} keys @{ $cols{col1} };
my @sorted2 = map { ${ $cols{col2} }[$_] } sort {
    ${ $cols{col1} }[$a] <=> ${ $cols{col1} }[$b] or
    ${ $cols{col2} }[$a] <=> ${ $cols{col2} }[$b] or
    ${ $cols{col3} }[$a] <=> ${ $cols{col3} }[$b]
} keys @{ $cols{col2} };

if ( "@sorted1" eq "@{ $cols{col1} }" and "@sorted2" eq "@{ $cols{col2} }") {
    print "File is sorted!\n"
}
else { print "File is unsorted!\n" };
__END__

If the columns are:

X1 Y1 Z1  
X2 Y2 Z2

Sort will be:

if (x1 > x2) then X1 Y1 Z1 > X2 Y2 Z2
if (X1 == X2) && (Y1 > Y2) then X1 Y1 Z1 > X2 Y2 Z2

To add more columns into the sort order, copy the pattern for the first two. I hope that's what you asked for.

Ubuntu – Showing file sizes in sorted order

From your folder:

find . -maxdepth 1 -type f -exec du -h {} + | sort --human-numeric-sort --reverse

You can set how deep it can look for files with -maxdepth parameter or without it to be recursive.

Best Answer

Related Solutions

Ubuntu – Find out if lines of a file is sorted

Ubuntu – Showing file sizes in sorted order

Related Question