Di bagian sebelumnya (, ) kita membicarakan global sebagai pohon, kali ini kita akan melihat global sebagai array yang jarang.
adalah jenis array yang sebagian besar nilainya mengambil nilai yang sama.
Dalam praktiknya, array renggang seringkali berukuran sangat besar sehingga tidak ada gunanya menempati memori dengan elemen yang identik. Oleh karena itu, masuk akal untuk mengimplementasikan array renggang sedemikian rupa sehingga memori tidak terbuang percuma untuk menyimpan nilai yang identik.
Dalam beberapa bahasa pemrograman, sparse array disertakan dalam bahasa itu sendiri, , . Bahasa pemrograman lain memiliki perpustakaan khusus yang memungkinkan Anda mengimplementasikannya. Untuk C++ - dan lain-lain
Global adalah kandidat yang baik untuk mengimplementasikan sparse array karena:
- Mereka hanya menyimpan nilai dari node tertentu dan tidak menyimpan nilai dari node yang tidak ditentukan;
- Antarmuka untuk mengakses nilai node sangat mirip dengan berapa banyak bahasa pemrograman yang menerapkan akses ke elemen array multidimensi.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global adalah struktur penyimpanan data tingkat rendah, oleh karena itu ia memiliki karakteristik kecepatan yang luar biasa (dari ratusan ribu hingga puluhan juta transaksi per detik, tergantung pada perangkat kerasnya, lihat di bawah). )
Karena global adalah struktur yang persisten, masuk akal untuk membuat array yang jarang pada struktur tersebut ketika diketahui sebelumnya bahwa jumlah RAM tidak akan cukup.
Salah satu properti implementasi array renggang adalah mengembalikan beberapa nilai default jika akses dilakukan ke sel yang tidak ditentukan.
Ini dapat diimplementasikan menggunakan fungsi tersebut di KOS. Contoh ini membahas array 3 dimensi.
SET a = $GET(^a(x,y,z), defValue)Tugas apa yang memerlukan sparse array dan bagaimana global bisa membantu?
Matriks ketetanggaan (konektivitas).
digunakan untuk mewakili grafik:
Jelasnya, semakin besar grafiknya, semakin banyak pula angka nol dalam matriksnya. Jika, misalnya, kita mengambil grafik jejaring sosial dan menyajikannya dalam bentuk matriks serupa, maka hampir seluruhnya terdiri dari nol, yaitu. akan menjadi array yang jarang.
Set ^m(id1, id2) = 1
Set ^m(id1, id3) = 1
Set ^m(id1, id4) = 1
Set ^m(id1) = 3
Set ^m(id2, id4) = 1
Set ^m(id2, id5) = 1
Set ^m(id2) = 2
....
Dalam contoh ini, kami menyimpan secara global ^m matriks konektivitas, serta jumlah edge pada setiap node (siapa berteman dengan siapa dan jumlah teman).
Jika jumlah unsur pada grafik tidak lebih dari 29 juta (bilangan ini diambil hasil kali 8 * ), artinya, cara yang lebih ekonomis untuk menyimpan matriks tersebut adalah string bit, karena implementasinya mengoptimalkan celah yang besar dengan cara yang khusus.
Manipulasi dengan string bit dilakukan oleh fungsi .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Tabel transisi mesin negara
Karena grafik transisi otomat berhingga merupakan graf biasa, maka tabel transisi otomat berhingga merupakan matriks ketetanggaan yang sama seperti yang dibahas di atas.
Automata seluler
Robot seluler yang paling terkenal adalah , yang karena aturannya (bila sel memiliki banyak tetangga, sel tersebut mati) adalah array yang jarang.
Stephen Wolfram percaya bahwa automata seluler memang demikian . Pada tahun 2002, ia menerbitkan buku setebal 1280 halaman, A New Kind of Science, di mana ia berpendapat secara luas bahwa kemajuan dalam automata seluler tidak berdiri sendiri, namun bertahan lama dan mempunyai implikasi besar bagi semua bidang ilmu pengetahuan.
Telah terbukti bahwa algoritma apa pun yang dapat dieksekusi di komputer dapat diimplementasikan menggunakan otomat seluler. Automata seluler digunakan untuk memodelkan lingkungan dan sistem yang dinamis, untuk memecahkan masalah algoritmik, dan untuk tujuan lainnya.
Jika kita memiliki bidang yang sangat besar dan kita perlu mencatat semua keadaan peralihan dari otomat seluler, maka masuk akal untuk menggunakan global.
Pemetaan
Hal pertama yang terlintas dalam pikiran saya ketika menggunakan array renggang adalah tugas pemetaan.
Biasanya, ada banyak ruang kosong di peta. Jika peta direpresentasikan sebagai piksel besar, maka 71% piksel bumi akan ditempati oleh lautan. Array yang jarang. Dan jika yang diterapkan hanya karya tangan manusia, maka ruang kosongnya akan lebih dari 95%.
Tentu saja, tidak ada yang menyimpan peta dalam bentuk array raster, representasi vektor digunakan.
Tapi apa itu peta vektor? Ini adalah semacam bingkai dan polyline serta poligon yang terdiri dari titik-titik.
Pada dasarnya database poin dan koneksi di antara mereka.
Salah satu misi pemetaan paling ambisius adalah misi Teleskop Gaia untuk memetakan galaksi kita. Secara kiasan, galaksi kita, seperti seluruh alam semesta, adalah susunan yang jarang dan berkesinambungan: ruang kosong yang sangat besar di mana terdapat titik-titik kecil yang langka - bintang. Ruang kosong adalah 99,999999…….%. Untuk menyimpan peta galaksi kita, database global dipilih - Cache.
Saya tidak tahu persis struktur global dalam proyek ini, saya dapat berasumsi bahwa ini mirip dengan:
Set ^galaxy(b, l, d) = 1; Номер звезды по каталогу, если есть
Set ^galaxy(b, l, d, "name") = "Sun"
Set ^galaxy(b, l, d, "type") = "normal" ; варианты blackhole, quazar, red_dwarf и т.д.
Set ^galaxy(b, l, d, "weight") = 14E50
Set ^galaxy(b, l, d, "planetes") = 7
Set ^galaxy(b, l, d, "planetes", 1) = "Mercury"
Set ^galaxy(b, l, d, "planetes", 1, weight) = 1E20
...
Dimana b, l, d berada dan jarak ke Matahari.
Struktur global yang fleksibel memungkinkan Anda menyimpan karakteristik bintang dan planet yang diperlukan, karena basis global tidak memiliki skema.
Untuk menyimpan peta alam semesta kita, Caché dipilih tidak hanya karena fleksibilitasnya, namun juga karena kemampuannya menyimpan aliran data dengan sangat cepat, sekaligus menciptakan indeks global untuk pencarian cepat.
Jika kita kembali ke Bumi, maka proyek kartografi dibuat secara global dan cabang OpenStreetMap - .
Baru-baru ini aktif indeks geospasial diterapkan . Kami menunggu artikel dari penulis dengan detail implementasi.
Implementasi indeks spasial secara global di OpenStreetMap XAPI
Gambar diambil dari .
Seluruh globe dibagi menjadi beberapa kotak, kemudian sub-kotak, dan sub-kotak menjadi sub-sub-kotak, dan seterusnya. Secara umum, kita mendapatkan struktur hierarki untuk menyimpan global yang dibuat.
Kapan saja, kami dapat langsung meminta kotak yang diinginkan atau menghapusnya, dan semua subkotak juga akan dikembalikan atau dibersihkan.
Skema serupa di tingkat global dapat diterapkan dengan beberapa cara.
Option 1:
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 1) = idПервойТочки
Set ^m(a, b, a, c, d, a, b,c, d, a, b, a, c, d, a, b,c, d, a, 2) = idВторойТочки
...Option 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Dalam kedua kasus tersebut, tidak sulit menggunakan COS/M untuk meminta titik-titik yang terletak di persegi pada tingkat apa pun. Akan lebih mudah untuk membersihkan ruang berbentuk persegi di tingkat mana pun pada opsi pertama, tetapi hal ini jarang diperlukan.
Contoh salah satu kotak tingkat bawah:
Dan berikut beberapa global dari proyek XAPI: representasi indeks pada global:
global ^cara digunakan untuk menyimpan poin (jalan, sungai kecil, dll) dan poligon (area tertutup: bangunan, hutan, dll).
Klasifikasi kasar penggunaan array renggang pada global.
- Kami menyimpan koordinat objek tertentu dan statusnya (pemetaan, automata seluler)
- Kami menyimpan matriks renggang.
Untuk kasus 2) ketika meminta koordinat tertentu di mana elemen tidak diberi nilai, kita harus mendapatkan nilai elemen array sparse default.
Bonus yang kami terima saat menyimpan matriks multidimensi di global
Hapus dengan cepat dan/atau pilih bagian ruang yang merupakan kelipatan baris, bidang, kubus, dll. Untuk kasus di mana indeks bilangan bulat digunakan, kemampuan untuk dengan cepat menghapus dan/atau mengambil potongan ruang yang merupakan kelipatan baris, bidang, kubus, dll. mungkin berguna.
tim kita dapat menghapus satu elemen atau satu baris, atau bahkan seluruh bidang. Berkat sifat global, hal ini terjadi dengan sangat cepat - ribuan kali lebih cepat daripada penghapusan elemen demi elemen.
Gambar tersebut menunjukkan array tiga dimensi secara global ^a dan berbagai jenis penghapusan.
Untuk memilih bagian ruang menggunakan indeks yang diketahui, Anda dapat menggunakan perintah .
Memilih kolom matriks ke dalam variabel Kolom:
; Зададим трёхмерный разреженный массив 3x3x3
Set ^a(0,0,0)=1,^a(2,2,0)=1,^a(2,0,1)=1,^a(0,2,1)=1,^a(2,2,2)=1,^a(2,1,2)=1
Merge Column = ^a(2,2)
; Выведем переменную Column
Zwrite Column
Kesimpulan:
Column(0)=1
Column(2)=1
Yang menarik dari variabel Column adalah kita juga memiliki sparse array, yang juga harus diakses melaluinya , karena nilai default tidak disimpan di dalamnya.
Memilih potongan ruang juga dapat dilakukan melalui program kecil menggunakan fungsi tersebut . Hal ini terutama berguna pada ruang yang indeksnya tidak terkuantisasi (kartografi).
Kesimpulan
Saat ini menimbulkan tugas-tugas baru yang ambisius. Grafik dapat terdiri dari milyaran titik, peta dapat terdiri dari milyaran titik, dan beberapa bahkan mungkin ingin menjalankan semesta mereka sendiri pada automata seluler (, ).
Ketika volume data dari array renggang tidak lagi dapat masuk ke dalam RAM, tetapi Anda perlu bekerja dengannya, maka ada baiknya mempertimbangkan kemungkinan untuk mengimplementasikan proyek serupa di global dan COS.
Terima kasih atas perhatian Anda! Kami menunggu pertanyaan dan keinginan Anda di komentar.
Penolakan tanggung jawab: Artikel ini dan komentar saya adalah pendapat saya dan tidak ada hubungannya dengan posisi resmi InterSystems Corporation.
Sumber: www.habr.com