Сортировка и разметка больших файлов с помощью Node.js

Question

У меня есть два файла с UUID на каждой строке. Каждый файл имеет несколько сотен тысяч строк (они создаются из дампов базы данных). Эти файлы должны быть отсортированы и обнаружены различия (добавление/удаление). Это легко сделать с помощью нескольких * NIX инструментов и занимает всего несколько секунд:

$ sort file-a.txt > file-a-sorted.txt 
$ sort file-b.txt > file-b-sorted.txt 
$ diff file-a-sorted.txt file-b-sorted.txt 

Однако я хотел бы добавить эту функцию в CLI мы (построен на узле), который предназначен для мультиплатформенной использования , Таким образом, нереста подпроцесса и делегирование этих инструментов не является вариантом.

Будучи «немым» и загружая каждый файл в память, разделение на строки новой строки и вызывание .sort() на результирующий массив работает на удивление хорошо (это быстро, хотя и с использованием довольно большой памяти ...), но обнаружение различий оказывается довольно сложным ,

Я уверен, что ответ лежит где-то в области потоков, но мне не хватает опыта, манипулируя ими, поэтому я не уверен, с чего начать.

Что такое эффективные методы для загрузки, сортировки и различения таких больших файлов с помощью Node.js?

Я не ищу полных решений (хотя, не стесняйтесь!), Только указатели были бы действительно полезны на этом этапе.

Спасибо!

Answer 1

Поскольку у вас уже есть файлы в памяти как отсортированные массивы, выезд difflib.

Это, кажется, соответствует именно ваш случай использования:

>>> difflib.unifiedDiff('one two three four'.split(' '), 
...      'zero one tree four'.split(' '), { 
...      fromfile: 'Original' 
...      tofile: 'Current', 
...      fromfiledate: '2005-01-26 23:30:50', 
...      tofiledate: '2010-04-02 10:20:52', 
...      lineterm: '' 
...      }) 
[ '--- Original\t2005-01-26 23:30:50', 
    '+++ Current\t2010-04-02 10:20:52', 
    '@@ -1,4 +1,4 @@', 
    '+zero', 
    ' one', 
    '-two', 
    '-three', 
    '+tree', 
    ' four' ] 

Answer 2

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

const fs = require('fs') 
const readline = require('readline') 

const memory =() => process.memoryUsage().rss/1048576).toFixed(2) 

const loadFile = (filename, cb) => { 
    // this is more complex that simply calling fs.readFile() but 
    // means we do not have to buffer the whole file in memory 
    return new Promise((resolve, reject) => { 
    const input = fs.createReadStream(filename) 
    const reader = readline.createInterface({ input }) 

    input.on('error', reject) 

    reader.on('line', cb) 
    reader.on('close', resolve) 
    }) 
} 

const start = Date.now() 

const uniqueA = new Set() 
const uniqueB = new Set() 

// when reading the first file add every line to the set 
const handleA = (line) => { 
    uniqueA.add(line) 
} 

// this will leave us with unique lines only 
const handleB = (line) => { 
    if (uniqueA.has(line)) { 
    uniqueA.delete(line) 
    } else { 
    uniqueB.add(line) 
    } 
} 

console.log(`Starting memory: ${memory()}mb`) 

Promise.resolve() 
    .then(() => loadFile('uuids-eu.txt', handleA)) 
    .then(() => { 
    console.log(`${uniqueA.size} items loaded into set`) 
    console.log(`Memory: ${memory()}mb`) 
    }) 
    .then(() => loadFile('uuids-us.txt', handleB)) 
    .then(() => { 
    const end = Date.now() 

    console.log(`Time taken: ${(end - start)/1000}s`) 
    console.log(`Final memory: ${memory()}mb`) 

    console.log('Differences A:', Array.from(uniqueA)) 
    console.log('Differences B:', Array.from(uniqueB)) 
    }) 

Что дает нам этот выход (2011 Macbook Air):

Starting memory: 19.71mb 
678336 items loaded into set 
Memory: 135.95mb 
Time taken: 1.918s 
Final memory: 167.06mb 
Differences A: [ ... ] 
Differences B: [ ... ] 

Использование «немой» метод загрузки файла и разделения на переводы строк даже быстрее (~ 1,2 с), но со значительно большим объемом памяти (~ 2x).

Наше решение с использованием Set также имеет то преимущество, что мы можем пропустить шаг сортировки, делая это быстрее, чем инструменты * nix, изложенные в исходном вопросе.