Frage:
Wie kann ich eine sehr große zeilenbasierte Datei effizient unterteilen?
Konrad Rudolph
2017-06-05 17:49:25 UTC
view on stackexchange narkive permalink

Dies ist in letzter Zeit wiederholt aufgetreten: Ich habe eine sehr große Textdatei (in der Größenordnung von mehreren GiB) und muss eine zeilenbasierte Teilmenge für etwa 10.000 Zeilen durchführen. Es gibt Lösungen für bestimmte Szenarien (z. B. samtools view -s zum zufälligen Abtasten von BAM-Dateien), aber manchmal passt mein Anwendungsfall nicht in diese Kategorien.

Leider naiv sed basierende Lösung ist extrem langsam:

  time sed -n -f < (awk -vOFS = '' '{print $ 0, "p"} 'line_numbers.txt) input_file > selected_lines.txt  

Wobei line_numbers.txt eine Datei ist, die eine Zeilennummer pro Zeile enthält.

Vergessen Sie, dies für 10.000 Zeilen auszuführen. Es kommt bereits für nur 1000 zum Stillstand.

Wie kann ich dies beschleunigen, idealerweise so, dass es nur mit der Größe der Eingabedatei skaliert und eine mehr oder weniger konstante Laufzeit in der Anzahl von hat Zeilen, die ich untersetze?

Ich denke, diese Frage gehört mehr zum Stackoverflow als hier, weil der allgemeine Fall angesprochen werden soll, nicht ein bestimmtes Bioinformatik-Dateiformat. Ich habe versucht abzustimmen, um zu schließen, aber irgendwie habe ich nicht die Wahl, Stackoverflow als geeignetere Site auszuwählen.
@bli Ich bin anderer Meinung, ich denke, wir sollten offen sein für alle Fragen, die sich im Verlauf der Arbeit eines Bioinformatikers stellen können. Viele, viele Fragen der Bioinformatik lassen sich auf einfache Textanalysevorgänge reduzieren (z. B. die Übersetzung zwischen verschiedenen Sequenzformaten in Betracht ziehen), aber ich bin immer noch der Meinung, dass diese Themen behandelt werden sollten. Sie können auch nicht auf eine andere Site migrieren, es sei denn, ein bestimmter Migrationspfad wurde eingerichtet, und wir haben noch keinen davon.
@bli Ich bin ebenfalls anderer Meinung, da Fragen zum Stapelüberlauf so gut wie immer an eine Sprache gebunden sind (oder umgekehrt, an keine gebunden sind und keine Codelösung erforderlich ist). Im Gegensatz dazu bin ich an einer Lösung interessiert, aber die Technologie interessiert mich nicht.
Es wäre hilfreich, etwas mehr Bioinformatik-Kontext / Geschichte in diese Frage aufzunehmen. Sie haben ein Beispiel gegeben, was kein Anwendungsfall wäre, aber nicht was. Ich kann mir keine Gedanken über eine Situation machen, in der ich anhand der Zeile * Nummer * eine Teilmenge erstellen musste. Es ist üblicher für mich, eine Teilmenge basierend auf einem Wert in einer der Spalten zu erstellen.
Nur mit awk: `awk 'BEGIN {while ((getline <" line_num.txt ")> 0) l [$ 1] = 1} NR in l' input_file`.
In Verbindung stehender Beitrag zu SO unter Verwendung von awk [Unterteilen einer Datei nach Zeilen- und Spaltennummern] (https://stackoverflow.com/q/40842008/680068). Ich bin mir einig, dass dies häufig vorkommt, und ich denke, dieser Beitrag ist ein Thema für die Bioinformatik.
Es wäre schön, Benchmarking-Ergebnisse für Top-Antworten zu sehen.
Wenn es Ihnen nichts ausmacht, die gesamten Dateien in den Speicher einzulesen, sollte dies in Python `operator.itemgetter (* [int (Zeile) für Zeile in open (Zeilendatei)]) (open (Eingabedatei) .readlines ())` schnell sein
@Chris_Rands Warum nicht `itertools.islice` für einen Generator verwenden? Dadurch wird vermieden, dass die gesamte Datei auf einmal geladen wird, und der Aufwand ist minimal.
@KonradRudolph Sie meinen wie "islice" jeden fortlaufenden Bereich von Zeilennummern separat, wobei die relative Zeilennummer verwendet wird, wenn der Generator verbraucht wird?
@Chris_Rands Verdammt, ich habe zu viel R verwendet. Ich dachte, Sie könnten nicht zusammenhängende Indexbereiche an "islice" übergeben.
Vier antworten:
#1
+7
Konrad Rudolph
2017-06-05 17:49:25 UTC
view on stackexchange narkive permalink

Es stellt sich heraus, dass das einfache Verfolgen der nächsten Kandidatenzeile (nach dem Sortieren der Probenzeilennummern) das Leistungsproblem behebt, und der größte Teil der verbleibenden Langsamkeit scheint auf den Aufwand beim tatsächlichen Lesen der Datei zurückzuführen zu sein, sodass nicht viel vorhanden ist

Da ich nicht weiß, wie dies in sed zu tun ist und es auch in awk nicht trivial ist, ist hier ein Perl-Skript :

  #! / usr / bin / env perluse strict; Warnungen verwenden; my $ file = $ ARGV [0]; my $ lines_file = $ ARGV [1]; öffne meine $ lines_fh, '<', $ lines_file oder stirb "Datei $ lines_file kann nicht gelesen werden"; chomp (meine @lines = < $ lines_fh>); schließe $ lines_fh; @lines = sort {$ a < = > $ b} @lines; öffne meine $ fh, '<', $ file oder die "Datei $ file kann nicht gelesen werden"; meine $ line = 1; meine $ next_line = 0; while (< $ fh>) {last if $ next_line == scalar @lines; if ($ line ++ == $ lines [$ next_line]) {$ next_line ++; drucken; }} close $ fh;  

Ich habe eine ähnliche Funktion in C ++ für ein R-Paket implementiert, die nur geringfügig länger ist als das Perl-Skript. Es ist ~ 3 mal schneller als das Perl-Skript in meiner Testdatei.

Wäre das nicht viel schneller, wenn Sie stattdessen einen Hash verwenden würden? $ line {$ _} ++ für @lines und dann in der while-Schleife: print if $ line {$.}.
@terdon Nein. Die Hash-Suchzeit ist im Durchschnitt konstant, jedoch langsamer als eine direkte Indexsuche in einem zusammenhängenden Array (plus gelegentliches Indexinkrement). Soviel zur Theorie. Ich habe es auch getestet und es gilt in der Praxis. (Und wie erwartet ist der tatsächliche Unterschied fast vernachlässigbar.)
Nun, bis. Danke, ich hatte immer angenommen, dass Hashes per Definition schneller sind (das bekommen Sie, wenn Sie Biologen Code schreiben lassen :).
#2
+5
gringer
2017-06-06 00:54:57 UTC
view on stackexchange narkive permalink

Perl sollte damit ziemlich schnell sein, wenn ein Hash-Set zum Speichern der Zeilenliste verwendet wird. Eine solche Struktur funktioniert auch für Teilmengen, die auf einem Feldwert basieren, wobei der Vergleich eher mit dem Feld als mit "$" erfolgen würde:

  #! / Usr / bin / perluse strict; use Warnungen; meine $ lines_file = $ ARGV [0]; meine% include_lines = (); öffne meine $ lines_fh, '<', $ lines_file oder stirb "Datei $ lines_file kann nicht gelesen werden"; while (< $ lines_fh>) {chomp; $ include_lines {$ _} = 1;} close $ lines_fh; while (<>) {if ($ include_lines {$.}) {# "$." - Zeilennummer des aktuellen Dateidrucks; }}  

Beachten Sie, dass gemäß dieser SO-Antwort das "$". Der Operator ist nicht ausschließlich die aktuelle Zeilennummer und kann durch verschiedene Dateivorgänge oder andere Einstellungen beeinflusst werden.

Bearbeiten: Ich habe gerade Ihren Kommentar zur Geschwindigkeit in Ihrer Antwort gesehen und Hash-Sätze mit einer sortierten Liste verglichen. Das Bit $ lines [$ next_line] fühlt sich für mich etwas seltsam an. Haben Sie versucht, shift oder pop in einer sortierten Liste zu verwenden, um die nächste Zeile abzurufen:

  #! / Usr / bin / perluse streng; Warnungen verwenden; meine $ lines_file = $ ARGV [0]; öffne meine $ lines_fh, '<', $ lines_file oder sterbe "Datei $ lines_file kann nicht gelesen werden"; chomp (meine @lines = < $ lines_fh>); schließe $ lines_fh ; @lines = sort {$ a < = > $ b} @lines; my $ next_line = shift (@lines); while (<>) {if ($. == $ next_line) {$ next_line = shift (@lines) ;; drucken; last if (! @lines); }}  

Ich habe die Verschiebung in einen pop geändert (wobei die Sortierreihenfolge umgekehrt wurde) und für Konrads Originalcode Zeiten von 4,8 s, 5,8 s und 4,1 s erhalten. Mein Hash-Code bzw. mein Pop-Code rufen 25 Mal 10.000 Zeilen aus / usr / share / dict / britisch-englisch-verrückt ab (nachdem die Eingabedateien nach / tmp code kopiert wurden >). Aus meiner Sicht sind sie alle gleich: schnell genug, dass ich länger brauchen würde, um den Befehl einzugeben, als um ihn auszuführen. Die Verwendung von shift anstelle von pop scheint die Zeit nicht merklich zu ändern.

`shift` /` pop` modifiziert das Array, was sehr langsam sein kann, wenn der Speicher in der Folge verschoben wird (aber ich gebe zu, ich weiß nicht, ob Perl das tut). Es sollte definitiv niemals schneller sein als der indizierte Zugriff. Um ehrlich zu sein, ist es weniger Code.
Das tut mir leid; Ich schrieb diese schnell ohne zu testen. Ich habe diese Fehler behoben (in Zeile 12 ein% in ein $ geändert) und ein "my" an die Spitze von Zeile 18 gesetzt.
#3
+4
bli
2017-06-05 19:17:42 UTC
view on stackexchange narkive permalink

Einige verwandte Fragen erscheinen auf anderen Websites mit potenziell interessanten Lösungen, die ich hier berichte:

So probieren Sie ungefähr 1% der nicht leeren Zeilen aus:

  awk 'BEGIN {srand ()}! / ^ $ / {if (rand () < = .01) print $ 0}' Eingabedatei  

(von https: // stackoverflow .com / a / 692321/18878788)

So wählen Sie 1000 zufällige Zeilen aus:

  shuf -n 1000 Eingabedatei  

(von https://stackoverflow.com/a/15065490/1878788 und https://unix.stackexchange.com/a/108604/55127)

Bearbeiten: Python-Lösungen mit einer Liste von Zeilen

Verwenden einer Reihe von Zeilenindizes und Auswählen von Zeilen durch Testen der Gruppenzugehörigkeit:

  #! / usr / bin / env python3import syswith open (sys.argv [2], "r") als line_numbers_file: line_indices = set (int (line) - 1 für line in line_numbers_file) mit open (sys.argv [1], "r") ) als Eingabedatei: print (* (line.strip () für (idx, line) in enumerate (Eingabedatei) wenn idx in line_indices), sep = "\ n")  

Verwenden eines numpy-Booleschen Arrays zusammen mit itertools.compress :

  #! / usr / bin / env python3import sysfrom itertools importieren komprimieren von numpy importieren Nullen mit open ( sys.argv [2], "r") als line_numbers_file: line_indices = [int (line) - 1 für line in line_numbers_file] selector = Nullen (max (line_indices) + 1, dtype = bool) selector [line_indices] = 1with open (sys.argv [1], "r") als Eingabedatei: print (* (line.strip () für Zeile in compress (Eingabedatei, Selektor)), sep = "\ n")  

Ich habe einige Tests an einer Datei durchgeführt, die 15774756 Sam-Datensätze und eine Liste von 10000 vorgenerierten Zufallszeilen enthält.

Das von Konrad Rudolph vorgeschlagene Perl-Skript ( https: // bioinformatics). stackexchange.com/a/454/292) wird in ca. 5,3 Sekunden ausgeführt.

Die Python-Lösung zum Testen der festgelegten Mitgliedschaft wird in ca. 4,45 Sekunden ausgeführt.

Die komprimierungsbasierte Lösung läuft in ca. 3,4 Sekunden. Ich vermute, dass dies abhängig von der höchsten gewünschten Zeilennummer sehr unterschiedlich sein kann, da die Anzahl der Iterationen von der Länge des booleschen Arrays abhängt. Hier war die höchste Zeilennummer 15773768, also ziemlich hoch im Vergleich zur Gesamtzahl der Zeilen.

Ich habe es mit Python 3.6 versucht. Ich vermute, dass Python 2.7 etwas schneller sein könnte, habe es aber nicht getestet.

Ich denke, die Frage betrifft die Auswahl eines bestimmten Satzes von Zeilen aus der Datei, nicht nur eine zufällige Stichprobe.
@terdon ist richtig, die Benutzerfälle, auf die ich kürzlich gestoßen bin, erforderten bestimmte, nicht zufällige Zeilen. Trotzdem ist dies eine gute Ergänzung.
@KonradRudolph Da Sie "samtools view -s" erwähnt haben, dachte ich, dass Sie für den Rest der Frage an eine zufällige Auswahl denken und dass Ihre Liste der Zeilennummern zufällig generiert wurde.
@bli Meine Absicht war es, dies als Gegenbeispiel zu zeigen, wie ich das Problem * nicht * lösen kann.
`int (line.strip ())` kann zu `int (line)` vereinfacht werden; `int` ignoriert sowieso führende / nachfolgende Leerzeichen
@Chris_Rands Das wusste ich nicht. Vielen Dank.
#4
+1
Alex Reynolds
2017-06-10 01:27:11 UTC
view on stackexchange narkive permalink

Ich habe ein Befehlszeilentool (C ++ 14) namens subset geschrieben, das auf Github verfügbar ist: https://github.com/alexpreynolds/subset

Dies sollte einigermaßen speichereffizient und schnell sein. Das Tool subset speichert keine Eingabezeilen in einer Tabelle, sondern überträgt die Datei einmal und speichert einen 4- oder 8-KB-Pufferblock der Eingabedatei (je nach Betriebssystem).

Es speichert Zeilennummern in einem Array, aber acht Bytes pro Ganzzahl * 100 KB sind 800 KB für diesen Anwendungsfall - nicht sehr viel Speicher.

Es gibt eine O-Sortierung (nlogn) Strafe für das Zeilennummernarray, aber auch diese Liste ist viel kleiner als die Abfragedatei, und die Ganzzahlsortierung ist ziemlich optimiert, sodass der Treffer klein sein sollte.

Wenn Ihre Zeilennummernliste bereits sortiert ist, kann ich eine Option zum Überspringen der Sortierung hinzufügen. Lassen Sie mich wissen, ob dies nützlich wäre.

Der Filterungsschritt geht linear durch das Zeilennummernarray und die Eingabedatei, druckt Zeilen mit Indexübereinstimmungen und überspringt den Rest.

Tatsächlich wird die -Untergruppe vorzeitig beendet, wenn die Eingabedatei analysiert wird, wenn keine Zeilennummern mehr abgefragt werden müssen. Diese Funktion ist daher besonders nützlich, um das Filtern sehr großer Abfragedateien zu beschleunigen. (Wenn Ihre Abfragedatei beispielsweise 1 Million Zeilen enthält und Ihre letzte interessierende Zeilennummer 12345 ist, gibt es keinen Grund, den Rest der Datei durchzulesen.)

Sie können sie wie folgt abrufen, erstellen und installieren Also:

  $ git-Klon https://github.com/alexpreynolds/subset.git$ cd-Teilmenge $ make $ cp-Teilmenge / usr / local / bin  

Sobald sich die Binärdatei in Ihrem Pfad befindet, gibt es verschiedene Möglichkeiten, sie zu verwenden.

Sie können beispielsweise einen Startindex und einen Längenwert angeben. Im Folgenden werden sieben Zeilen ab der 33. Zeile (32 als 0-indizierter Wert) erfasst:

  $ subset --prefix-with-indices -s 32 -n 7 -i query.txt > answer.txt  

Oder Sie können eine Textdatei mit Zeilennummern in einer separaten Zeile angeben. Im Folgenden wird eine Datei mit dem Namen line-numbers.txt eingelesen und zum Filtern von query.txt :

  $ subset --prefix verwendet -with-indizes -l Zeilennummern.txt -i query.txt > answer.txt  

Die Indizes in Zeilennummern.txt sollten positiv sein. 0-indizierte Ganzzahlen. Die Liste der Nummern muss nicht sortiert werden, da die -Untergruppe die Liste der Nummern für Sie sortiert. Auf diese Weise kann ein effizienter Durchlauf durch die Eingabe- / Abfragedatei durchgeführt werden.

Sie können - Präfix mit Indizes weglassen, um das Debug-Präfix wegzulassen. Hier können Sie das Ergebnis überprüfen.

Die Tests test / makefile zeigen Optionen und Verwendungsmöglichkeiten für die beiden Filterarten.



Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...