Mengapa Penayak Serentak Algoritma Eratosthenes Lebih Lambat Daripada Versi Berjujukan?

Nombor Perdana oleh Eratosthenes Lebih Pantas Secara Berurutan daripada Serentak?

Secara amnya diandaikan bahawa algoritma serentak adalah lebih pantas daripada algoritma berjujukan. Walau bagaimanapun, dalam kod yang diberikan, versi serentak algoritma Sieve of Eratosthenes adalah lebih perlahan daripada versi berjujukan. Artikel ini meneroka sebab di sebalik hasil yang tidak dijangka ini, menyerlahkan potensi isu dalam kod yang disediakan dan mencadangkan beberapa pengoptimuman untuk meningkatkan prestasi kedua-dua pelaksanaan berurutan dan serentak.

Analisis Kod

Pelaksanaan Berjujukan

Kelas PrimesSeq melaksanakan versi berjujukan algoritma Sieve of Eratosthenes. Ia menggunakan bitArr tatasusunan bait untuk mewakili penapis. Setiap bit dalam tatasusunan mewakili nombor, dan jika bit ditetapkan, nombor itu ditandakan sebagai bukan perdana. Algoritma melelaran ke atas ayak, bermula dari 2, dan menandakan semua gandaan nombor semasa sebagai bukan perdana. Fungsi isPrime menyemak sama ada nombor adalah perdana dengan menyemak sama ada bit yang sepadan dalam penapis tidak ditetapkan. Fungsi printAllPrimes mencetak semua nombor perdana yang ditemui oleh algoritma.

Pelaksanaan Serentak

Kelas PrimesPara melaksanakan versi serentak algoritma Sieve of Eratosthenes. Ia membahagikan ayak kepada beberapa ketulan dan memberikan setiap ketulan kepada benang yang berasingan. Setiap utas bertanggungjawab untuk menandakan gandaan nombor yang diberikan kepadanya sebagai bukan perdana. Benang utama bertanggungjawab untuk menjana nombor perdana dan memulakan benang. Fungsi crossOut digunakan untuk menandakan nombor sebagai bukan perdana. Fungsi generateErastothenesConcurrently menjana nombor perdana secara serentak.

Perbandingan Prestasi

Dalam kod yang diberikan, versi serentak algoritma adalah kira-kira 10 kali lebih perlahan daripada versi berjujukan. Ini tidak dijangka kerana algoritma serentak biasanya lebih pantas daripada yang berurutan.

Kemacetan dalam Pelaksanaan Serentak

Terdapat beberapa kemungkinan kesesakan dalam kod yang disediakan:

• Penciptaan benang dan overhed penyegerakan: Mencipta dan menyegerakkan berbilang benang boleh menjadi mahal. Dalam kes ini, pelaksanaan serentak mencipta benang untuk setiap bahagian ayak, yang boleh menambah overhed yang ketara.
• Perkongsian palsu: Apabila berbilang benang mengakses lokasi memori yang sama, ia boleh mengganggu satu sama lain, menyebabkan kemerosotan prestasi. Dalam kes ini, benang berkongsi tatasusunan bitArr, yang boleh membawa kepada perkongsian palsu.
• Ketidakseimbangan beban: Jika ayak tidak dibahagikan sama rata antara benang, sesetengah benang mungkin mempunyai lebih banyak kerja untuk dilakukan daripada yang lain, yang membawa kepada ketidakseimbangan beban.

Pengoptimuman

Terdapat beberapa pengoptimuman yang boleh digunakan pada kedua-dua pelaksanaan berjujukan dan serentak:

• Gunakan struktur data yang lebih cekap: Daripada menggunakan tatasusunan bait untuk mewakili penapis, struktur data yang lebih cekap, seperti set bit atau tatasusunan jarang, boleh digunakan. Ini boleh mengurangkan penggunaan memori dan meningkatkan prestasi.
• Kurangkan penciptaan benang dan overhed penyegerakan: Jika boleh, bilangan benang yang digunakan harus dikurangkan untuk meminimumkan penciptaan benang dan overhed penyegerakan.
• Kurangkan perkongsian palsu: Perkongsian palsu boleh dikurangkan dengan menggunakan padding atau dengan menggunakan struktur data berbeza yang tidak mengalami perkongsian palsu.
• Imbangi beban: Ayak hendaklah dibahagikan sama rata di antara benang untuk memastikan semua benang mempunyai jumlah kerja yang hampir sama untuk dilakukan.

Kesimpulan

Walaupun algoritma serentak biasanya lebih pantas daripada berjujukan satu, terdapat kes di mana algoritma berjujukan mungkin lebih pantas. Dalam kes algoritma Sieve of Eratosthenes, overhed penciptaan benang dan penyegerakan, perkongsian palsu dan ketidakseimbangan beban boleh mengatasi faedah konkurensi.

Dengan menggunakan pengoptimuman yang diterangkan dalam artikel ini, adalah mungkin untuk meningkatkan prestasi kedua-dua pelaksanaan berurutan dan serentak bagi algoritma Ayak Eratosthenes.

Atas ialah kandungan terperinci Mengapa Penayak Serentak Algoritma Eratosthenes Lebih Lambat Daripada Versi Berjujukan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!