过滤从巨大的.csv文件中的文本，在C

Question

我有一个csv文件中的原始和未经过滤的记录（超过1000000条记录），我想从文件列表中筛选出这些记录（每个文件重量超过282MB;约200多万条记录）。我尝试使用在C的strstr这是我的代码：

while (!feof(rawfh)) //loop to read records from raw file 
{ 
    j=0; //counter 


    while((c = fgetc(rawfh))!='\n' && !feof(rawfh)) //read a line from raw file 
    { 
     line[j] = c; line[j+1] = '\0'; j++; 
    } 
    //function to extract the element in the specified column, in the CSV 
    extractcol(line, relcolraw, entry); 

    printf("\nWorking on : %s", entry); 


    found=0; 
    //read a set of 4000 bytes; this is the target file 
    while(fgets(buffer, 4000, dncfh)!=NULL && !found) 
    { 
     if(strstr(buffer, entry) !=NULL) //compare it 
      found++; 
    } 
    rewind(dncfh); //put the file pointer back to the start 

    // if the record was not found in the target list, write it into another file 
    if(!found) 
     { 
     fprintf(out, "%s,\n", entry); printf(" *** written to filtered ***"); 
     } 
     else 
     { 
     found=0; printf(" *** Found ***"); 
     } 
     //I hope this is the right way to null out a string 
     entry[0] = '\0'; line[0] ='\0'; 

     //just to display a # on the screen, to let the user know that the program 
     //is still alive and running. 
     rawreccntr++; 
     if(rawreccntr>=10) 
     { 
     printf("#"); rawreccntr=0; 
     } 
} 

此程序需要大约7到10秒，平均，来搜索在目标文件（282 MB）一个条目。所以，10 * 1000000 = 10000000秒:(上帝知道要花多少钱，如果我决定在25个文件中搜索。

我正在考虑编写一个程序，而不是去勺子喂解决方案（grep， sed等）哦，不好意思，但是我用的是Windows 8（64位，4GB内存，AMD处理器Radeon 2核心--1000Mhz），我用DevC++（gcc）来编译这个。

请赐教你的想法。提前

谢谢，对不起，如果我听起来很蠢。

---

更新由Ali，从评论中提取关键信息：

我与客户的电话号码和详细地址原始CSV文件。我有CSV格式的目标文件;不要呼叫列表。我想编写一个程序来过滤掉电话号码，这些电话号码在Do No Call List中不存在。电话号码（两个文件）都在第二栏。然而，我不知道任何其他方法。我搜索了Boyer-Moore算法，但是无法在C中实现这一点。任何有关我应该如何去搜索记录的建议？

Answer 1

EDITED

我会建议你在任何Unix/Linux系统的现成工具一试，grep和awk。您可能会发现它们同样快速且易于维护。我还没有看到你的数据格式，但你说的电话号码都在第二列，这样你可以得到的电话号码对自己是这样的：

awk '{print $2}' DontCallFile.csv 

如果您的电话号码在双引号，你可以删除那些像这样：

awk '{print $2}' DontCallFile.csv | tr -d '"' 

然后你可以使用fgrep一样与-f选项，搜索在一个文件中列出的字符串是否存在于第二个文件，如：

fgrep -f file1.csv file2.csv 

或者您可以反转搜索并搜索不存在于另一个文件中的字符串，方法是将-v开关添加到fgrep。

那么，您的最终命令可能最终是这样的：

fgrep -v -f <(awk '{print $2}' DontCallFile.csv | tr -d '"') file2.csv 

，说...搜索，在file2.csv不存在（-v选项）的所有字符串列2文件“DontCallFile .csv”文件。如果您想了解<()中的位，则将其称为进程替换，它基本上会在括号内运行命令的结果中生成一个伪文件。我们需要一个伪文件，因为fgrep -f需要一个文件。

你为什么要使用龟etc（）反正

原来的答复。当然你可以使用函数getline（）是这样的：

while(getline(myfile,line)) 
{ 
... 
} 

你真的读从一开始就整个“目标”的文件在你的主文件每一行？那会杀了你！你为什么要以4,000字节的大小做它？如果你的一个字符串跨越你比较的4,000个字节 - 即前8个字节是在一个4k块中，而最后一个字节是在4k块中？

我想你会在这里得到更好的帮助，如果你花时间来正确地解释你正在做什么 - 也许用awk或grep来做（至少比喻性地），以便我们可以看到你实际上在尝试什么实现。例如，您的描述没有提及您在代码中使用的“目标”文件。

Answer 2

这是需要改进的一个想法...

在下面的代码，什么是在设置line[j+1] = '\0'在每迭代点？

while((c = fgetc(rawfh))!='\n' && !feof(rawfh)) 
{ 
    line[j] = c; line[j+1] = '\0'; j++; 
} 

你还不如做外循环：

while((c = fgetc(rawfh))!='\n' && !feof(rawfh)) 
    line[j++] = c; 
line[j] = '\0'; 

Answer 3

我的建议如下。

1. 把所有不拨打电话号码到一个数组。

2. 对此数组进行排序。

3. 使用二进制搜索来检查给定的电话号码是否在排序中 不要拨打电话号码。

在下面的代码中，我只是硬编码了数字。在您的应用程序中，您将不得不将其替换为相应的代码。

#include <stddef.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

int compare(const void* a, const void* b) { 
    return (strcmp(*(char **)a, *(char **)b)); 
} 

int binary_search(const char** first, const char** last, const char* val) { 
    ptrdiff_t len = last - first; 
    while (len > 0) { 
    ptrdiff_t half = len >> 1; 
    const char** middle = first; 
    middle += half; 
    if (compare(&*middle, &val)) { 
     first = middle; 
     ++first; 
     len = len - half - 1; 
    } 
    else 
     len = half; 
    } 
    return first != last && !compare(&val,&*first); 
} 

int main(int argc, char** argv) { 

    size_t i; 

    /* Read _all_ of your don't call phone numbers into an array. */ 
    /* For the sake of the example, I just hard-coded it. */ 
    char* dont_call[] = { "908-444-555", "800-200-400", "987-654-321" }; 

    /* in your program, change length to the number of dont_call numbers actually read. */ 
    size_t length = sizeof dont_call/sizeof dont_call[0]; 

    qsort(dont_call, length, sizeof(char *), compare); 

    printf("The don\'t call numbers sorted\n"); 

    for (i=0; i<length; ++i) 
    printf("%lu %s\n", i, dont_call[i]); 

    /* For each phone number, check if it is in the sorted dont_call list. */ 
    /* Use binary search to check it. */ 
    char* numbers[] = { "999-000-111", "333-444-555", "987-654-321" }; 

    size_t n = sizeof numbers/sizeof numbers[0]; 

    printf("Now checking if we should call a given number\n"); 

    for (i=0; i<n; ++i) { 

    int should_call = binary_search((const char **)dont_call, (const char **)dont_call+length, numbers[i]); 

    char* as_text = should_call ? "no" : "yes"; 

    printf("Should we call %s? %s\n",numbers[i], as_text); 
    } 

    return 0; 
} 

此打印：

 
    The don't call numbers sorted 
    0 800-200-400 
    1 908-444-555 
    2 987-654-321 
    Now checking if we should call a given number 
    Should we call 999-000-111? yes 
    Should we call 333-444-555? yes 
    Should we call 987-654-321? no 

代码绝对不是完美的，但它足以让你开始。

Answer 4

您可以AWK做到这一点，是这样的：

awk -F, ' 
    FNR==NR {gsub(/"/,"",$2);dcn[$2]++;next} 
    {gsub(/ /,"",$2);if(!dcn[$2])print} 
' DontCallFile.csv x.csv 

，说...领域分隔符是逗号（-F,）。现在读取第一个文件（DontCallFile.csv）并根据FNR==NR后面的大括号中的部分进行处理。使用gsub（全局替换）删除字段2中电话号码周围的双引号。然后递增关联数组中的元素（即散列），如未加引号的字段2索引，然后移至下一条记录。所以基本上，在处理文件“DontCallFile.csv”后，数组dcn []将包含所有不需要调用的数字（dcn = dontcallnumbers）。然后，为第二个文件（“x.csv”）的每一行执行第二组花括号中的代码。这就是说...删除字段2中电话号码周围的所有空格。然后，如果该电话号码不在我们之前构建的阵列dcn []中，请打印该行。

Answer 5

您的算法的问题是复杂性。您的方法是O(n*m)其中n是客户数量，m是do_not_call记录的数量（或您的案例中的文件大小）。您需要降低这种复杂性。 （并且Boyer-Moore算法对Ali没有帮助，它不会提高渐近复杂度，但只能保持不变）。即使是二进制搜索Ali暗示他的answer也不是最好的。这将是O((n+m)*log m)。我们可以做得更好。好的解决方案使用fgrep和awk，正如Mark Setchell在他的回答中所建议的那样。 （我会选择一个使用fgrep，它应该更好地执行我猜测，但它只是猜测）。我可以提供一个类似的解决方案在Perl中，将提供更强大的CSV解析，并应该处理您的数据大小容易在体面的硬件。这种解决方案的复杂性为O(n+m)。

#!/usr/bin/env perl 

use strict; 
use warnings; 
use autodie; 
use Text::CSV_XS; 

use constant PHN_COL_DNC => 1; 
use constant PHN_COL_CUSTOMERS => 1; 

die "Usage: $0 dnc_file [customers]" unless @ARGV>0; 
my $dncfile = shift @ARGV; 

my $csv = Text::CSV_XS->new({eol=>"\n", allow_whitespace=>1, binary=>1}); 
my %dnc; 

open my $dnc, '<', $dncfile; 
while(my $row = $csv->getline($dnc)){ 
    $dnc{$row->[PHN_COL_DNC]} = undef; 
} 
close $dnc; 

while(my $row = $csv->getline(*ARGV)){ 
    $csv->print(*STDOUT, $row) unless exists $dnc{$row->[PHN_COL_CUSTOMERS]}; 
} 

如果它不符合我们期望的性能，你可以倒转至C道路，但我肯定会推荐使用一些好的CSV解析和HashMap库。我会尝试libcsv和khash.h