전역 변수는 데이터 저장을 위한 보물 같은 검입니다. 희소 배열. 3부

이전 부분에서 (1, 2) 우리는 전역을 트리로 이야기했는데, 여기서는 전역을 희소 배열로 살펴보겠습니다.

희소 배열 대부분의 값이 동일한 값을 갖는 배열 유형입니다.

실제로 희소 배열은 크기가 너무 커서 동일한 요소로 메모리를 점유할 필요가 없는 경우가 많습니다. 따라서 동일한 값을 저장하는 데 메모리가 낭비되지 않는 방식으로 희소 배열을 구현하는 것이 합리적입니다.
일부 프로그래밍 언어에서는 언어 자체에 희소 배열이 포함되어 있습니다. 예를 들어 J에서, Matlab. 다른 프로그래밍 언어에는 이를 구현할 수 있는 특수 라이브러리가 있습니다. C++의 경우 - 아이겐 기타

전역 변수는 다음과 같은 이유로 희소 배열을 구현하기에 좋은 후보입니다.

1. 특정 노드의 값만 저장하고 정의되지 않은 노드의 값은 저장하지 않습니다.
2. 노드의 값에 액세스하기 위한 인터페이스는 다차원 배열 요소에 대한 액세스를 구현하는 프로그래밍 언어 수와 매우 유사합니다.

   Set ^a(1, 2, 3)=5
   Write ^a(1, 2, 3)

3. 글로벌은 데이터를 저장하기 위한 상당히 낮은 수준의 구조이므로 뛰어난 속도 특성을 가지고 있습니다(하드웨어에 따라 초당 수십만에서 수천만 건의 트랜잭션, 아래 참조). 1)

전역은 지속적인 구조이기 때문에 RAM의 양이 충분하지 않다는 것을 미리 알고 있는 경우 전역 배열에 희소 배열을 만드는 것이 합리적입니다.

희소 배열 구현의 속성 중 하나는 정의되지 않은 셀에 액세스하는 경우 일부 기본값을 반환하는 것입니다.

이는 함수를 사용하여 구현할 수 있습니다. $GET COS에서 이 예에서는 3차원 배열을 고려합니다.

SET a = $GET(^a(x,y,z), defValue)

희소 배열이 필요한 작업은 무엇이며 전역이 어떻게 도움이 될 수 있습니까?

인접(연결) 매트릭스

이러한 행렬 그래프를 나타내는 데 사용됩니다.

분명히 그래프가 클수록 행렬에 XNUMX이 더 많아집니다. 예를 들어, 소셜 네트워크 그래프를 비슷한 행렬의 형태로 표현한다면 거의 전적으로 XNUMX으로 구성될 것입니다. 희소 배열이 됩니다.

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
....

이 예에서는 전 세계적으로 저장합니다. ^m 연결성 매트릭스와 각 노드의 에지 수(누가 누구와 친구인지, 친구 수).

그래프의 요소 수가 29만 개 이하인 경우(이 숫자는 8 *의 곱으로 간주됩니다. 최대 라인 크기), 즉 이러한 행렬을 저장하는 훨씬 더 경제적인 방법은 비트 문자열입니다. 그 구현은 특별한 방법으로 큰 간격을 최적화하기 때문입니다.

비트 문자열을 사용한 조작은 함수에 의해 수행됩니다. $비트.

; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)

상태 머신 전환 테이블

유한 오토마타의 전이 그래프는 일반 그래프이므로 유한 오토마타의 전이 테이블은 위에서 설명한 인접 행렬과 동일합니다.

셀룰러 오토마타

가장 유명한 세포자동인형은 게임 "라이프", 이는 규칙(셀에 이웃이 많으면 죽는다)으로 인해 희소 배열입니다.

스티븐 울프램(Stephen Wolfram)은 세포 자동인형이 다음과 같다고 믿습니다. 새로운 과학 분야. 2002년에 그는 1280페이지 분량의 책 A New Kind of Science를 출판했는데, 이 책에서 그는 세포 자동 장치의 발전이 고립된 것이 아니라 지속적이고 과학의 모든 영역에 큰 영향을 미친다고 광범위하게 주장했습니다.

컴퓨터에서 실행 가능한 모든 알고리즘은 셀룰러 자동 장치를 사용하여 구현할 수 있다는 것이 입증되었습니다. 셀룰러 오토마타는 동적 환경과 시스템을 모델링하고, 알고리즘 문제를 해결하고, 기타 목적으로 사용됩니다.

거대한 필드가 있고 셀룰러 자동 장치의 모든 중간 상태를 기록해야 한다면 전역을 사용하는 것이 합리적입니다.

지도 작성

희소 배열을 사용할 때 가장 먼저 떠오르는 것은 매핑 작업입니다.

일반적으로 지도에는 빈 공간이 많이 있습니다. 지도가 큰 픽셀로 표현된다면 지구 픽셀의 71%가 바다가 차지하게 됩니다. 희소 배열. 그리고 사람의 손으로 만든 작품만 적용하면 빈 공간이 95% 이상이 됩니다.

물론 래스터 배열 형태로 지도를 저장하는 사람은 없으며 벡터 표현이 사용됩니다.
그런데 벡터 지도란 무엇입니까? 이것은 일종의 프레임과 점으로 구성된 폴리라인과 폴리곤입니다.
본질적으로 포인트와 포인트 간의 연결에 대한 데이터베이스입니다.

가장 야심 찬 매핑 임무 중 하나는 우리 은하계를 매핑하는 가이아 망원경 임무입니다. 비 유적으로 말하면, 우리 은하계는 전체 우주와 마찬가지로 연속적인 희소 배열입니다. 희귀한 작은 점인 별이 있는 거대한 공허 공간입니다. 빈 공간은 99,999999…….%입니다. 우리 은하계의 지도를 저장하기 위해 글로벌 데이터베이스인 Caché가 선택되었습니다.

이 프로젝트의 전역 변수의 정확한 구조를 모르지만 다음과 유사하다고 가정할 수 있습니다.

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는 은하 좌표 위도, 경도 그리고 태양까지의 거리.

전역의 유연한 구조를 사용하면 전역의 기반이 구성표가 없기 때문에 별과 행성의 필요한 특성을 저장할 수 있습니다.

우리 우주의 지도를 저장하기 위해 Caché는 유연성뿐만 아니라 데이터 스트림을 매우 빠르게 저장하는 동시에 빠른 검색을 위해 인덱스 전역을 생성하는 능력 때문에 선택되었습니다.

우리가 지구로 돌아오면 전 세계에 지도 제작 프로젝트가 생성됩니다. 오픈스트리트맵 XAPI 그리고 OpenStreetMap의 포크 - 포스엠.

최근에 해커톤 캐시 지리공간 색인이 구현되었습니다. 지리 공간. 우리는 구현 세부 사항이 포함된 작성자의 기사를 기다리고 있습니다.

OpenStreetMap XAPI에서 글로벌 공간 인덱스 구현

에서 찍은 사진 이 프레젠테이션.

전체 지구본은 정사각형, 하위 정사각형으로 나뉘고 하위 정사각형은 하위 하위 정사각형 등으로 나뉩니다. 일반적으로 우리는 생성된 전역 변수를 저장하기 위한 계층적 구조를 얻습니다.

언제든지 원하는 스퀘어를 거의 즉각적으로 요청하거나 삭제할 수 있으며, 모든 하위 스퀘어도 반환되거나 삭제됩니다.

전역에 대한 유사한 체계는 여러 가지 방법으로 구현될 수 있습니다.

옵션 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ВторойТочки
...

옵션 2 :

Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...

두 경우 모두 COS/M을 사용하여 모든 레벨의 사각형에 위치한 포인트를 요청하는 것은 어렵지 않습니다. 첫 번째 옵션에서는 모든 수준에서 정사각형 공간을 청소하는 것이 다소 쉬울 수 있지만 이는 거의 필요하지 않습니다.

낮은 수준의 사각형 중 하나의 예:

다음은 XAPI 프로젝트의 여러 전역 항목입니다. 전역 항목에 대한 인덱스 표현입니다.

글로벌 ^방식 포인트를 저장하는 데 사용됩니다. 폴리라인 (도로, 작은 강 등) 및 다각형(폐쇄 구역: 건물, 숲 등).

전역에서 희소 배열 사용을 대략적으로 분류합니다.

1. 특정 객체의 좌표와 상태(매핑, 셀룰러 오토마타)를 저장합니다.
2. 희소 행렬을 저장합니다.

2)의 경우 요소에 값이 할당되지 않은 특정 좌표를 요청할 때 기본 희소 배열 요소의 값을 가져와야 합니다.

다차원 행렬을 전역에 저장할 때 받는 보너스

행, 평면, 큐브 등의 배수인 공간 조각을 빠르게 제거 및/또는 선택합니다. 정수 인덱스가 사용되는 경우 행, 평면, 큐브 등의 배수인 공간 덩어리를 신속하게 제거 및/또는 가져오는 기능이 유용할 수 있습니다.

팀 죽이다 단일 요소나 행, 심지어 전체 평면을 삭제할 수도 있습니다. 전역 속성 덕분에 이는 매우 빠르게 발생합니다. 즉, 요소별 제거보다 수천 배 더 빠릅니다.

그림은 전역 배열의 XNUMX차원 배열을 보여줍니다. ^a 다양한 유형의 삭제가 가능합니다.

알려진 인덱스를 사용하여 공간 조각을 선택하려면 다음 명령을 사용할 수 있습니다. 병합.

열 변수에 행렬 열 선택:

; Зададим трёхмерный разреженный массив 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

결론 :

Column(0)=1
Column(2)=1

Column 변수에 대한 흥미로운 점은 희소 배열도 있다는 것입니다. 이 배열은 다음을 통해 액세스해야 합니다. $GET, 기본값이 저장되지 않기 때문입니다.

공간 선택은 기능을 사용하여 작은 프로그램을 통해 수행할 수도 있습니다. $주문. 이는 인덱스가 양자화되지 않은 공간(지도 제작)에서 특히 편리합니다.

결론

현재 시대는 새로운 야심찬 과제를 제시하고 있습니다. 그래프는 수십억 개의 정점으로 구성될 수 있고, 지도는 수십억 개의 점으로 구성될 수 있으며, 일부는 셀룰러 오토마타에서 자체 우주를 실행하기를 원할 수도 있습니다(1, 2).

희소 배열의 데이터 볼륨이 더 이상 RAM에 맞지 않지만 이를 사용하여 작업해야 하는 경우 전역 및 COS에서 유사한 프로젝트를 구현할 가능성을 고려해 볼 가치가 있습니다.

관심을 가져주셔서 감사합니다! 댓글로 여러분의 질문과 희망사항을 기다리고 있습니다.

책임 부인: 이 기사와 이에 대한 내 의견은 내 의견이며 InterSystems Corporation의 공식 입장과 관련이 없습니다.

출처 : habr.com