Quali comandi standard posso utilizzare per stampare in modo efficiente solo le prime righe dell'output ordinato sulla riga di comando?

Question

Voglio basicamente l'equivalente di

... | sort -arg1 -arg2 -... | head -n $k 

ma, la mia comprensione è quella sorta andrà O (n registro n) su tutta d'ingresso. Nel mio caso ho a che fare con molti dati, quindi il runtime conta per me - e ho anche l'abitudine di traboccare il mio tmp/cartella con i file temporanei di ordinamento.

avrei preferito andare O (n registro k) utilizzando per esempio un heap, che presumibilmente andrebbe più veloce, e che riduce anche la memoria del working set a k.

Esiste qualche combinazione di strumenti da riga di comando standard in grado di farlo in modo efficiente, senza che io debba codificare qualcosa da solo? Idealmente sosterrebbe la piena potenza espressiva del comando sort. sort (su Ubuntu almeno) sembra non avere alcun interruttore documentato in man-page per estrarlo ...

Answer 1

UNIX/Linux fornisce set di strumenti generalisti. Per i set di dati di grandi dimensioni fa un sacco di I/O. Farà tutto ciò che puoi, ma lentamente. Se avessimo un'idea dei dati di input, sarebbe di grande aiuto.

IMO, hai alcune scelte, nessuna ti piacerà davvero.

1. fare un multipart "Radix" pre-Sort - per esempio hanno awk scrivere tutte le linee di cui chiavi iniziare con 'A' in un unico file 'B' ad un altro, ecc O se solo 'P '' D '&' Q ', fai awk semplicemente succhiare ciò che vuoi. Quindi fai un ordinamento completo su un piccolo sottoinsieme. Questo crea 26 file denominati A, B ... Z

   awk '{print $ 0> substr ($ 0,1,1)} bigfile; ordina [opzioni qui] P D Q> risultato

2. Spendere $$: (Esempio) Acquista CoSort da iri.com qualsiasi altro software di ordinamento. Questi tipi usano tutti i tipi di ottimizzazioni, ma non sono gratuiti come bash. È inoltre possibile acquistare un SSD che velocizza l'ordinamento su disco di diversi ordini di grandezza. 5000iops ora a 75000iops. Utilizzare la variabile TMPDIR per inserire i file tmp sull'unità SSD, leggere e scrivere solo sull'unità SSD. Ma usa il tuo set di strumenti UNIX esistente.

3. Utilizzare alcuni software come R o strati, o preferibilmente un database; tutti questi sono pensati per dataset di grandi dimensioni.

4. Fai quello che stai facendo ora, ma guarda YouTube mentre viene eseguito l'ordinamento UNIX.

IMO, si stanno utilizzando gli strumenti sbagliati per dataset di grandi dimensioni quando si desidera risultati rapidi.

Answer 2

Ecco parziale soluzione grezza:

#!/usr/bin/perl 

use strict; 
use warnings; 

my @lines =(); 

while (<>) { 
    push @lines, $_; 
    @lines = sort @lines; 
    if (scalar @lines > 10) { 
     pop @lines; 
    } 
} 
print @lines; 

legge i dati di input solo una volta, mantenendo costantemente un array ordinato delle 10 linee.

L'ordinamento dell'intero array ogni volta è inefficiente, ovviamente, ma suppongo che per un ingresso in gigabyte sarà comunque sostanzialmente più veloce di sort huge-file | head.

Aggiungere un'opzione per variare il numero di righe stampate sarebbe abbastanza semplice. Aggiungere opzioni per controllare come è fatto l'ordinamento sarebbe un po 'più difficile, anche se non sarei sorpreso se ci fosse qualcosa in CPAN che sarebbe d'aiuto.

In modo più astratto, un approccio per ottenere solo i primi N elementi ordinati da un array di grandi dimensioni consiste nell'utilizzare un Quicksort parziale, in cui non si deve preoccupare di ordinare la partizione corretta a meno che non sia necessario. Ciò richiede il mantenimento dell'intero array in memoria, il che è probabilmente poco pratico nel tuo caso.

È possibile dividere l'input in blocchi di medie dimensioni, applicare un algoritmo intelligente per ottenere le prime righe N di ogni blocco, concatenare i blocchi, quindi applicare lo stesso algoritmo al risultato. A seconda delle dimensioni dei blocchi, sort ... | head potrebbe essere sufficientemente intelligente. Non dovrebbe essere difficile mettere insieme uno script di shell usando split -l ... per farlo.

(inserire più se necessario-agitando la mano.)

Disclaimer: Ho appena provato questo su un file molto più piccolo di quello che si sta lavorando (circa 1,7 milioni di linee), e il mio metodo è stato più lento di sort ... | head .

Answer 3

Sulla base di quanto sopra, e alcuni più spunti, direi che la risposta ufficiale alla mia domanda è "non c'è soluzione". Puoi utilizzare strumenti specializzati, oppure puoi utilizzare gli strumenti che hai con le loro prestazioni attuali, oppure puoi scrivere il tuo strumento.

Sto discutendo sul rilevamento del codice sorgente di ordinamento e sull'offerta di una patch. Nel frattempo, nel caso in cui questo rapido codice di abilitazione aiuti qualcuno a fare qualcosa di simile a quello che stavo facendo, ecco cosa ho scritto per me stesso. Non è la migliore pitone, e un punto di riferimento molto ombroso: offro a chiunque altro che si preoccupa di fornire più rigorosa:

• 256 file, di circa 1,6 concerti dimensione totale, tutti seduti su uno SSD, linee separate da \ n, righe di formato [^ \ t] * \ t [0-9] +
• Ubuntu 10.4, 6 core, 8 giga di ram,/tmp su ssd.
• $ time sort -t^v<tab> -k2,2n foo* | tail -10000
  • reali 7m26.444s
  • utente 7m19.790s
  • sys 0m17.530s
• $ time python test.py 10000 foo*
  
  • reali 1m29.935s
  • utente 1m28.640s
  • sys 0m1.220s
• utilizzando diff per analizzare, i due metodi differiscono per tie-break, ma in caso contrario l'ordinamento è lo stesso.

test

.py:

#!/usr/bin/env python 
# test.py 

from sys import argv 
import heapq 
from itertools import chain 

# parse N - the size of the heap, and confirm we can open all input files 
N = int(argv[1]) 
streams = [open(f, "r") for f in argv[2:]] 

def line_iterator_to_tuple_iterator(line_i): 
    for line in line_i: 
     s,c = line.split("\t") 
     c = int(c) 
     yield (c, s) 

# use heap to process inputs 
rez = heapq.nlargest(N, 
       line_iterator_to_tuple_iterator(chain(*streams)), 
       key=lambda x: x[0]) 

for r in rez: 
    print "%s\t%s" % (r[1], r[0]) 

for s in streams: 
    s.close()