Каков эффективный способ обработки больших текстовых файлов? - PullRequest
Новая
       2

Каков эффективный способ обработки больших текстовых файлов?

4 голосов
/ 09 декабря 2010

У меня есть два файла:
1- с 1400000 строк или записей --- 14 МБ
2- с 16000000 - 170 МБ

Я хочу найти, если каждая запись или строка вФайл 1 также находится в файле 2 или нет

Я разрабатываю Java-приложение, которое выполняет следующее: Читает файл построчно и передает каждую строку методу, который зацикливается в файле 2

Вотмой код: 

public boolean hasIDin(String bioid) throws Exception {

    BufferedReader br = new BufferedReader(new FileReader("C://AllIDs.txt"));
    long bid = Long.parseLong(bioid);
    String thisLine;
    while((thisLine = br.readLine( )) != null)
    {
         if (Long.parseLong(thisLine) == bid)
            return true;

    }
        return false;
    }

public void getMBD() throws Exception{

     BufferedReader br = new BufferedReader(new FileReader("C://DIDs.txt"));
     OutputStream os = new FileOutputStream("C://MBD.txt");
     PrintWriter pr = new PrintWriter(os);
     String thisLine;
     int count=1;
     while ((thisLine = br.readLine( )) != null){
         String bioid = thisLine;
         System.out.println(count);
         if(! hasIDin(bioid))
                pr.println(bioid);
     count++;
     }
    pr.close();
}

Когда я запускаю, кажется, что потребуется больше 1944.44444444444 часов для завершения, так как обработка каждой строки занимает 5 секунд.Это примерно три месяца!

Есть ли идеи сделать это за гораздо более короткое время?

Заранее спасибо.

Ответы [ 4 ]

5 голосов
/ 09 декабря 2010

Почему бы и нет;

  • читать все строки в файле2 в набор. Установить в порядке, но TLongHashSet будет более эффективным.
  • для каждой строки во втором файле, посмотрите, есть ли она в наборе.

Вот настроенная реализация, которая печатает следующее и использует <64 МБ. </p> 

Generating 1400000 ids to /tmp/DID.txt
Generating 16000000 ids to /tmp/AllIDs.txt
Reading ids in /tmp/DID.txt
Reading ids in /tmp/AllIDs.txt
Took 8794 ms to find 294330 valid ids

код 

public static void main(String... args) throws IOException {
    generateFile("/tmp/DID.txt", 1400000);
    generateFile("/tmp/AllIDs.txt", 16000000);

    long start = System.currentTimeMillis();
    TLongHashSet did = readLongs("/tmp/DID.txt");
    TLongHashSet validIDS = readLongsUnion("/tmp/AllIDs.txt",did);

    long time = System.currentTimeMillis() - start;
    System.out.println("Took "+ time+" ms to find "+ validIDS.size()+" valid ids");
}

private static TLongHashSet readLongs(String filename) throws IOException {
    System.out.println("Reading ids in "+filename);
    BufferedReader br = new BufferedReader(new FileReader(filename), 128*1024);
    TLongHashSet ids = new TLongHashSet();
    for(String line; (line = br.readLine())!=null;)
        ids.add(Long.parseLong(line));
    br.close();
    return ids;
}

private static TLongHashSet readLongsUnion(String filename, TLongHashSet validSet) throws IOException {
    System.out.println("Reading ids in "+filename);
    BufferedReader br = new BufferedReader(new FileReader(filename), 128*1024);
    TLongHashSet ids = new TLongHashSet();
    for(String line; (line = br.readLine())!=null;) {
        long val = Long.parseLong(line);
        if (validSet.contains(val))
            ids.add(val);
    }
    br.close();
    return ids;
}

private static void generateFile(String filename, int number) throws IOException {
    System.out.println("Generating "+number+" ids to "+filename);
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(filename), 128*1024));
    Random rand = new Random();
    for(int i=0;i<number;i++)
        pw.println(rand.nextInt(1<<26));
    pw.close();
}
4 голосов
/ 09 декабря 2010

170Мб + 14Мб это не очень большие файлы. Я предлагаю загрузить самый маленький файл в java.util.Map, проанализировать самый большой файл построчно (запись за записью) и проверить, присутствует ли текущая строка на этой карте.

P.S. Вопрос выглядит как что-то тривиальное с точки зрения RDBMS - может быть, стоит использовать любой?

2 голосов
/ 09 декабря 2010

Вы не можете сделать O (N ^ 2), когда каждая итерация такая длинная, это совершенно неприемлемо.

Если у вас достаточно ОЗУ, вы просто анализируете файл 1, создаете карту всех чисел, затем проанализируйте файл 2 и проверьте свою карту.

Если у вас недостаточно ОЗУ, проанализируйте файл 1, создайте карту и сохраните ее в файл, затем проанализируйте файл 2 и прочитайте карту.Ключ заключается в том, чтобы сделать карту как можно более простой для анализа - сделать ее двоичным форматом, возможно, с двоичным деревом или чем-то таким, что можно быстро пропустить и выполнить поиск.(РЕДАКТИРОВАТЬ: я должен добавить ссылку Майкла Боргвардта «Grace Hash Join», которая показывает еще лучший способ: http://en.wikipedia.org/wiki/Hash_join#Grace_hash_join)

Если есть ограничение на размер ваших файлов, вариант 1 проще реализовать - если тольковы имеете дело с файлами huuuuuuuge (я много говорю о ГБ), вы определенно хотите это сделать.

1 голос
/ 09 декабря 2010

Обычно отображение памяти является наиболее эффективным способом чтения больших файлов. Вам нужно использовать java.nio.MappedByteBuffer и java.io.RandomAccessFile.

Но ваш алгоритм поиска - настоящая проблема. Вам нужно создать какой-нибудь индекс или хеш-таблицу.

...