Node.jsで大きなファイルをソートして比較する

Question

各行にUUIDを持つ2つのファイルがあります。各ファイルには数十万行があります（データベースダンプから生成されます）。これらのファイルはソートされ、差異が見つかる（追加/削除）必要があります。これは、いくつかの* 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

：

は、これはまさにあなたのユースケースに合わせているようです。さらに高速（

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

改行上のファイルや分割をロードする「ダム」メソッドを使用している：私たちは、この出力（2011 Macbook Airは）を与える

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)) 
    }) 

：これが私たちの最初のテストコードです〜1.2秒）、メモリオーバヘッドが大幅に高くなります（〜2倍）。

Setを使用したソリューションでも、ソート手順をスキップできるという利点があります。これは、元の質問に記載されている* nixツールよりも高速です。