গ্লোবালগুলি ডেটা সঞ্চয় করার জন্য ভান্ডারের তরবারি। স্পার্স অ্যারে। পার্ট 3

আগের অংশে (1, 2) আমরা গাছ হিসাবে গ্লোবাল সম্পর্কে কথা বলেছি, এখানে আমরা গ্লোবালগুলিকে স্পারস অ্যারে হিসাবে দেখব।

স্পারস অ্যারে হল এক ধরনের অ্যারে যেখানে বেশিরভাগ মান একই মান নেয়।

অনুশীলনে, স্পার্স অ্যারেগুলি প্রায়শই এত বিশাল হয় যে একই উপাদানগুলির সাথে মেমরি দখল করার কোনও অর্থ নেই। অতএব, স্পার্স অ্যারেগুলিকে এমনভাবে প্রয়োগ করা বোধগম্য হয় যাতে অভিন্ন মান সংরক্ষণে মেমরি নষ্ট না হয়।
কিছু প্রোগ্রামিং ভাষায়, স্পার্স অ্যারে ভাষাতেই অন্তর্ভুক্ত করা হয়, উদাহরণস্বরূপ জে, ম্যাটল্যাব. অন্যান্য প্রোগ্রামিং ভাষার বিশেষ লাইব্রেরি রয়েছে যা আপনাকে সেগুলি বাস্তবায়ন করতে দেয়। C++ এর জন্য - আইগেন এবং অন্যদের

গ্লোবালগুলি স্পার্স অ্যারে বাস্তবায়নের জন্য ভাল প্রার্থী কারণ:

1. তারা শুধুমাত্র নির্দিষ্ট নোডের মান সঞ্চয় করে এবং অনির্ধারিতগুলির মান সংরক্ষণ করে না;
2. একটি নোডের মান অ্যাক্সেস করার জন্য ইন্টারফেসটি একটি বহুমাত্রিক অ্যারে উপাদানে কতগুলি প্রোগ্রামিং ভাষা অ্যাক্সেস কার্যকর করে তার সাথে অত্যন্ত মিল।

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

3. গ্লোবাল ডেটা সঞ্চয় করার জন্য একটি মোটামুটি নিম্ন-স্তরের কাঠামো, তাই এটির অসামান্য গতির বৈশিষ্ট্য রয়েছে (হার্ডওয়্যারের উপর নির্ভর করে প্রতি সেকেন্ডে কয়েক লক্ষ থেকে লক্ষ লক্ষ লেনদেন, নীচে দেখুন)। 1)

যেহেতু গ্লোবাল একটি স্থায়ী কাঠামো, তাই র‍্যামের পরিমাণ পর্যাপ্ত হবে না তা আগে থেকেই জানা থাকলে তাদের উপর স্পার্স অ্যারে তৈরি করা বোধগম্য।

স্পার্স অ্যারে বাস্তবায়নের বৈশিষ্ট্যগুলির মধ্যে একটি হল একটি অনির্ধারিত ঘরে অ্যাক্সেস করা হলে কিছু ডিফল্ট মান ফিরিয়ে দেওয়া।

এটি ফাংশন ব্যবহার করে বাস্তবায়ন করা যেতে পারে $GET COS-এ। এই উদাহরণটি একটি 3-মাত্রিক অ্যারে বিবেচনা করে।

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

কোন কাজের জন্য স্পার্স অ্যারে প্রয়োজন এবং গ্লোবাল কিভাবে সাহায্য করতে পারে?

সংলগ্নতা (সংযোগ) ম্যাট্রিক্স

যেমন ম্যাট্রিক্স গ্রাফ প্রতিনিধিত্ব করতে ব্যবহৃত:

স্পষ্টতই, গ্রাফটি যত বড় হবে, ম্যাট্রিক্সে তত বেশি শূন্য থাকবে। উদাহরণস্বরূপ, যদি আমরা একটি সামাজিক নেটওয়ার্ক গ্রাফ গ্রহণ করি এবং এটিকে একটি অনুরূপ ম্যাট্রিক্স আকারে উপস্থাপন করি, তবে এটি প্রায় সম্পূর্ণরূপে শূন্য দ্বারা গঠিত হবে, অর্থাৎ একটি স্পার্স অ্যারে হবে।

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)

স্টেট মেশিন ট্রানজিশন টেবিল

যেহেতু একটি সীমিত অটোমেটনের ট্রানজিশন গ্রাফ একটি সাধারণ গ্রাফ, তাই সসীম অটোমেটনের ট্রানজিশন টেবিলটি উপরে আলোচনা করা একই সংলগ্ন ম্যাট্রিক্স।

সেলুলার অটোমেটা

সবচেয়ে বিখ্যাত সেলুলার automaton হয় খেলা "জীবন", যা, তার নিয়মের কারণে (যখন একটি কক্ষের অনেক প্রতিবেশী থাকে, এটি মারা যায়) একটি স্পার্স অ্যারে।

স্টিফেন ওলফ্রাম বিশ্বাস করেন যে সেলুলার অটোমেটা বিজ্ঞানের নতুন ক্ষেত্র. 2002 সালে, তিনি 1280-পৃষ্ঠার একটি বই প্রকাশ করেন, এ নিউ কাইন্ড অফ সায়েন্স, যেখানে তিনি বিস্তৃতভাবে যুক্তি দেন যে সেলুলার অটোমেটাতে অগ্রগতি বিচ্ছিন্ন নয়, তবে স্থায়ী এবং বিজ্ঞানের সমস্ত ক্ষেত্রের জন্য দুর্দান্ত প্রভাব রয়েছে।

এটি প্রমাণিত হয়েছে যে কম্পিউটারে নির্বাহযোগ্য যে কোনও অ্যালগরিদম সেলুলার অটোমেটন ব্যবহার করে প্রয়োগ করা যেতে পারে। সেলুলার অটোমেটা ব্যবহার করা হয় গতিশীল পরিবেশ এবং সিস্টেমের মডেল, অ্যালগরিদমিক সমস্যা সমাধানের জন্য এবং অন্যান্য উদ্দেশ্যে।

যদি আমাদের একটি বিশাল ক্ষেত্র থাকে এবং আমাদের একটি সেলুলার অটোমেটনের সমস্ত মধ্যবর্তী অবস্থা রেকর্ড করতে হয়, তাহলে এটি গ্লোবাল ব্যবহার করা বোধগম্য।

মানচিত্র

স্পার্স অ্যারে ব্যবহার করার সময় আমার মনে প্রথম যে জিনিসটি আসে তা হল ম্যাপিং কাজ।

একটি নিয়ম হিসাবে, মানচিত্রে অনেক খালি জায়গা রয়েছে। যদি মানচিত্রটিকে বড় পিক্সেল হিসাবে উপস্থাপন করা হয়, তাহলে পৃথিবীর পিক্সেলের 71% সমুদ্র দ্বারা দখল করা হবে। স্পার্স অ্যারে। এবং যদি আপনি শুধুমাত্র মানুষের হাতের কাজ প্রয়োগ করেন, তাহলে খালি স্থান 95% এর বেশি হবে।

অবশ্যই, কেউ রাস্টার অ্যারে আকারে মানচিত্র সংরক্ষণ করে না একটি ভেক্টর উপস্থাপনা ব্যবহার করা হয়;
কিন্তু ভেক্টর মানচিত্র কি? এটি এক ধরণের ফ্রেম এবং পলিলাইন এবং বহুভুজ বিন্দু নিয়ে গঠিত।
মূলত পয়েন্ট এবং তাদের মধ্যে সংযোগের একটি ডাটাবেস।

সবচেয়ে উচ্চাভিলাষী ম্যাপিং মিশনগুলির মধ্যে একটি হল আমাদের গ্যালাক্সি ম্যাপ করার জন্য গায়া টেলিস্কোপ মিশন। রূপকভাবে বলতে গেলে, আমাদের ছায়াপথ, সমগ্র মহাবিশ্বের মতো, একটি অবিচ্ছিন্ন স্পার্স অ্যারে: শূন্যতার বিশাল স্থান যেখানে বিরল ছোট বিন্দু - তারা রয়েছে। খালি স্থান হল 99,999999…….%। আমাদের গ্যালাক্সির মানচিত্র সংরক্ষণ করতে, একটি বিশ্বব্যাপী ডাটাবেস বেছে নেওয়া হয়েছিল - ক্যাশে।

আমি এই প্রকল্পে গ্লোবালগুলির সঠিক কাঠামো জানি না, আমি অনুমান করতে পারি যে এটি অনুরূপ কিছু:

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 আছে গ্যালাকটিক স্থানাঙ্ক অক্ষাংশ, দ্রাঘিমাংশ এবং সূর্যের দূরত্ব।

গ্লোবালের নমনীয় কাঠামো আপনাকে নক্ষত্র এবং গ্রহের প্রয়োজনীয় বৈশিষ্ট্যগুলি সংরক্ষণ করতে দেয়, যেহেতু গ্লোবালের ভিত্তিগুলি স্কিম-লেস।

আমাদের মহাবিশ্বের মানচিত্র সঞ্চয় করার জন্য, ক্যাশে শুধুমাত্র এর নমনীয়তার জন্য নয়, একই সাথে দ্রুত অনুসন্ধানের জন্য সূচক গ্লোবাল তৈরি করার সাথে সাথে খুব দ্রুত ডেটার একটি স্ট্রিম সঞ্চয় করার ক্ষমতার জন্যও বেছে নেওয়া হয়েছিল।

যদি আমরা পৃথিবীতে ফিরে যাই, তাহলে বিশ্বব্যাপী কার্টোগ্রাফিক প্রকল্পগুলি তৈরি করা হয়েছিল OpenStreetMap XAPI এবং OpenStreetMap-এর একটি কাঁটা - FOSM.

সম্প্রতি হ্যাকাথন ক্যাশে ভূ-স্থানিক সূচকগুলি বাস্তবায়িত হয়েছিল ভৌগলিক অবস্থান বিষয়ক প্রযুক্তিবিদ্যা. আমরা বাস্তবায়নের বিবরণ সহ লেখকদের কাছ থেকে একটি নিবন্ধের জন্য অপেক্ষা করছি।

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) একটি নির্দিষ্ট স্থানাঙ্কের জন্য অনুরোধ করার সময় যেখানে উপাদানটির একটি মান নির্ধারণ করা হয়নি, আমাদের অবশ্যই ডিফল্ট স্পারস অ্যারে উপাদানটির মান পেতে হবে।

বিশ্বব্যাপী বহুমাত্রিক ম্যাট্রিক্স সংরক্ষণ করার সময় আমরা যে বোনাসগুলি পাই

দ্রুত সরান এবং/অথবা সারি, সমতল, কিউব ইত্যাদির গুণিতক স্থানের টুকরোগুলি নির্বাচন করুন। যে ক্ষেত্রে পূর্ণসংখ্যা সূচী ব্যবহার করা হয়, সেখানে সারি, সমতল, কিউব ইত্যাদির গুণিতক স্থানের অংশগুলি দ্রুত সরানোর এবং/অথবা আনার ক্ষমতা কার্যকর হতে পারে।

টীম বধ আমরা একটি একক উপাদান বা একটি সারি, এমনকি একটি সম্পূর্ণ সমতল মুছে ফেলতে পারি। গ্লোবালের বৈশিষ্ট্যগুলির জন্য ধন্যবাদ, এটি খুব দ্রুত ঘটে - উপাদান দ্বারা উপাদান অপসারণের চেয়ে হাজার গুণ দ্রুত।

চিত্রটি বিশ্বব্যাপী একটি ত্রিমাত্রিক অ্যারে দেখায় ^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

কলাম ভেরিয়েবল সম্পর্কে যা আকর্ষণীয় তা হল আমাদের একটি স্পার্স অ্যারেও রয়েছে, যা অবশ্যই এর মাধ্যমে অ্যাক্সেস করতে হবে $GET, যেহেতু ডিফল্ট মান এটিতে সংরক্ষণ করা হয় না।

ফাংশন ব্যবহার করে একটি ছোট প্রোগ্রামের মাধ্যমে স্থানের টুকরো নির্বাচন করা যেতে পারে $Order. এটি বিশেষ করে এমন স্থানগুলিতে সুবিধাজনক যার সূচকগুলি পরিমাপ করা হয় না (কার্টোগ্রাফি)।

উপসংহার

বর্তমান সময় নতুন উচ্চাভিলাষী কাজ পোজ. গ্রাফগুলি কোটি কোটি শীর্ষবিন্দু দিয়ে তৈরি হতে পারে, কোটি কোটি বিন্দু দিয়ে তৈরি মানচিত্র এবং কেউ কেউ হয়তো সেলুলার অটোমেটা (1, 2).

যখন স্পার্স অ্যারে থেকে ডেটার ভলিউম আর র‌্যামে ফিট করতে পারে না, তবে আপনাকে তাদের সাথে কাজ করতে হবে, তখন গ্লোবাল এবং সিওএস-এ অনুরূপ প্রকল্প বাস্তবায়নের সম্ভাবনা বিবেচনা করা উচিত।

আপনার মনোযোগের জন্য আপনাকে ধন্যবাদ! আমরা মন্তব্যে আপনার প্রশ্ন এবং শুভেচ্ছা জন্য অপেক্ষা করছি.

দায়িত্ব অস্বীকার: এই নিবন্ধটি এবং এটিতে আমার মন্তব্যগুলি আমার মতামত এবং ইন্টারসিস্টেম কর্পোরেশনের অফিসিয়াল অবস্থানের সাথে কোন সম্পর্ক নেই।

উত্স: www.habr.com