Beberapa bulan yang lalu, saya akhirnya harus mengakui bahwa saya tidak cukup pintar untuk melewati beberapa tingkat puzzle
Snakebird . Satu-satunya cara untuk mendapatkan kembali harga diri adalah dengan menulis solver. Jadi saya bisa berpura-pura bahwa membuat program untuk memecahkan teka-teki hampir sama dengan memecahkannya sendiri. Kode untuk program C ++ yang dihasilkan tersedia di
Github . Bagian utama dari kode yang dipertimbangkan dalam artikel diimplementasikan di
search.h dan
compress.h . Dalam posting ini, saya terutama akan berbicara tentang mengoptimalkan pencarian pertama, yang akan membutuhkan 50-100 GB memori agar muat dalam 4 GB.
Nanti saya akan menulis posting lain, yang akan menjelaskan spesifik dari permainan. Dalam posting ini, Anda perlu tahu bahwa saya tidak dapat menemukan alternatif yang baik untuk kekerasan, karena tidak ada trik yang biasa. Gim ini memiliki banyak keadaan, karena ada banyak benda yang bergerak atau didorong, dan bentuk beberapa di antaranya penting, yang dapat berubah seiring waktu. Tidak ada heuristik konservatif yang cocok untuk algoritma seperti A * untuk mempersempit ruang pencarian. Grafik pencarian berorientasi dan ditentukan secara implisit, oleh karena itu, pencarian simultan di arah maju dan mundur tidak mungkin. Satu-satunya langkah bisa mengubah keadaan dengan banyak cara yang tidak terkait, jadi tidak ada yang berguna seperti
hashing Zobrist .
Perkiraan kasar menunjukkan bahwa dalam teka-teki terbesar, setelah menghilangkan semua posisi simetris, akan ada sekitar 10 miliar negara. Bahkan setelah mengemas deskripsi status dengan kepadatan maksimum, ukuran status adalah 8-10 byte. Dengan memori 100 GB, tugasnya akan sepele, tetapi tidak untuk mesin rumah saya dengan memori 16 GB. Dan karena Chrome membutuhkannya 12 GB, persediaan memori saya yang sebenarnya mendekati 4 GB. Segala sesuatu yang akan melebihi volume ini harus disimpan ke disk (hard drive lama dan berkarat).
Bagaimana cara memuat 100 GB data dalam 4 GB RAM? Baik a) status perlu diperas 1/20 dari ukuran aslinya, sudah dioptimalkan, atau b) algoritma harus dapat secara efektif menyimpan status ke dan dari disk, atau c) kombinasi dari dua metode di atas, atau d) saya perlu membeli lebih banyak RAM atau sewa mesin virtual yang kuat selama beberapa hari. Saya tidak mempertimbangkan opsi D, karena terlalu membosankan. Opsi A dan B dikeluarkan setelah bukti konsep menggunakan gzip: sebuah fragmen deskripsi keadaan 50 MB dikompresi menjadi hanya 35 MB. Ini sekitar 7 byte per negara, dan memori saya sekitar 0,4 byte per negara. Artinya, opsi B tetap, meskipun pencarian pertama kali tampak agak tidak nyaman untuk penyimpanan pada drive sekunder.
Isi
Ini adalah posting yang cukup panjang, jadi di sini adalah gambaran singkat dari bagian-bagian berikut:
- Breadth-first pencarian breadth-first - apa kata pencarian breadth-first (BFS) biasa, dan mengapa tidak cocok untuk menyimpan bagian dari keadaan ke disk?
- BFS dengan penyortiran dan penggabungan - suatu perubahan dalam algoritma untuk pembuangan data yang berlebihan secara efisien.
- Kompresi - mengurangi jumlah memori yang digunakan seratus kali karena kombinasi kompresi standar dan asli.
- Oh-oh, aku curang! - di bagian pertama saya diam tentang sesuatu: itu tidak cukup bagi kita untuk hanya tahu di mana solusinya, tetapi kita perlu memahami persis bagaimana mencapainya. Di bagian ini, kami memperbarui algoritma dasar sehingga mentransfer cukup data untuk membuat ulang solusi dari kondisi terakhir.
- Sortir + gabungkan dengan beberapa output - menyimpan lebih banyak status sepenuhnya meniadakan manfaat kompresi. Algoritma pengurutan + penggabungan perlu diubah sehingga menyimpan dua set data output: satu, terkompresi dengan baik, digunakan selama pencarian, dan yang lainnya hanya digunakan untuk membuat ulang solusi setelah menemukan yang pertama.
- Swap - Swap di Linux jauh lebih buruk dari yang saya kira.
- Kompresi status baru sebelum penggabungan - hingga sekarang, optimasi memori hanya berfungsi dengan banyak status yang dikunjungi. Tetapi ternyata daftar status yang dihasilkan baru jauh lebih besar daripada yang Anda pikirkan. Bagian ini menunjukkan diagram untuk deskripsi yang lebih efisien dari status baru.
- Menghemat ruang pada status induk - jelajahi trade-off antara menggunakan CPU / memori untuk membuat ulang solusi di akhir.
- Apa yang tidak berhasil atau tidak berhasil - beberapa ide tampak menjanjikan, tetapi sebagai hasilnya mereka harus dibatalkan, sementara yang lain, yang seharusnya menjadi pekerja riset, secara intuitif bagi saya tampaknya tidak pantas dalam kasus ini.
Pencarian “oleh buku teks”
Seperti apa pencarian pertama kali dan mengapa Anda tidak menggunakan disk di dalamnya? Sebelum proyek kecil ini, saya hanya mempertimbangkan opsi untuk kata-kata "dari buku teks," misalnya, seperti:
def bfs(graph, start, end): visited = {start} todo = [start] while todo: node = todo.pop_first() if node == end: return True for kid in adjacent(node): if kid not in visited: visited.add(kid) todo.push_back(kid) return False
Dalam proses membuat calon node baru oleh program, setiap node diperiksa dengan tabel hash dari node yang sudah dikunjungi. Jika sudah ada di tabel hash, maka node diabaikan. Jika tidak, ditambahkan ke antrian dan ke tabel hash. Terkadang dalam implementasi, informasi yang "dikunjungi" dimasukkan dalam node, dan bukan dalam tabel asing; tetapi ini adalah optimasi yang berisiko dan sangat tidak mungkin jika grafik secara implisit ditentukan.
Mengapa menggunakan tabel hash bermasalah? Karena tabel hash cenderung membuat pola akses memori yang sepenuhnya acak. Jika tidak, maka ini adalah fungsi hash yang buruk, dan tabel hash kemungkinan besar akan memiliki kinerja yang buruk karena tabrakan. Pola akses acak ini dapat menyebabkan masalah kinerja, bahkan jika data sesuai dalam memori: akses ke tabel hash besar kemungkinan menyebabkan kehilangan cache dan buffer terjemahan asosiatif (TLBs). Tetapi bagaimana jika sebagian besar data ada di disk, dan bukan di memori? Konsekuensinya akan menjadi bencana besar: sekitar 10 ms per operasi pencarian.
Dengan 10 miliar status unik, hanya mengakses tabel hash akan memakan waktu sekitar empat bulan untuk menunggu disk I / O. Ini tidak cocok untuk kita; tugas tersebut benar-benar perlu dikonversi agar program dapat memproses paket data besar dalam sekali jalan.
BFS dengan penyortiran dan penggabungan
Jika kita ingin mengintegrasikan operasi akses data ke dalam paket sebanyak mungkin, lalu apa yang akan menjadi perkiraan maksimum yang bisa dicapai? Karena program tidak tahu simpul mana yang diproses dalam lapisan kedalaman N + 1 hingga lapisan N selesai diproses, tampak jelas bahwa perlu untuk mendeduplikasi status setidaknya satu kali per kedalaman.
Jika kita bekerja dengan seluruh lapisan pada saat yang sama, kita dapat mengabaikan tabel hash dan menggambarkan set status yang dikunjungi dan baru sebagai beberapa aliran yang diurutkan (misalnya, sebagai aliran file, array, daftar). Kami sepele dapat menemukan set baru yang dikunjungi dengan menggabungkan set aliran dan itu sama sepele untuk menemukan set todo menggunakan perbedaan set.
Dua operasi dengan set dapat digabungkan sehingga mereka bekerja dalam satu lintasan dengan kedua utas. Faktanya, kita melihat ke kedua aliran, memproses elemen yang lebih kecil, dan kemudian bergerak maju sepanjang aliran dari mana elemen tersebut diambil (atau sepanjang kedua aliran jika elemen pada awalnya sama). Dalam kedua kasus, kami menambahkan item ke set yang baru dikunjungi. Kemudian kami bergerak maju di sepanjang aliran negara baru, dan juga menambahkan elemen ke set todo baru:
def bfs(graph, start, end): visited = Stream() todo = Stream() visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return True for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited) return False
Pola akses data sekarang sepenuhnya linier dan dapat diprediksi, tidak ada akses sewenang-wenang di seluruh merger. Oleh karena itu, keterlambatan dalam operasi disk menjadi tidak penting bagi kami, dan satu-satunya hal yang tetap penting adalah bandwidth.
Akan seperti apa kinerja teoretis dengan distribusi data yang disederhanakan di atas 100 level kedalaman, yang masing-masingnya memiliki 100 juta negara? Status rata-rata akan dibaca dan ditulis 50 kali. Ini menghasilkan 10 byte / status * 5 miliar status * 50 = 2,5 TB. Hard drive saya seharusnya dapat membaca dan menulis dengan kecepatan rata-rata 100 MB / s, yaitu, rata-rata I / O akan memakan waktu (2 * 2,5 TB) / (100 MB / s) = ~ 50k / s = ~ 13 jam . Ini adalah beberapa pesanan kurang dari hasil sebelumnya (empat bulan)!
Perlu juga dicatat bahwa model yang disederhanakan ini tidak memperhitungkan ukuran status yang dihasilkan baru. Sebelum langkah penggabungan, mereka harus disimpan dalam memori untuk mengurutkan + deduplikasi. Kami akan membahas ini di bagian di bawah ini.
Kompresi
Dalam pengantar, saya mengatakan bahwa dalam percobaan awal, kompresi keadaan tidak terlihat menjanjikan, dan rasio kompresi hanya 30%. Tetapi setelah melakukan perubahan pada algoritma, status menjadi efisien. Mereka seharusnya lebih mudah dikompres.
Untuk menguji teori ini, saya menggunakan zstd dengan puzzle 14,6 juta state, yang masing-masing state berukuran 8 byte. Setelah disortir, mereka dikompres rata-rata menjadi 1,4 byte per negara. Sepertinya ini langkah maju yang serius. Ini tidak cukup untuk menjalankan seluruh program dalam memori, tetapi dapat mengurangi waktu I / O disk menjadi hanya beberapa jam.
Apakah mungkin untuk entah bagaimana meningkatkan hasil dari algoritma kompresi tujuan umum modern jika kita mengetahui sesuatu tentang struktur data? Anda hampir yakin akan hal itu. Contoh yang baik dari ini adalah format PNG. Secara teoritis, kompresi hanyalah pass Deflate standar. Tetapi alih-alih mengompresi data mentah, gambar pertama-tama dikonversi menggunakan
filter PNG . Filter PNG pada dasarnya adalah rumus untuk memprediksi nilai byte data mentah berdasarkan nilai byte yang sama pada baris sebelumnya dan / atau byte yang sama dari piksel sebelumnya. Misalnya, filter "atas" mengubah setiap byte dengan mengurangi nilai dari baris sebelumnya saat mengompres, dan melakukan operasi yang berlawanan saat membongkar. Mengingat jenis gambar yang digunakan PNG, hasilnya hampir selalu terdiri dari nol atau angka mendekati nol. Deflate dapat mengompres data seperti itu jauh lebih baik daripada data mentah.
Bisakah prinsip ini diterapkan pada catatan negara BFS? Sepertinya ini harusnya mungkin. Seperti halnya PNG, kami memiliki ukuran garis yang konstan, dan kami dapat mengharapkan garis yang berdekatan menjadi sangat mirip. Sampel pertama dengan filter pengurangan / penambahan, diikuti oleh zstd, menyebabkan peningkatan rasio kompresi dengan 40%: 0,87 byte per negara. Operasi penyaringan sepele, oleh karena itu, dari sudut pandang konsumsi CPU, mereka praktis "gratis".
Tidak jelas bagi saya apakah ada perbaikan lain yang bisa dilakukan, atau apakah ini merupakan batas praktis. Dalam data gambar, Anda dapat mengharapkan secara logis bahwa byte yang berdekatan dari garis yang sama akan serupa. Tetapi di negara-negara ini tidak ada hal seperti itu. Namun sebenarnya, filter yang sedikit lebih canggih masih dapat meningkatkan hasil. Pada akhirnya, saya sampai pada sistem ini:
Misalkan kita memiliki baris yang berdekatan R1 = [1, 2, 3, 4] dan R2 = [1, 2, 6, 4]. Saat mengeluarkan R2, kami membandingkan setiap byte dengan byte yang sama dari baris sebelumnya, dan 0 akan menunjukkan kecocokan, dan 1 akan menunjukkan ketidakcocokan: diff = [0, 0, 1, 0]. Kemudian kami melewati bitmap ini, dikodekan sebagai VarInt, diikuti oleh hanya byte yang tidak cocok dengan baris sebelumnya. Dalam contoh ini, kita mendapatkan dua byte 0b00000100 6. Dengan sendirinya, filter ini memampatkan data referensi menjadi 2,2 byte / negara. Tetapi dengan menggabungkan filter + zstd, kami mengurangi ukuran data menjadi 0,42 byte / negara. Atau, dengan kata lain, ini berjumlah 3,36 bit per negara, yang hanya sedikit lebih dari perkiraan perkiraan indikator kami yang diperlukan untuk memastikan bahwa semua data sesuai dalam RAM.
Dalam praktiknya, rasio kompresi meningkat karena set yang diurutkan menjadi lebih padat. Ketika pencarian mencapai titik di mana memori mulai menyebabkan masalah, tingkat kompresi bisa menjadi jauh lebih baik. Masalah terbesar adalah pada akhirnya kita mendapatkan 4,6 miliar negara yang dikunjungi. Setelah pengurutan, status ini menempati 405 MB dan dikompresi sesuai dengan skema yang disajikan di atas. Ini memberi kita
0,7 bit per negara . Pada akhirnya, kompresi dan dekompresi mengambil sekitar 25% dari waktu CPU program, tetapi ini adalah kompromi yang sangat baik untuk mengurangi konsumsi memori hingga seratus kali.
Filter di atas tampaknya agak mahal karena header VarInt di setiap baris. Sepertinya mudah untuk ditingkatkan dengan biaya biaya CPU yang rendah atau sedikit peningkatan kompleksitas. Saya mencoba beberapa opsi berbeda, mentransposisi data dalam urutan kolom, atau menulis topeng bit di blok yang lebih besar, dll. Opsi-opsi ini saja menghasilkan rasio kompresi yang jauh lebih tinggi, tetapi tidak berkinerja baik ketika output filter dikompresi oleh zstd. Dan itu bukan semacam kesalahan zstd, hasil dengan gzip dan bzip2 ternyata serupa. Saya tidak memiliki teori yang sangat cerdik tentang mengapa jenis pengkodean khusus ini ternyata jauh lebih baik dalam kompresi daripada opsi lain.
Misteri lain: tingkat kompresi ternyata jauh lebih baik ketika data diurutkan berdasarkan little-endian, daripada big-endian. Awalnya, saya pikir itu terjadi karena dalam pengurutan little-endian ada lebih banyak nol terkemuka dengan topeng bit dikodekan oleh VarInt. Tetapi perbedaan ini tetap ada bahkan dengan filter yang tidak memiliki ketergantungan seperti itu.
(Ada banyak penelitian tentang mengompresi set bilangan bulat yang disortir, karena mereka adalah blok bangunan dasar mesin pencari. Namun, saya tidak menemukan banyak informasi tentang mengompresi catatan yang diurutkan dengan panjang konstan, dan tidak mau menebak, menyajikan data sebagai nilai integer dengan presisi sewenang-wenang.)
Oh-oh, aku curang!
Anda mungkin memperhatikan bahwa implementasi BFS di atas dalam pseudo-code hanya mengembalikan nilai Boolean - solusinya ditemukan / tidak ditemukan. Ini tidak terlalu berguna. Dalam kebanyakan kasus, kita perlu membuat daftar langkah-langkah yang tepat dari solusi, dan tidak hanya melaporkan ketersediaan solusi.
Pada awalnya tampaknya masalah ini mudah diselesaikan. Alih-alih mengumpulkan set negara, Anda perlu mengumpulkan hubungan negara dengan negara induk. Kemudian, setelah menemukan solusinya, Anda dapat dengan mudah kembali dari daftar solusi orang tua dari awal hingga awal. Untuk solusi berbasis tabel hash, ini akan terlihat seperti ini:
def bfs(graph, start, end): visited = {start: None} todo = [start] while todo: node = todo.pop_first() if node == end: return trace_solution(node, visited) for kid in adjacent(node): if kid not in visited: visited[kid] = node todo.push_back(kid) return None def trace_solution(state, visited): if state is None: return [] return trace_solution(start, visited[state]) + [state]
Sayangnya, ini akan menghancurkan semua manfaat kompresi yang diperoleh di bagian sebelumnya; mereka didasarkan pada asumsi bahwa garis yang berdekatan sangat mirip. Ketika kita hanya melihat negara bagian itu sendiri, ini benar. Tetapi tidak ada alasan untuk percaya bahwa ini akan berlaku untuk keadaan orang tua; sebenarnya, mereka adalah data acak. Kedua, solusi sort + gabungan harus membaca dan menulis semua status yang dilihat pada setiap iterasi. Untuk menyimpan tautan dari status negara / induk, kita harus membaca dan menulis ke disk di setiap iterasi semua data yang terkompresi dengan buruk ini.
Sortir + gabungkan dengan beberapa output
Pada akhirnya, ketika kembali ke solusi, program hanya akan membutuhkan kumpulan negara / negara induk. Oleh karena itu, kita dapat menyimpan dua struktur data secara paralel. Dikunjungi akan terus menjadi set negara yang dikunjungi, seperti yang sebelumnya dihitung ulang selama penggabungan. Orang tua setidaknya adalah daftar pasangan negara bagian / orang tua yang diurutkan yang tidak ditimpa. Setelah setiap operasi penggabungan, pasangan "negara + negara induk" ditambahkan ke orang tua.
def bfs(graph, start, end): parents = Stream() visited = Stream() todo = Stream() parents.add((start, None)) visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return trace_solution(node, parents) for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited, parents) return None
Ini memungkinkan kami untuk mengambil keuntungan dari kedua pendekatan dalam hal runtime dan work set, tetapi membutuhkan lebih banyak ruang penyimpanan sekunder. Selain itu, ternyata di masa depan, karena alasan lain, salinan terpisah dari negara yang dikunjungi akan berguna, dikelompokkan berdasarkan kedalaman.
Tukar
Detail lain diabaikan dalam pseudo-code: tidak ada kode eksplisit untuk disk I / O, tetapi hanya antarmuka Stream abstrak. Streaming dapat berupa aliran file atau array di dalam memori, tetapi kami mengabaikan detail implementasi ini. Sebaliknya, kode pseudo menciptakan pola akses memori yang memungkinkan penggunaan disk secara optimal. Di dunia yang ideal, ini sudah cukup, dan sisanya dapat diambil oleh subsistem memori virtual OS.
Tapi ini tidak terjadi, setidaknya di Linux. Di beberapa titik (sebelum kumpulan data yang bisa dikompres ke ukuran memori), saya menjalankan program dalam waktu sekitar 11 jam, dan data disimpan terutama ke disk. Kemudian saya membuat program menggunakan halaman anonim daripada disimpan dalam file, dan memilih file swap dengan ukuran yang cukup pada drive yang sama. Namun, tiga hari kemudian, program berjalan hanya seperempat jalan, dan masih, seiring waktu, itu menjadi lebih lambat. Menurut perkiraan optimis saya, dia seharusnya menyelesaikan pekerjaan dalam 20 hari.
Saya akan mengklarifikasi - itu kode yang sama dan
pola akses yang persis sama . Satu-satunya hal yang telah berubah adalah bahwa memori itu disimpan bukan sebagai file disk eksplisit, tetapi sebagai swap. Hampir tidak ada bukti yang diperlukan bahwa bertukar sepenuhnya menghancurkan kinerja Linux, sedangkan file I / O biasa tidak. Saya selalu berasumsi bahwa ini disebabkan oleh fakta bahwa program cenderung menganggap RAM sebagai memori akses acak. Tapi ini bukan masalahnya.
Ternyata halaman penyimpanan file dan halaman anonim ditangani secara berbeda oleh subsistem mesin virtual. Mereka disimpan dalam cache LRU yang terpisah dengan kebijakan kedaluwarsa yang berbeda; selain itu, sepertinya mereka memiliki sifat baca / muat baca-depan yang berbeda.
Sekarang saya tahu: bertukar di Linux kemungkinan besar tidak akan bekerja dengan baik bahkan dalam kondisi yang optimal. Jika sebagian ruang alamat cenderung diturunkan untuk beberapa saat ke disk, lebih baik menyimpannya secara manual dalam file daripada mempercayai swap. Saya menyelesaikan ini dengan menerapkan kelas vektor saya sendiri, yang awalnya hanya bekerja di memori, dan setelah melebihi ambang ukuran tertentu, ia beralih ke mmap dalam file terpisah sementara.
Kompresi negara baru sebelum bergabung
Dalam model kinerja yang disederhanakan, kami mengasumsikan bahwa 100 juta kondisi baru akan terjadi pada setiap kedalaman. Ternyata ini tidak terlalu jauh dari kenyataan (dalam teka-teki paling kompleks, maksimum lebih dari 150 juta keadaan baru yang unik pada satu lapisan kedalaman). Tetapi ini tidak diukur; set kerja sebelum penggabungan tidak hanya dikaitkan dengan status unik, tetapi juga dengan semua status yang disimpulkan untuk iterasi ini. Angka ini mencapai 880 juta status keluaran per lapisan kedalaman. Ini 880 juta negara a) perlu diproses dengan pola akses acak untuk menyortir, b) tidak dapat dikompresi secara efektif karena kurangnya penyortiran, c) harus disimpan bersama dengan negara induk. Perangkat kerja ini sekitar 16 GB.
Solusi yang jelas: gunakan semacam penyortiran eksternal. Cukup tulis semua status ke disk, lakukan penyortiran eksternal, deduplikasi, dan kemudian gabungkan seperti biasa. Awalnya saya menggunakan solusi ini, dan meskipun itu paling banyak menghilangkan masalah A, saya tidak bisa mengatasi B dan C.
Pada akhirnya, saya mengambil pendekatan alternatif: Saya mengumpulkan status ke dalam array di memori. Jika array menjadi terlalu besar (misalnya, lebih dari 100 juta elemen), maka itu diurutkan, diduplikasi, dan dikompresi. Ini memberi kami paket run state yang diurutkan, dan tidak ada duplikat di dalam setiap run, tetapi mereka dimungkinkan di antara run. Pada dasarnya, kode untuk menggabungkan negara baru dan yang dikunjungi tetap sama; masih didasarkan pada bagian bertahap melalui aliran. Satu-satunya perbedaan adalah bahwa alih-alih hanya melewati dua aliran, ada aliran terpisah untuk masing-masing proses yang diurutkan dari negara baru.
Tentu saja, tingkat kompresi dari 100 juta negara ini tidak sebaik kompresi semua negara yang dikunjungi. Tetapi bahkan dengan indikator seperti itu, secara signifikan mengurangi volume set kerja dan persyaratan untuk disk I / O. Anda memerlukan lebih banyak sumber daya CPU untuk memproses antrian utas prioritas, tetapi ini masih merupakan kompromi yang hebat.
Menghemat ruang pada status induk
Pada tahap ini, sebagian besar ruang yang ditempati oleh program dihabiskan untuk menyimpan status induk, sehingga setelah menemukan solusinya kita dapat menciptakan kembali prosesnya. Kemungkinan besar, mereka tidak dapat diperas dengan baik, tetapi mungkin ada semacam kompromi antara CPU dan memori?
Kita perlu menghubungkan negara S 'pada kedalaman D + 1 dengan negara induknya S di kedalaman D. Jika kita dapat mengulangi semua kemungkinan status orangtua S', maka kita dapat memeriksa apakah ada di antara mereka yang muncul di kedalaman D pada set yang dikunjungi. . (Kami telah membuat banyak dikunjungi, dikelompokkan berdasarkan kedalaman sebagai produk sampingan yang nyaman dari derivasi negara / bundel keadaan orang tua selama penggabungan). Sayangnya, pendekatan ini tidak akan berfungsi untuk tugas ini; terlalu sulit bagi kita untuk menghasilkan semua kemungkinan status S untuk S yang diberikan. Namun, untuk banyak tugas pencarian lainnya solusi seperti itu mungkin berfungsi.Jika kita hanya dapat menghasilkan transisi antar negara ke depan, tetapi tidak mundur, lalu mengapa tidak melakukan ini saja? Mari kita berputar-putar di sekitar semua status di kedalaman D dan melihat seperti apa status keluaran yang mereka dapatkan. Jika beberapa negara bagian pada output memberikan S ', maka kami menemukan S. yang sesuai. Masalah dengan rencana ini adalah bahwa ia meningkatkan konsumsi CPU total program sebesar 50%. (Tidak 100%, karena rata-rata kita akan menemukan S dengan melihat setengah keadaan pada kedalaman D).Oleh karena itu, saya tidak suka bukan salah satu dari kasus pembatas, tetapi di sini, setidaknya, kompromi antara CPU / memori dimungkinkan. Apakah ada solusi yang lebih dapat diterima di antara keduanya? Pada akhirnya, saya memutuskan untuk tidak menyimpan pasangan (S ', S), tetapi pasangan (S', H (S)), di mana H adalah fungsi hash 8-bit. Untuk menemukan S untuk S yang diberikan, kita kembali mengulangi semua status di kedalaman D. Tapi sebelum melakukan hal lain, kita menghitung hash yang sama. Jika output tidak cocok dengan H (S), maka ini bukan keadaan yang kita cari, dan kita bisa langsung melewatkannya. Pengoptimalan ini berarti bahwa penghitungan ulang yang mahal hanya perlu dilakukan untuk 1/256 status, yang mewakili sedikit peningkatan dalam beban CPU, dan pada saat yang sama mengurangi jumlah memori untuk menyimpan status induk dari 8-10 byte menjadi 1 byte.Apa yang tidak berhasil atau tidak berhasil
Di bagian sebelumnya, kami melihat urutan optimasi tingkat tinggi yang berfungsi. Saya mencoba hal-hal lain yang tidak berhasil, atau yang saya temukan dalam literatur, tetapi memutuskan bahwa dalam kasus khusus ini mereka tidak akan berhasil. Berikut adalah sebagian daftar.Pada titik ini, saya tidak menghitung ulang seluruh set yang dikunjungi pada setiap iterasi. Alih-alih, itu disimpan karena banyak proses yang diurutkan, dan proses ini dikompres dari waktu ke waktu. Keuntungan dari pendekatan ini adalah bahwa lebih sedikit penulisan disk dan sumber daya CPU digunakan untuk kompresi. Kerugiannya adalah meningkatnya kompleksitas kode dan mengurangi tingkat kompresi. Awalnya, saya pikir skema seperti itu masuk akal, karena dalam kasus saya, operasi tulis lebih mahal daripada membaca. Namun pada akhirnya, rasio kompresi ternyata dua kali lipat. Keuntungan dari kompromi semacam itu tidak jelas, oleh karena itu, saya kembali ke bentuk yang lebih sederhana.Sedikit penelitian yang telah dilakukan dalam melakukan pencarian pertama volumetrik untuk grafik yang didefinisikan secara implisit di penyimpanan sekunder, Anda dapat mulai menjelajahi topik inidari artikel 2008 ini . Seperti yang mungkin Anda tebak, gagasan melakukan deduplikasi bersama dengan menyortir + menggabungkan di penyimpanan sekunder bukanlah hal baru. Apa yang mengejutkan tentang ini adalah bahwa itu dibuka hanya pada tahun 1993. Terlambat! Ada saran selanjutnya untuk pencarian luas pertama di penyimpanan sekunder yang tidak memerlukan langkah penyortiran.Salah satunya adalah untuk mengikat negara ke integer, dan menyimpan dalam bitmap memori negara yang dikunjungi. Dalam kasus saya, ini sama sekali tidak berguna, karena ukuran negara yang disandikan sangat berbeda dibandingkan dengan ruang keadaan yang benar-benar terjangkau. Dan saya sangat meragukan bahwa ada masalah menarik di mana pendekatan seperti itu akan berhasil.Alternatif serius lain didasarkan pada tabel hash sementara. Status yang dikunjungi disimpan tanpa mengurutkan dalam file. Kami menyimpan output yang diperoleh dari kedalaman D ke tabel hash. Kemudian secara iteratif berkeliling negara yang dikunjungi dan mencarinya di tabel hash. Jika item ditemukan di tabel hash, maka hapus. Setelah melewati seluruh file secara iteratif, hanya elemen non-duplikat yang akan tetap ada di dalamnya. Mereka kemudian ditambahkan ke file dan digunakan untuk menginisialisasi daftar todo untuk iterasi berikutnya. Jika jumlah output sangat besar sehingga tabel hash tidak muat di memori, maka kedua file dan tabel hash dapat dibagi menjadi beberapa bagian menggunakan kriteria yang sama (misalnya, bit bagian atas negara) dan masing-masing bagian diproses secara terpisah.Meski ada tolok ukurmenunjukkan bahwa pendekatan berbasis hash sekitar 30% lebih cepat daripada menyortir + penggabungan, tetapi tampaknya mereka tidak memperhitungkan kompresi akun. Saya hanya tidak melihat bagaimana penolakan terhadap manfaat kompresi dapat membenarkan dirinya sendiri, jadi saya bahkan tidak bereksperimen dengan pendekatan seperti itu.Bidang penelitian lain yang patut diperhatikan adalah optimalisasi permintaan basis data. Sepertinya. bahwa tugas deduplikasi sangat terkait dengan penggabungan basis data, yang juga memiliki pengurutan yang sama persis dan dilema hashing. Jelas, beberapa studi ini dapat diterapkan pada masalah pencarian. Perbedaannya mungkin bahwa output gabungan database bersifat sementara, sedangkan output deduplikasi BFS disimpan hingga akhir perhitungan. Tampaknya ini mengubah keseimbangan kompromi: sekarang ini menyangkut tidak hanya pemrosesan yang paling efisien dari satu iterasi, tetapi juga penciptaan format data output paling optimal untuk iterasi berikutnya.Kesimpulan
Ini menyimpulkan akun saya tentang apa yang saya pelajari dari sebuah proyek yang secara umum berlaku untuk tugas pencarian lainnya oleh brute force. Kombinasi dari trik-trik ini memungkinkan untuk mengurangi volume solusi untuk teka-teki paling kompleks dari game dari 50-100 GB menjadi 500 MB dan untuk meningkatkan biaya dengan lancar jika tugas melebihi memori yang tersedia dan ditulis ke disk. Selain itu, solusi saya adalah 50% lebih cepat daripada deduplikasi naif berdasarkan tabel hash, bahkan untuk puzzle yang sesuai dengan memori.Snakebird dapat dibeli di Steam , Google Play, dan App Store . Saya merekomendasikan hal ini kepada siapa pun yang tertarik dengan teka-teki yang sangat kompleks, tetapi jujur.