CodeGym /Java Course /মডিউল 1 /সংগ্রহ ব্যবহার করার টিপস

সংগ্রহ ব্যবহার করার টিপস

মডিউল 1
লেভেল 18 , পাঠ 2
বিদ্যমান

1. সংগ্রহের তালিকা

আপনি মনে করতে পারেন, জাভাতে সংগ্রহ রয়েছে - একই ধরনের বস্তু সংরক্ষণের জন্য একটি সহজ টুল।

আসুন মূল সংগ্রহ-সম্পর্কিত ইন্টারফেসগুলি স্মরণ করার চেষ্টা করি:

তালিকা , সেট , মানচিত্র এবং সারি

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

1. তালিকা

সবচেয়ে বেশি ব্যবহৃত সংগ্রহ দিয়ে শুরু করা যাক।

একটি সাধারণ পুরানো অ্যারের যতটা সম্ভব কাছাকাছি তালিকা করুন ।

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

2. সেট

সেট একটি সম্পূর্ণ ভিন্ন কাঠামো আছে.

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

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

3. মানচিত্র

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

মানচিত্রের জন্য , এই সম্পর্কগুলিকে কী-মান জোড়া বলা হয়।

আমরা আমাদের লাইব্রেরিতে লেখক অবজেক্টগুলিকে কী এবং বইগুলির তালিকা ( লিস্ট অবজেক্ট) মান হিসাবে ব্যবহার করে এই কাঠামোটি ব্যবহার করতে পারি। এইভাবে, একটি সেট চেক করার পর লাইব্রেরিতে কোনো লেখকের বস্তু বিদ্যমান আছে কিনা, আমরা একটি মানচিত্র থেকে তার বইয়ের তালিকা পেতে একই লেখক অবজেক্ট ব্যবহার করতে পারি ।

4. সারি

সারিতে এমন এক সংগ্রহ যা—আশ্চর্য! - একটি সারির আচরণ প্রয়োগ করে। এবং সারিটি হয় LIFO (লাস্ট ইন, ফার্স্ট আউট) বা FIFO (ফার্স্ট ইন, ফার্স্ট আউট) হতে পারে। আরও কী, সারিটি দ্বিমুখী হতে পারে, বা "দ্বিগুণ-সম্পন্ন" হতে পারে।

এই কাঠামোটি সহায়ক যখন ক্লাসে যোগ করা বস্তুগুলিকে প্রাপ্ত করার ক্রমে ব্যবহার করা প্রয়োজন। উদাহরণস্বরূপ, আমাদের লাইব্রেরি নিন।

আমরা নতুন আগত দর্শকদের একটি সারিতে যোগ করতে পারি এবং তাদের জন্য যে বইগুলি এসেছে তা ইস্যু করে তাদের পরিবেশন করতে পারি।

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

2. জটিলতা

ইতিমধ্যেই উল্লেখ করা হয়েছে, আমরা উপরে যে সংগ্রহগুলি বিবেচনা করেছি তা হল ইন্টারফেস, যার মানে আমাদের ব্যবহার করার জন্য তাদের অবশ্যই বাস্তবায়ন থাকতে হবে।

অনুবীক্ষণ যন্ত্রের সাহায্যে নখ কাটা যেমন সেরা ধারণা নয়, তেমনি একটি সংগ্রহের প্রতিটি বাস্তবায়ন প্রতিটি পরিস্থিতির জন্য উপযুক্ত নয়।

একটি কাজের জন্য সঠিক টুল নির্বাচন করার সময়, আমরা সাধারণত 2টি বৈশিষ্ট্য দেখি:

  • টুলটি কাজের সাথে কতটা মানানসই?
  • কত দ্রুত কাজ সম্পন্ন হবে?

কিভাবে একটি কাজের জন্য একটি উপযুক্ত টুল বাছাই করা যায় তা বের করতে আমরা কিছু সময় ব্যয় করেছি, কিন্তু এর গতি নতুন কিছু।

কম্পিউটিংয়ে, একটি টুলের গতি প্রায়ই সময়ের জটিলতার পরিপ্রেক্ষিতে প্রকাশ করা হয় এবং একটি বড় অক্ষর O দ্বারা চিহ্নিত করা হয়।

পৃথিবীতে সময়ের জটিলতা কি?

সহজ ভাষায়, সময়ের জটিলতা একটি নির্দিষ্ট ক্রিয়া সম্পাদনের জন্য সংগ্রহে একটি অ্যালগরিদমের জন্য প্রয়োজনীয় সময় নির্দেশ করে (একটি উপাদান যোগ করা/সরানো, একটি উপাদান অনুসন্ধান করা)।

অ্যারেলিস্ট বনাম লিঙ্কডলিস্ট

লিস্ট ইন্টারফেসের দুটি ইমপ্লিমেন্টেশন ব্যবহার করে দেখা যাক - ArrayList এবং LinkedList

বাহ্যিক উপস্থিতির জন্য, এই সংগ্রহগুলির সাথে কাজ করা একই রকম:


List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

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

তালিকা ইন্টারফেসের তাদের ভিন্ন রূপায়নের কারণে , এই দুটি কাঠামো অন্যদের তুলনায় আরও দক্ষতার সাথে বিভিন্ন ক্রিয়া সম্পাদন করে।

একটি উপাদান অপসারণ এবং যোগ করার কথা বিবেচনা করুন।

যদি আমাদের একটি ArrayList এর মাঝখান থেকে একটি উপাদান অপসারণ করতে হয় , তাহলে তালিকার যে অংশটি আমরা অপসারণ করি তা অনুসরণ করে আমাদেরকে ওভাররাইট করতে হবে।

ধরুন আমাদের কাছে 5টি উপাদানের একটি তালিকা রয়েছে এবং আমরা 3য়টি সরাতে চাই।


List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

এই ক্ষেত্রে, অপসারণ একটি ঘর মুক্ত করে, তাই আমাদের 4র্থ উপাদানটি লিখতে হবে যেখানে 3য়টি ছিল এবং 5মটি যেখানে 4টি ছিল।

এটি অত্যন্ত অদক্ষ।

তালিকার মাঝখানে একটি উপাদান যোগ করার সময় একই ঘটনা ঘটে।

LinkedList ভিন্নভাবে গঠন করা হয়। উপাদানগুলি যোগ করা বা অপসারণ করা দ্রুত, যেহেতু আমাদের কেবলমাত্র পূর্ববর্তী এবং পরবর্তী উপাদানগুলির রেফারেন্সগুলি পরিবর্তন করতে হবে, যার ফলে আমরা উপাদানগুলির শৃঙ্খল থেকে যে বস্তুটি সরিয়ে ফেলছি তা বাদ দিয়ে।

5টি উপাদানের একই তালিকার উদাহরণে ফিরে আসা, 3য় উপাদানটি সরানোর পরে, আমাদের যা করতে হবে তা হল 2য় উপাদানটির পরবর্তী উপাদানের রেফারেন্স এবং 4র্থ উপাদানের পূর্ববর্তীটির রেফারেন্স পরিবর্তন করতে হবে।

যখন একটি উপাদান তালিকায় যোগ করা হয়, একই প্রক্রিয়া ঘটবে, কিন্তু বিপরীতে।

একটি ArrayList এর তুলনায় লিঙ্কডলিস্টে আমাদের কত কম কাজ করতে হবে তা লক্ষ্য করুন । এবং যে মাত্র 5 উপাদান. আমাদের তালিকায় 100 বা তার বেশি উপাদান থাকলে, LinkedList- এর শ্রেষ্ঠত্ব আরও বেশি লক্ষণীয় হয়ে উঠত।

কিন্তু কিভাবে পরিস্থিতি পরিবর্তন হয় যদি আমরা সূচক দ্বারা একটি উপাদান অ্যাক্সেস করে?

এখানে সবকিছু ঠিক উল্টো।

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

কিন্তু একটি লিঙ্কডলিস্ট কেবল সেভাবে কাজ করে না। একটি নির্দিষ্ট সূচক সহ উপাদানটি খুঁজে পেতে আমাদের তালিকার সমস্ত উপাদানের মধ্য দিয়ে যেতে হবে।

আমরা কি বড় হে পরিপ্রেক্ষিতে এই সব প্রকাশ করার চেষ্টা করব?

সূচী দ্বারা একটি উপাদান অ্যাক্সেস করে শুরু করা যাক.

একটি ArrayList- এ , এটি একটি ধাপে ঘটে, তালিকার উপাদানটি যেখানেই থাকুক না কেন। শুরুতেই হোক বা শেষের দিকে।

এই ক্ষেত্রে, সময়ের জটিলতা হবে O(1)

একটি লিঙ্কডলিস্টে , আমাদের প্রয়োজনীয় সূচকের মানের সমান কিছু উপাদানের উপর পুনরাবৃত্তি করতে হবে।

এই ধরনের কর্মের জন্য সময় জটিলতা হল O(n) , যেখানে n হল আমাদের প্রয়োজনীয় উপাদানের সূচক।

এখানে আপনি দেখতে পাচ্ছেন যে আমরা বড়-ও বন্ধনীতে যে সংখ্যাটি রাখি তা সম্পাদিত ক্রিয়াগুলির সংখ্যার সাথে মিলে যায়।

শেল আমরা অপসারণ এবং যোগ করার জন্য ফিরে?

চলুন শুরু করা যাক LinkedList দিয়ে।

কারণ আমাদের একটি উপাদান যোগ বা অপসারণ করতে প্রচুর পরিমাণে ক্রিয়া করার প্রয়োজন নেই এবং এই ক্রিয়াকলাপের গতি উপাদানটি কোথায় অবস্থিত তার উপর কোনওভাবেই নির্ভর করে না, এটি জটিলতাকে O(1) হিসাবে প্রকাশ করা হয় এবং বলা হয় ধ্রুবক হতে

ArrayList- এর জন্য এই অপারেশনের সময় জটিলতা হল O(n) , যাকে আমরা লিনিয়ার কমপ্লেক্সিটি বলি।

রৈখিক জটিলতা সহ অ্যালগরিদমগুলিতে, চলমান সময় প্রক্রিয়াকরণের উপাদানগুলির সংখ্যার উপর সরাসরি নির্ভর করে। এটি উপাদানটির অবস্থানের উপরও নির্ভর করতে পারে, এটি তালিকার শুরুতে বা শেষের দিকে।

সময়ের জটিলতা লগারিদমিকও হতে পারে। এটিকে O(log n) হিসাবে প্রকাশ করা হয় ।

একটি উদাহরণ হিসাবে, 10টি সংখ্যা সমন্বিত একটি সাজানো TreeSet বিবেচনা করুন। আমরা 2 নম্বরটি খুঁজে পেতে চাই।

যেহেতু তালিকাটি সাজানো হয়েছে এবং এতে কোনো সদৃশ নেই, তাই আমরা এটিকে অর্ধেক ভাগ করতে পারি এবং কোন অর্ধেকটি পছন্দসই সংখ্যা ধারণ করবে তা পরীক্ষা করতে পারি, অপ্রাসঙ্গিক অংশটি বাতিল করে দিতে পারি এবং তারপরে আমরা পছন্দসই উপাদানে না পৌঁছানো পর্যন্ত এই প্রক্রিয়াটি পুনরাবৃত্তি করতে পারি। শেষ পর্যন্ত, আমরা উপাদানগুলির লগ(n) সংখ্যা প্রক্রিয়াকরণের পরে সংখ্যাটি খুঁজে পাব (বা খুঁজে পাব না)।

এখানে একটি সারণী রয়েছে যা বাকি সংগ্রহের সময় জটিলতার সংক্ষিপ্ত বিবরণ দেয়।

সূচক দ্বারা চাবি দ্বারা অনুসন্ধান করুন শেষে সন্নিবেশ শেষে সন্নিবেশ অপসারণ
অ্যারেলিস্ট O(1) N/A চালু) O(1) চালু) চালু)
যোজিত তালিকা চালু) N/A চালু) O(1) O(1) O(1)
হ্যাশসেট N/A O(1) O(1) N/A O(1) O(1)
ট্রি সেট N/A O(1) O(লগ n) N/A O(লগ n) O(লগ n)
হ্যাশ মানচিত্র N/A O(1) O(1) N/A O(1) O(1)
ট্রিম্যাপ N/A O(1) O(লগ n) N/A O(লগ n) O(লগ n)
ArrayDeque N/A N/A চালু) O(1) O(1) O(1)

এখন যেহেতু আমাদের কাছে জনপ্রিয় সংগ্রহের সময় জটিলতা দেখানোর একটি সারণী আছে, আমরা এই প্রশ্নের উত্তর দিতে পারি কেন, এতগুলি সংগ্রহের মধ্যে, আমরা প্রায়শই ArrayList , HashSet এবং HashMap ব্যবহার করি ।

এটা সহজ যে তারা বেশিরভাগ কাজের জন্য সবচেয়ে দক্ষ :)

মন্তব্য
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION