ในส่วนก่อนหน้า (, ) เราได้พูดถึง globals ว่าเป็นเหมือนต้นไม้ ในอันนี้เราจะมอง globals ว่าเป็นอาร์เรย์แบบกระจัดกระจาย
เป็นอาร์เรย์ประเภทหนึ่งซึ่งค่าส่วนใหญ่ใช้ค่าเดียวกัน
ในทางปฏิบัติ อาร์เรย์แบบกระจัดกระจายมักจะมีขนาดใหญ่มากจนไม่มีประโยชน์ในการครอบครองหน่วยความจำที่มีองค์ประกอบเหมือนกัน ดังนั้นจึงเหมาะสมที่จะใช้อาร์เรย์แบบกระจายในลักษณะที่หน่วยความจำไม่สูญเปล่าในการจัดเก็บค่าที่เหมือนกัน
ในภาษาการเขียนโปรแกรมบางภาษา อาร์เรย์แบบกระจายจะรวมอยู่ในภาษานั้นด้วย , - ภาษาโปรแกรมอื่นๆ มีไลบรารีพิเศษที่ให้คุณนำไปใช้ได้ สำหรับภาษา C++ - เป็นต้น
Globals เป็นตัวเลือกที่ดีสำหรับการนำอาร์เรย์แบบกระจายไปใช้เนื่องจาก:
- พวกเขาเก็บค่าของโหนดบางโหนดเท่านั้นและไม่เก็บค่าของโหนดที่ไม่ได้กำหนด
- อินเทอร์เฟซสำหรับการเข้าถึงค่าของโหนดนั้นคล้ายกันมากกับจำนวนภาษาการเขียนโปรแกรมที่ใช้การเข้าถึงองค์ประกอบอาร์เรย์หลายมิติ
Set ^a(1, 2, 3)=5 Write ^a(1, 2, 3) - Global เป็นโครงสร้างระดับต่ำสำหรับการจัดเก็บข้อมูล ดังนั้นจึงมีลักษณะความเร็วที่โดดเด่น (จากธุรกรรมนับแสนถึงหลายสิบล้านรายการต่อวินาที ขึ้นอยู่กับฮาร์ดแวร์ ดูด้านล่าง) )
เนื่องจากโกลบอลเป็นโครงสร้างแบบถาวร จึงสมเหตุสมผลที่จะสร้างอาร์เรย์แบบกระจัดกระจายเมื่อทราบล่วงหน้าว่าจำนวน RAM จะไม่เพียงพอ
คุณสมบัติประการหนึ่งของการใช้งานอาร์เรย์แบบกระจายคือการส่งคืนค่าเริ่มต้นบางส่วนหากมีการเข้าถึงเซลล์ที่ไม่ได้กำหนดไว้
สิ่งนี้สามารถนำไปใช้ได้โดยใช้ฟังก์ชัน ในคอส ตัวอย่างนี้พิจารณาอาร์เรย์ 3 มิติ
SET a = $GET(^a(x,y,z), defValue)งานใดบ้างที่ต้องใช้อาร์เรย์แบบกระจาย และ globals จะช่วยได้อย่างไร
เมทริกซ์ที่อยู่ติดกัน (การเชื่อมต่อ)
ใช้เพื่อแสดงกราฟ:
แน่นอนว่ายิ่งกราฟมีขนาดใหญ่เท่าใด เมทริกซ์ก็จะยิ่งมีศูนย์มากขึ้นเท่านั้น ตัวอย่างเช่น หากเราใช้กราฟเครือข่ายโซเชียลและนำเสนอในรูปแบบของเมทริกซ์ที่คล้ายกัน กราฟนั้นจะประกอบด้วยศูนย์เกือบทั้งหมด กล่าวคือ จะเป็นอาร์เรย์แบบกระจัดกระจาย
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)
ตารางการเปลี่ยนสถานะเครื่อง
เนื่องจากกราฟการเปลี่ยนแปลงของออโตมาตอนจำกัดเป็นกราฟธรรมดา ตารางการเปลี่ยนแปลงของออโตมาตอนจำกัดจึงเป็นเมทริกซ์ adjacency เดียวกับที่กล่าวถึงข้างต้น
ออโตมาต้าเซลลูล่าร์
หุ่นยนต์เซลลูล่าร์ที่มีชื่อเสียงที่สุดคือ ซึ่งเนื่องจากกฎของมัน (เมื่อเซลล์มีเพื่อนบ้านจำนวนมาก มันจะตาย) จึงเป็นอาร์เรย์แบบกระจัดกระจาย
Stephen Wolfram เชื่อว่าหุ่นยนต์เซลลูล่าร์นั้นเป็นเช่นนั้น - ในปี พ.ศ. 2002 เขาได้ตีพิมพ์หนังสือ 1280 หน้าชื่อ A New Kind of Science ซึ่งเขาให้เหตุผลอย่างกว้างๆ ว่าความก้าวหน้าในออโตมาตาเซลลูลาร์ไม่ได้ถูกแยกออกจากกัน แต่มีความคงทนและมีผลกระทบอย่างมากต่อวิทยาศาสตร์ทุกแขนง
ได้รับการพิสูจน์แล้วว่าอัลกอริธึมใด ๆ ที่สามารถเรียกใช้งานได้บนคอมพิวเตอร์สามารถนำไปใช้ได้โดยใช้ระบบอัตโนมัติเซลลูล่าร์ ออโตมาตาเซลลูลาร์ถูกใช้เพื่อสร้างแบบจำลองสภาพแวดล้อมและระบบแบบไดนามิก เพื่อแก้ปัญหาอัลกอริทึมและเพื่อวัตถุประสงค์อื่น
หากเรามีสนามขนาดใหญ่และเราจำเป็นต้องบันทึกสถานะขั้นกลางทั้งหมดของหุ่นยนต์เซลลูลาร์ ก็สมเหตุสมผลที่จะใช้โกลบอล
การทำแผนที่
สิ่งแรกที่ฉันนึกถึงเมื่อพูดถึงการใช้อาร์เรย์แบบกระจายคือการแมปงาน
ตามกฎแล้ว จะมีพื้นที่ว่างมากมายบนแผนที่ หากแผนที่แสดงเป็นพิกเซลขนาดใหญ่ 71% ของพิกเซลของโลกจะถูกครอบครองโดยมหาสมุทร อาร์เรย์กระจัดกระจาย และถ้าคุณใช้เฉพาะงานมือมนุษย์ พื้นที่ว่างก็จะมากกว่า 95%
แน่นอนว่าไม่มีใครจัดเก็บแผนที่ในรูปแบบของอาร์เรย์แรสเตอร์ แต่จะใช้การแสดงเวกเตอร์
แต่แผนที่เวกเตอร์คืออะไร? นี่คือกรอบและเส้นหลายเส้นและรูปหลายเหลี่ยมที่ประกอบด้วยจุด
โดยพื้นฐานแล้วเป็นฐานข้อมูลของจุดต่างๆ และการเชื่อมต่อระหว่างกัน
หนึ่งในภารกิจการทำแผนที่ที่ทะเยอทะยานที่สุดคือภารกิจกล้องโทรทรรศน์ไกอาเพื่อทำแผนที่กาแลคซีของเรา หากพูดโดยนัยแล้ว กาแลคซีของเราก็เหมือนกับจักรวาลทั้งหมด คือมีการจัดเรียงแบบกระจัดกระจายอย่างต่อเนื่อง ซึ่งเป็นช่องว่างขนาดใหญ่แห่งความว่างเปล่าซึ่งมีจุดเล็กๆ ที่หายาก ซึ่งก็คือดวงดาว พื้นที่ว่างคือ 99,999999…….% เพื่อจัดเก็บแผนที่กาแล็กซีของเรา จึงมีการเลือกฐานข้อมูลทั่วโลก - แคช
ฉันไม่ทราบโครงสร้างที่แน่นอนของ globals ในโปรเจ็กต์นี้ ฉันสามารถสรุปได้ว่ามันจะคล้ายกับ:
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é ได้รับเลือกไม่เพียงเพราะความยืดหยุ่นเท่านั้น แต่ยังรวมถึงความสามารถในการจัดเก็บกระแสข้อมูลอย่างรวดเร็ว ในขณะเดียวกันก็สร้างดัชนีทั่วโลกเพื่อการค้นหาที่รวดเร็ว
ถ้าเรากลับมายังโลก โครงการทำแผนที่ก็ถูกสร้างขึ้นบนโลก และทางแยกของ OpenStreetMap - .
เมื่อเร็วๆ นี้ มีการใช้ดัชนีภูมิสารสนเทศ - เรากำลังรอบทความจากผู้เขียนพร้อมรายละเอียดการดำเนินการ
การใช้งานดัชนีเชิงพื้นที่ทั่วโลกใน OpenStreetMap XAPI
ภาพที่ถ่ายจาก .
โลกทั้งใบถูกแบ่งออกเป็นสี่เหลี่ยมจัตุรัส จากนั้นสี่เหลี่ยมย่อย และสี่เหลี่ยมย่อยเป็นสี่เหลี่ยมจัตุรัสย่อย และอื่นๆ โดยทั่วไปแล้ว เราได้รับโครงสร้างแบบลำดับชั้นสำหรับจัดเก็บ globals ที่ถูกสร้างขึ้น
เมื่อใดก็ได้ เราสามารถร้องขอหรือเคลียร์สแควร์ที่ต้องการได้แทบจะในทันที และสแควร์ย่อยทั้งหมดก็จะถูกส่งคืนหรือเคลียร์เช่นกัน
โครงการที่คล้ายกันใน globals สามารถนำไปใช้ได้หลายวิธี
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 เพื่อขอคะแนนที่อยู่ในช่องสี่เหลี่ยมของระดับใดๆ ไม่ใช่เรื่องยาก มันจะค่อนข้างง่ายกว่าในการทำความสะอาดพื้นที่สี่เหลี่ยมจัตุรัสในระดับใดก็ได้ในตัวเลือกแรก แต่ก็ไม่ค่อยจำเป็น
ตัวอย่างของช่องสี่เหลี่ยมระดับล่างช่องใดช่องหนึ่ง:
และนี่คือ Globals หลายรายการจากโครงการ XAPI: การแสดงดัชนีใน Globals:
ทั่วโลก ^ทาง ใช้สำหรับเก็บคะแนน (ถนน แม่น้ำสายเล็ก ฯลฯ) และรูปหลายเหลี่ยม (พื้นที่ปิด: อาคาร ป่าไม้ ฯลฯ)
การจำแนกประเภทคร่าวๆ ของการใช้อาร์เรย์แบบกระจายบนโกลบอล
- เราจัดเก็บพิกัดของวัตถุบางอย่างและสถานะของวัตถุนั้น (การทำแผนที่ ออโตมาตะเซลลูลาร์)
- เราเก็บเมทริกซ์แบบเบาบาง
สำหรับกรณีที่ 2) เมื่อขอพิกัดเฉพาะโดยที่องค์ประกอบไม่ได้กำหนดค่า เราต้องได้รับค่าขององค์ประกอบอาร์เรย์แบบกระจายเริ่มต้น
โบนัสที่เราได้รับเมื่อจัดเก็บเมทริกซ์หลายมิติในโกลบอล
ลบและ/หรือเลือกพื้นที่ที่มีหลายแถว ระนาบ ลูกบาศก์ ฯลฯ อย่างรวดเร็ว สำหรับกรณีที่ใช้ดัชนีจำนวนเต็ม ความสามารถในการลบและ/หรือดึงข้อมูลชิ้นส่วนของพื้นที่ที่เป็นทวีคูณของแถว ระนาบ ลูกบาศก์ ฯลฯ ได้อย่างรวดเร็วอาจมีประโยชน์
ทีม เราสามารถลบองค์ประกอบเดียวหรือหนึ่งแถว หรือแม้แต่ทั้งระนาบก็ได้ ด้วยคุณสมบัติของโกลบอล สิ่งนี้เกิดขึ้นเร็วมาก - เร็วกว่าการลบทีละองค์ประกอบหลายพันเท่า
รูปนี้แสดงอาร์เรย์สามมิติในระดับโลก ^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 ก็คือ เรามีอาร์เรย์แบบกระจายซึ่งต้องเข้าถึงผ่านด้วย เนื่องจากค่าเริ่มต้นจะไม่ถูกจัดเก็บไว้
การเลือกพื้นที่สามารถทำได้ผ่านโปรแกรมขนาดเล็กโดยใช้ฟังก์ชัน - วิธีนี้จะสะดวกเป็นพิเศษในพื้นที่ที่ไม่มีการวัดปริมาณดัชนี (การทำแผนที่)
ข้อสรุป
เวลาปัจจุบันทำให้เกิดภารกิจใหม่ที่มีความทะเยอทะยาน กราฟสามารถสร้างขึ้นจากจุดยอดหลายพันล้านจุด แผนที่ที่ประกอบด้วยจุดหลายพันล้านจุด และบางคนอาจต้องการใช้จักรวาลของตัวเองบนระบบเซลลูล่าร์ออโตมาต้า (, ).
เมื่อปริมาณข้อมูลจากอาร์เรย์กระจัดกระจายไม่สามารถใส่ลงใน RAM ได้อีกต่อไป แต่คุณต้องทำงานร่วมกับพวกมันจึงควรพิจารณาความเป็นไปได้ในการดำเนินโครงการที่คล้ายกันใน globals และ COS
ขอขอบคุณสำหรับความสนใจของคุณ! เรากำลังรอคำถามและความปรารถนาของคุณในความคิดเห็น
ข้อจำกัดความรับผิดชอบ: บทความนี้และความคิดเห็นของฉันเป็นความคิดเห็นของฉัน และไม่เกี่ยวข้องกับตำแหน่งอย่างเป็นทางการของ InterSystems Corporation
ที่มา: will.com