Masalah Gabungan Luaran - Panduan Lengkap untuk Gophers

Masalah pengisihan luaran adalah topik yang terkenal dalam kursus sains komputer dan sering digunakan sebagai alat pengajaran. Walau bagaimanapun, jarang untuk bertemu seseorang yang sebenarnya telah melaksanakan penyelesaian kepada masalah ini dalam kod untuk senario teknikal tertentu, apatah lagi menangani pengoptimuman yang diperlukan. Menghadapi cabaran ini semasa hackathon memberi inspirasi kepada saya untuk menulis artikel ini.

Jadi, inilah tugas hackathon:

Anda mempunyai fail teks ringkas dengan alamat IPv4. Satu baris ialah satu alamat, baris demi baris:

145.67.23.4
8.34.5.23
89.54.3.124
89.54.3.124
3.45.71.5
... 

Saiz fail tidak terhad dan boleh memuatkan puluhan dan ratusan gigabait.

Anda harus mengira bilangan alamat unik dalam fail ini menggunakan memori dan masa sesedikit mungkin. Terdapat algoritma "naif" untuk menyelesaikan masalah ini (baca baris demi baris, letakkan baris ke dalam HashSet). Lebih baik jika pelaksanaan anda lebih rumit dan lebih pantas daripada algoritma naif ini.

Fail 120GB dengan 8 bilion baris telah diserahkan untuk penghuraian.

Tiada keperluan khusus mengenai kelajuan pelaksanaan program. Walau bagaimanapun, selepas menyemak maklumat yang tersedia mengenai topik dalam talian dengan pantas, saya membuat kesimpulan bahawa masa pelaksanaan yang boleh diterima untuk perkakasan standard (seperti PC rumah) ialah kira-kira satu jam atau kurang.

Atas sebab yang jelas, fail tidak boleh dibaca dan diproses secara keseluruhan melainkan sistem mempunyai sekurang-kurangnya 128GB memori yang tersedia. Tetapi adakah bekerja dengan ketulan dan penggabungan tidak dapat dielakkan?

Jika anda tidak selesa melaksanakan gabungan luaran, saya cadangkan anda mula-mula membiasakan diri dengan penyelesaian alternatif yang boleh diterima, walaupun jauh daripada optimum.

Idea

• Buat peta bit 2^32 bit. Ini ialah tatasusunan uint64, kerana uint64 mengandungi 64 bit.

• Untuk setiap IP:

1. Hilangkan alamat rentetan kepada empat oktet: A.B.C.D.
2. Terjemahkannya ke dalam nombor ipNum = (A << 24) | (B << 16) | (C << 8) | D.
3. Tetapkan bit yang sepadan dalam peta bit.

• 1. Selepas membaca semua alamat, jalankan peta bit dan kira bilangan bit yang ditetapkan.

Kebaikan:
Pengesanan keunikan yang sangat pantas: menetapkan bit O(1), tidak perlu menyemak, tetapkan sahaja.

Tiada overhed untuk pencincangan, pengisihan, dsb.
Keburukan:
Penggunaan memori yang besar (512 MB untuk ruang IPv4 penuh, tanpa mengambil kira overhed).

Jika fail itu besar, tetapi lebih kecil daripada ruang IPv4 penuh, ini masih boleh menguntungkan dari segi masa, tetapi tidak selalunya munasabah dari segi ingatan.

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
    "math/bits"
)

//  Parse IP address "A.B.C.D"  => uint32 number
func ipToUint32(ipStr string) (uint32, error) {
    parts := strings.Split(ipStr, ".")
    if len(parts) != 4 {
        return 0, fmt.Errorf("invalid IP format")
    }

    var ipNum uint32
    for i := 0; i < 4; i++ {
        val, err := strconv.Atoi(parts[i])
        if err != nil || val < 0 || val > 255 {
            return 0, fmt.Errorf("invalid IP octet: %v", parts[i])
        }
        ipNum = (ipNum << 8) | uint32(val)
    }

    return ipNum, nil
}


func popcount64(x uint64) int {
    return bits.OnesCount64(x)
}

func main() {
    filePath := "ips.txt"

    file, err := os.Open(filePath)
    if err != nil {
        fmt.Printf("Error opening file: %v\n", err)
        return
    }
    defer file.Close()

    // IPv4 space size: 2^32 = 4,294,967,296
    // We need 2^32 bits, that is (2^32)/64 64-bit words
    totalBits := uint64(1) << 32       // 2^32
    arraySize := totalBits / 64        //how many uint64 do we need
    bitset := make([]uint64, arraySize)

    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        ipStr := scanner.Text()
        ipNum, err := ipToUint32(ipStr)
        if err != nil {
            fmt.Printf("Incorrect IP: %s\n", ipStr)
            continue
        }

        idx := ipNum / 64
        bit := ipNum % 64
        mask := uint64(1) << bit
        // Setting the bit
        bitset[idx] |= mask
    }

    if err := scanner.Err(); err != nil {
        fmt.Printf("Error reading file: %v\n", err)
        return
    }

    count := 0
    for _, val := range bitset {
        count += bits.OnesCount64(val)
    }

    fmt.Printf("Number of unique IP addresses: %d\n", count)
}

Pendekatan ini mudah dan boleh dipercayai, menjadikannya pilihan yang berdaya maju apabila tiada alternatif tersedia. Walau bagaimanapun, dalam persekitaran pengeluaran—terutamanya apabila menyasarkan untuk mencapai prestasi optimum—adalah penting untuk membangunkan penyelesaian yang lebih cekap.

Oleh itu, pendekatan kami melibatkan pengisihan, pengisihan gabungan dalaman dan penyahduaan.

Prinsip Keselarian dalam Isih Luaran

1. Membaca dan mengubah potongan:

Fail dibahagikan kepada bahagian yang agak kecil (ketulan), katakan beberapa ratus megabait atau beberapa gigabait. Untuk setiap ketul:

• Groutine (atau kumpulan goroutin) dilancarkan, yang membaca bongkahan, menghuraikan alamat IP kepada nombor dan menyimpannya dalam tatasusunan sementara dalam ingatan.

• Kemudian tatasusunan ini diisih (contohnya, dengan isihan standard.Slice), dan hasilnya, selepas mengalih keluar pendua, ditulis pada fail sementara.

Memandangkan setiap bahagian boleh diproses secara bebas, anda boleh menjalankan beberapa pengendali sedemikian secara selari, jika anda mempunyai beberapa teras CPU dan lebar jalur cakera yang mencukupi. Ini akan membolehkan anda menggunakan sumber dengan seefisien mungkin.

1. Gabungkan ketulan yang diisih (langkah gabung):

Setelah semua bahagian diisih dan ditulis ke fail sementara, anda perlu menggabungkan senarai diisih ini ke dalam satu strim diisih, mengalih keluar pendua:

• Sama seperti proses pengisihan luaran, anda boleh menyelarikan cantuman dengan membahagikan berbilang fail sementara kepada kumpulan, menggabungkannya secara selari dan mengurangkan bilangan fail secara beransur-ansur.

• Ini meninggalkan satu strim keluaran yang diisih dan dinyahduplikasi, yang mana anda boleh mengira jumlah bilangan IP unik.

Kelebihan selari:

• Penggunaan berbilang teras CPU:
  Pengisihan berbenang tunggal bagi tatasusunan yang sangat besar boleh menjadi perlahan, tetapi jika anda mempunyai pemproses berbilang teras, anda boleh mengisih berbilang ketulan secara selari, mempercepatkan proses beberapa kali.

• Pengimbangan beban:

Jika saiz ketulan dipilih dengan bijak, setiap ketulan boleh diproses dalam masa yang lebih kurang sama. Jika sesetengah bahagian lebih besar/lebih kecil atau lebih kompleks, anda boleh mengedarkan pemprosesannya secara dinamik merentas gorouti yang berbeza.

• Pengoptimuman IO:

Persejajaran membolehkan satu bahagian dibaca manakala satu lagi sedang diisih atau ditulis, mengurangkan masa terbiar.

Bottom Line

Pengisihan luaran secara semula jadi meminjamkan dirinya kepada penyejajaran melalui pengisihan fail. Pendekatan ini membolehkan penggunaan pemproses berbilang teras dengan cekap dan meminimumkan kesesakan IO, menghasilkan pengisihan dan penyahduplikasian yang jauh lebih pantas berbanding pendekatan berbenang tunggal. Dengan mengagihkan beban kerja dengan berkesan, anda boleh mencapai prestasi tinggi walaupun semasa berurusan dengan set data yang besar.

Pertimbangan penting:

Semasa membaca fail baris demi baris, kita juga boleh mengira jumlah baris. Semasa proses, kami melakukan penyahduplikasian dalam dua peringkat: pertama semasa chunking dan kemudian semasa penggabungan. Akibatnya, tidak perlu mengira baris dalam fail output akhir. Sebaliknya, jumlah bilangan baris unik boleh dikira sebagai:

finalCount := totalLines - (DeletedInChunks DeletedInMerge)

Pendekatan ini mengelakkan operasi berlebihan dan menjadikan pengiraan lebih cekap dengan menjejaki pemadaman semasa setiap peringkat penyahduplikasian. Ini menjimatkan minit pelayan kami.

Tiada lagi perkara:

Memandangkan sebarang keuntungan prestasi kecil penting pada jumlah data yang besar, saya cadangkan menggunakan analog rentetan dipercepatkan yang ditulis sendiri. Slice()

145.67.23.4
8.34.5.23
89.54.3.124
89.54.3.124
3.45.71.5
... 

Selain itu, templat pekerja telah diterima pakai untuk mengurus pemprosesan selari, dengan bilangan utas boleh dikonfigurasikan. Secara lalai, bilangan utas ditetapkan kepada masa jalan.NumCPU(), membenarkan atur cara menggunakan semua teras CPU yang tersedia dengan cekap. Pendekatan ini memastikan penggunaan sumber yang optimum di samping menyediakan fleksibiliti untuk melaraskan bilangan utas berdasarkan keperluan khusus atau had persekitaran.

Nota Penting: Apabila menggunakan multithreading, adalah penting untuk melindungi data yang dikongsi untuk mengelakkan keadaan perlumbaan dan memastikan ketepatan program. Ini boleh dicapai dengan menggunakan mekanisme penyegerakan seperti mutex, saluran (dalam Go) atau teknik selamat serentak lain, bergantung pada keperluan khusus pelaksanaan anda.

Ringkasan setakat ini

Pelaksanaan idea-idea ini menghasilkan kod yang, apabila dilaksanakan pada pemproses Ryzen 7700 yang dipasangkan dengan SSD M.2, menyelesaikan tugasan dalam kira-kira 40 minit.

Mempertimbangkan pemampatan.

Pertimbangan seterusnya, berdasarkan volum data dan oleh itu kehadiran operasi cakera yang ketara, ialah penggunaan pemampatan. Algoritma Brotli dipilih untuk pemampatan. Nisbah mampatan yang tinggi dan penyahmampatan yang cekap menjadikannya pilihan yang sesuai untuk mengurangkan overhed IO cakera sambil mengekalkan prestasi yang baik semasa penyimpanan dan pemprosesan pertengahan.

Berikut ialah contoh chunking dengan Brotli:

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
    "math/bits"
)

//  Parse IP address "A.B.C.D"  => uint32 number
func ipToUint32(ipStr string) (uint32, error) {
    parts := strings.Split(ipStr, ".")
    if len(parts) != 4 {
        return 0, fmt.Errorf("invalid IP format")
    }

    var ipNum uint32
    for i := 0; i < 4; i++ {
        val, err := strconv.Atoi(parts[i])
        if err != nil || val < 0 || val > 255 {
            return 0, fmt.Errorf("invalid IP octet: %v", parts[i])
        }
        ipNum = (ipNum << 8) | uint32(val)
    }

    return ipNum, nil
}


func popcount64(x uint64) int {
    return bits.OnesCount64(x)
}

func main() {
    filePath := "ips.txt"

    file, err := os.Open(filePath)
    if err != nil {
        fmt.Printf("Error opening file: %v\n", err)
        return
    }
    defer file.Close()

    // IPv4 space size: 2^32 = 4,294,967,296
    // We need 2^32 bits, that is (2^32)/64 64-bit words
    totalBits := uint64(1) << 32       // 2^32
    arraySize := totalBits / 64        //how many uint64 do we need
    bitset := make([]uint64, arraySize)

    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        ipStr := scanner.Text()
        ipNum, err := ipToUint32(ipStr)
        if err != nil {
            fmt.Printf("Incorrect IP: %s\n", ipStr)
            continue
        }

        idx := ipNum / 64
        bit := ipNum % 64
        mask := uint64(1) << bit
        // Setting the bit
        bitset[idx] |= mask
    }

    if err := scanner.Err(); err != nil {
        fmt.Printf("Error reading file: %v\n", err)
        return
    }

    count := 0
    for _, val := range bitset {
        count += bits.OnesCount64(val)
    }

    fmt.Printf("Number of unique IP addresses: %d\n", count)
}

Keputusan Penggunaan Mampatan

Keberkesanan pemampatan boleh dipertikaikan dan sangat bergantung pada keadaan di mana penyelesaian digunakan. Mampatan tinggi mengurangkan penggunaan ruang cakera tetapi secara berkadar meningkatkan masa pelaksanaan keseluruhan. Pada HDD yang perlahan, pemampatan boleh memberikan peningkatan kelajuan yang ketara, kerana cakera I/O menjadi halangan. Sebaliknya, pada SSD yang pantas, pemampatan boleh menyebabkan masa pelaksanaan yang lebih perlahan.

Dalam ujian yang dijalankan pada sistem dengan SSD M.2, pemampatan tidak menunjukkan peningkatan prestasi. Akibatnya, saya akhirnya memutuskan untuk melupakannya. Walau bagaimanapun, jika anda sanggup mengambil risiko menambah kerumitan pada kod anda dan berpotensi mengurangkan kebolehbacaannya, anda boleh melaksanakan pemampatan sebagai ciri pilihan, dikawal oleh bendera boleh dikonfigurasikan.

Apa yang perlu dilakukan seterusnya

Dalam mengejar pengoptimuman selanjutnya, kami mengalihkan perhatian kami kepada transformasi binari penyelesaian kami. Setelah alamat IP berasaskan teks ditukar kepada cincang berangka, semua operasi seterusnya boleh dilakukan dalam format binari.

145.67.23.4
8.34.5.23
89.54.3.124
89.54.3.124
3.45.71.5
... 

Kelebihan Format Binari

• Kekompakan:

Setiap nombor menduduki saiz tetap (cth., uint32 = 4 bait).
Untuk 1 juta alamat IP, saiz fail hanya ~4 MB.

• Pemprosesan Pantas:

Tidak perlu menghuraikan rentetan, yang mempercepatkan operasi membaca dan menulis.

• Keserasian Merentas Platform:

Dengan menggunakan susunan bait yang konsisten (sama ada LittleEndian atau BigEndian), fail boleh dibaca merentas platform yang berbeza.

Kesimpulan
Menyimpan data dalam format binari adalah kaedah yang lebih cekap untuk menulis dan membaca nombor. Untuk pengoptimuman lengkap, tukar kedua-dua proses penulisan dan pembacaan data kepada format binari. Gunakan binari.Tulis untuk menulis dan binari.Baca untuk membaca.

Begini rupa fungsi processChunk berfungsi dengan format binari:

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
    "math/bits"
)

//  Parse IP address "A.B.C.D"  => uint32 number
func ipToUint32(ipStr string) (uint32, error) {
    parts := strings.Split(ipStr, ".")
    if len(parts) != 4 {
        return 0, fmt.Errorf("invalid IP format")
    }

    var ipNum uint32
    for i := 0; i < 4; i++ {
        val, err := strconv.Atoi(parts[i])
        if err != nil || val < 0 || val > 255 {
            return 0, fmt.Errorf("invalid IP octet: %v", parts[i])
        }
        ipNum = (ipNum << 8) | uint32(val)
    }

    return ipNum, nil
}


func popcount64(x uint64) int {
    return bits.OnesCount64(x)
}

func main() {
    filePath := "ips.txt"

    file, err := os.Open(filePath)
    if err != nil {
        fmt.Printf("Error opening file: %v\n", err)
        return
    }
    defer file.Close()

    // IPv4 space size: 2^32 = 4,294,967,296
    // We need 2^32 bits, that is (2^32)/64 64-bit words
    totalBits := uint64(1) << 32       // 2^32
    arraySize := totalBits / 64        //how many uint64 do we need
    bitset := make([]uint64, arraySize)

    scanner := bufio.NewScanner(file)
    for scanner.Scan() {
        ipStr := scanner.Text()
        ipNum, err := ipToUint32(ipStr)
        if err != nil {
            fmt.Printf("Incorrect IP: %s\n", ipStr)
            continue
        }

        idx := ipNum / 64
        bit := ipNum % 64
        mask := uint64(1) << bit
        // Setting the bit
        bitset[idx] |= mask
    }

    if err := scanner.Err(); err != nil {
        fmt.Printf("Error reading file: %v\n", err)
        return
    }

    count := 0
    for _, val := range bitset {
        count += bits.OnesCount64(val)
    }

    fmt.Printf("Number of unique IP addresses: %d\n", count)
}





  
  
  WTF?! Ia menjadi lebih perlahan!!


Dalam format binari ia menjadi lebih perlahan untuk berfungsi. Fail dengan 100 juta baris (alamat IP) diproses dalam bentuk binari dalam 4.5 minit, berbanding 25 saat dalam teks. Dengan saiz ketulan dan bilangan pekerja yang sama. Kenapa?

Bekerja dengan Format Binari Mungkin Lebih Lambat daripada Format Teks

Menggunakan format binari kadangkala boleh menjadi lebih perlahan daripada format teks disebabkan oleh kekhususan cara binari.Baca dan binari.Tulis beroperasi, serta potensi ketidakcekapan dalam pelaksanaannya. Berikut ialah sebab utama mengapa ini mungkin berlaku:

Operasi I/O


Format Teks:


Berfungsi dengan blok data yang lebih besar menggunakan bufio.Scanner, yang dioptimumkan untuk membaca baris.

Membaca keseluruhan baris dan menghuraikannya, yang boleh menjadi lebih cekap untuk operasi penukaran kecil.


Format Perduaan:


perduaan.Baca membaca 4 bait pada satu masa, menghasilkan operasi I/O kecil yang lebih kerap.

Panggilan kerap ke binari. Baca peningkatan overhed daripada bertukar antara pengguna dan ruang sistem.

Penyelesaian: Gunakan penimbal untuk membaca berbilang nombor serentak.



func fastSplit(s string) []string {
    n := 1
    c := DelimiterByte

    for i := 0; i < len(s); i++ {
        if s[i] == c {
            n++
        }
    }

    out := make([]string, n)
    count := 0
    begin := 0
    length := len(s) - 1

    for i := 0; i <= length; i++ {
        if s[i] == c {
            out[count] = s[begin:i]
            count++
            begin = i + 1
        }
    }
    out[count] = s[begin : length+1]

    return out
}




Mengapa Penimbalan Meningkatkan Prestasi?

Kurang Operasi I/O:

Daripada menulis setiap nombor terus ke cakera, data terkumpul dalam penimbal dan ditulis dalam blok yang lebih besar.
Penurunan Overhed:


Setiap operasi tulis cakera dikenakan overhed disebabkan penukaran konteks antara proses dan sistem pengendalian. Penimbalan mengurangkan bilangan panggilan sedemikian.

Kami juga membentangkan kod untuk cantuman berbilang fasa binari:



145.67.23.4
8.34.5.23
89.54.3.124
89.54.3.124
3.45.71.5
... 




Hasilnya hebat: 14 min untuk fail 110Gb dengan 8 bilion talian!



Itu keputusan yang cemerlang! Memproses fail 110 GB dengan 8 bilion baris dalam 14 minit sememangnya mengagumkan. Ia menunjukkan kuasa:


I/O Tertimbal:


Dengan memproses sebahagian besar data dalam ingatan dan bukannya baris demi baris atau nilai demi nilai, anda mengurangkan secara drastik bilangan operasi I/O, yang selalunya menjadi halangan.


Pemprosesan Binari Dioptimumkan:


Bertukar kepada membaca dan menulis binari meminimumkan penghuraian overhed, mengurangkan saiz data perantaraan dan meningkatkan kecekapan memori.


Deduplikasi Cekap:


Menggunakan algoritma cekap memori untuk penyahduplikasian dan pengisihan memastikan kitaran CPU digunakan dengan berkesan.


Paralelisme:


Memanfaatkan goroutin dan saluran untuk menyelaraskan beban kerja merentas pekerja mengimbangi penggunaan CPU dan cakera.


  
  
  Kesimpulan


Akhir sekali, berikut ialah kod lengkap untuk penyelesaian akhir. Jangan ragu untuk menggunakannya dan menyesuaikannya dengan keperluan anda!

Penyelesaian gabungan luaran untuk Gophers

Semoga berjaya!


          

            
        
Atas ialah kandungan terperinci Masalah Gabungan Luaran - Panduan Lengkap untuk Gophers. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!