ডেটা স্ট্রাকচার কী?
একটি ডেটা স্ট্রাকচার হলো ডেটা অর্গানাইজ এবং অ্যাক্সেস করার একটি নির্দিষ্ট পদ্ধতি।
উদাহরণ রয়েছে:
- অ্যারে
- বাইনারি ট্রি
- হ্যাশ
বিভিন্ন ডেটা স্ট্রাকচার বিভিন্ন টাস্কে এক্সেল করে।
উদাহরণস্বরূপ, হ্যাশ খুব ভালো যদি আপনি ডিকশনারির মতো ডেটা (শব্দ এবং সংজ্ঞা), বা ফোন বুকের মতো ডেটা (ব্যক্তির নাম এবং নম্বর) স্টোর করতে চান।
কোন ডেটা স্ট্রাকচারগুলো উপলব্ধ, এবং প্রতিটিটির বৈশিষ্ট্য জানা আপনাকে একটি ভালো রুবি ডেভেলপার বানাবে।
আপনি আজকে সেটাই শিখবেন!
অ্যারে বুঝতে
অ্যারে হলো প্রথম ডেটা স্ট্রাকচার যা আপনি প্রোগ্রামিং শেখার শুরুতে জানেন।
অ্যারে মেমরির একটি সन्नিবিষ্ট চানক ব্যবহার করে যেখানে অবজেক্টগুলো একে অপরের পরে গ্যাপ ছাড়া স্টোর থাকে।
নিম্ন-স্তরের প্রোগ্রামিং ল্যাঙ্গুয়েজের মতো, যেমন C-এ, রুবি আপনার মেমরি ম্যানেজ করার, সর্বোচ্চ অ্যারে সাইজ বাড়ানোর এবং এলিমেন্ট ডিলিট করলে কম্প্যাক্ট করার সব কঠিন কাজ নিজে করে।
ব্যবহার:
- আরও উন্নত ডেটা স্ট্রাকচার বেস হিসেবে
- লুপ চালালে ফলাফল জমা করতে
- আইটেম সংগ্রহ করতে
আপনি সর্বত্র অ্যারে পাবেন, যেমন split এবং chars মেথড, যা একটি স্ট্রিংকে ক্যারেক্টারর অ্যারেতে ভাঙে।
উদাহরণ:
out = []
10.times { |i| out << i }
out # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
নিচের টেবিলটি দেখায় কিভাবে ভিন্ন অ্যারে অপারেশন আচরণ করে অ্যারের সাইজ বড় হলে।
আপনি যদি টাইম কমপ্লেক্সিটি নোটেশনের সাথে পরিচিত না হন তবে এই আর্টিকেল পড়ুন।
অ্যারের জন্য টাইম কমপ্লেক্সিটি:
| অপারেশন | কমপ্লেক্সিটি |
|---|---|
| push | O(1) |
| pop | O(1) |
| access | O(1) |
| find | O(n) |
| delete | O(n) |
এটি কেন উপকারী?
কারণ এটি আপনাকে অ্যারের পারফরম্যান্স বৈশিষ্ট্য বোঝাতে সাহায্য করে।
আপনি যদি একটি বিশাল অ্যারেতে প্রচুর find অপারেশন করেন তবে সেটা স্লো হবে…
কিন্তু আপনি যদি জানেন কোন ইনডেক্স ব্যবহার করতে হবে, তবে অ্যারে দ্রুত হবে O(1) টাইম কমপ্লেক্সিটির কারণে।
এই কRITE রিয়া দিয়ে আপনার ডেটা স্ট্রাকচার বেছে নিন:
- পারফরম্যান্স বৈশিষ্ট্য => আপনি ডেটার সাথে কী করছেন? আপনার ডেটাসেট কত বড়?
- ডেটার আকার ও রূপ => আপনি কী ধরনের ডেটার সাথে কাজ করছেন? কি আপনি আপনার ডেটা পুনর্গঠন করে একটি ভালো ডেটা স্ট্রাকচারের উপযোগী করতে পারেন?
হ্যাশ ডেটা স্ট্রাকচার
আপনার কি কান্ট্রি কোড এবং কান্ট্রি নেমের মধ্যে ম্যাপিং রয়েছে? অথবা হয়তো আপনি শুধু জিনিসগুলো কাউন্ট করতে চান। হ্যাশ সেটাই কাজে আসে!
একটি হ্যাশ হলো এমন একটি ডেটা স্ট্রাকচার যেখানে প্রতিটি ভ্যালুর একটি কি থাকে এবং এই কি যেকোনো কিছুর মতো হতে পারে, স্ট্রিং, ইন্টিজার, সিম্বল ইত্যাদি।
এটি কীভাবে কাজ করে?
একটি হ্যাশ আপনার কিকে একটি নম্বরে কনভার্ট করে (রুবিতে hash মেথড ব্যবহার করে) এবং তারপর সেই নম্বরটিকে ইনডেক্স হিসেবে ব্যবহার করে। কিন্তু হ্যাশ আপনার রুবি প্রোগ্রামে ব্যবহার করার জন্য আপনাকে সেটা বুঝতে হবে না।
ব্যবহার:
- স্ট্রিং-এ ক্যারেক্টার কাউন্ট করা
- শব্দ থেকে সংজ্ঞা, নাম থেকে ফোন নম্বর ইত্যাদি ম্যাপ করা
- একটি অ্যারেতে ডুপ্লিকেট খুঁজে বের করা
উদাহরণ:
"aaabcd"
.each_char
.with_object(Hash.new(0)) { |ch, hash| hash[ch] += 1 }
# {"a"=>3, "b"=>1, "c"=>1, "d"=>1}
টাইম কমপ্লেক্সিটি:
| অপারেশন | কমপ্লেক্সিটি |
|---|---|
| store | O(1) |
| access | O(1) |
| delete | O(1) |
| find (value) | O(n) |
হ্যাশ পারফরম্যান্সের ক্ষেত্রে সবচেয়ে সহায়ক ডেটা স্ট্রাকচারগুলির একটি কারণ এটির কনস্ট্যান্ট O(1) স্টোর, ডিলিট এবং অ্যাক্সেস টাইম। হ্যাশের প্রসঙ্গে "find" মানে আপনি একটি নির্দিষ্ট ভ্যালু খুঁজছেন।
স্ট্যাক
একটি স্ট্যাক হলো প্লেটের একটি স্ট্যাকের মতো, আপনি একটি প্লেট অন্যটির ওপর রাখেন এবং আপনি শুধু উপরের প্লেটটি সরাতে পারেন।
এটি শুনতে যতটা বেসরকারি লাগে, কাজের ততটুকু বেশি!
ব্যবহার:
- রিকার্সিভ মেথডকে সাধারণ লুপ দিয়ে রিপ্লেস করতে
- বাকি কাজের ট্র্যাক রাখতে, সবচেয়ে সাম্প্রতিকটি উপরে রেখে
- একটি অ্যারে রিভার্স করতে
উদাহরণ:
stack = [1,2,3,4,5]
(1..stack.size).map { stack.pop }
# [5, 4, 3, 2, 1]
হ্যাঁ, আপনি এর বদলে reverse ব্যবহার করতে পারেন। এটি শুধু স্ট্যাকের এই নির্দিষ্ট বৈশিষ্ট্য দেখানোর একটি উদাহরণ।
টাইম কমপ্লেক্সিটি:
| অপারেশন | কমপ্লেক্সিটি |
|---|---|
| push | O(1) |
| pop | O(1) |
| find | --- |
| access | --- |
লক্ষ্য করুন স্ট্যাক (এবং কিউ) এর শুধু দুটি অপারেশন রয়েছে, insert এবং delete, বা push এবং pop। স্ট্যাকের ভেতরে সার্চ করা সম্ভব হলেও, এটি খুব दुর্লভ।
বাইনারি ট্রি কীভাবে ব্যবহার করবেন
অधিকাংশ রুবি ডেভেলপার বাইনারি ট্রি সম্পর্কে শুনে থাকেন কিন্তু কখনো ব্যবহার করেননি।
কেন?
প্রথমে, আমাদের বাইনারি ট্রির বিল্ট-ইন ইমপ্লিমেন্টেশন নেই। দ্বিতীয়, বাইনারি ট্রি দৈনন্দিন প্রোগ্রামিং চ্যালেঞ্জের জন্য অ্যারে এবং হ্যাশের মতো তত উপকারী নয়, যেগুলো আপনি সবসময় ব্যবহার করেন।
কিন্তু বাইনারি ট্রি একটি খুব রোচক ডেটা স্ট্রাকচার।
বার biến thể রয়েছে, যেমন ট্রাই (পরবর্তী সেকশনে আলোচনা করা হয়েছে), মাল্টিওয়ে ট্রি যেমন বি-ট্রি (ডেটাবেসে ব্যবহৃত) এবং হিপ।
ব্যবহার:
- ডেটা কম্প্রেশন
- রাউটিং টেবিল
- অবস্ট্রাক্ট সিনট্যাক্স ট্রি (AST)
উদাহরণ:
# https://github.com/jamesconant/bstree require 'bstree' root = Bstree::Node.new(5) root.insert(2) root.insert(7) root.search(3) # nil
টাইম কমপ্লেক্সিটি:
| অপারেশন | কমপ্লেক্সিটি |
|---|---|
| insert | O(log n) |
| delete | O(log n) |
| find | O(log n) |
| access | --- |
একটি ব্যালেন্সড বাইনারি ট্রি হলো যখন সব নোডের দুটি চাইল্ড থাকে এবং সব লিফ একই লেভেলে থাকে।
যদি ট্রি آنব্যালেন্সড হয়, পারফরম্যান্স নিম্নগামী হয়ে O(n) হয়ে যায়।
একটি সেলফ-ব্যালেন্সড বাইনারি ট্রি-তে (যেমন রেড-ব্ল্যাক ট্রি, বা AVL ট্রি), প্রতিটি অপারেশন টাইম নেয় ট্রির হাইট (বা লেভেল) এর অনুপাতে।
লক্ষ্য করুন এখানে কোনো অ্যাক্সেস টাইম নেই কারণ একটি নোড অ্যাক্সেস করতে আপনাকে প্রথমে সেটা খুঁজে বের করতে হয়… সেক্ষেত্রে, আপনি O(log n) অ্যাক্সেস টাইম পাবেন। কিন্তু আপনি যদি একটি নির্দিষ্ট নোডের রেফারেন্স (একটি ভেরিয়েবল হিসেবে) রাখেন, তবে সেটা O(1) অ্যাক্সেস টাইম হবে।
ট্রাই ডেটা স্ট্রাকচার
একটি ট্রাই হলো একটি স্পেশালাইজড ট্রি-লাইক ডেটা স্ট্রাকচার। এটি শব্দের সাথে কাজ করার জন্য এবং দ্রুত প্রেফিক্স দিয়ে শব্দ খুঁজে বের করার জন্য বা পুরো শব্দ সার্চ করার জন্য সহায়ক।
ব্যবহার:
- ওয়ার্ড গেম
- স্পেলিং চেকার
- অটোকমপ্লিট সাজেশন
উদাহরণ:
# https://github.com/gonzedge/rambling-trie
require 'rambling-trie'
trie = Rambling::Trie.create('words.txt')
trie.include?('chocolate') # true
trie.include?('salmon') # true
টাইম কমপ্লেক্সিটি:
| অপারেশন | কমপ্লেক্সিটি |
|---|---|
| add | O(k) |
| include? | O(k) |
| words | O(k) |
এই টেবিলে, আমি k ব্যবহার করেছি ইনপুট স্ট্রিংর সাইজ নির্দেশ করতে, যখন n ব্যবহার করা হয় ডেটা স্ট্রাকচারটিইর সাইজ নির্দেশ করতে। তাই apple শব্দের জন্য, k হবে ৫।
সারসংক্ষেপ
আপনি সাধারণ ডেটা স্ট্রাকচার, তাদের প্রধান ব্যবহার এবং বৈশিষ্ট্য, এবং রুবিতে কীভাবে ব্যবহার করবেন সেটা শিখলেন।
আপনি যখন এই নতুন জ্ঞান প্রয়োগ করবেন, আপনি সমস্যাগুলো দ্রুত সমাধান করতে পারবেন!
আপনি যদি এই পোস্টটি সহায়ক পান তবে কি আমার জন্য শেয়ার করতে পারেন? ধন্যবাদ 🙂
