Önceki bölümlerde (, ) küresellerden ağaçlar olarak bahsettik, bu sefer küresellere seyrek diziler olarak bakacağız.
değerlerin çoğunun aynı değeri aldığı dizi türüdür.
Pratikte seyrek diziler genellikle o kadar büyüktür ki hafızayı aynı öğelerle doldurmanın bir anlamı yoktur. Bu nedenle, seyrek dizileri, belleğin aynı değerleri depolamak için boşa harcanmayacağı şekilde uygulamak mantıklıdır.
Bazı programlama dillerinde seyrek diziler dilin kendisinde bulunur, , . Diğer programlama dillerinde bunları uygulamanıza olanak tanıyan özel kütüphaneler bulunur. C++ için - vb
Globaller seyrek dizileri uygulamak için iyi adaylardır çünkü:
- Yalnızca belirli düğümlerin değerlerini saklarlar ve tanımlanmamış olanların değerlerini saklamazlar;
- Bir düğümün değerine erişmeye yönelik arayüz, çok boyutlu bir dizi öğesine erişimi uygulayan programlama dillerinin sayısına son derece benzer.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global, verileri depolamak için oldukça düşük seviyeli bir yapıdır, bu nedenle olağanüstü hız özelliklerine sahiptir (donanımlara bağlı olarak saniyede yüz binlerce ila on milyonlarca işlem, aşağıya bakın). )
Global kalıcı bir yapı olduğundan RAM miktarının yeterli olmayacağı önceden bilindiğinde üzerlerinde seyrek diziler oluşturmak mantıklıdır.
Seyrek dizi uygulamalarının özelliklerinden biri, tanımlanmamış bir hücreye erişim yapıldığında bazı varsayılan değerleri döndürmektir.
Bu fonksiyon kullanılarak uygulanabilir COS'ta. Bu örnekte 3 boyutlu bir dizi ele alınmaktadır.
SET a = $GET(^a(x,y,z), defValue)Hangi görevler seyrek diziler gerektirir ve geneller nasıl yardımcı olabilir?
Bitişiklik (bağlantı) matrisi
grafikleri temsil etmek için kullanılır:
Açıkçası, grafik ne kadar büyük olursa matriste o kadar fazla sıfır olacaktır. Örneğin, bir sosyal ağ grafiğini alıp benzer bir matris biçiminde sunarsak, neredeyse tamamen sıfırlardan oluşacaktır, yani. seyrek bir dizi olacak.
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
....
Bu örnekte global olarak tasarruf ediyoruz ^m bağlantı matrisinin yanı sıra her düğümdeki kenar sayısı (kimin kiminle arkadaş olduğu ve arkadaş sayısı).
Grafikteki eleman sayısı 29 milyondan fazla değilse (bu sayı 8*'in çarpımı olarak alınır) ), yani bu tür matrisleri saklamanın daha da ekonomik bir yolu bit dizeleridir, çünkü bunların uygulanması büyük boşlukları özel bir şekilde optimize eder.
Bit dizeleriyle yapılan manipülasyonlar işlev tarafından gerçekleştirilir .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Durum makinesi geçiş tablosu
Sonlu bir otomatın geçiş grafiği sıradan bir grafik olduğundan, sonlu otomatın geçiş tablosu yukarıda tartışılan aynı bitişiklik matrisidir.
Hücresel otomat
En ünlü hücresel otomat kuralları nedeniyle (bir hücrenin çok sayıda komşusu olduğunda ölür) seyrek bir dizidir.
Stephen Wolfram hücresel otomatların . 2002 yılında, 1280 sayfalık A New Kind of Science adlı kitabını yayımladı; bu kitapta hücresel otomatadaki gelişmelerin izole olmadığını, kalıcı olduğunu ve bilimin tüm alanları için büyük etkileri olduğunu genel olarak tartışıyor.
Bilgisayarda çalıştırılabilen herhangi bir algoritmanın hücresel otomat kullanılarak uygulanabileceği kanıtlanmıştır. Hücresel otomatlar dinamik ortamları ve sistemleri modellemek, algoritmik problemleri çözmek ve diğer amaçlar için kullanılır.
Eğer çok büyük bir alanımız varsa ve bir hücresel otomatın tüm ara durumlarını kaydetmemiz gerekiyorsa, o zaman globalleri kullanmak mantıklıdır.
Haritacılık
Seyrek dizileri kullanmak denildiğinde aklıma ilk gelen şey haritalama görevleridir.
Kural olarak haritalarda çok fazla boş alan var. Harita büyük piksellerle temsil edilirse, Dünya'nın piksellerinin %71'i okyanus tarafından kaplanacaktır. Seyrek dizi. Ve yalnızca insan elinin eserlerini uygularsanız, boş alan% 95'ten fazla olacaktır.
Elbette hiç kimse haritaları raster dizileri biçiminde saklamaz; bir vektör gösterimi kullanılır.
Peki vektör haritaları nedir? Bu bir çeşit çerçeve ve noktalardan oluşan çoklu çizgiler ve çokgenlerdir.
Temel olarak noktalar ve bunlar arasındaki bağlantılardan oluşan bir veritabanı.
En iddialı haritalama görevlerinden biri Gaia Teleskobu'nun galaksimizi haritalandırma görevidir. Mecazi anlamda konuşursak, galaksimiz, tüm evren gibi, sürekli ve seyrek bir dizidir: nadir küçük noktaların (yıldızların) bulunduğu devasa boşluk alanları. Boş alan %99,999999…….'dur. Galaksimizin haritasını saklamak için küresel bir veritabanı seçildi - Caché.
Bu projedeki globallerin tam yapısını bilmiyorum, bunun şuna benzer bir şey olduğunu varsayabilirim:
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
...
b, l, d nerede ve Güneş'e olan uzaklık.
Küresellerin esnek yapısı, yıldızların ve gezegenlerin gerekli özelliklerini korumanıza olanak tanır, çünkü küresellerin temelleri şemasızdır.
Evrenimizin haritasını depolamak için Caché, yalnızca esnekliği nedeniyle değil, aynı zamanda bir veri akışını çok hızlı bir şekilde depolayabilmesi ve aynı zamanda hızlı aramalar için küresel dizinler oluşturabilmesi nedeniyle seçildi.
Dünya'ya dönersek, küresellerde kartografik projeler yaratıldı ve bir OpenStreetMap çatalı - .
Son zamanlarda coğrafi indeksler uygulandı . Yazarlardan uygulama detaylarını içeren bir makale bekliyoruz.
OpenStreetMap XAPI'de mekansal indekslerin global olarak uygulanması
Resimler şuradan alınmıştır: .
Dünyanın tamamı karelere, ardından alt karelere ve alt kareler, alt alt karelere vb. bölünür. Genel olarak hangi globallerin oluşturulduğunu depolamak için hiyerarşik bir yapı elde ederiz.
İstediğimiz kareyi neredeyse anında talep edebilir veya temizleyebiliriz; ayrıca tüm alt kareler de geri döndürülecek veya temizlenecektir.
Küreseller üzerinde benzer bir plan çeşitli şekillerde uygulanabilir.
Seçenek 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ВторойТочки
...Seçenek 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Her iki durumda da herhangi bir seviyedeki karede yer alan noktaları talep etmek için COS/M'yi kullanmak zor değildir. İlk seçenekte kare şeklindeki alan parçalarını herhangi bir seviyede temizlemek biraz daha kolay olacaktır, ancak bu nadiren gerekli olur.
Alt seviyedeki karelerden birine bir örnek:
Ve işte XAPI projesinden birkaç global: bir indeksin globaller üzerinde temsili:
Küresel ^ yol noktaları depolamak için kullanılır (yollar, küçük nehirler vb.) ve çokgenler (kapalı alanlar: binalar, ormanlar vb.).
Küresel dizilerde seyrek dizilerin kullanımının kaba sınıflandırması.
- Belirli nesnelerin koordinatlarını ve durumlarını saklıyoruz (haritalama, hücresel otomatlar)
- Seyrek matrisleri saklıyoruz.
Durum 2) için, öğeye bir değer atanmamış belirli bir koordinat istenirken, varsayılan seyrek dizi öğesinin değerini almalıyız.
Çok boyutlu matrisleri globallerde saklarken aldığımız bonuslar
Satırların, düzlemlerin, küplerin vb. katları olan alan parçalarını hızla kaldırın ve/veya seçin. Tamsayı indekslerinin kullanıldığı durumlarda, satırların, düzlemlerin, küplerin vb. katları olan alan parçalarını hızlı bir şekilde kaldırma ve/veya getirme yeteneği yararlı olabilir.
takım tek bir öğeyi, bir satırı, hatta bir düzlemin tamamını silebiliriz. Küresellerin özellikleri sayesinde bu çok hızlı bir şekilde gerçekleşir; öğelerin tek tek çıkarılmasından binlerce kat daha hızlı.
Şekil küresel ölçekte üç boyutlu bir diziyi göstermektedir. ^a ve farklı silme türleri.
Bilinen indeksleri kullanarak alan parçalarını seçmek için şu komutu kullanabilirsiniz: .
Sütun değişkenine bir matris sütunu seçme:
; Зададим трёхмерный разреженный массив 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
Sonuç:
Column(0)=1
Column(2)=1
Sütun değişkeninin ilginç yanı, aynı zamanda üzerinden erişilmesi gereken seyrek bir diziye de sahip olmamızdır. , çünkü varsayılan değerler içinde saklanmaz.
İşlev kullanılarak küçük bir program aracılığıyla alan parçalarının seçilmesi de yapılabilir. . Bu özellikle indeksleri nicelenmemiş (haritacılık) alanlarda kullanışlıdır.
Sonuç
İçinde bulunduğumuz zamanlar yeni iddialı görevleri ortaya çıkarıyor. Grafikler milyarlarca köşeden, haritalar milyarlarca noktadan oluşabilir ve hatta bazıları kendi evrenlerini hücresel otomatlar üzerinde çalıştırmak isteyebilir (, ).
Seyrek dizilerden gelen veri hacmi artık RAM'e sığamadığında, ancak onlarla çalışmanız gerektiğinde, benzer projeleri globals ve COS üzerinde uygulama olasılığını düşünmeye değer.
İlginiz için teşekkür ederiz! Soru ve dileklerinizi yorumlara bekliyoruz.
Feragatname: Bu makale ve ona ilişkin yorumlarım benim görüşümdür ve InterSystems Corporation'ın resmi konumuyla hiçbir ilgisi yoktur.
Kaynak: habr.com