Wie finde ich in PHP dieselben Datensätze in zwei großen Dateien?

Bei zwei Dateien a und b mit x- bzw. y-Datenzeilen (x und y sind beide größer als 1 Milliarde) beträgt die Maschinenspeichergrenze 100 MB Sie? Die Hauptschwierigkeit bei der Lösung dieses Problems besteht darin, dass diese riesigen Daten nicht gleichzeitig in den Speicher eingelesen werden können. Wenn sie nicht gleichzeitig in den Speicher eingelesen werden können, können sie dann mehrfach berücksichtigt werden? Lassen Sie es uns gemeinsam besprechen

Einführung

Gegeben sind zwei Dateien a und b mit x- bzw. y-Datenzeilen, wobei (x, y beide größer als 1 Milliarde sind) die Maschinenspeichergrenze 100 MB beträgt Finden Sie heraus, dass derselbe Datensatz vorhanden ist Kann die Erinnerung gleichzeitig mehrfach berücksichtigt werden? Wenn es möglich ist, wie können wir denselben Wert berechnen, nachdem wir ihn mehrmals gelesen haben?

Wir können das Teilen-und-Herrsche-Denken nutzen, um das Große auf das Kleine zu reduzieren. Wenn die Werte derselben Zeichenfolge nach dem Hashing gleich sind, können wir erwägen, Hash-Modulo zu verwenden, um die Datensätze auf n Dateien zu verteilen. Wie bekomme ich dieses N? PHP verfügt über 100 MB Speicher und das Array kann etwa 1 Million Daten speichern. Wenn man also bedenkt, dass die Datensätze a und b nur 1 Milliarde Zeilen haben, muss n mindestens größer als 200 sein.

• Zu diesem Zeitpunkt gibt es 200 Dateien. Die gleichen Datensätze müssen sich in derselben Datei befinden und jede Datei kann in den Speicher eingelesen werden. Dann können Sie nacheinander dieselben Datensätze in diesen 200 Dateien finden und sie dann in derselben Datei ausgeben. Das Endergebnis sind die gleichen Datensätze in den beiden Dateien a und b.

• Es ist einfach, denselben Datensatz in einer kleinen Datei zu finden. Verwenden Sie einfach jede Zeile von Datensätzen als Schlüssel der Hash-Tabelle und zählen Sie die Anzahl der Vorkommen des Schlüssels >= 2.

• Praktische Bedienung

• 1 Milliarde Dateien sind zu groß. Erreichen Sie einfach den praktischen Zweck.

Die Problemgröße wird reduziert auf: 1 MB Speicherlimit, a und b haben jeweils 100.000 Datensatzzeilen. Das Speicherlimit kann durch PHPs ini_set('memory_limit', '1M'); begrenzt werden.

• Testdatei generieren

Zufallszahlen zum Füllen der Datei generieren:

/**
 * 生成随机数填充文件
 * Author: ClassmateLin
 * Email: classmatelin.site@gmail.com
 * Site: https://www.classmatelin.top
 * @param string $filename 输出文件名
 * @param int $batch 按多少批次生成数据
 * @param int $batchSize 每批数据的大小
 */function generate(string $filename, int $batch=1000, int $batchSize=10000){
    for ($i=0; $i<$batch; $i++) {
        $str = &#39;&#39;;
        for ($j=0; $j<$batchSize; $j++) {
            $str .= rand($batch, $batchSize) . PHP_EOL; // 生成随机数
        }
        file_put_contents($filename, $str, FILE_APPEND);  // 追加模式写入文件
    }}generate(&#39;a.txt&#39;, 10);generate(&#39;b.txt&#39;, 10);

Datei aufteilen

ini_set('memory_limit', '1M');来限制。

生成测试文件

生成随机数用于填充文件:

/**
 * 用hash取模方式将文件分散到n个文件中
 * Author: ClassmateLin
 * Email: classmatelin.site@gmail.com
 * Site: https://www.classmatelin.top
 * @param string $filename 输入文件名
 * @param int $mod 按mod取模
 * @param string $dir 文件输出目录
 */
function spiltFile(string $filename, int $mod=20, string $dir='files')
{
    if (!is_dir($dir)){
        mkdir($dir);
    }

    $fp = fopen($filename, 'r');

    while (!feof($fp)){
        $line = fgets($fp);
        $n = crc32(hash('md5', $line)) % $mod; // hash取模
        $filepath = $dir . '/' . $n . '.txt';  // 文件输出路径
        file_put_contents($filepath, $line, FILE_APPEND); // 追加模式写入文件
    }

    fclose($fp);
}

spiltFile('a.txt');
spiltFile('b.txt');

分割文件

• 将a.txt, b.txt通过hash取模的方式分割到n个文件中.

/**
 * 查找一个文件中相同的记录输出到指定文件中
 * Author: ClassmateLin
 * Email: classmatelin.site@gmail.com
 * Site: https://www.classmatelin.top
 * @param string $inputFilename 输入文件路径
 * @param string $outputFilename 输出文件路径
 */
function search(string $inputFilename, $outputFilename='output.txt')
{
    $table = [];
    $fp = fopen($inputFilename, 'r');

    while (!feof($fp))
    {
        $line = fgets($fp);
        !isset($table[$line]) ? $table[$line] = 1 : $table[$line]++; // 未设置的值设1，否则自增
    }

    fclose($fp);

    foreach ($table as $line => $count)
    {
        if ($count >= 2){ // 出现大于2次的则是相同的记录，输出到指定文件中
            file_put_contents($outputFilename, $line, FILE_APPEND);
        }
    }
}

执行splitFile函数, 得到如下图filesÄndern Sie a.txt , b.txt wird durch Hash-Modul in n Dateien aufgeteilt.

/**
 * 从给定目录下文件中分别找出相同记录输出到指定文件中
 * Author: ClassmateLin
 * Email: classmatelin.site@gmail.com
 * Site: https://www.classmatelin.top
 * @param string $dirs 指定目录
 * @param string $outputFilename 输出文件路径
 */
function searchAll($dirs='files', $outputFilename='output.txt')
{
    $files = scandir($dirs);

    foreach ($files as $file)
    {
        $filepath = $dirs . '/' . $file;
        if (is_file($filepath)){
            search($filepath, $outputFilename);
        }
    }
}

Führen Sie die Funktion splitFile aus und rufen Sie das Verzeichnis files ab, wie unten gezeigt von 20 Dateien.

Duplikate Datensätze finden

• Jetzt müssen wir dieselben Datensätze in 20 Dateien finden. Tatsächlich müssen wir dieselben Datensätze in einer Datei finden und 20 Mal arbeiten.

• Finden Sie die gleichen Datensätze in einer Datei:

  Nach dem Login kopieren

• Finden Sie die gleichen Datensätze in allen Dateien:

  rrreee

Das Platzproblem bei der Verarbeitung großer Dateien wurde bisher gelöst. Wie geht man also mit der Zeit um? Problem? Eine einzelne Maschine kann durch die Nutzung der Multi-Core-Verarbeitung der CPU, wenn nicht ausreichend, von mehreren Servern verarbeitet werden.

Vollständiger Coderrreee

Empfohlenes Lernen: „🎜PHP-Video-Tutorial🎜“🎜

Das obige ist der detaillierte Inhalt vonWie finde ich in PHP dieselben Datensätze in zwei großen Dateien?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!