удалить повторяющиеся строки из файла

Question

У меня есть следующие данные:

number1 
I am writing line1 . 
number2 
First line . 
number3 
I am writing line2. 
number4 
Second line . 
number5 
I am writing line3 . 
number6 
Third line. 
number7 
I am writing line2 . 
number8 
Fourth line . 
number9 
I am writing line5 . 
number10 
Fifth line . 

Теперь я хочу, чтобы удалить повторяющиеся строки из этого текстового файла - наряду с этим я хочу, чтобы удалить 1 предшествующую и 2 последующие строки по дубликат строки. Такой, что после удаления моих данные выглядят следующим образом:

number1 
I am writing line1 . 
number2 
First line . 
number3 
I am writing line2. 
number4 
Second line . 
number5 
I am writing line3 . 
number6 
Third line. 
number9 
I am writing line5 . 
number10 
Fifth line . 

Размер моего файла 60 Гб, и я использую сервер с 64 ГБ оперативной памяти. Я использую следующий код для удаления дубликатов:

fOutput = open('myfile','w') 

table_size = 2**16 
seen = [False]*table_size 
infile = open('test.ttl', 'r') 
while True: 
    inFileLine1=infile.readline() 
    if not inFileLine1: 
     break #EOF 
    inFileLine2=infile.readline() 
    inFileLine3=infile.readline() 
    inFileLine4=infile.readline() 
    h = hash(inFileLine2) % table_size 
    if seen[h]: 
     dup = False 
     with open('test.ttl','r') as f: 
      for line1 in f: 
       if inFileLine2 == line1: 
        dup = True 
        break 
      if not dup: 
       fOutput.write(inFileLine1) 
       fOutput.write(inFileLine2) 
       fOutput.write(inFileLine3) 
       fOutput.write(inFileLine4) 
    else: 
     seen[h] = True 
     fOutput.write(inFileLine1) 
     fOutput.write(inFileLine2) 
     fOutput.write(inFileLine3) 
     fOutput.write(inFileLine4) 

fOutput.close() 

Однако, оказывается, этот код очень медленный. Есть ли способ, с помощью которого я могу повысить эффективность кода, используя распараллеливание, то есть используя все 24 ядра, доступные мне в моей системе, или используя любую другую технику.

Хотя приведенный выше код написан на Python - но я в порядке с эффективными решениями в C++ или Python или Java или с помощью Linux команд

Здесь test.ttl мой входной файл с размером 60GB

Answer 1

Кажется, что ваш код читает каждую строку ровно один раз и записывает каждую строку (которая должна быть записана) также ровно один раз. Таким образом, нет возможности оптимизировать алгоритм в части чтения текста.

Я сильно подозреваю, что ваш код медленный из-за очень плохого использования таблицы хэшей. Ваша хеш-таблица имеет размер 2^16, в то время как ваш файл может содержать около 2^28 строк, предполагая в среднем 240 байт на строку.

Поскольку у вас есть такая большая оперативная память (достаточно, чтобы содержать весь файл), я предлагаю вам изменить хеш-таблицу на размер 2^30. Это должно значительно помочь.

Редактировать: В этом случае вы можете попробовать использовать очень простую функцию Хэша. Например:

long long weight[] = {generate some random numbers}; 
long long Hash(char * s, int length) 
{ 
    long long result = 0; 
    int i = 0, j = 0; 
    while (i < length) 
    { 
     result += s[i] * weight[j ++]; 
     i += j; 
    } 
    return result & ((1 << 30) - 1); // assume that your hash table has size 2^30 
} 

Answer 2

Если повторяющиеся строки довольно часто, то я думаю, что правильный способ решить эту проблему похож на тот, который вы имеете, но вы должны использовать хэш-таблицу, которая может расти по требованию и автоматически обрабатывать столкновений. Попробуйте использовать тип данных Python set для хранения уже достигнутых линий. С set вам не нужно будет подтверждать, что повторяющиеся строки действительно дублируются; если они уже находятся в set, они определенно дублируются. Это будет работать и быть достаточно эффективным. Однако управление памятью Python может быть не очень эффективным, и тип данных set может превысить доступную память, и в этом случае потребуется переосмысление. Попробуй.

Редактировать: ok, поэтому set стал слишком большим.

Для хорошего решения вы хотите избежать повторного повторного чтения входного файла. В вашем исходном решении входной файл снова считывается для каждого возможного дубликата, поэтому, если есть N строк, общее количество прочитанных строк может быть до N^2. Оптимизация (профилирование) и параллелизм не улучшат ее. И из-за массивного размера файла у вас также есть ограничение памяти, которое исключает простые трюки, такие как сохранение всех строк, просмотренных до сих пор в хеш-таблице (например, set).

Вот мое второе предложение. В этом предположении требования к памяти будут масштабироваться, чтобы соответствовать всем имеющимся.Вам потребуется достаточно места на диске, по крайней мере, для одной копии вашего входного файла. Этапы образуют конвейер - вывод с одного шага является входом следующего.

Шаг 1. Я думаю, вы заинтересованы в работе над группами из 4-х строк. Вы хотите сохранить всю группу из 4 человек или ни одного из них. Ваш первый шаг должен состоять в том, чтобы объединить каждую группу из 4 строк в одну строку. Например:

number1 
I am writing line1 . 
number2 
First line . 
number3 
I am writing line2. 
number4 
Second line . 

становится

number1#I am writing line1 .#number2#First line . 
number3#I am writing line2 .#number4#Second line . 

Обратите внимание, что я использовал '#', чтобы отметить, где разрывы строк были. Это важно. Здесь вы можете использовать любой символ, если он не используется ни в каком другом месте вашего входного файла.

Этап 2. Подготовьте номер строки в каждой строке.

1#number1#I am writing line1 .#number2#First line . 
2#number3#I am writing line2 .#number4#Second line . 

Шаг 3. Используйте утилиту Unix sort (или порт Windows). Он уже оптимизирован. Есть даже варианты для сортировки параллельно для дополнительной скорости. Сортировка со следующими параметрами:

sort '-t#' -k3 

Эти sort опции заставляют программу рассматривать только 3-е поле - которое является второй линии в каждой группе.

Этап 4. Теперь сделайте шаг вперед на выходе предыдущего этапа, ищите дубликаты, используя тот факт, что они будут рядом друг с другом. Посмотрите на 3-е поле. Если вы найдете дубликат строки, отбросьте ее.

Этап 5. Реконструировать порядок исходного файла с помощью другого sort:

sort '-t#' -k1 -n 

На этот раз, сортировка использует числовое значение номера строки (первое поле).

Этап 6. Удалите номер строки с начала каждой строки.

Этап 7. Поверните каждый символ «#» обратно в символ новой строки. Работа выполнена.

Хотя это похоже на много шагов, все, кроме шагов 3 и 5, включают только один проход через входной файл, поэтому они будут очень быстрыми. N шагов для N строк. Шаги сортировки (3 и 5) также быстры, потому что программа sort была сильно оптимизирована и использует хороший алгоритм сортировки (не более N log N шагов для N строк).

Answer 3

fOutput = open('myfile','w') 
infile = open('test.ttl', 'r') 

all_line2 = {} 
while True: 
    inFileLine1 = infile.readline() 
    if not inFileLine1: 
     break #EOF 
    inFileLine2 = infile.readline() 
    _ = infile.readline() 
    _ = infile.readline() 
    all_line2[inFileLine2] = False 
infile.seek(0)  
while True: 
    inFileLine1=infile.readline() 
    if not inFileLine1: 
     break #EOF 
    inFileLine2=infile.readline() 
    inFileLine3=infile.readline() 
    inFileLine4=infile.readline() 
    if not all_line2.get(inFileLine2): 
     fOutput.write(inFileLine1) 
     fOutput.write(inFileLine2) 
     fOutput.write(inFileLine3) 
     fOutput.write(inFileLine4) 
     all_line2[inFileLine2] = True 

Answer 4

Посмотрите на java.util.concurrent.ConcurrentHashMap на Java. Он разработан, чтобы хорошо работать при использовании несколькими потоками, которые одновременно получают доступ к карте.

Кроме того, прочитайте файл с использованием Java NIO через фиксированный пул потоков Executor.

Для начала вы можете использовать этот код

import java.io.IOException; 
import java.nio.file.Files; 
import java.nio.file.Paths; 
import java.util.concurrent.ConcurrentHashMap; 
import java.util.concurrent.ExecutorService; 
import java.util.concurrent.Executors; 

public class Main { 
    private static final ConcurrentHashMap map = new ConcurrentHashMap(); 

    public static class Task implements Runnable { 
     private final String line; 

     public Task(String line) { 
      this.line = line; 
     } 

     @Override 
     public void run() { 
      // if (!map.containsKey(line)) // not needed 
       map.put(line, true); 
     } 
    } 

    public static void main(String[] args) throws IOException { 
     ExecutorService service = Executors.newFixedThreadPool(10); 
     String dir_path, file_name; 
     Files.lines(Paths.get(dir_path, file_name)).forEach(l -> service.execute(new Task(l))); 
     service.shutdown(); 
     map.keySet().forEach(System.out::println); 
    } 
} 

Answer 5

Я предпочел бы использовать Java для этого. И учитывая, что размер файла составляет 60 ГБ, Java предоставляет хорошо подходит API для этого имени MappedByteBuffer.

Вы загружаете файл, используя файл канал и отображение канала с использованием вышеуказанного API следующим образом: FileChannel fileChannel = new RandomAccessFile(new File(inputFile), "r").getChannel();

mappedBuffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size());

Это загружает весь файл в память. Для лучшей эффективной работы, отобразить его на куски (грузы 50k байт)

mappedBuffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, 50000);

Теперь вы можете перебрать mappedBuffer и сделать вашу обработку. Дайте знать для любой ясности.

Answer 6

Я хотел бы прочитать файл в последовательности образом. Рассмотрим некоторые факторы, влияющие на производительность и возможные решения:

Язык: голосовать за C/C++.

IO: мы можем использовать карту памяти, которая доступна в Windows и Linux, в Linux это функция mmap(); в основном это отображает содержимое файла на указатель, например. char* data. Скажите, если вы используете Windows и нуждаетесь в коде.

Поиск ключа: Я предлагаю использовать Дерево двоичного поиска, каждый раз, когда мы берем новую пару строк => значение, ключ; нам нужно пройти дерево, чтобы найти ключ. Если он найден, пропустите эту и следующую пару. Если не найдено, вставьте эту пару в дерево в виде нового узла в конечной позиции поиска; а также напишите эту пару в выходной файл. Конечно, поиск принимает O (logN).

Структура данных узла:

struct Node { 
    char* key; 
    unsigned short keyLen; 
    char* value; 
    unsigned short valueLen; 
    Node* leftNode; 
    Node* rightNode; 
} 

Вы можете изменить unsigned short к unsigned char при необходимости. Указатели key и value фактически указывают на определенные позиции блока трюме памяти, data, что никакая новая память не выделяется для хранения ключа и значения.

ищущий может быть дополнительно улучшена с помощью фильтра Блума. Если фильтр отвечает НЕТ (очень быстро), то окончательно ключ не существует в нашем дереве, больше не нужно пересекать дерево. Если ответ «ДА», то обычно проходите дерево. Bloom Filter реализован в Redis и HBase, пожалуйста, взгляните на эти системы с открытым исходным кодом, если это необходимо.