How do I efficiently subset a very large line-based file?
Turns out, simply keeping track of the next candidate line (after sorting the sample line numbers) fixes the performance issue, and most of the remaining slowness seems to be due to the overhead of actually reading the file so there’s not very much to improve.

Since I don’t know how how to do this in sed, and it’s not trivial in awk either, here’s a Perl script:

#!/usr/bin/env perl

use strict;
use warnings;

my $file = $ARGV[0];
my $lines_file = $ARGV[1];

open my $lines_fh, '&lt;', $lines_file or die "Cannot read file $lines_file";
chomp (my @lines = &lt;$lines_fh&gt;);
close $lines_fh;

@lines = sort {$a &lt;=&gt; $b} @lines;

open my $fh, '&lt;', $file or die "Cannot read file $file";
my $line = 1;
my $next_line = 0;
while (&lt;$fh&gt;) {
    last if $next_line == scalar @lines;
    if ($line++ == $lines[$next_line]) {
        $next_line++;
        print;
    }
}
close $fh;


I’ve implemented a similar function in C++ for an R package, that's only slightly longer than the Perl script. It is ~3 times faster than the Perl script on my test file.