linux - बैश में किसी अन्य बड़ी फ़ाइल से फ़ाइल की पंक्तियाँ खोजने का सबसे तेज़ तरीका




bash perl (11)

IMHO, grep एक बहुत अच्छा उपकरण है जो बहुत बड़ी file2.txt के लिए अनुकूलित है, लेकिन शायद इतने सारे पैटर्न को खोजने के लिए नहीं। मैं file1.txt के सभी स्ट्रिंग्स को एक ही विशाल regexp में संयोजित करने का सुझाव देता हूं, जैसे \ | bar1 | bar2 | foo1 | foo2 \ |

echo  '\|'$(paste -s -d '|' file1.txt)'\|' > regexp1.txt

grep -E -f regexp1.txt file2.txt > file.matched

और हां LANG = C मदद कर सकता है। कृपया प्रतिक्रिया दें या अपनी फाइलें भेजें ताकि मैं खुद का परीक्षण कर सकूं।

मेरे पास दो फाइलें हैं, file1.txt और file2.txtfile1.txt में लगभग 14K लाइनें हैं और file2.txt में लगभग 2 बिलियन हैं। file1.txt पास एक एकल फ़ील्ड f1 प्रति पंक्ति है जबकि file2.txt में 3 फ़ील्ड हैं, f1 माध्यम से f1 , सीमांकित द्वारा |

मैं file2.txt से सभी पंक्तियों को खोजना चाहता हूँ जहाँ file2.txt f1 में file1.txt मेल f2 (या लाइन पर कहीं भी हो अगर हम अतिरिक्त समय बिताना नहीं चाहते हैं तो file2.txt के मूल्यों को विभाजित करते file2.txt )।

file1.txt (लगभग 14K लाइनें, क्रमबद्ध नहीं ):

foo1
foo2
...
bar1
bar2
...

file2.txt (लगभग 2 बिलियन लाइनें, सॉर्ट नहीं ):

date1|foo1|number1
date2|foo2|number2
...
date1|bar1|number1
date2|bar2|number2
...

आउटपुट अपेक्षित:

date1|foo1|number1
date2|foo2|number2
...
date1|bar1|number1
date2|bar2|number2
...

यहाँ मैंने कोशिश की है और इसे चलाने में कई घंटे लग रहे हैं:

fgrep -F -f file1.txt file2.txt > file.matched

मुझे आश्चर्य है कि अगर इस ऑपरेशन को सामान्य यूनिक्स कमांड के साथ या एक छोटी स्क्रिप्ट के साथ करने का एक बेहतर और तेज़ तरीका है।


आप इसके लिए पर्ल का उपयोग भी कर सकते हैं:

कृपया ध्यान दें कि यह मेमोरी को हॉग करेगा और आपके मशीन / सर्वर में कुछ बेहतर है।

नमूना डेटा:

%[email protected] * /root/ga/pl> head file1.txt file2.txt
==> file1.txt <==
foo1
foo2
...
bar1
bar2
...

==> file2.txt <==
date1|foo1|number1
date2|foo2|number2
date3|foo3|number3
...
date1|bar1|number1
date2|bar2|number2
date3|bar3|number3
%[email protected] * /root/ga/study/pl>

स्क्रिप्ट आउटपुट: स्क्रिप्ट नाम की फ़ाइल में अंतिम आउटपुट का उत्पादन करेगी output_comp

%[email protected] * /root/ga/pl> ./comp.pl  file1.txt file2.txt ; cat output_comp
date1|bar1|number1
date2|bar2|number2
date2|foo2|number2
date1|foo1|number1
%[email protected] * /root/ga/pl>

स्क्रिप्ट:

%[email protected] * /root/ga/pl> cat comp.pl
#!/usr/bin/perl

use strict ;
use warnings ;
use Data::Dumper ;

my ($file1,$file2) = @ARGV ;
my $output = "output_comp" ;
my %hash ;    # This will store main comparison data.
my %tmp ;     # This will store already selected results, to be skipped.
(scalar @ARGV != 2 ? (print "Need 2 files!\n") : ()) ? exit 1 : () ;

# Read all files at once and use their name as the key.
for (@ARGV) {
  open FH, "<$_" or die "Cannot open $_\n" ;
  while  (my $line = <FH>) {chomp $line ;$hash{$_}{$line} = "$line"}
  close FH ;
}

# Now we churn through the data and compare to generate
# the sorted output in the output file.
open FH, ">>$output" or die "Cannot open outfile!\n" ;
foreach my $k1 (keys %{$hash{$file1}}){
  foreach my $k2 (keys %{$hash{$file2}}){
    if ($k1 =~ m/^.+?$k2.+?$/) {
      if (!defined $tmp{"$hash{$file2}{$k2}"}) {
        print FH "$hash{$file2}{$k2}\n" ;
        $tmp{"$hash{$file2}{$k2}"} = 1 ;
      }
    }
  }
}
close FH  ;
%[email protected] * /root/ga/pl>

धन्यवाद।


क्या आप एक कोशिश दे सकते हैं join ? फ़ाइलों को हल किया जाना चाहिए ...

$ cat d.txt
bar1
bar2
foo1
foo2

$ cat e.txt
date1|bar1|number1
date2|bar2|number2
date3|bar3|number3
date1|foo1|number1
date2|foo2|number2
date3|foo3|number3

$ join --nocheck-order -11 -22 -t'|' -o 2.1 2.2 2.3 d.txt e.txt
date1|bar1|number1
date2|bar2|number2
date1|foo1|number1
date2|foo2|number2

छोटा अद्यतन:
ज्वाइन के सामने LC_ALL = C का उपयोग करके, चीजें वास्तव में तेज़ हो जाती हैं जैसा कि Håkon Hågland के बेंचमार्क में देखा जा सकता है

PS1: मुझे संदेह है कि अगर जुड़ने से grep -f से तेज हो सकता है ...


भाषा आदि सेट करने में थोड़ी मदद मिलती है, शायद।

अन्यथा मैं आपके मूल मुद्दे से बचने के लिए एक जादुई समाधान के बारे में नहीं सोच सकता: डेटा संरचित नहीं है, इसलिए आपके पास एक खोज होगी जो फ़ाइल 1 में लाइनों की संख्या से नीचे आती है और फ़ाइल 2 में लाइनों की संख्या से गुणा की जाती है।

एक डेटाबेस में अरब लाइनें डालें, और इसे स्मार्ट तरीके से अनुक्रमित करें, एकमात्र गति है जो मैं सोच सकता हूं। हालांकि, यह इंडेक्स बहुत ही स्मार्ट होगा।

SImple समाधान है: में सब कुछ फिट करने के लिए पर्याप्त मेमोरी है। अन्यथा इससे ज्यादा कुछ नहीं आप इस बारे में कर सकते हैं ...।


यह पर्ल स्क्रिप्ट ( a ) एक रेगेक्स पैटर्न उत्पन्न करता है:

#!/usr/bin/perl

use strict;
use warnings;

use Regexp::Assemble qw( );

chomp( my @ids = <> );
my $ra = Regexp::Assemble->new();
$ra->add(quotemeta($_)) for @ids;
print("^[^|]*\\|(?:" . (re::regexp_pattern($ra->re()))[0] . ")\\|");

यहां बताया गया है कि इसका उपयोग कैसे किया जा सकता है:

$ LC_ALL=C grep -P "$( a file1.txt )" file2.txt
date1|foo1|number1
date2|foo2|number2
date1|bar1|number1
date2|bar2|number2

नोट करें स्क्रिप्ट Regexp का उपयोग करती है :: इकट्ठा करें, इसलिए आपको इसे स्थापित करने की आवश्यकता हो सकती है।

sudo su
cpan Regexp::Assemble

टिप्पणियाँ:

  • BOC1, BOC2, codeforester_orig, gregory1, inian2, inian4 और oliv के समाधान के विपरीत, मेरा समाधान सही ढंग से संभालता है

    file1.txt
    foo1
    
    file2.txt
    date1|foo12|number5
  • मेरा @BOC द्वारा इसी तरह के solution से बेहतर होना चाहिए क्योंकि पैटर्न बैकट्रैकिंग को कम करने के लिए अनुकूलित है। (मेरा भी काम करता है अगर वहाँ तीन से अधिक क्षेत्र हैं file2.txt , जबकि जुड़ा हुआ समाधान विफल हो सकता है।)

  • मुझे नहीं पता कि यह विभाजन + शब्दकोश समाधानों की तुलना कैसे करता है।


यहाँ पर्ल समाधान है जो Inline::C बड़ी फ़ाइल में मिलान वाले फ़ील्ड की खोज को तेज़ करने के लिए उपयोग करता है:

use strict;
use warnings;
use Inline C => './search.c';

my $smallfile = 'file1.txt';
my $bigfile   = 'file2.txt';

open my $fh, '<', $smallfile or die "Can't open $smallfile: $!";
my %word = map { chomp; $_ => 1 } <$fh>;
search( $bigfile, \%word );

search() उप दिनचर्या का उपयोग कर सी शुद्ध में कार्यान्वित किया जाता perlapi छोटे फ़ाइल शब्दकोश में कुंजी को देखने के लिए %words :

search.c :

#include <stdio.h>
#include <sys/stat.h> 
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>


#define BLOCK_SIZE 8192       /* how much to read from file each time */
static char read_buf[BLOCK_SIZE + 1];

/*  reads a block from file, returns -1 on error, 0 on EOF, 
     else returns chars read, pointer to buf, and pointer to end of buf  */
size_t read_block( int fd, char **ret_buf, char **end_buf ) {
    int ret;
    char *buf = read_buf;
    size_t len = BLOCK_SIZE;
    while (len != 0 && (ret = read(fd, buf, len)) != 0) {
        if (ret == -1) {
            if (errno == EINTR)
                continue;
            perror( "read" );
            return ret;
        }
        len -= ret;
        buf += ret;
    }
    *end_buf = buf;
    *ret_buf = read_buf;
    return (size_t) (*end_buf - *ret_buf);
}

/* updates the line buffer with the char pointed to by cur,
   also updates cur
    */
int update_line_buffer( char **cur, char **line, size_t *llen, size_t max_line_len ) {
    if ( *llen > max_line_len ) {
        fprintf( stderr, "Too long line. Maximimum allowed line length is %ld\n",
                 max_line_len );
        return 0;
    }
    **line = **cur;
    (*line)++;
    (*llen)++;
    (*cur)++; 
    return 1;
}


/*    search for first pipe on a line (or next line if this is empty),
    assume line ptr points to beginning of line buffer.
  return 1 on success
  Return 0 if pipe could not be found for some reason, or if 
    line buffer length was exceeded  */
int search_field_start(
    int fd, char **cur, char **end_buf, char **line, size_t *llen, size_t max_line_len
) {
    char *line_start = *line;

    while (1) {
        if ( *cur >= *end_buf ) {
            size_t res = read_block( fd, cur, end_buf );        
            if (res <= 0) return 0;
        }
        if ( **cur == '|' ) break;
        /* Currently we just ignore malformed lines ( lines that do not have a pipe,
           and empty lines in the input */
        if ( **cur == '\n' ) {
            *line = line_start;
            *llen = 0;
            (*cur)++;
        }
        else {
            if (! update_line_buffer( cur, line, llen, max_line_len ) ) return 0;
        }
    }
    return 1;
}

/* assume cur points at starting pipe of field
  return -1 on read error, 
  return 0 if field len was too large for buffer or line buffer length exceed,
  else return 1
  and field, and  length of field
 */
int copy_field(
    int fd, char **cur, char **end_buf, char *field,
    size_t *flen, char **line, size_t *llen, size_t max_field_len, size_t max_line_len
) {
    *flen = 0;
    while( 1 ) {
        if (! update_line_buffer( cur, line, llen, max_line_len ) ) return 0;
        if ( *cur >= *end_buf ) {
            size_t res = read_block( fd, cur, end_buf );        
            if (res <= 0) return -1;
        }
        if ( **cur == '|' ) break;
        if ( *flen > max_field_len ) {
            printf( "Field width too large. Maximum allowed field width: %ld\n",
                    max_field_len );
            return 0;
        }
        *field++ = **cur;
        (*flen)++;
    }
    /* It is really not necessary to null-terminate the field 
       since we return length of field and also field could 
       contain internal null characters as well
    */
    //*field = '\0';
    return 1;
}

/* search to beginning of next line,
  return 0 on error,
  else return 1 */
int search_eol(
    int fd, char **cur, char **end_buf, char **line, size_t *llen, size_t max_line_len)
{
    while (1) {
        if ( *cur >= *end_buf ) {
            size_t res = read_block( fd, cur, end_buf );        
            if (res <= 0) return 0;
        }
        if ( !update_line_buffer( cur, line, llen, max_line_len ) ) return 0;
        if ( *(*cur-1) == '\n' ) {
            break;
        }
    }
    //**line = '\0'; // not necessary
    return 1;
}

#define MAX_FIELD_LEN 80  /* max number of characters allowed in a field  */
#define MAX_LINE_LEN 80   /* max number of characters allowed on a line */

/* 
   Get next field ( i.e. field #2 on a line). Fields are
   separated by pipes '|' in the input file.
   Also get the line of the field.
   Return 0 on error,
   on success: Move internal pointer to beginning of next line
     return 1 and the field.
 */
size_t get_field_and_line_fast(
    int fd, char *field, size_t *flen, char *line, size_t *llen
) {
    static char *cur = NULL;
    static char *end_buf = NULL;

    size_t res;
    if (cur == NULL) {
        res = read_block( fd, &cur, &end_buf );        
        if ( res <= 0 ) return 0;
    }
    *llen = 0;
    if ( !search_field_start( fd, &cur, &end_buf, &line, llen, MAX_LINE_LEN )) return 0;
    if ( (res = copy_field(
        fd, &cur, &end_buf, field, flen, &line, llen, MAX_FIELD_LEN, MAX_LINE_LEN
    ) ) <= 0)
        return 0;
    if ( !search_eol( fd, &cur, &end_buf, &line, llen, MAX_LINE_LEN ) ) return 0;
    return 1;
}

void search( char *filename, SV *href) 
{
    if( !SvROK( href ) || ( SvTYPE( SvRV( href ) ) != SVt_PVHV ) ) {
        croak( "Not a hash reference" );
    }

    int fd = open (filename, O_RDONLY);
    if (fd == -1) {
        croak( "Could not open file '%s'", filename );
    }
    char field[MAX_FIELD_LEN+1];
    char line[MAX_LINE_LEN+1];
    size_t flen, llen;
    HV *hash = (HV *)SvRV( href );
    while ( get_field_and_line_fast( fd, field, &flen, line, &llen ) ) {
        if( hv_exists( hash, field, flen ) )
            fwrite( line, sizeof(char), llen, stdout);
    }
    if (close(fd) == -1)
        croak( "Close failed" );

}

परीक्षणों से संकेत मिलता है कि यह सबसे तेज शुद्ध पर्ल समाधान ( zdim2 मेरे अन्य उत्तर में विधि देखें ) की तुलना में लगभग 3 गुना तेज है।


हालाँकि यह थ्रेड खत्म हो गया है, लेकिन इस पोस्ट में दो फाइलों के बीच सभी grep-alike तरीके इकट्ठे किए गए हैं, क्यों न इस अवतरण विकल्प को, समान (या और भी बेहतर) इनाम जीतने वाले Inian के awk solution में जोड़ा जाए:

awk 'NR==FNR{a[$0]=1;next}a[$2]' patterns.txt FS="|" datafile.txt >matches.txt # For matches restricted on Field2 of datafile

यह Inian awk $2 in hash solution के बराबर है लेकिन यह इस तथ्य के कारण और भी तेज हो सकता है कि हम awk को यह जांचने के लिए न कहें कि क्या पूरे हैश एरे में file2 का $ 2 है - हम सिर्फ यह चेक करते हैं कि क्या [$ 2] का मूल्य है या नहीं।

हैश सरणी बनाने से पहले पैटर्न फ़ाइल एपार्ट को पढ़ते हुए हम एक मान भी देते हैं।

यदि $2 पैटर्न फ़ाइल में पहले डेटाफ़ाइल पाया गया था, तो a[$2] इसका एक मूल्य होगा और इस प्रकार मुद्रित किया जाएगा क्योंकि यह अशक्त नहीं है।

अगर a[$2] डेटाफाइल रिटर्न का कोई मूल्य नहीं है (अशक्त) तो इसका अनुवाद गलत => कोई मुद्रण नहीं है।

डेटाफ़ाइल के तीन क्षेत्रों में से किसी से मेल खाने के लिए एक्सटेंशन:

awk 'NR==FNR{a[$0]=1;next}(a[$1] || a[$2] || a[$3])' patterns.txt FS="|" datafile.txt >matches.txt. #Printed if any of the three fields of datafile match pattern.

दोनों ही मामलों में, LC_ALL = C को awk के सामने लगाने से चीजों को गति मिलती है।

PS1: ऑफकोर्स इस समाधान में सभी awk समाधानों के नुकसान भी हैं। एक पैटर्न मिलान नहीं है। समाधानों के अधिकांश भाग की तरह, दो फाइलों के बीच सीधा / निश्चित मिलान है।

PS2: Håkon Hlandgland की छोटी बेंचमार्क फ़ाइलों का उपयोग करके मेरी खराब मशीन बेंचमार्क में , मुझे तुलना करने पर लगभग 20% बेहतर प्रदर्शन मिलता है awk 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt


एक पर्ल समाधान। [नीचे नोट देखें।]

पहली फ़ाइल के लिए हैश का उपयोग करें। जैसा कि आप बड़ी फ़ाइल लाइन-बाय-लाइन पढ़ते हैं, regex द्वारा फ़ील्ड निकालें (बीच के पहले पैटर्न को पकड़ता है)) (या दूसरा शब्द मिलता है) और प्रिंट करें यदि exists । वे संभवतः थोड़ी गति में भिन्न होते हैं (समय उन्हें)। split चेक // (परिभाषित-या) कि शॉर्ट-सर्किट के लिए regex में defined चेक की आवश्यकता नहीं है।

use warnings;
use strict;

# If 'prog smallfile bigfile' is the preferred use
die "Usage: $0 smallfile bigfile\n"  if @ARGV != 2;
my ($smallfile, $bigfile) = @ARGV;

open my $fh, '<', $smallfile or die "Can't open $smallfile: $!";    
my %word = map { chomp; $_ => 1 } <$fh>;

open    $fh, '<', $bigfile or die "Can't open $bigfile: $!";       
while (<$fh>) 
{
    exists $word{ (/\|([^|]+)/)[0] } && print;  

    # Or
    #exists $word{ (split /\|/)[1] // '' } && print;
}
close $fh;

if शाखा से बचना और शॉर्ट-सर्किट का उपयोग करना तेज है, लेकिन केवल बहुत कम है। अरबों रेखाओं पर ये मोड़ जुड़ते हैं लेकिन फिर से बहुत ज्यादा नहीं होते हैं। उपरोक्त के रूप में सूची के बजाय छोटी फ़ाइल लाइन को लाइन से पढ़ने के लिए यह (या नहीं हो सकता है) थोड़ा तेज हो सकता है, लेकिन यह ध्यान देने योग्य नहीं होना चाहिए।

अपडेट लेखन को STDOUT दो परिचालनों को सहेजता है और मैं बार-बार इसे फ़ाइल लिखने की तुलना में थोड़ा तेज करता हूं। इस तरह का उपयोग अधिकांश यूनिक्स उपकरणों के साथ भी संगत है इसलिए मैंने STDOUT लिखना बदल दिया। अगला, exists परीक्षण की आवश्यकता नहीं है और इसे छोड़ने से एक ऑपरेशन होता है। हालांकि, मुझे लगातार इसके साथ एक बेहतर रनटाइम मिलता है, जबकि यह उद्देश्य को बेहतर तरीके से बताता है। कुल मिलाकर मैं इसे छोड़ रहा हूं। टिप्पणी के लिए ikegami धन्यवाद।

नोट नीचे दिए गए बेंचमार्क द्वारा टिप्पणी किया गया संस्करण दूसरे की तुलना में लगभग 50% तेज है। ये दोनों दिए गए हैं क्योंकि वे अलग - अलग हैं , एक पहला मैच और दूसरा दूसरा क्षेत्र। मैं इसे इस तरह से अधिक सामान्य विकल्प के रूप में रख रहा हूं, क्योंकि यह सवाल उस पर अस्पष्ट है।

कुछ तुलना (बेंचमार्क) [ STDOUT को लिखने के लिए अद्यतन, ऊपर "अपडेट" देखें]

सबसे समाधान के एक रन समय, HåkonHlandgland द्वारा जवाब में एक व्यापक विश्लेषण है। यहाँ एक और उपाय है, ऊपर दिए गए दो समाधानों की बेंचमार्किंग, ओपी का अपना उत्तर, और पोस्ट किया गया fgrep एक, प्रश्न में और कई उत्तरों में तेज़ और उपयोग होने की उम्मीद है।

मैं निम्नलिखित तरीके से परीक्षण डेटा का निर्माण करता हूं। मोटे तौर पर दिखाई गई लंबाई की कुछ पंक्तियों को यादृच्छिक शब्दों के साथ दोनों फाइलों के लिए बनाया गया है, इसलिए दूसरे क्षेत्र में मिलान करने के लिए। फिर मैं इस "बीज" को उन डेटा नमूनों के लिए पैड करता हूं, जो मेल नहीं खाएंगे, इसलिए ओपी द्वारा उद्धृत आकार और मैचों के बीच अनुपातों की नकल करते हैं: 14 k लाइनों के लिए छोटी फ़ाइल में बड़ी फ़ाइल में 1.3M लाइनें हैं, 126K मैचों की उपज है। फिर इन नमूनों को ओपी के रूप में पूर्ण डेटा फ़ाइलों के निर्माण के लिए बार-बार लिखा जाता है, List::Util का उपयोग करते हुए हर बार shuffle List::Util

नीचे दिए गए फ़ाइल आकार के लिए 106_120 मैचों की तुलना में सभी रन नीचे दिए गए हैं (चेक के लिए अलग-अलग), इसलिए मिलान की आवृत्ति काफी करीब है। वे my $res = timethese(60 ...) का उपयोग करके पूर्ण कार्यक्रमों को बुलाकर बेंचमार्क किए जाते हैं। cmpthese($res) को cmpthese($res) का परिणाम है

        Rate regex  cfor split fgrep
regex 1.05/s    --  -23%  -35%  -44%
cfor  1.36/s   30%    --  -16%  -28%
split 1.62/s   54%   19%    --  -14%
fgrep 1.89/s   80%   39%   17%    --

तथ्य यह है कि अनुकूलित सी कार्यक्रम fgrep शीर्ष पर आता है आश्चर्य की बात नहीं है। " स्प्लिट " के पीछे " रेगेक्स " का अंतराल कई बार छोटे मैचों के लिए इंजन शुरू करने के ओवरहेड के कारण हो सकता है। यह विकासशील संस्करण इंजन अनुकूलन को देखते हुए, पर्ल संस्करणों पर भिन्न हो सकता है। मैं @codeforester (" cfor ") के उत्तर को शामिल करता हूं क्योंकि यह सबसे तेज़ होने का दावा किया गया था, और इसके 20% बहुत समान " विभाजन " के पीछे होने की संभावना है क्योंकि यह छोटी अक्षमताओं के कारण बिखरा हुआ है (इस उत्तर के नीचे एक टिप्पणी देखें)।

यह पूरी तरह से अलग नहीं है, जबकि हार्डवेयर और सॉफ्टवेयर और डेटा विवरण में निश्चित रूप से बदलाव हैं। मैंने इसे विभिन्न पर्ल्स और मशीनों पर चलाया, और उल्लेखनीय अंतर यह है कि कुछ मामलों में fgrep वास्तव में तेजी का परिमाण था

बहुत धीमी fgrep की ओपी का अनुभव आश्चर्यजनक है। उनके उद्धृत समय को देखते हुए, ऊपर की तुलना में धीमी गति का क्रम, मुझे लगता है कि "दोष" के लिए एक पुरानी प्रणाली है।

भले ही यह पूरी तरह से I / O आधारित है, लेकिन इसे कई कोर पर डालने से लाभ होता है और मैं एक अच्छे स्पीडअप की अपेक्षा करता हूं, कुछ के कारक तक।

काश, टिप्पणी हटा दी गई (?)। संक्षेप में: एक स्केलर की अनावश्यक उपयोग (लागत), if एक शाखा की, defined , print बजाय print (धीमी!)। 2 बिलियन लाइनों पर दक्षता के लिए ये मामला।


पर्ल कोड के एक छोटे टुकड़े ने समस्या को हल किया। यह लिया गया तरीका है:

  • एक हैश में file1.txt की लाइनों को स्टोर करें
  • file2.txt पढ़ें file2.txt लाइन पर लाइन, पार्स और दूसरी फील्ड निकालें
  • जांच लें कि निकाला गया क्षेत्र हैश में है; यदि ऐसा है, तो लाइन प्रिंट करें

यहाँ कोड है:

#!/usr/bin/perl -w

use strict;
if (scalar(@ARGV) != 2) {
  printf STDERR "Usage: fgrep.pl smallfile bigfile\n";
  exit(2);
}

my ($small_file, $big_file) = ($ARGV[0], $ARGV[1]);
my ($small_fp, $big_fp, %small_hash, $field);

open($small_fp, "<", $small_file) || die "Can't open $small_file: " . $!;
open($big_fp, "<", $big_file)     || die "Can't open $big_file: "   . $!;

# store contents of small file in a hash
while (<$small_fp>) {
  chomp;
  $small_hash{$_} = undef;
}
close($small_fp);

# loop through big file and find matches
while (<$big_fp>) {
  # no need for chomp
  $field = (split(/\|/, $_))[1];
  if (defined($field) && exists($small_hash{$field})) {
    printf("%s", $_);
  }
}

close($big_fp);
exit(0);

मैंने file1.txt में 14K लाइनों और file2.txt में 1.3M लाइनों के साथ उपरोक्त स्क्रिप्ट को चलाया। यह लगभग 13 सेकंड में समाप्त हो गया, जिससे 126K मैचों का निर्माण हुआ। यहाँ उसी के लिए time आउटपुट है:

real    0m11.694s
user    0m11.507s
sys 0m0.174s

मैंने @ Inian का awk कोड चलाया:

awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt

यह पर्ल समाधान की तुलना में धीमा था, क्योंकि यह file2.txt में प्रत्येक पंक्ति के लिए 14K बार लूपिंग कर रहा है - जो वास्तव में महंगा है। यह फ़ाइल2. file2.txt 592K रिकॉर्ड के प्रसंस्करण और 40K मिलान लाइनों के निर्माण के बाद निरस्त हो गया। यहां बताया गया है कि यह कितना लंबा है:

awk: illegal primary in regular expression 24/Nov/2016||592989 at 592989
 input record number 675280, file file2.txt
 source line number 1

real    55m5.539s
user    54m53.080s
sys 0m5.095s

@ इनियन के अन्य जाग समाधान का उपयोग करना, जो लूपिंग समस्या को समाप्त करता है:

time awk -F '|' 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt > awk1.out

real    0m39.966s
user    0m37.916s
sys 0m0.743s

time LC_ALL=C awk -F '|' 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt > awk.out

real    0m41.057s
user    0m38.475s
sys 0m0.904s

awk यहाँ बहुत प्रभावशाली है, यह देखते हुए कि हमें इसे करने के लिए एक पूरा कार्यक्रम नहीं लिखना है।

मैंने @ ओलिव का पायथन कोड भी चलाया। नौकरी को पूरा करने में लगभग 15 घंटे लग गए, और ऐसा लग रहा था कि इसने सही परिणाम दिए हैं। हैश लुकअप का उपयोग करके एक विशाल रेक्सक्स का निर्माण उतना कुशल नहीं है। यहाँ time उत्पादन:

real    895m14.862s
user    806m59.219s
sys 1m12.147s

मैंने parallel उपयोग करने के सुझाव का पालन करने की कोशिश की । हालांकि, यह fgrep: memory exhausted बहुत छोटे ब्लॉक आकारों के साथ, त्रुटि के साथ विफल रहा ।

मुझे जो आश्चर्य हुआ वह fgrep इसके लिए पूरी तरह अनुपयुक्त था। मैंने 22 घंटों के बाद इसका गर्भपात किया और इसने लगभग 100K मैचों का उत्पादन किया। मेरी इच्छा है fgrep कि एक सामग्री को -f file हैश में रखने के लिए बाध्य करने का एक विकल्प हो, जैसे कि पर्ल कोड ने क्या किया।

मैंने join दृष्टिकोण की जाँच नहीं की - मैं फ़ाइलों को छाँटने का अतिरिक्त ओवरहेड नहीं चाहता था। इसके अलावा, fgrep खराब प्रदर्शन को देखते हुए, मुझे नहीं लगता join कि पर्ल कोड की तुलना में बेहतर किया गया होगा।

आपके ध्यान और प्रतिक्रियाओं के लिए सभी को धन्यवाद।


मान्यताओं: 1. आप इस खोज को केवल अपने स्थानीय कार्य केंद्र पर चलाना चाहते हैं। 2. समानांतर खोज का लाभ उठाने के लिए आपके पास कई कोर / सीपीयू हैं।

parallel --pipepart -a file2.txt --block 10M fgrep -F -f file1.txt

संदर्भ के आधार पर कुछ और मोड़: ए। एन। एल। एस। के साथ एनएलएस अक्षम करें (यह पहले से ही एक अन्य जवाब में उल्लेख किया गया है) बी-एम ध्वज के साथ अधिकतम मैच सेट करें।

नोट: मैं अनुमान लगा रहा हूं कि file2 ~ 4GB है और 10M ब्लॉक का आकार ठीक है, लेकिन आपको सबसे तेज़ रन पाने के लिए ब्लॉक आकार को अनुकूलित करने की आवश्यकता हो सकती है।


फ्लेक्स का उपयोग करना :

1: फ्लेक्स प्रोसेसर का निर्माण करें:

$ awk 'NR==1{ printf "%%%%\n\n.*\\|(%s",$0 } 
            { printf "|%s",$0 } 
       END  { print ")\\|.*\\n ECHO;\n.*\\n ;\n%%\n" }' file1.txt > a.fl

2: इसे संकलित करें

$ flex -Ca -F a.fl ; cc -O lex.yy.c -lfl

3: और भागो

$ a.out < file2.txt  > out

संकलन (cc ...) एक धीमी प्रक्रिया है; यह दृष्टिकोण केवल स्थिर file1.txt के मामलों के लिए भुगतान करेगा

(मेरी मशीन में) इस दृष्टिकोण में एक खोज "100 में 10_000_000" परीक्षण चलाने के लिए लिया गया समय 3 गुना अधिक तेज है LC_ALL=C fgrep...






grep