Answers.Body: <p>Perl should be fairly fast with this when using a hash set to store the list of lines. A structure like this also works for subsetting based on a field value, where the comparison would be with the field rather than "$.":</p>
  
  <pre><code>#!/usr/bin/perl
  
  use strict;
  use warnings;
  
  my $lines_file = $ARGV[0];
  my %include_lines = ();
  
  open my $lines_fh, '&lt;', $lines_file or die "Cannot read file $lines_file";
  while(&lt;$lines_fh&gt;){
    chomp;
    $include_lines{$_} = 1;
  }
  close $lines_fh;
  
  while(&lt;&gt;){
    if($include_lines{$.}){ # "$." -- line number of current file
      print;
    }
  }
  </code></pre>
  
  <p>Note that according to <a href="https://stackoverflow.com/questions/5920686/how-to-get-the-current-line-number-of-a-file-open-using-perl#comment6821096_5920709">this SO answer</a>, the "$." operator is not strictly the current line number, and can be influenced by different file operations or other settings.</p>
  
  <p>Edit: just saw your comment about speed in your answer, comparing hash sets to a sorted list. The <code>$lines[$next_line]</code> bit feels a bit odd to me. Have you tried out using <code>shift</code> or <code>pop</code> on a sorted list to fetch the next line:</p>
  
  <pre><code>#!/usr/bin/perl
  
  use strict;
  use warnings;
  
  my $lines_file = $ARGV[0];
  
  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;
  my $next_line = shift(@lines);
  
  while (&lt;&gt;) {
      if ($. == $next_line) {
          $next_line = shift(@lines);
          print;
          last if (!@lines);
      }
  }
  </code></pre>
  
  <p>I changed the <code>shift</code> to a <code>pop</code> (reversing the sort order to match), and got times of 4.8s, 5.8s and 4.1s for Konrad's original code, my hash code, and my pop code respectively, fetching 10,000 lines from <code>/usr/share/dict/british-english-insane</code> 25 times over (after copying input files to <code>/tmp</code>). They're all the same from my perspective: quick enough that it would take me longer to type out the command than it would to run it. Using <code>shift</code> instead of <code>pop</code> doesn't seem to change the time noticeably.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T21:38:15.590Z
Answers.Text: `shift`/`pop` modify the array which may be quite slow if memory is moved as a consequence (but I admit I don’t know whether Perl does that). It should definitely never be faster than indexed access; though to be honest it’s less code.
Answers.UserDisplayName: Konrad Rudolph
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-06T08:07:23.993Z
Answers.Text: Sorry about that; I wrote these up quickly without testing. I've fixed those bugs (changed a % to a $ in line 12), and put a "my" at the front of line 18.
Answers.UserDisplayName: gringer
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T19:54:57.300Z
Answers.LastActivityDate: 2018-01-28T23:06:13.360Z
Answers.LastEditDate: 2018-01-28T23:06:13.360Z
Answers.UserDisplayName: gringer
Answers.Body: <p>Some related questions appear in other sites, with potentially interesting solutions, which I report here:</p>
  
  <p>To sample approximately 1% of the non-empty lines:</p>
  
  <pre><code>awk 'BEGIN {srand()} !/^$/ { if (rand() &lt;= .01) print $0}' input_file
  </code></pre>
  
  <p>(from <a href="https://stackoverflow.com/a/692321/1878788">https://stackoverflow.com/a/692321/1878788</a>)</p>
  
  <p>To select 1000 random lines:</p>
  
  <pre><code>shuf -n 1000 input_file
  </code></pre>
  
  <p>(from <a href="https://stackoverflow.com/a/15065490/1878788">https://stackoverflow.com/a/15065490/1878788</a>, and <a href="https://unix.stackexchange.com/a/108604/55127">https://unix.stackexchange.com/a/108604/55127</a>)</p>
  
  <h3>Edit: Python solutions using a list of lines</h3>
  
  <p>Using a set of line indices and selecting lines by testing set membership:</p>
  
  
  
  <pre><code>#!/usr/bin/env python3
  
  import sys
  
  with open(sys.argv[2], "r") as line_numbers_file:
      line_indices = set(int(line) - 1 for line in line_numbers_file)
  
  with open(sys.argv[1], "r") as input_file:
      print(*(line.strip() for (idx, line) in enumerate(input_file)
              if idx in line_indices), sep="\n")
  </code></pre>
  
  <p>Using a numpy boolean array together with <code>itertools.compress</code>:</p>
  
  
  
  <pre><code>#!/usr/bin/env python3
  
  import sys
  from itertools import compress
  from numpy import zeros
  
  with open(sys.argv[2], "r") as line_numbers_file:
      line_indices = [int(line) - 1 for line in line_numbers_file]
  
  selector = zeros(max(line_indices) + 1, dtype=bool)
  selector[line_indices] = 1
  
  with open(sys.argv[1], "r") as input_file:
      print(*(line.strip() for line in compress(input_file, selector)), sep="\n")
  </code></pre>
  
  <p>I did some tests on a file containing 15774756 sam records and a list of 10000 pre-generated random line numbers.</p>
  
  <p>The perl script proposed by Konrad Rudolph (<a href="https://bioinformatics.stackexchange.com/a/454/292">https://bioinformatics.stackexchange.com/a/454/292</a>) runs in about 5.3 seconds.</p>
  
  <p>The set membership testing python solution runs in about 4.45 seconds.</p>
  
  <p>The compress based solution runs in about 3.4 seconds.
  I suspect this may vary a lot depending on the highest line number we want, since the number of iterations will depend on the length of the boolean array. Here the highest line number was 15773768, so pretty high compared with the total number of lines.</p>
  
  <p>I tried with python 3.6. I suspect that python 2.7 could be slightly faster, but haven't tested.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T14:33:37.927Z
Answers.Text: I think the question is about selecting a specific set of lines from the file, not just a random sample.
Answers.UserDisplayName: terdon
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T14:54:28.900Z
Answers.Text: @terdon is right, the user cases I've come across recently required specific, nonrandom lines. Nevertheless, this is a good complement.
Answers.UserDisplayName: Konrad Rudolph
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T15:06:56.853Z
Answers.Text: @KonradRudolph Since you mentioned `samtools view -s`, I thought that you were thinking of random selection for the rest of the question and that your list of line numbers was randomly generated.
Answers.UserDisplayName: bli
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T15:10:46.623Z
Answers.Text: @bli My intention was to show this as a counter-example how I *can't* solve the problem. 
Answers.UserDisplayName: Konrad Rudolph
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T19:01:43.320Z
Answers.Text: `int(line.strip())` can be simplified to `int(line)`; `int` ignores leading/trailing whitespace anyway
Answers.UserDisplayName: Chris_Rands
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T14:17:42.013Z
Answers.LastActivityDate: 2017-06-06T07:10:27.073Z
Answers.LastEditDate: 2017-06-06T07:10:27.073Z
Answers.UserDisplayName: bli
Answers.Body: <p>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.</p>
  
  <p>Since I don’t know how how to do this in <code>sed</code>, and it’s not trivial in <code>awk</code> either, here’s a Perl script:</p>
  
  <pre class="lang-perl prettyprint-override"><code>#!/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;
  </code></pre>
  
  <p>I’ve implemented a <a href="https://gist.github.com/klmr/a3e88c0ce102be0d3b2ce52ae83825e5" rel="nofollow noreferrer">similar function in C++</a> for an <a href="https://github.com/HannahVMeyer/PhenotypeSimulator" rel="nofollow noreferrer">R package</a>, that's only slightly longer than the Perl script. It is ~3 times faster than the Perl script on my test file.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T13:07:12.710Z
Answers.Text: Wouldn't this be far faster if you used a hash instead? `$line{$_}++ for @lines` and then, in the `while` loop: `print if $line{$.}`.
Answers.UserDisplayName: terdon
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T13:08:31.940Z
Answers.Text: @terdon No. Hash lookup time is constant on average, but slower than a direct index lookup in a contiguous array (plus the occasional index increment). So much for theory. I also tested it, and it holds in practice. (And, just as expected, the actual difference is almost negligible.)
Answers.UserDisplayName: Konrad Rudolph
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T13:50:43.013Z
Answers.Text: Well, TIL. Thanks, I had always assumed hashes were faster by definition (that's what you get when you let biologists write code :).
Answers.UserDisplayName: terdon
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-05T12:49:24.763Z
Answers.LastActivityDate: 2017-06-09T01:58:30.053Z
Answers.LastEditDate: 2017-06-09T01:58:30.053Z
Answers.UserDisplayName: Konrad Rudolph
Answers.Body: <p>I wrote a command-line (C++14) tool called <code>subset</code> which is up on Github: <a href="https://github.com/alexpreynolds/subset" rel="nofollow noreferrer">https://github.com/alexpreynolds/subset</a></p>
  
  <p>This should be reasonably memory efficient and fast. The <code>subset</code> tool does not store input lines in a table, but instead streams through the file once, storing a 4 or 8k buffer chunk of the input file (depending on OS). </p>
  
  <p>It stores line numbers in an array, but eight bytes per integer * 100k is 800kB, for that use case — not very much memory there.</p>
  
  <p>There's an O(nlogn) sort penalty on the line number array, but again this list will be much smaller than the query file, and integer sorting is fairly optimized, so the hit should be small. </p>
  
  <p>If your line number list is already sorted, I could add an option to skip sorting; let me know if that would be useful.</p>
  
  <p>The filtering step walks through the line number array and input file linearly, printing lines where there are index matches, and skipping over the rest. </p>
  
  <p>Indeed, <code>subset</code> will quit early in parsing the input file if there are no more line numbers to query. So this feature is especially useful for speeding up filtering of very large query files. (If your query file has 1M rows, say, and your last line number of interest is 12345, there's no reason to read through the rest of the file.)</p>
  
  <p>You can grab, build and install it like so:</p>
  
  <pre><code>$ git clone https://github.com/alexpreynolds/subset.git
  $ cd subset
  $ make
  $ cp subset /usr/local/bin
  </code></pre>
  
  <p>Once the binary is in your path, there are a couple ways to use it.</p>
  
  <p>For example, you can specify a start index and length value. The following grabs seven lines starting with the 33rd line (32 as a 0-indexed value):</p>
  
  <pre><code>$ subset --prefix-with-indices -s 32 -n 7 -i query.txt &gt; answer.txt
  </code></pre>
  
  <p>Or you can specify a text file containing line numbers, each on a separate line. The following reads in a file called <code>line-numbers.txt</code> and uses that to filter <code>query.txt</code>:</p>
  
  <pre><code>$ subset --prefix-with-indices -l line-numbers.txt -i query.txt &gt; answer.txt
  </code></pre>
  
  <p>The indices in <code>line-numbers.txt</code> should be positive, 0-indexed integers. The list of numbers does not need to be sorted, as <code>subset</code> will sort the list of numbers for you. This is so that an efficient single pass through the input/query file can be done.</p>
  
  <p>You can leave out <code>--prefix-with-indices</code> to leave out the debug prefix. This is there so that you can do a sanity check on the result.</p>
  
  <p>The <code>test/makefile</code> tests demonstrate options and usages for the two types of filtering.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-09T20:27:11.420Z
Answers.LastActivityDate: 2017-06-10T01:29:46.010Z
Answers.LastEditDate: 2017-06-10T01:29:46.010Z
Answers.UserDisplayName: Alex Reynolds
Body: <p>This has come up repeatedly recently: I have a very large text file (in the order of several GiB) and I need to perform line-based subsetting for around 10,000 lines. There exist solutions for specific scenarios (e.g. <code>samtools view -s</code> for randomly sampling BAM files) but sometimes my use-case doesn’t fit into these categories.</p>
  
  <p>Unfortunately a naïve <code>sed</code>-based solution is <em>extremely</em> slow:</p>
  
  <pre><code>time sed -n -f &lt;(awk -vOFS='' '{print $0, "p"}' line_numbers.txt) input_file &gt; selected_lines.txt
  </code></pre>
  
  <p>Where <code>line_numbers.txt</code> is a file containing one line number per line.</p>
  
  <p>Forget running this for 10,000 lines; it’s already grinding to a halt for a mere 1000.</p>
  
  <p>How can I speed this up, ideally so that it scales only with the size of the input file, and has more or less constant runtime n the number of lines that I subset?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-05T13:53:36.263Z
Comments.Text: I think this question belongs more to stackoverflow than here, because it wants the general case to be addressed, not some specific bioinformatics file format. I tried to vote to close, but somehow, I don't have the choice to select stackoverflow as a more appropriate site.
Comments.UserDisplayName: bli
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-05T14:35:15.183Z
Comments.Text: @bli I disagree, I think we should be open to any question that can arise in the course of a bioinformatician's work. Many, many bioinformatics questions can be boiled down to simple text parsing operations (consider translating between different sequence formats, for example) but I still feel those should be on topic. Also, you can't migrate to another site unless a specific migration path has been set up and we don't have any of those yet.
Comments.UserDisplayName: terdon
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-05T14:51:51.203Z
Comments.Text: @bli I disagree as well, because Stack Overflow questions are pretty much always tied to a language (or the opposite, tied to none, and no code solution is required). By contrast, I'm interested in a solution but I don't care about the technology.
Comments.UserDisplayName: Konrad Rudolph
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-05T20:05:40.827Z
Comments.Text: It would be helpful to include a bit more bioinformatics context / story into this question. You've given an example of what wouldn't be a use case, but not what would. I can't think off the top of my head about a situation where I've needed to subset based on the line *number*. It's more common for me to be subsetting based on a value in one of the columns.
Comments.UserDisplayName: gringer
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-06T02:29:18.963Z
Comments.Text: With awk only: `awk 'BEGIN{while((getline<"line_num.txt")>0)l[$1]=1}NR in l' input_file`.
Comments.UserDisplayName: user172818
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-06T08:13:31.927Z
Comments.Text: Related post on SO, using awk, [Subset a file by row and column numbers](https://stackoverflow.com/q/40842008/680068). Agreed this comes up frequently, and I think this post is on-topic for bioinformatics.
Comments.UserDisplayName: zx8754
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-06T08:19:24.217Z
Comments.Text: It would be nice to see benchmarking results for top answers.
Comments.UserDisplayName: zx8754
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-06T08:22:08.817Z
Comments.Text: If you don't mind reading the whole files into memory, this should be quick in Python `operator.itemgetter(*[int(line) for line in open(line_file)])(open(input_file).readlines())`
Comments.UserDisplayName: Chris_Rands
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-06T08:43:30.167Z
Comments.Text: @Chris_Rands Why not use `itertools.islice` on a generator? This will avoid loading the whole file at once, and have minimal overhead.
Comments.UserDisplayName: Konrad Rudolph
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-06T09:06:46.743Z
Comments.Text: @KonradRudolph you mean like `islice` each continuous range of line numbers separately, using the relative line number as the generator is consumed?
Comments.UserDisplayName: Chris_Rands
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-06T09:53:19.500Z
Comments.Text: @Chris_Rands Damn, I’ve been using too much R. I thought you could pass non-contiguous index ranges to `islice`.
Comments.UserDisplayName: Konrad Rudolph
Tags: <shell><benchmarking><subset><text>
Title: How do I efficiently subset a very large line-based file?
ThreadText: # How do I efficiently subset a very large line-based file?
  
  (Asked by: username_0 on 2017-06-05)
  
  This has come up repeatedly recently: I have a very large text file (in the order of several GiB) and I need to perform line-based subsetting for around 10,000 lines. There exist solutions for specific scenarios (e.g. `samtools view -s` for randomly sampling BAM files) but sometimes my use-case doesn’t fit into these categories.
  
  Unfortunately a naïve `sed`-based solution is *extremely* slow:
  
  ```
  time sed -n -f <(awk -vOFS='' '{print $0, "p"}' line_numbers.txt) input_file > selected_lines.txt
  
  ```
  
  Where `line_numbers.txt` is a file containing one line number per line.
  
  Forget running this for 10,000 lines; it’s already grinding to a halt for a mere 1000.
  
  How can I speed this up, ideally so that it scales only with the size of the input file, and has more or less constant runtime n the number of lines that I subset?
  
  **Tags:** shell, benchmarking, subset, text
  
  > **Comments:**
  > **username_1**: I think this question belongs more to stackoverflow than here, because it wants the general case to be addressed, not some specific bioinformatics file format. I tried to vote to close, but somehow, I don't have the choice to select stackoverflow as a more appropriate site.  
  > **username_2**: @username_1 I disagree, I think we should be open to any question that can arise in the course of a bioinformatician's work. Many, many bioinformatics questions can be boiled down to simple text parsing operations (consider translating between different sequence formats, for example) but I still feel those should be on topic. Also, you can't migrate to another site unless a specific migration path has been set up and we don't have any of those yet.  
  > **username_0**: @username_1 I disagree as well, because Stack Overflow questions are pretty much always tied to a language (or the opposite, tied to none, and no code solution is required). By contrast, I'm interested in a solution but I don't care about the technology.  
  > **username_3**: It would be helpful to include a bit more bioinformatics context / story into this question. You've given an example of what wouldn't be a use case, but not what would. I can't think off the top of my head about a situation where I've needed to subset based on the line *number*. It's more common for me to be subsetting based on a value in one of the columns.  
  > **username_4**: With awk only: `awk 'BEGIN{while((getline<"line_num.txt")>0)l[$1]=1}NR in l' input_file`.  
  > **username_5**: Related post on SO, using awk, [Subset a file by row and column numbers](https://stackoverflow.com/q/40842008/680068). Agreed this comes up frequently, and I think this post is on-topic for bioinformatics.  
  > **username_5**: It would be nice to see benchmarking results for top answers.  
  > **username_6**: If you don't mind reading the whole files into memory, this should be quick in Python `operator.itemgetter(*[int(line) for line in open(line_file)])(open(input_file).readlines())`  
  > **username_0**: @username_6 Why not use `itertools.islice` on a generator? This will avoid loading the whole file at once, and have minimal overhead.  
  > **username_6**: @username_0 you mean like `islice` each continuous range of line numbers separately, using the relative line number as the generator is consumed?  
  > **username_0**: @username_6 Damn, I’ve been using too much R. I thought you could pass non-contiguous index ranges to `islice`.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_0 on 2017-06-05. Score: 7
  
  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:
  
  ```perl
  #!/usr/bin/env perl
  
  use strict;
  use warnings;
  
  my $file = $ARGV[0];
  my $lines_file = $ARGV[1];
  
  open my $lines_fh, '<', $lines_file or die "Cannot read file $lines_file";
  chomp (my @lines = <$lines_fh>);
  close $lines_fh;
  
  @lines = sort {$a <=> $b} @lines;
  
  open my $fh, '<', $file or die "Cannot read file $file";
  my $line = 1;
  my $next_line = 0;
  while (<$fh>) {
      last if $next_line == scalar @lines;
      if ($line++ == $lines[$next_line]) {
          $next_line++;
          print;
      }
  }
  close $fh;
  
  ```
  
  I’ve implemented a [similar function in C++](https://gist.github.com/klmr/a3e88c0ce102be0d3b2ce52ae83825e5) for an [R package](https://github.com/HannahVMeyer/PhenotypeSimulator), that's only slightly longer than the Perl script. It is ~3 times faster than the Perl script on my test file.
  
  > **Comments:**
  > **username_2**: Wouldn't this be far faster if you used a hash instead? `$line{$_}++ for @lines` and then, in the `while` loop: `print if $line{$.}`.  
  > **username_0**: @username_2 No. Hash lookup time is constant on average, but slower than a direct index lookup in a contiguous array (plus the occasional index increment). So much for theory. I also tested it, and it holds in practice. (And, just as expected, the actual difference is almost negligible.)  
  > **username_2**: Well, TIL. Thanks, I had always assumed hashes were faster by definition (that's what you get when you let biologists write code :).  
  
  ---
  
  ### Answer by username_3 on 2017-06-05. Score: 5
  
  Perl should be fairly fast with this when using a hash set to store the list of lines. A structure like this also works for subsetting based on a field value, where the comparison would be with the field rather than "$.":
  
  ```
  #!/usr/bin/perl
  
  use strict;
  use warnings;
  
  my $lines_file = $ARGV[0];
  my %include_lines = ();
  
  open my $lines_fh, '<', $lines_file or die "Cannot read file $lines_file";
  while(<$lines_fh>){
    chomp;
    $include_lines{$_} = 1;
  }
  close $lines_fh;
  
  while(<>){
    if($include_lines{$.}){ # "$." -- line number of current file
      print;
    }
  }
  
  ```
  
  Note that according to [this SO answer](https://stackoverflow.com/questions/5920686/how-to-get-the-current-line-number-of-a-file-open-using-perl#comment6821096_5920709), the "$." operator is not strictly the current line number, and can be influenced by different file operations or other settings.
  
  Edit: just saw your comment about speed in your answer, comparing hash sets to a sorted list. The `$lines[$next_line]` bit feels a bit odd to me. Have you tried out using `shift` or `pop` on a sorted list to fetch the next line:
  
  ```
  #!/usr/bin/perl
  
  use strict;
  use warnings;
  
  my $lines_file = $ARGV[0];
  
  open my $lines_fh, '<', $lines_file or die "Cannot read file $lines_file";
  chomp (my @lines = <$lines_fh>);
  close $lines_fh;
  
  @lines = sort {$a <=> $b} @lines;
  my $next_line = shift(@lines);
  
  while (<>) {
      if ($. == $next_line) {
          $next_line = shift(@lines);
          print;
          last if (!@lines);
      }
  }
  
  ```
  
  I changed the `shift` to a `pop` (reversing the sort order to match), and got times of 4.8s, 5.8s and 4.1s for username_0's original code, my hash code, and my pop code respectively, fetching 10,000 lines from `/usr/share/dict/british-english-insane` 25 times over (after copying input files to `/tmp`). They're all the same from my perspective: quick enough that it would take me longer to type out the command than it would to run it. Using `shift` instead of `pop` doesn't seem to change the time noticeably.
  
  > **Comments:**
  > **username_0**: `shift`/`pop` modify the array which may be quite slow if memory is moved as a consequence (but I admit I don’t know whether Perl does that). It should definitely never be faster than indexed access; though to be honest it’s less code.  
  > **username_3**: Sorry about that; I wrote these up quickly without testing. I've fixed those bugs (changed a % to a $ in line 12), and put a "my" at the front of line 18.  
  
  ---
  
  ### Answer by username_1 on 2017-06-05. Score: 4
  
  Some related questions appear in other sites, with potentially interesting solutions, which I report here:
  
  To sample approximately 1% of the non-empty lines:
  
  ```
  awk 'BEGIN {srand()} !/^$/ { if (rand() <= .01) print $0}' input_file
  
  ```
  
  (from <https://stackoverflow.com/a/692321/1878788>)
  
  To select 1000 random lines:
  
  ```
  shuf -n 1000 input_file
  
  ```
  
  (from <https://stackoverflow.com/a/15065490/1878788>, and <https://unix.stackexchange.com/a/108604/55127>)
  
  ### Edit: Python solutions using a list of lines
  
  Using a set of line indices and selecting lines by testing set membership:
  
  ```
  #!/usr/bin/env python3
  
  import sys
  
  with open(sys.argv[2], "r") as line_numbers_file:
      line_indices = set(int(line) - 1 for line in line_numbers_file)
  
  with open(sys.argv[1], "r") as input_file:
      print(*(line.strip() for (idx, line) in enumerate(input_file)
              if idx in line_indices), sep="\n")
  
  ```
  
  Using a numpy boolean array together with `itertools.compress`:
  
  ```
  #!/usr/bin/env python3
  
  import sys
  from itertools import compress
  from numpy import zeros
  
  with open(sys.argv[2], "r") as line_numbers_file:
      line_indices = [int(line) - 1 for line in line_numbers_file]
  
  selector = zeros(max(line_indices) + 1, dtype=bool)
  selector[line_indices] = 1
  
  with open(sys.argv[1], "r") as input_file:
      print(*(line.strip() for line in compress(input_file, selector)), sep="\n")
  
  ```
  
  I did some tests on a file containing 15774756 sam records and a list of 10000 pre-generated random line numbers.
  
  The perl script proposed by username_0 username_0 (<https://bioinformatics.stackexchange.com/a/454/292>) runs in about 5.3 seconds.
  
  The set membership testing python solution runs in about 4.45 seconds.
  
  The compress based solution runs in about 3.4 seconds.
  I suspect this may vary a lot depending on the highest line number we want, since the number of iterations will depend on the length of the boolean array. Here the highest line number was 15773768, so pretty high compared with the total number of lines.
  
  I tried with python 3.6. I suspect that python 2.7 could be slightly faster, but haven't tested.
  
  > **Comments:**
  > **username_2**: I think the question is about selecting a specific set of lines from the file, not just a random sample.  
  > **username_0**: @username_2 is right, the user cases I've come across recently required specific, nonrandom lines. Nevertheless, this is a good complement.  
  > **username_1**: @username_0 Since you mentioned `samtools view -s`, I thought that you were thinking of random selection for the rest of the question and that your list of line numbers was randomly generated.  
  > **username_0**: @username_1 My intention was to show this as a counter-example how I *can't* solve the problem.   
  > **username_6**: `int(line.strip())` can be simplified to `int(line)`; `int` ignores leading/trailing whitespace anyway  
  
  ---
  
  ### Answer by username_7 on 2017-06-09. Score: 1
  
  I wrote a command-line (C++14) tool called `subset` which is up on Github: <https://github.com/alexpreynolds/subset>
  
  This should be reasonably memory efficient and fast. The `subset` tool does not store input lines in a table, but instead streams through the file once, storing a 4 or 8k buffer chunk of the input file (depending on OS).
  
  It stores line numbers in an array, but eight bytes per integer \* 100k is 800kB, for that use case — not very much memory there.
  
  There's an O(nlogn) sort penalty on the line number array, but again this list will be much smaller than the query file, and integer sorting is fairly optimized, so the hit should be small.
  
  If your line number list is already sorted, I could add an option to skip sorting; let me know if that would be useful.
  
  The filtering step walks through the line number array and input file linearly, printing lines where there are index matches, and skipping over the rest.
  
  Indeed, `subset` will quit early in parsing the input file if there are no more line numbers to query. So this feature is especially useful for speeding up filtering of very large query files. (If your query file has 1M rows, say, and your last line number of interest is 12345, there's no reason to read through the rest of the file.)
  
  You can grab, build and install it like so:
  
  ```
  $ git clone https://github.com/alexpreynolds/subset.git
  $ cd subset
  $ make
  $ cp subset /usr/local/bin
  
  ```
  
  Once the binary is in your path, there are a couple ways to use it.
  
  For example, you can specify a start index and length value. The following grabs seven lines starting with the 33rd line (32 as a 0-indexed value):
  
  ```
  $ subset --prefix-with-indices -s 32 -n 7 -i query.txt > answer.txt
  
  ```
  
  Or you can specify a text file containing line numbers, each on a separate line. The following reads in a file called `line-numbers.txt` and uses that to filter `query.txt`:
  
  ```
  $ subset --prefix-with-indices -l line-numbers.txt -i query.txt > answer.txt
  
  ```
  
  The indices in `line-numbers.txt` should be positive, 0-indexed integers. The list of numbers does not need to be sorted, as `subset` will sort the list of numbers for you. This is so that an efficient single pass through the input/query file can be done.
  
  You can leave out `--prefix-with-indices` to leave out the debug prefix. This is there so that you can do a sanity check on the result.
  
  The `test/makefile` tests demonstrate options and usages for the two types of filtering.
  
  
  ---
  
  