On Thu, Nov 29, 2001 at 01:34:02PM -0500, Michael G Schwern wrote:
> On Thu, Nov 29, 2001 at 03:17:39PM +0200, Ariel Scolnicov wrote:
> > > Yesterday, I saw an interesting related exercise. Write a program that
> > > reads the lines from a file and outputs the middle line. The kicker is
> > > that you can't use arrays.
>
> I'll interpret that as O(1) memory, O(n) time.
In which case your program below doesn't meet the qualifications.
The only way to achieve O(1) memory is reading in a fixed amount
of characters at a time - reading in entire lines means you may
have to read in the entire file at once.
>
> > #!/usr/local/bin/perl -w
> > # Print middle line of file(s)
> > use strict;
> > open F,$ARGV[0] or die;
> > open G,$ARGV[0] or die;
> > my $l;
> > 1 while (defined(<F>) && defined($l=<G>) && defined(<F>));
> > print $l;
>
> That requires reading each line three times. Here's one where each
> line only need be read once:
File::ReadBackwards read in a chuck of a file, hoping to find a newline.
It doesn't read just a single line from the end.
> use File::ReadBackwards;
> open F, $ARGV[0] or die;
> tie *G, 'File::ReadBackwards', $ARGV[0] or die;
>
> while(1) {
> $front = <F>;
> last if $front eq $back;
> $back = <G>;
> last if $front eq $back;
> }
> print $front;
Here's an (untested) version that uses O(1) memory, and O(n) time:
$/ = \1;
open my $fh => shift or die;
my ($c, $d) = (0, 0);
while (<$fh>) {
$c ++ if $_ eq "\n";
}
seek $fh => 0, 0 or die;
$d = int ($c / 2);
while (<$fh>) {
if ($_ eq "\n") {last unless -- $d}
}
while (<$fh>) {
print;
exit if $_ eq "\n";
}
Abigail
