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.

Keputusan Penanda Aras

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
</my-package></my-project></my-package></my-project>

Konfigurasi Beban Kerja

Semua algoritma telah diuji menggunakan set data yang sama, tetapi beban kerja (iaitu, bilangan kali setiap item diproses) berbeza antara pelaksanaan.

Beban Kerja Pelaksanaan ILP dan Cawangan dan Terikat:

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

A* Beban Kerja Pelaksanaan:

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

Analisis Beban Kerja

Untuk memahami kesan beban kerja ini pada hasil penanda aras, mari kita hitung jumlah bilangan lelaran (iaitu, jumlah nilai Times) untuk setiap pelaksanaan.

Jumlah Lelaran:

• ILP dan Cawangan dan Pelaksanaan Terikat:

  100 + 150 + 200 + 50 + 75 + 80 + 90 + 85 + 60 + 110 = 1000

• A* Pelaksanaan:

  1 + 1 + 5 + 5 + 5 + 5 + 9 + 5 + 5 + 5 = 46

Nisbah Beban Kerja:

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*.

Perbandingan Prestasi

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

Pemerhatian

1. Masa Pelaksanaan setiap Operasi:
   • BenchmarkGenerateReportILP-24 lwn BenchmarkBranchGenerateReportLocal-24:
     • Cawangan dan Terikat adalah 99.29% lebih pantas daripada ILP, mengurangkan masa pelaksanaan daripada 1,694,029 ns/op kepada 6 ns .

• BenchmarkGenerateReportILP-24 lwn BenchmarkGenerateReportLocal-24:

  • ILP adalah 99.80% lebih pantas daripada Tempatan, mengurangkan masa pelaksanaan daripada 851,314,106 ns/op kepada 0,9 ns/op1,99 ns >.

• BenchmarkGenerateReportILPParallel-24 lwn BenchmarkBranchGenerateReportLocalParallel-24:

  • Branch and Bound Parallel adalah 94.28% lebih pantas daripada ILP Parallel, mengurangkan masa pelaksanaan daripada 187,871 ns/op kepada kepada /op
  .

• BenchmarkGenerateReportILPParallel-24 lwn BenchmarkGenerateReportLocalParallel-24:

  • ILP Parallel adalah 99.95% lebih cepat daripada Local Parallel, mengurangkan masa pelaksanaan daripada 349,605,952 ns/op1 kepada 1 ns/op
  1 kepada
.

1. Peruntukan Memori:
   • Pelaksanaan ILP: Peningkatan sedikit dalam penggunaan memori dan peruntukan apabila berjalan secara selari.
   • Pelaksanaan Cawangan dan Terikat: Penggunaan dan peruntukan memori yang lebih rendah berbanding dengan pelaksanaan A*.
   A* Pelaksanaan:
Peruntukan memori yang sangat tinggi, membawa kepada penggunaan sumber yang tidak cekap.

2. Harus keluar:
   • ILP Parallel dan Branch and Bound Parallel
   boleh mengendalikan
   • kira-kira 21.74 kali lebih banyak lelaran disebabkan oleh beban kerja yang lebih tinggi.
   Implementasi A*
bergelut dengan daya pemprosesan bukan disebabkan bilangan lelaran yang jauh lebih rendah tetapi disebabkan penggunaan dan pelaksanaan memori yang tidak cekap.

Kesan Pelbagai Beban Kerja terhadap Prestasi

Memandangkan algoritma ILP dan Branch mengendalikan

21.74 kali
• lebih banyak daya bagi setiap lelaran ujian, perbezaan beban kerja ini memberi kesan kepada prestasi dan kecekapan setiap algoritma:
  ILP 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.

Gambaran Keseluruhan Algoritma

Untuk memberikan pemahaman yang lebih jelas tentang cara setiap algoritma mendekati penyelesaian masalah, berikut ialah gambaran umum mekanisme dan metodologinya.

Pengaturcaraan Linear Integer (ILP)

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:

1. Takrifkan Pembolehubah:
   
   Kenal pasti pembolehubah keputusan yang mewakili pilihan yang akan dibuat.

2. Fungsi Objektif:
   
   Bentukkan persamaan linear yang perlu dimaksimumkan atau diminimumkan.

3. Kekangan:
   
   Wujudkan ketaksamaan linear atau kesamaan yang mesti dipenuhi oleh penyelesaian.

4. 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
</my-package></my-project></my-package></my-project>

Algoritma A* (Pelaksanaan Tempatan)

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:

1. Permulaan:
   
   Mulakan dengan nod awal dan tambahkannya pada baris gilir keutamaan.

2. Gelung:

   • Alih keluar nod dengan anggaran kos terendah daripada baris gilir keutamaan.
   • Jika nod gol, tamatkan.
   • Jika tidak, kembangkan nod dengan meneroka jirannya.
   • Untuk setiap jiran, kira kos baharu dan kemas kini baris gilir keutamaan dengan sewajarnya.

3. 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
</my-package></my-project></my-package></my-project>

Algoritma Cawangan dan Terikat

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:

1. Permulaan:
   
   Mulakan dengan penyelesaian awal dan tetapkan penyelesaian yang paling terkenal.

2. Cawangan:
   
   Pada setiap nod, bahagikan masalah kepada submasalah yang lebih kecil.

3. Pengikat:
   
   Kira anggaran optimistik (batas atas) penyelesaian terbaik yang mungkin di setiap cawangan.

4. Pemangkasan:
   
   Buang cawangan di mana sempadan atas lebih teruk daripada penyelesaian yang paling terkenal.

5. Cari:
   
   Terokai cawangan yang tinggal secara rekursif menggunakan carian mendalam-dahulukan atau terbaik-dahulukan.

6. 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
</my-package></my-project></my-package></my-project>

Analisis Perbandingan

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.

Implikasi untuk Prestasi Pelayan

• Skalabiliti:

  • Pelaksanaan Cabang dan Terikat menunjukkan kebolehskalaan yang sangat baik, dengan cekap mengendalikan sejumlah besar permintaan serentak dengan kependaman yang dikurangkan.
  • Pelaksanaan ILP Parallel juga menunjukkan kebolehskalaan yang sangat baik, dengan cekap mengendalikan sejumlah besar permintaan serentak dengan kependaman yang dikurangkan.
  • Pelaksanaan A* tidak sesuai untuk persekitaran beban tinggi kerana had prestasi.

• Penggunaan Sumber:

  • Pelaksanaan Cawangan dan Terikat menggunakan sumber dengan cekap, dengan penggunaan memori yang rendah dan masa pelaksanaan yang pantas.
  • ILP Parallel menggunakan CPU berbilang teras dengan berkesan, memberikan daya pemprosesan yang tinggi dengan penggunaan memori yang boleh diurus.
  • A* Pelaksanaan menggunakan memori yang berlebihan, yang berpotensi membawa kepada keletihan sumber.

Kesan Beban Kerja pada Prestasi

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.

Kesimpulan

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.

Fikiran Akhir

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!