Ở các phần trước (, ) chúng ta đã nói về các hình toàn cầu như những cái cây, trong phần này chúng ta sẽ xem các hình toàn cầu như những mảng thưa thớt.
là một kiểu mảng trong đó hầu hết các giá trị đều có cùng giá trị.
Trong thực tế, các mảng thưa thớt thường rất lớn đến mức không có ích gì khi chiếm bộ nhớ bằng các phần tử giống hệt nhau. Do đó, sẽ hợp lý hơn khi triển khai các mảng thưa thớt theo cách mà bộ nhớ không bị lãng phí khi lưu trữ các giá trị giống hệt nhau.
Trong một số ngôn ngữ lập trình, mảng thưa thớt được bao gồm trong chính ngôn ngữ đó, , . Các ngôn ngữ lập trình khác có các thư viện đặc biệt cho phép bạn triển khai chúng. Đối với C++ - vv
Globals là ứng cử viên tốt để triển khai mảng thưa thớt vì:
- Chúng chỉ lưu trữ giá trị của một số nút nhất định và không lưu trữ giá trị của các nút không xác định;
- Giao diện truy cập giá trị của một nút cực kỳ giống với cách nhiều ngôn ngữ lập trình thực hiện quyền truy cập vào một phần tử mảng đa chiều.
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global là cấu trúc cấp thấp để lưu trữ dữ liệu nên có đặc tính tốc độ vượt trội (từ hàng trăm nghìn đến hàng chục triệu giao dịch mỗi giây, tùy thuộc vào phần cứng, xem bên dưới). )
Vì toàn cục là một cấu trúc bền vững nên việc tạo các mảng thưa thớt trên chúng là điều hợp lý khi biết trước rằng dung lượng RAM sẽ không đủ.
Một trong những đặc tính của việc triển khai mảng thưa thớt là trả về một số giá trị mặc định nếu có quyền truy cập vào một ô không xác định.
Điều này có thể được thực hiện bằng cách sử dụng chức năng trong COS. Ví dụ này xem xét một mảng 3 chiều.
SET a = $GET(^a(x,y,z), defValue)Những nhiệm vụ nào yêu cầu mảng thưa thớt và toàn cầu có thể trợ giúp như thế nào?
Ma trận liền kề (kết nối)
dùng để biểu diễn đồ thị:
Rõ ràng, đồ thị càng lớn thì càng có nhiều số 0 trong ma trận. Ví dụ: nếu chúng ta lấy một biểu đồ mạng xã hội và trình bày nó dưới dạng một ma trận tương tự, thì nó sẽ gần như hoàn toàn bao gồm các số 0, tức là. sẽ là một mảng thưa thớt.
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
....
Trong ví dụ này, chúng tôi lưu trên toàn cầu ^m ma trận kết nối, cũng như số cạnh tại mỗi nút (ai là bạn với ai và số lượng bạn bè).
Nếu số phần tử trong đồ thị không quá 29 triệu (con số này được lấy là tích của 8 * ), nghĩa là, một cách thậm chí còn tiết kiệm hơn để lưu trữ các ma trận như vậy là sử dụng chuỗi bit, vì việc triển khai chúng sẽ tối ưu hóa các khoảng trống lớn theo một cách đặc biệt.
Các thao tác với chuỗi bit được thực hiện bởi hàm .
; установка бита
SET $BIT(rowID, positionID) = 1
; получение бита
Write $BIT(rowID, positionID)
Bảng chuyển đổi trạng thái máy
Vì đồ thị chuyển tiếp của máy tự động hữu hạn là một đồ thị thông thường nên bảng chuyển đổi của máy tự động hữu hạn chính là ma trận kề đã thảo luận ở trên.
Automata di động
Máy di động tự động nổi tiếng nhất là , do quy tắc của nó (khi một ô có nhiều ô lân cận, nó sẽ chết) là một mảng thưa thớt.
Stephen Wolfram tin rằng các máy tự động của tế bào là . Năm 2002, ông xuất bản một cuốn sách dài 1280 trang, Một loại khoa học mới, trong đó ông lập luận rộng rãi rằng những tiến bộ trong máy tự động tế bào không bị cô lập mà tồn tại lâu dài và có ý nghĩa to lớn đối với mọi lĩnh vực khoa học.
Người ta đã chứng minh rằng bất kỳ thuật toán nào thực thi được trên máy tính đều có thể được thực hiện bằng cách sử dụng máy tự động di động. Máy tự động di động được sử dụng để mô hình hóa các môi trường và hệ thống động, để giải quyết các vấn đề thuật toán và cho các mục đích khác.
Nếu chúng ta có một trường lớn và chúng ta cần ghi lại tất cả các trạng thái trung gian của máy tự động di động, thì việc sử dụng toàn cục là hợp lý.
bản đồ học
Điều đầu tiên tôi nghĩ đến khi sử dụng mảng thưa thớt là các tác vụ ánh xạ.
Theo quy định, có rất nhiều khoảng trống trên bản đồ. Nếu bản đồ được thể hiện dưới dạng pixel lớn thì 71% pixel của Trái đất sẽ bị đại dương chiếm giữ. Mảng thưa thớt. Và nếu bạn chỉ áp dụng các tác phẩm của bàn tay con người thì khoảng trống sẽ lên tới hơn 95%.
Tất nhiên, không ai lưu trữ bản đồ dưới dạng mảng raster; biểu diễn vectơ được sử dụng.
Nhưng bản đồ vector là gì? Đây là một loại khung và polylines và đa giác bao gồm các điểm.
Về cơ bản là cơ sở dữ liệu về các điểm và kết nối giữa chúng.
Một trong những sứ mệnh lập bản đồ đầy tham vọng nhất là sứ mệnh Kính viễn vọng Gaia để lập bản đồ thiên hà của chúng ta. Nói một cách hình tượng, thiên hà của chúng ta, giống như toàn bộ vũ trụ, là một mảng thưa thớt liên tục: những không gian trống rỗng rộng lớn trong đó có những điểm nhỏ hiếm hoi - những ngôi sao. Chỗ trống là 99,999999…….%. Để lưu trữ bản đồ thiên hà của chúng ta, một cơ sở dữ liệu toàn cầu đã được chọn - Caché.
Tôi không biết cấu trúc chính xác của toàn cầu trong dự án này, tôi có thể cho rằng nó tương tự như:
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
...
Trong đó b, l, d là và khoảng cách tới Mặt Trời.
Cấu trúc linh hoạt của hình cầu cho phép bạn lưu bất kỳ đặc điểm cần thiết nào của các ngôi sao và hành tinh, vì các cơ sở trên hình cầu không có sơ đồ.
Để lưu trữ bản đồ vũ trụ của chúng ta, Caché được chọn không chỉ vì tính linh hoạt mà còn vì khả năng lưu trữ luồng dữ liệu rất nhanh, đồng thời tạo chỉ mục toàn cầu để tìm kiếm nhanh.
Nếu chúng ta quay trở lại Trái đất, thì các dự án bản đồ đã được tạo trên toàn cầu và một nhánh của OpenStreetMap - .
Gần đây trên chỉ số không gian địa lý đã được thực hiện . Chúng tôi đang chờ đợi một bài viết từ các tác giả với chi tiết thực hiện.
Triển khai các chỉ mục không gian trên toàn cầu trong OpenStreetMap XAPI
Hình ảnh được chụp từ .
Toàn bộ quả địa cầu được chia thành các hình vuông, sau đó là các ô vuông phụ và các ô vuông phụ thành các ô vuông phụ, v.v. Nói chung, chúng ta có một cấu trúc phân cấp để lưu trữ những toàn cầu nào được tạo.
Tại bất kỳ thời điểm nào, chúng tôi gần như có thể yêu cầu hoặc xóa hình vuông mong muốn ngay lập tức và tất cả các ô vuông phụ cũng sẽ được trả lại hoặc xóa.
Một sơ đồ tương tự trên toàn cầu có thể được thực hiện theo nhiều cách.
Lựa chọn 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ВторойТочки
...Lựa chọn 2:
Set ^m('abacdabcdabacdabcda', 1) = idПервойТочки
Set ^m('abacdabcdabacdabcda', 2) = idВторойТочки
...Trong cả hai trường hợp, không khó để sử dụng COS/M để yêu cầu các điểm nằm trong một hình vuông ở bất kỳ cấp độ nào. Sẽ dễ dàng hơn một chút để làm sạch các mảnh không gian hình vuông ở mọi cấp độ trong tùy chọn đầu tiên, nhưng điều này hiếm khi cần thiết.
Một ví dụ về một trong những hình vuông cấp thấp hơn:
Và đây là một số hình ảnh toàn cầu từ dự án XAPI: biểu diễn một chỉ mục trên các hình ảnh toàn cục:
toàn cầu ^cách dùng để lưu trữ điểm (đường, sông nhỏ, v.v.) và đa giác (khu vực khép kín: tòa nhà, rừng, v.v.).
Phân loại sơ bộ việc sử dụng mảng thưa thớt trên toàn cầu.
- Chúng tôi lưu trữ tọa độ của một số đối tượng nhất định và trạng thái của chúng (ánh xạ, ô tô di động)
- Chúng tôi lưu trữ ma trận thưa thớt.
Đối với trường hợp 2) khi yêu cầu tọa độ cụ thể mà phần tử không được gán giá trị, chúng ta phải lấy giá trị của phần tử mảng thưa mặc định.
Phần thưởng mà chúng tôi nhận được khi lưu trữ ma trận đa chiều trong toàn cục
Nhanh chóng loại bỏ và/hoặc chọn các phần không gian là bội số của hàng, mặt phẳng, hình khối, v.v. Đối với trường hợp sử dụng chỉ mục số nguyên, khả năng loại bỏ và/hoặc tìm nạp nhanh chóng các khối không gian là bội số của hàng, mặt phẳng, hình khối, v.v. có thể hữu ích.
đội chúng ta có thể xóa một phần tử hoặc một hàng hoặc thậm chí toàn bộ mặt phẳng. Nhờ các đặc tính của toàn cầu, điều này xảy ra rất nhanh - nhanh hơn hàng nghìn lần so với việc loại bỏ từng phần tử.
Hình này cho thấy một mảng ba chiều trong một toàn cục ^a và các kiểu xóa khác nhau.
Để chọn các phần không gian bằng các chỉ mục đã biết, bạn có thể sử dụng lệnh .
Chọn một cột ma trận vào biến Cột:
; Зададим трёхмерный разреженный массив 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
Kết luận:
Column(0)=1
Column(2)=1
Điều thú vị về biến Column là chúng ta cũng có một mảng thưa thớt, mảng này cũng phải được truy cập thông qua , vì các giá trị mặc định không được lưu trữ trong đó.
Việc chọn các phần không gian cũng có thể được thực hiện thông qua một chương trình nhỏ sử dụng hàm . Điều này đặc biệt thuận tiện trong các không gian có chỉ số không được lượng tử hóa (bản đồ).
Kết luận
Thời đại hiện nay đặt ra những nhiệm vụ đầy tham vọng mới. Đồ thị có thể được tạo thành từ hàng tỷ đỉnh, bản đồ được tạo thành từ hàng tỷ điểm và một số thậm chí có thể muốn vận hành vũ trụ của riêng mình trên các máy tự động di động (, ).
Khi khối lượng dữ liệu từ các mảng thưa thớt không còn vừa với RAM nữa, nhưng bạn cần phải làm việc với chúng, thì đáng để xem xét khả năng triển khai các dự án tương tự trên toàn cầu và COS.
Cám ơn vì sự quan tâm của bạn! Chúng tôi đang chờ đợi câu hỏi và mong muốn của bạn trong phần bình luận.
Từ chối trách nhiệm: Bài viết này và những bình luận của tôi về nó là quan điểm của tôi và không liên quan đến quan điểm chính thức của InterSystems Corporation.
Nguồn: www.habr.com