AI menulis semula algoritma pengisihan dan 70% lebih pantas: DeepMind AlphaDev menginovasi asas pengkomputeran dan memanggil trilion kemas kini perpustakaan setiap hari

"Dengan menukar dan memindahkan salinan, AlphaDev melangkau satu langkah dan menyambungkan item dengan cara yang kelihatan salah tetapi sebenarnya merupakan jalan pintas yang tidak pernah berlaku sebelum ini dan berlawanan dengan intuisi .

Tujuh tahun lalu, AlphaGo mengalahkan juara dunia manusia di Go, dan kini AI telah mengajar kita satu lagi pelajaran dalam pengaturcaraan.

Awal pagi ini, dua ayat daripada Ketua Pegawai Eksekutif Google DeepMind Hassabis meletupkan medan komputer: "AlphaDev telah menemui algoritma pengisihan baharu dan lebih pantas, dan kami telah membuka sumbernya ke dalam perpustakaan C++ utama untuk digunakan oleh pembangun. Ini hanyalah permulaan kemajuan AI dalam meningkatkan kecekapan kod , sistem pembelajaran tetulang baharu Google DeepMind AlphaDev menemui algoritma cincang yang lebih pantas daripada sebelumnya, iaitu algoritma asas dalam bidang sains komputer hasil AI kini telah dimasukkan ke dalam perpustakaan C++ standard LLVM Abseil dan sumber terbuka.

Seberapa pentingkah keputusan ini? Daniel J. Mankowitz, salah seorang pengarang utama AlphaDev dan seorang saintis penyelidikan di Google DeepMind, berkata: "Kami menganggarkan bahawa algoritma pengisihan dan pencincangan yang ditemuinya dipanggil bertrilion kali setiap hari di seluruh dunia." >

AI nampaknya mempercepatkan dunia dari tahap algoritma.

Algoritma ini menambah baik pustaka pengisihan LLVM libc++ Untuk jujukan yang lebih pendek, kelajuan pustaka pengisihan ditingkatkan sebanyak 70% dan untuk jujukan lebih daripada 250,000 elemen. kelajuan juga bertambah baik. Ia boleh ditingkatkan sebanyak kira-kira 1.7%. Google DeepMind mengatakan ini adalah perubahan pertama pada bahagian perpustakaan penjujukan ini dalam lebih sedekad. Nampaknya kini AI bukan sahaja boleh membantu orang menulis kod, tetapi juga membantu kami menulis kod yang lebih baik.

Dalam blog terbaru, pengarang sistem baharu memperkenalkan AlphaDev secara terperinci. Algoritma baharu akan mengubah asas pengkomputeran

Masyarakat digital memacu permintaan yang semakin meningkat untuk pengkomputeran dan tenaga. Sepanjang lima puluh tahun yang lalu, era digital telah bergantung pada penambahbaikan dalam perkakasan untuk mengikuti permintaan. Tetapi apabila mikrocip menghampiri had fizikalnya, penambahbaikan kod yang dijalankan padanya menjadi kritikal. Ini amat penting untuk algoritma yang terkandung dalam kod yang dijalankan bertrilion kali setiap hari.

Penyelidikan oleh Google DeepMind ini lahir daripada kertas kerja yang berkaitan telah diterbitkan dalam "Nature". hasil kerja berpuluh tahun oleh saintis dan jurutera.

Alamat kertas: https://www.nature.com/articles /s41586-023-06004-9

Secara keseluruhannya, AlphaDev menemui algoritma pengisihan yang lebih pantas. Walaupun berbilion orang menggunakan algoritma ini setiap hari, tiada siapa yang menyedari bahawa terdapat ruang untuk pengoptimuman. Algoritma pengisihan digunakan dalam pelbagai aplikasi, daripada hasil carian dalam talian, pengisihan siaran sosial, kepada pelbagai pemprosesan data pada komputer dan telefon mudah alih, yang kesemuanya tidak dapat dipisahkan daripada algoritma pengisihan. Menggunakan AI untuk menjana algoritma yang lebih baik akan mengubah cara manusia memprogram komputer dan akan memberi kesan yang ketara kepada masyarakat yang semakin digital.

Dengan sumber terbuka algoritma pengisihan baharu dalam perpustakaan C++ utama, berjuta-juta pembangun dan syarikat di seluruh dunia kini boleh memanfaatkan kecerdasan buatan dalam industri yang pelbagai seperti pengkomputeran awan, membeli-belah dalam talian, dan pengurusan rantaian bekalan Gunakannya dalam aplikasi pintar. Ini merupakan perubahan pertama kepada pustaka kedudukan dalam lebih sedekad, dan kali pertama algoritma direka bentuk dengan pembelajaran pengukuhan telah ditambahkan pada perpustakaan. Pertimbangkan ini sebagai peristiwa penting dalam menggunakan kecerdasan buatan untuk mengoptimumkan kod dunia secara progresif.

Mengenai pengisihan

Algoritma pengisihan ialah kaedah menyusun tugasan tertentu dalam susunan tertentu. Contohnya, susun tiga huruf mengikut abjad, susun lima nombor daripada terbesar kepada terkecil, atau susun pangkalan data berjuta-juta rekod.

Algoritma ini telah wujud sejak sekian lama dan telah berkembang dengan baik. Salah satu contoh tempahan terawal bermula pada abad ke-2 dan ke-3 Masihi, apabila para sarjana mengabjadkan ribuan buku dengan tangan di rak Perpustakaan Alexandria. Dengan kemunculan Revolusi Perindustrian muncul mesin yang boleh membantu orang menyusun, dengan mesin penjadual menyimpan maklumat menggunakan kad tebuk yang digunakan untuk mengumpul hasil bancian A.S. 1890.

Dengan kebangkitan komputer komersial pada tahun 1950-an, algoritma sains komputer terawal untuk menyusun algoritma mula berkembang. Hari ini, terdapat banyak teknik dan algoritma pengisihan berbeza yang digunakan dalam pangkalan kod di seluruh dunia untuk memproses sejumlah besar data dalam talian.

Masukkan siri nombor yang tidak diisih ke dalam algoritma dan keluarkan nombor yang diisih.

Selepas beberapa dekad penyelidikan oleh saintis komputer dan pengaturcara, algoritma pengisihan semasa sudah begitu cekap sehingga sukar untuk mencapai peningkatan selanjutnya, yang agak serupa dengan Cuba untuk mencari cara baharu untuk menjimatkan kuasa atau menjadi lebih cekap dengan matematik, dan algoritma ini merupakan asas sains komputer.

Teroka algoritma baharu: arahan pemasangan

AlphaDev meneroka algoritma yang lebih pantas dari awal dan bukannya membina algoritma sedia ada Selain itu, AlphaDev juga boleh digunakan Mencari kawasan yang kebanyakan orang tidak terlibat dalam: arahan pemasangan komputer.

Arahan pemasangan boleh digunakan untuk mencipta kod binari yang komputer laksanakan. Pembangun menulis kod dalam bahasa peringkat tinggi seperti C++, tetapi mesti menukarnya kepada arahan pemasangan "peringkat rendah" yang difahami oleh komputer.

Google DeepMind percaya terdapat banyak ruang untuk penambahbaikan pada tahap ini, yang mungkin sukar dikesan dalam bahasa pengaturcaraan peringkat tinggi. Pada tahap ini, komputer lebih fleksibel dalam storan dan operasinya, yang bermaksud terdapat lebih banyak kemungkinan yang berpotensi untuk penambahbaikan yang boleh memberi kesan yang lebih besar pada kelajuan dan penggunaan tenaga.

Kod biasanya ditulis dalam bahasa pengaturcaraan peringkat tinggi seperti C++. Pengkompil kemudian menukar ini kepada arahan CPU peringkat rendah, dipanggil arahan pemasangan. Pemasang menukar arahan pemasangan kepada kod mesin boleh laku supaya komputer boleh menjalankannya.

Rajah A: Contoh algoritma C++ yang boleh menyusun sehingga dua elemen ; B: Perwakilan perhimpunan yang sepadan.

Gunakan kaedah AlphaGo untuk mencari algoritma terbaik

AlphaDev adalah berdasarkan pencapaian Google DeepMind sebelum ini: mengalahkan permainan seperti Go, catur dan catur model pembelajaran pengukuhan juara dunia AlphaZero. Dan AlphaDev menunjukkan cara model ini beralih daripada permainan kepada cabaran saintifik, dan daripada simulasi kepada aplikasi dunia sebenar.

Untuk melatih AlphaDev menemui algoritma baharu, pasukan bertukar mengisih menjadi "permainan pemasangan" pemain tunggal. Pada setiap pusingan, AlphaDev memerhati algoritma yang dihasilkannya dan maklumat yang terkandung dalam CPU, dan kemudian membuat langkah seterusnya dengan memilih arahan untuk ditambah pada algoritma.

Memasang permainan adalah sangat sukar kerana AlphaDev perlu mencari dengan cekap melalui sejumlah besar kombinasi arahan yang mungkin untuk mencari algoritma yang boleh mengisih dan lebih pantas daripada algoritma terbaik semasa. Bilangan gabungan arahan yang mungkin adalah serupa dengan bilangan zarah di alam semesta, atau bilangan kemungkinan gabungan pergerakan dalam catur (10^120 permainan) dan Go (10^700 permainan), dan satu langkah yang salah boleh menjatuhkan keseluruhan algoritma.

Rajah A: Permainan perhimpunan. Pemain AlphaDev menerima sebagai input keadaan sistem st dan bermain catur dengan memilih arahan pemasangan untuk ditambah pada algoritma yang dihasilkan pada masa ini. Rajah B: Pengiraan ganjaran. Selepas setiap langkah, algoritma yang terhasil diberi jujukan input ujian—untuk sort3, ini sepadan dengan semua gabungan tiga jujukan elemen. Algoritma kemudiannya menghasilkan output yang dibandingkan dengan output yang dijangkakan dari urutan yang disusun berdasarkan situasi pengisihan. Ejen diberi ganjaran berdasarkan ketepatan dan kependaman algoritma.

Apabila membina algoritma, satu arahan pada satu masa, AlphaDev menyemak bahawa output algoritma adalah betul dengan membandingkannya dengan hasil yang dijangkakan. Untuk algoritma pengisihan, ini bermakna nombor tidak tertib masuk dan nombor yang diisih dengan betul keluar. Pasukan memberi ganjaran kepada AlphaDev untuk mengisih nombor dengan betul dan untuk seberapa cepat dan cekap pengisihan berlaku, dan AlphaDev kemudiannya memenangi permainan dengan menemui program yang betul dan lebih pantas.

Ia menemui algoritma pengisihan yang lebih pantas

AlphaDev menemui algoritma pengisihan baharu yang menghasilkan penambahbaikan pada perpustakaan pengisihan LLVM libc++: Pustaka penjujukan ialah 70 % lebih pantas untuk jujukan yang lebih pendek dan kira-kira 1.7% lebih pantas untuk jujukan melebihi 250,000 elemen.

Antaranya, pasukan Google DeepMind lebih menumpukan pada menambah baik algoritma pengisihan jujukan pendek tiga hingga lima elemen. Algoritma ini adalah antara yang paling banyak digunakan kerana ia sering dipanggil beberapa kali sebagai sebahagian daripada fungsi pengisihan yang lebih besar, dan menambah baik algoritma ini boleh meningkatkan kelajuan keseluruhan untuk mengisih sebarang bilangan item.

Untuk menjadikan algoritma pengisihan baharu lebih berguna kepada orang ramai, pasukan itu merekayasa balik algoritma dan menterjemahkannya ke dalam C++, yang merupakan alat paling popular digunakan oleh pembangun. Salah satu bahasa pengaturcaraan yang popular.

Pada masa ini, algoritma ini disediakan dalam perpustakaan pengisihan standard LLVM libc++ (https://reviews.llvm.org/D118029) dan digunakan oleh berjuta-juta orang di seluruh dunia Digunakan oleh pemaju dan syarikat.

"Bertukar dan meniru tindakan", tangan Tuhan muncul kembali?

Malah, AlphaDev bukan sahaja menemui algoritma yang lebih pantas, tetapi juga kaedah baharu. Algoritma pengisihannya terdiri daripada urutan arahan baharu yang menyimpan arahan setiap kali ia digunakan - yang jelas mempunyai kesan yang besar, kerana algoritma ini digunakan bertrilion kali setiap hari. Mereka memanggil ini "tindakan pertukaran dan salin AlphaDev."

Kaedah novel ini mengingatkan kepada "Langkah 37" AlphaGo - pada masa itu, langkah balas intuitif ini mengejutkan penonton dan membawa kepada pemain legenda Lee Sedol The Go telah dikalahkan. Dengan menukar dan menyalin tindakan, AlphaDev melangkau satu langkah, menyambungkan item dengan cara yang kelihatan seperti kesilapan tetapi sebenarnya adalah jalan pintas. Ini menunjukkan keupayaan AlphaDev untuk mendedahkan penyelesaian asal dan mencabar cara manusia berfikir tentang cara memperbaik algoritma sains komputer.

Kiri: min (A,B,C) pelaksanaan sort3 asal kanan: Pergerakan AlphaDev Swapping - AlphaDev mendapati bahawa anda hanya memerlukan min (A,B).

Kiri: Pelaksanaan asal menggunakan maks(B,min(A,C,D)) dalam algoritma pengisihan yang lebih besar untuk mengisih lapan elemen Kanan: AlphaDev discovery , apabila menggunakan tindakan penyalinannya, hanya maks (B, min(A, C)) diperlukan.

Ujian keupayaan skala: daripada "isih" kepada "pencincangan"

Selepas menemui algoritma pengisihan yang lebih pantas, pasukan menguji sama ada AlphaDev boleh membuat generalisasi dan menambah baik sesuatu algoritma sains komputer yang berbeza: pencincangan.

Hashing ialah algoritma asas dalam pengkomputeran yang digunakan untuk mendapatkan semula, menyimpan dan memampatkan data. Sama seperti pustakawan yang menggunakan sistem klasifikasi untuk mencari buku tertentu, algoritma pencincangan membantu pengguna mengetahui perkara yang mereka cari dan tempat untuk mencarinya. Algoritma ini mengambil data untuk kunci tertentu (seperti nama pengguna "Jane Doe") dan mencincangnya - proses yang menukar data mentah kepada rentetan unik (seperti 1234ghfty). Komputer menggunakan cincang ini untuk mendapatkan semula data yang berkaitan dengan kunci dengan cepat dan bukannya mencari semua data.

Pasukan menggunakan AlphaDev pada salah satu algoritma pencincangan yang paling biasa digunakan dalam struktur data dalam usaha untuk menemui algoritma yang lebih pantas. Apabila digunakan pada fungsi cincang dalam julat 9-16 bait, AlphaDev mendapati peningkatan 30% dalam kelajuan algoritma.

Tahun ini, algoritma pencincangan baharu AlphaDev telah dikeluarkan ke dalam perpustakaan Abseil sumber terbuka, menjadikannya tersedia kepada berjuta-juta pembangun di seluruh dunia, di mana ia berada sekarang digunakan mungkin setiap hari Digunakan bertrilion kali.

Alamat sumber terbuka: https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024eConclusion . AlphaDev boleh dilihat sebagai satu langkah ke arah membangunkan alatan AI tujuan umum yang boleh membantu mengoptimumkan keseluruhan ekosistem pengkomputeran dan menyelesaikan masalah lain untuk manfaat masyarakat.

Walaupun ia sangat berkuasa untuk mengoptimumkan dalam ruang arahan pemasangan peringkat rendah, AlphaDev masih mempunyai had apabila algoritma berkembang, dan pasukan sedang meneroka pelaksanaan langsungnya dalam peringkat tinggi bahasa seperti C++ Keupayaan untuk mengoptimumkan algoritma, yang lebih berguna untuk pembangun.

Penemuan AlphaDev, seperti tindakan swap dan salin, menunjukkan bukan sahaja ia boleh menambah baik algoritma tetapi juga mencari penyelesaian baharu. Penemuan ini mungkin memberi inspirasi kepada penyelidik dan pembangun untuk mencipta teknologi dan kaedah yang boleh mengoptimumkan lagi algoritma asas untuk mencipta ekosistem pengkomputeran yang lebih teguh dan mampan.

Atas ialah kandungan terperinci AI menulis semula algoritma pengisihan dan 70% lebih pantas: DeepMind AlphaDev menginovasi asas pengkomputeran dan memanggil trilion kemas kini perpustakaan setiap hari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!