Pada bahagian sebelumnya (, ) kita bercakap tentang global sebagai pokok, dalam yang ini kita akan melihat global sebagai tatasusunan jarang.
ialah sejenis tatasusunan di mana kebanyakan nilai mengambil nilai yang sama.
Dalam praktiknya, tatasusunan jarang selalunya sangat besar sehingga tidak ada gunanya mengisi memori dengan elemen yang sama. Oleh itu, masuk akal untuk melaksanakan tatasusunan jarang sedemikian rupa sehingga ingatan tidak terbuang untuk menyimpan nilai yang sama.
Dalam sesetengah bahasa pengaturcaraan, tatasusunan jarang disertakan dalam bahasa itu sendiri, , . Bahasa pengaturcaraan lain mempunyai perpustakaan khas yang membolehkan anda melaksanakannya. Untuk C++ - dan lain-lain
Globals ialah calon yang baik untuk melaksanakan tatasusunan jarang kerana:
- Mereka menyimpan nilai nod tertentu sahaja dan tidak menyimpan nilai nod yang tidak ditentukan;
- Antara muka untuk mengakses nilai nod sangat serupa dengan bilangan bahasa pengaturcaraan yang melaksanakan akses kepada elemen tatasusunan berbilang dimensi.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global ialah struktur tahap yang agak rendah untuk menyimpan data, oleh itu ia mempunyai ciri kelajuan yang luar biasa (daripada ratusan ribu hingga puluhan juta transaksi sesaat, bergantung pada perkakasan, lihat di bawah). )
Memandangkan global adalah struktur yang berterusan, masuk akal untuk mencipta tatasusunan yang jarang padanya apabila diketahui terlebih dahulu bahawa jumlah RAM tidak akan mencukupi.
Salah satu sifat pelaksanaan tatasusunan jarang adalah untuk mengembalikan beberapa nilai lalai jika akses dibuat kepada sel yang tidak ditentukan.
Ini boleh dilaksanakan menggunakan fungsi dalam COS. Contoh ini mempertimbangkan tatasusunan 3 dimensi.
SET a = $GET(^a(x,y,z), defValue)Apakah tugas yang memerlukan tatasusunan yang jarang dan bagaimanakah global boleh membantu?
Matriks bersebelahan (sambungan).
digunakan untuk mewakili graf:
Jelas sekali, lebih besar graf, lebih banyak sifar akan ada dalam matriks. Jika, sebagai contoh, kita mengambil graf rangkaian sosial dan membentangkannya dalam bentuk matriks yang serupa, maka ia akan hampir keseluruhannya terdiri daripada sifar, i.e. akan menjadi susunan 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 ketersambungan, serta bilangan tepi pada setiap nod (siapa berkawan dengan siapa dan bilangan rakan).
Jika bilangan unsur dalam graf tidak lebih daripada 29 juta (nombor ini diambil sebagai hasil darab 8 * ), iaitu, cara yang lebih menjimatkan untuk menyimpan matriks sedemikian ialah rentetan bit, kerana pelaksanaannya mengoptimumkan jurang yang besar dengan cara yang istimewa.
Manipulasi dengan rentetan bit dilakukan oleh fungsi .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Jadual peralihan mesin negeri
Oleh kerana graf peralihan bagi automata terhingga ialah graf biasa, maka jadual peralihan bagi automata terhingga ialah matriks bersebelahan yang sama yang dibincangkan di atas.
Automata selular
Automatik selular yang paling terkenal ialah , yang, disebabkan oleh peraturannya (apabila sel mempunyai banyak jiran, ia mati) adalah tatasusunan yang jarang.
Stephen Wolfram percaya bahawa automata selular adalah . Pada tahun 2002, beliau menerbitkan sebuah buku setebal 1280 halaman, A New Kind of Science, di mana beliau secara meluas berhujah bahawa kemajuan dalam automata selular tidak terpencil, tetapi berkekalan dan mempunyai implikasi yang besar untuk semua bidang sains.
Telah terbukti bahawa mana-mana algoritma boleh laku pada komputer boleh dilaksanakan menggunakan automaton selular. Automata selular digunakan untuk memodelkan persekitaran dan sistem dinamik, untuk menyelesaikan masalah algoritma dan untuk tujuan lain.
Jika kita mempunyai bidang yang besar dan kita perlu merekodkan semua keadaan perantaraan automasi selular, maka masuk akal untuk menggunakan global.
Kartografi
Perkara pertama yang terlintas di fikiran saya apabila menggunakan tatasusunan jarang ialah tugasan pemetaan.
Sebagai peraturan, terdapat banyak ruang kosong pada peta. Jika peta diwakili sebagai piksel besar, maka 71% daripada piksel Bumi akan diduduki oleh lautan. Susunan jarang. Dan jika anda hanya menggunakan kerja tangan manusia, maka ruang kosong akan menjadi lebih daripada 95%.
Sudah tentu, tiada siapa yang menyimpan peta dalam bentuk tatasusunan raster digunakan.
Tetapi apakah itu peta vektor? Ini adalah sejenis bingkai dan poligaris dan poligon yang terdiri daripada titik.
Pada asasnya pangkalan data mata dan sambungan antara mereka.
Salah satu misi pemetaan yang paling bercita-cita tinggi ialah misi Teleskop Gaia untuk memetakan galaksi kita. Secara kiasan, galaksi kita, seperti seluruh alam semesta, adalah susunan jarang berterusan: ruang besar kekosongan yang terdapat titik-titik kecil yang jarang berlaku - bintang. Ruang kosong ialah 99,999999…….%. Untuk menyimpan peta galaksi kita, pangkalan data global telah dipilih - Caché.
Saya tidak tahu struktur sebenar global dalam projek ini, saya boleh mengandaikan bahawa ia adalah sesuatu yang serupa 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
...
Di mana b, l, d berada dan jarak ke Matahari.
Struktur global yang fleksibel membolehkan anda menyimpan sebarang ciri yang diperlukan bagi bintang dan planet, kerana asas pada global adalah tanpa skema.
Untuk menyimpan peta alam semesta kita, Caché dipilih bukan sahaja untuk fleksibilitinya, tetapi juga untuk keupayaannya untuk menyimpan aliran data dengan cepat, pada masa yang sama mencipta indeks global untuk carian pantas.
Jika kita kembali ke Bumi, maka projek kartografi telah dicipta di peringkat global dan cabang OpenStreetMap - .
Baru-baru ini pada indeks geospatial telah dilaksanakan . Kami sedang menunggu artikel daripada penulis dengan butiran pelaksanaan.
Pelaksanaan indeks spatial pada global dalam OpenStreetMap XAPI
Gambar diambil dari .
Seluruh dunia dibahagikan kepada petak, kemudian petak kecil, dan petak kecil menjadi petak kecil, dan seterusnya. Secara umum, kami mendapat struktur hierarki untuk menyimpan global yang dibuat.
Pada bila-bila masa, kami hampir serta-merta boleh meminta petak yang dikehendaki atau mengosongkannya, dan semua petak kecil juga akan dikembalikan atau dikosongkan.
Skim serupa pada global boleh dilaksanakan dalam beberapa cara.
Pilihan 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ВторойТочки
...Pilihan 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Dalam kedua-dua kes, tidak sukar untuk menggunakan COS/M untuk meminta mata yang terletak dalam segi empat sama mana-mana peringkat. Ia akan menjadi lebih mudah untuk membersihkan bahagian persegi ruang di mana-mana peringkat dalam pilihan pertama, tetapi ini jarang diperlukan.
Contoh salah satu petak aras bawah:
Dan berikut adalah beberapa global daripada projek XAPI: perwakilan indeks pada global:
Global ^ cara digunakan untuk menyimpan mata (jalan raya, sungai kecil, dll.) dan poligon (kawasan tertutup: bangunan, hutan, dll.).
Klasifikasi kasar penggunaan tatasusunan jarang pada global.
- Kami menyimpan koordinat objek tertentu dan keadaannya (pemetaan, automata selular)
- Kami menyimpan matriks jarang.
Untuk kes 2) apabila meminta koordinat khusus di mana elemen tidak diberikan nilai, kita mesti mendapatkan nilai unsur tatasusunan jarang lalai.
Bonus yang kami terima apabila menyimpan matriks multidimensi dalam global
Alih keluar dan/atau pilih cebisan ruang dengan cepat yang merupakan gandaan baris, satah, kiub, dsb. Untuk kes di mana indeks integer digunakan, keupayaan untuk mengalih keluar dan/atau mengambil cebisan ruang dengan cepat yang merupakan gandaan baris, satah, kiub, dsb. mungkin berguna.
pasukan kita boleh memadam sama ada satu elemen atau satu baris, atau malah keseluruhan satah. Terima kasih kepada sifat global, ini berlaku dengan sangat cepat - beribu kali lebih pantas daripada penyingkiran unsur demi unsur.
Rajah menunjukkan tatasusunan tiga dimensi dalam global ^a dan jenis pemadaman yang berbeza.
Untuk memilih bahagian ruang menggunakan indeks yang diketahui, anda boleh menggunakan arahan .
Memilih lajur matriks ke dalam pembolehubah Lajur:
; Зададим трёхмерный разреженный массив 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
Apa yang menarik tentang pembolehubah Lajur ialah kami juga mempunyai tatasusunan yang jarang, yang juga mesti diakses melalui , kerana nilai lalai tidak disimpan di dalamnya.
Memilih cebisan ruang juga boleh dilakukan melalui program kecil menggunakan fungsi tersebut . Ini amat sesuai pada ruang yang indeksnya tidak dikuantisasi (kartografi).
Kesimpulan
Masa kini menimbulkan cabaran bercita-cita tinggi baru. Graf boleh terdiri daripada berbilion-bilion bucu, peta terdiri daripada berbilion-bilion titik, dan ada juga yang mungkin mahu menjalankan alam semesta mereka sendiri pada automata selular (, ).
Apabila jumlah data daripada tatasusunan jarang tidak lagi boleh dimuatkan ke dalam RAM, tetapi anda perlu bekerja dengannya, maka ia patut mempertimbangkan kemungkinan melaksanakan projek serupa pada global dan COS.
Terima kasih kerana memberi perhatian! Kami sedang menunggu soalan dan hasrat anda dalam komen.
Penafian: Artikel ini dan ulasan saya mengenainya adalah pendapat saya dan tidak mempunyai kaitan dengan kedudukan rasmi InterSystems Corporation.
Sumber: www.habr.com