Rumah > Artikel > pembangunan bahagian belakang > Penandaarasan Perbandingan: ILP, A* dan Algoritma Cawangan dan Terikat dalam Senario Melalui Tinggi
Dalam catatan blog ini, kami akan membandingkan prestasi tiga algoritma berbeza yang digunakan dalam projek peribadi baru-baru ini: algoritma ILP (Integer Linear Programming), Algoritma tempatan menggunakan algoritma A* dan penyelesaian yang dioptimumkan menggunakan algoritma Cabang dan Terikat. Semua algoritma telah diuji menggunakan set data yang sama, dengan pelaksanaan ILP dan Branch and Bound berkongsi beban kerja yang sama, manakala pelaksanaan A* dihadkan kerana kekangan prestasi.
Penafian: Walaupun saya tidak akan menyelidiki butiran kod khusus projek, saya akan berkongsi beberapa cerapan daripadanya. Pangkalan kod tidak bertujuan untuk pendedahan awam, dan ini berfungsi sebagai penafian untuk menghormati kerahsiaannya.
Berikut ialah hasil penanda aras untuk ketiga-tiga algoritma:
goos: linux goarch: amd64 pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg cpu: 13th Gen Intel(R) Core(TM) i7-13700HX BenchmarkGenerateReportILP-24 724 1694029 ns/op 30332 B/op 181 allocs/op BenchmarkGenerateReportILPParallel-24 6512 187871 ns/op 34545 B/op 184 allocs/op BenchmarkGenerateReportLocal-24 2 851314106 ns/op 559466456 B/op 7379756 allocs/op BenchmarkBranchGenerateReportLocal-24 101449 12106 ns/op 29932 B/op 165 allocs/op BenchmarkGenerateReportLocalParallel-24 3 349605952 ns/op 559422440 B/op 7379837 allocs/op BenchmarkBranchGenerateReportLocalParallel-24 120543 10755 ns/op 29933 B/op 165 allocs/op PASS coverage: 81.4% of statements ok github.com/sosalejandro/<my-project>/<my-package>/pkg 11.121s
Semua algoritma telah diuji menggunakan set data yang sama, tetapi beban kerja (iaitu, bilangan kali setiap item diproses) berbeza antara pelaksanaan.
plan := []Plan{ {ID: "1", Times: 100}, {ID: "2", Times: 150}, {ID: "3", Times: 200}, {ID: "8", Times: 50}, {ID: "9", Times: 75}, {ID: "10", Times: 80}, {ID: "11", Times: 90}, {ID: "12", Times: 85}, {ID: "13", Times: 60}, {ID: "14", Times: 110}, }
plan := []Plan{ {ID: "1", Times: 1}, {ID: "2", Times: 1}, {ID: "3", Times: 5}, {ID: "8", Times: 5}, {ID: "9", Times: 5}, {ID: "10", Times: 5}, {ID: "11", Times: 9}, {ID: "12", Times: 5}, {ID: "13", Times: 5}, {ID: "14", Times: 5}, }
Untuk memahami kesan beban kerja ini pada hasil penanda aras, mari kita hitung jumlah bilangan lelaran (iaitu, jumlah nilai Times) untuk setiap pelaksanaan.
100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000
1 + 1 + 5 + 5 + 5 + 5 + 9 + 5 + 5 + 5 = 46
ILP Iterations / A* Iterations = 1000 / 46 ≈ 21.74
Ini bermakna pelaksanaan ILP dan Branch and Bound mengendalikan kira-kira 21.74 kali lebih banyak lelaran berbanding dengan pelaksanaan A*.
Mari kita pecahkan hasil penanda aras berhubung dengan perbezaan beban kerja.
Benchmark | Runs | ns/op | B/op | allocs/op | Total Time (ns) |
---|---|---|---|---|---|
BenchmarkGenerateReportILP-24 | 724 | 1,694,029 | 30,332 | 181 | ≈ 1,225,836,996 |
BenchmarkGenerateReportILPParallel-24 | 6,512 | 187,871 | 34,545 | 184 | ≈ 1,223,607,552 |
BenchmarkBranchGenerateReportLocal-24 | 101,449 | 12,106 | 29,932 | 165 | ≈ 1,224,505,394 |
BenchmarkGenerateReportLocal-24 | 2 | 851,314,106 | 559,466,456 | 7,379,756 | ≈ 1,702,628,212 |
BenchmarkGenerateReportLocalParallel-24 | 3 | 349,605,952 | 559,422,440 | 7,379,837 | ≈ 1,048,817,856 |
BenchmarkBranchGenerateReportLocalParallel-24 | 120,543 | 10,755 | 29,933 | 165 | ≈ 1,295,219,065 |
BenchmarkGenerateReportILP-24 lwn BenchmarkGenerateReportLocal-24:
BenchmarkGenerateReportILPParallel-24 lwn BenchmarkBranchGenerateReportLocalParallel-24:
BenchmarkGenerateReportILPParallel-24 lwn BenchmarkGenerateReportLocalParallel-24:
Kesan Pelbagai Beban Kerja terhadap Prestasi
Memandangkan algoritma ILP dan Branch mengendalikanILP dan Algoritma Cawangan: Memandangkan ini mengendalikan daya pemprosesan yang lebih besar, ia dioptimumkan untuk beban kerja yang lebih tinggi. Walaupun mengendalikan lebih banyak operasi, mereka mengekalkan masa pelaksanaan yang lebih pantas. Ini menunjukkan ia bukan sahaja cekap dari segi pengiraan tetapi juga sesuai untuk senario pemprosesan tinggi.
Algoritma Tempatan: Dengan daya pemprosesan yang lebih kecil dan masa pelaksanaan yang lebih tinggi, algoritma ini kurang cekap dalam mengendalikan peningkatan beban kerja. Jika diskalakan kepada daya pemprosesan yang sama seperti ILP atau Cawangan, masa pelaksanaannya akan meningkat dengan ketara, menunjukkan ia tidak sesuai untuk kes pemprosesan tinggi.
Dalam senario di mana beban kerja meningkat, ILP dan Cawangan akan mengatasi prestasi Tempatan kerana keupayaan mereka untuk mengurus daya pengeluaran yang lebih tinggi dengan cekap. Sebaliknya, jika beban kerja dikurangkan, algoritma Tempatan mungkin berprestasi lebih dekat dengan ILP dan Cawangan tetapi mungkin masih ketinggalan disebabkan perbezaan asas dalam kecekapan algoritma.
Untuk memberikan pemahaman yang lebih jelas tentang cara setiap algoritma mendekati penyelesaian masalah, berikut ialah gambaran umum mekanisme dan metodologinya.
Tujuan:
ILP ialah teknik pengoptimuman yang digunakan untuk mencari hasil terbaik (seperti keuntungan maksimum atau kos terendah) dalam model matematik yang keperluannya diwakili oleh hubungan linear. Ia amat berkesan untuk masalah yang boleh dinyatakan dari segi kekangan linear dan fungsi objektif linear.
Aliran Kerja Umum:
Takrifkan Pembolehubah:
Kenal pasti pembolehubah keputusan yang mewakili pilihan yang akan dibuat.
Fungsi Objektif:
Bentukkan persamaan linear yang perlu dimaksimumkan atau diminimumkan.
Kekangan:
Wujudkan ketaksamaan linear atau kesamaan yang mesti dipenuhi oleh penyelesaian.
Selesaikan:
Gunakan penyelesai ILP untuk mencari nilai optimum pembolehubah keputusan yang memaksimumkan atau meminimumkan fungsi objektif sambil memenuhi semua kekangan.
Pseudokod:
goos: linux goarch: amd64 pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg cpu: 13th Gen Intel(R) Core(TM) i7-13700HX BenchmarkGenerateReportILP-24 724 1694029 ns/op 30332 B/op 181 allocs/op BenchmarkGenerateReportILPParallel-24 6512 187871 ns/op 34545 B/op 184 allocs/op BenchmarkGenerateReportLocal-24 2 851314106 ns/op 559466456 B/op 7379756 allocs/op BenchmarkBranchGenerateReportLocal-24 101449 12106 ns/op 29932 B/op 165 allocs/op BenchmarkGenerateReportLocalParallel-24 3 349605952 ns/op 559422440 B/op 7379837 allocs/op BenchmarkBranchGenerateReportLocalParallel-24 120543 10755 ns/op 29933 B/op 165 allocs/op PASS coverage: 81.4% of statements ok github.com/sosalejandro/<my-project>/<my-package>/pkg 11.121s
Tujuan:
A* ialah algoritma penelusuran laluan dan graf yang terkenal dengan prestasi dan ketepatannya. Ia cekap mencari laluan terpendek antara nod dengan menggabungkan ciri carian kos seragam dan carian heuristik tulen.
Aliran Kerja Umum:
Permulaan:
Mulakan dengan nod awal dan tambahkannya pada baris gilir keutamaan.
Gelung:
Penamatan:
Algoritma menyimpulkan apabila nod matlamat dicapai atau baris gilir keutamaan kosong (menunjukkan tiada laluan wujud).
Pseudokod:
goos: linux goarch: amd64 pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg cpu: 13th Gen Intel(R) Core(TM) i7-13700HX BenchmarkGenerateReportILP-24 724 1694029 ns/op 30332 B/op 181 allocs/op BenchmarkGenerateReportILPParallel-24 6512 187871 ns/op 34545 B/op 184 allocs/op BenchmarkGenerateReportLocal-24 2 851314106 ns/op 559466456 B/op 7379756 allocs/op BenchmarkBranchGenerateReportLocal-24 101449 12106 ns/op 29932 B/op 165 allocs/op BenchmarkGenerateReportLocalParallel-24 3 349605952 ns/op 559422440 B/op 7379837 allocs/op BenchmarkBranchGenerateReportLocalParallel-24 120543 10755 ns/op 29933 B/op 165 allocs/op PASS coverage: 81.4% of statements ok github.com/sosalejandro/<my-project>/<my-package>/pkg 11.121s
Tujuan:
Branch and Bound ialah algoritma pengoptimuman yang meneroka ruang penyelesaian secara sistematik. Ia membahagikan masalah kepada submasalah yang lebih kecil (percabangan) dan menggunakan had untuk menghapuskan submasalah yang tidak dapat menghasilkan penyelesaian yang lebih baik daripada yang terbaik semasa (bounding).
Aliran Kerja Umum:
Permulaan:
Mulakan dengan penyelesaian awal dan tetapkan penyelesaian yang paling terkenal.
Cawangan:
Pada setiap nod, bahagikan masalah kepada submasalah yang lebih kecil.
Pengikat:
Kira anggaran optimistik (batas atas) penyelesaian terbaik yang mungkin di setiap cawangan.
Pemangkasan:
Buang cawangan di mana sempadan atas lebih teruk daripada penyelesaian yang paling terkenal.
Cari:
Terokai cawangan yang tinggal secara rekursif menggunakan carian mendalam-dahulukan atau terbaik-dahulukan.
Penamatan:
Apabila semua dahan telah dipangkas atau diterokai, penyelesaian yang paling terkenal adalah optimum.
Pseudokod:
goos: linux goarch: amd64 pkg: github.com/sosalejandro/<my-project>/<my-package>/pkg cpu: 13th Gen Intel(R) Core(TM) i7-13700HX BenchmarkGenerateReportILP-24 724 1694029 ns/op 30332 B/op 181 allocs/op BenchmarkGenerateReportILPParallel-24 6512 187871 ns/op 34545 B/op 184 allocs/op BenchmarkGenerateReportLocal-24 2 851314106 ns/op 559466456 B/op 7379756 allocs/op BenchmarkBranchGenerateReportLocal-24 101449 12106 ns/op 29932 B/op 165 allocs/op BenchmarkGenerateReportLocalParallel-24 3 349605952 ns/op 559422440 B/op 7379837 allocs/op BenchmarkBranchGenerateReportLocalParallel-24 120543 10755 ns/op 29933 B/op 165 allocs/op PASS coverage: 81.4% of statements ok github.com/sosalejandro/<my-project>/<my-package>/pkg 11.121s
Feature | ILP Implementation | Local (A*) Implementation | Branch and Bound Implementation |
---|---|---|---|
Optimization Approach | Formulates the problem as a set of linear equations and inequalities to find the optimal solution. | Searches through possible states using heuristics to find the most promising path to the goal. | Systematically explores and prunes the solution space to find optimal solutions efficiently. |
Scalability | Handles large-scale problems efficiently by leveraging optimized solvers. | Performance can degrade with increasing problem size due to the exhaustive nature of state exploration. | Efficient for combinatorial problems, with pruning reducing the search space significantly. |
Development Time | Faster implementation as it relies on existing ILP solvers and libraries. | Requires more time to implement, especially when dealing with complex state management and heuristics. | Moderate development time, balancing complexity and optimization benefits. |
Flexibility | Highly adaptable to various linear optimization problems with clear constraints and objectives. | Best suited for problems where pathfinding to a goal is essential, with heuristic guidance. | Effective for a wide range of optimization problems, especially combinatorial ones. |
Performance | Demonstrates superior performance in handling a higher number of iterations with optimized memory usage. | While effective for certain scenarios, struggles with high memory allocations and longer execution times under heavy workloads. | Shows significant performance improvements over ILP and A* with optimized memory usage and faster execution times. |
Developer Experience | Improves developer experience by reducing the need for extensive coding and optimization efforts. | May require significant debugging and optimization to achieve comparable performance levels. | Balances performance with manageable development effort, leveraging existing strategies for optimization. |
Integration | Currently integrates a C ILP module with Golang, facilitating efficient computation despite cross-language usage. | Fully implemented within Golang, but may face limitations in performance and scalability without optimizations. | Implemented in Golang, avoiding cross-language integration complexities and enhancing performance. |
Skalabiliti:
Penggunaan Sumber:
Perbezaan beban kerja mempengaruhi prestasi algoritma:
Pelaksanaan Cawangan dan Terikat mengendalikan beban kerja yang sama seperti pelaksanaan ILP dengan cekap, menyediakan masa pelaksanaan yang pantas dan penggunaan memori yang rendah, menjadikannya sesuai untuk penskalaan.
Pelaksanaan ILP mengendalikan beban kerja yang lebih besar dengan cekap disebabkan oleh penyelesai yang dioptimumkan.
A* Implementation bergelut dengan prestasi kerana masa pelaksanaan yang tinggi dan penggunaan memori.
Perbandingan tambahan telah ditambahkan menggunakan penyelesaian yang dioptimumkan dengan algoritma Cawangan dan Terikat, yang menunjukkan cara ia bertambah baik dengan ketara berbanding algoritma ILP dan A* dari segi prestasi dan penggunaan sumber. Beban kerja yang digunakan pada Algoritma Cawangan dan Terikat adalah sama dengan algoritma ILP.
Fungsi Branch and Bound-based BenchmarkBranchGenerateReportLocalParallel mempamerkan peningkatan prestasi yang luar biasa, menjadikannya sangat sesuai untuk persekitaran pelayan yang menuntut keselarasan tinggi dan pengurusan sumber yang cekap.
Dengan memfokuskan pada memanfaatkan kekuatan pendekatan Branch and Bound dan mengoptimumkannya untuk masalah khusus, kami boleh memastikan projek itu kekal berprestasi dan berskala, mampu mengendalikan permintaan yang semakin meningkat dengan mudah.
Mengimbangi prestasi, kebolehskalaan dan pengalaman pembangun adalah penting untuk membina aplikasi yang mantap. Pendekatan Cabang dan Terikat telah terbukti paling cekap dalam persediaan semasa, menawarkan peningkatan prestasi yang besar dengan usaha pembangunan yang munasabah.
Dengan memprofil, mengoptimumkan dan memanfaatkan kekuatan setiap pendekatan algoritma secara berterusan, kami boleh mengekalkan sistem berprestasi tinggi, berskala dan mesra pembangun.
Atas ialah kandungan terperinci Penandaarasan Perbandingan: ILP, A* dan Algoritma Cawangan dan Terikat dalam Senario Melalui Tinggi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!