ডগ লয়েড: সুতরাং CS50 মধ্যে আমরা আবৃত করেছি বিভিন্ন ডাটা স্ট্রাকচার অনেক, ঠিক আছে? আমরা অ্যারে দেখা, এবং সংযুক্ত থাকেন তালিকা, এবং হ্যাশ টেবিল, এবং চেষ্টা, stacks এবং সারির. আমরা একটু জানতে হবে গাছ এবং গাদা সম্পর্কে, কিন্তু সত্যিই কি এই সব শুধু শেষ আপ একটি থিমে বৈচিত্র হচ্ছে. সত্যিই আছে এইসব চারটি মৌলিক ধারণা ধরনের অন্য যে সবকিছু ফুটাইয়া কমান পারেন. অ্যারে, লিঙ্ক তালিকা, হ্যাশ টেবিল, এবং চেষ্টা করে. আর মত আমি সেখানে বলেন, তাদের উপর তারতম্য আছে, কিন্তু এই সুন্দর হয় অনেক সংক্ষেপ যাচ্ছে সবকিছু আমরা কথা বলতে যাচ্ছেন সি পরিপ্রেক্ষিতে এই ক্লাসে সম্পর্কে কিন্তু কিভাবে এই অধিকার, সব পরিমাপ আপ করতে? আমরা আগপাছ বিষয়ে কথা বলেছি তাদের উপর পৃথক ভিডিও প্রতিটি, কিন্তু সংখ্যা অনেক আছে প্রায় নিক্ষিপ্ত হচ্ছে. সাধারণ অনেক আছে চিন্তা প্রায় নিক্ষিপ্ত হচ্ছে. এর চেষ্টা এবং একত্রীকরণ যাক এটা শুধু এক জায়গায়. এর বিরুদ্ধে অনুকূল দেখুক কনস, এবং বিবেচনা যা ডাটা স্ট্রাকচার সঠিক তথ্য হতে পারে আপনার বিশেষ পরিস্থিতির জন্য কাঠামো, তথ্য যাহা ধরনের আপনি সংরক্ষণ করছেন. আপনি অগত্যা সবসময় প্রয়োজন হবে না , সুপার ফাস্ট সন্নিবেশ, অপসারণের ব্যবহার একটি trie এবং লুকআপ আপনি যদি সত্যিই সন্নিবেশ এবং মুছে ফেলার যত্নশীল না অতিরিক্ত. আপনি শুধু দ্রুত র্যান্ডম প্রয়োজন তাহলে প্রবেশাধিকার, হয়তো একটি অ্যারের ভালো. সুতরাং আসুন যে চুয়ান যাক. এর চার প্রতিটি সম্পর্কে কথা বলা যাক ডাটা স্ট্রাকচার প্রধান ধরণের আমরা স্বপ্ন করেছি, এবং যে তারা ভাল হতে পারে যখন শুধু দেখতে, এবং যখন তারা যাতে ভাল নাও হতে পারে. সুতরাং আসুন অ্যারে দিয়ে শুরু করা যাক. সন্নিবেশ সুতরাং, যে ধরনের খারাপ. 

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

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

লুকআপ, যদিও, মহান. আমরা র্যান্ডম এক্সেস আছে, ধ্রুব সময় লুকআপ. আমরা মাত্র সাত বলে, এবং আমরা যেতে অ্যারে স্থানান্তরের সাত. আমরা যেতে সঙ্গে, 20 বলে অ্যারে স্থানান্তরের 20. আমরা জুড়ে বারবার করতে হবে না. যে বেশ ভাল. 

অ্যারে সাজাতে অপেক্ষাকৃত সহজ. আমরা একটি বাছাই সম্পর্কে সায়ীদ প্রতিটি সময় যেমন নির্বাচন সাজানোর মত আলগোরিদিম, সন্নিবেশ সাজানোর, বুদ্বুদ সাজানোর, একত্রীকরণ সাজান, আমরা সবসময় এটা করতে অ্যারে ব্যবহার, অ্যারে বেশ সহজ হয় কারণ ডাটা স্ট্রাকচার আপেক্ষিক সাজান, আমরা এ পর্যন্ত দেখা করেছি. 

তারা অপেক্ষাকৃত ছোট করছি. অতিরিক্ত স্থান একটি অনেক আছে না. আপনি ঠিক ঠিক যতটা সেট একপাশে আপনি আপনার ডাটা রাখা প্রয়োজন হিসাবে, এবং যে বেশ ভালো এটা. সুতরাং তারা বেশ ছোট আছেন এবং যে ভাবে কার্যকরী. কিন্তু অন্য একটি downside, যদিও, তারা আকার সংশোধন করা হয়. আমরা কিভাবে ঠিক ডিক্লেয়ার করা আছে বড় আমরা আমাদের অ্যারে হতে চান এবং আমরা শুধুমাত্র এটা এক শট পেতে. আমরা বড় হয়ে যায় এবং তা সঙ্কুচিত পারবেন না. 

আমরা এটি হত্তয়া বা সঙ্কুচিত করার প্রয়োজন হলে, আমরা একটি সম্পূর্ণ নতুন অ্যারে ডিক্লেয়ার করতে হবে, উপাদান সব কপি দ্বিতীয় অ্যারের মধ্যে প্রথম অ্যারে. আর আমরা যে miscalculated যদি সময়, আমরা আবার এটা করতে হবে. অতো ভালো না. সুতরাং অ্যারে আমাদের নমনীয়তা দিতে হবে না উপাদানের পরিবর্তনশীল নম্বর আছে. 

একটি লিঙ্ক তালিকা, সন্নিবেশ বেশ সহজ. আমরা ঠিক সামনে সম্মুখের ট্যাক. বিলোপে এছাড়াও বেশ সহজ. আমরা উপাদান খুঁজে পেতে আছে. যে কয়েকটি প্রশ্ন জড়িত. 

কিন্তু আপনি উপাদান খুঁজে পাওয়া যাচ্ছে একবার আপনি আপনাকে যা করতে হবে, সব খুঁজছেন একটি পয়েন্টার পরিবর্তন হয়, সম্ভবত দুই আপনি যদি একটি একটি দোকর তালিকার লিঙ্ক লিঙ্ক তালিকা, rather-- এবং তারপর আপনি শুধু নোড মুক্ত করতে পারেন. যে আপনি Shift করতে হবে না প্রায় সবকিছু. আপনি মাত্র দুই পয়েন্টার পরিবর্তন তাই যে বেশ দ্রুত. 

লুকআপ অধিকার, যদিও খারাপ? আমাদের একটি এটি জন্য অর্ডার ইন একটি লিঙ্ক তালিকায় উপাদান, কিনা এককভাবে বা দ্বিগুণ, লিঙ্ক আমরা এটা রৈখিক অনুসন্ধান আছে. আমরা শুরুতে শুরু আছে এবং শেষ সরানো, বা শেষ পদক্ষেপ এ শুরু শুরুতে. আমরা আর র্যান্ডম অ্যাক্সেস না থাকে. আমরা একটি কাজ করছি, তাই যদি খোঁজের অনেক, হতে পারে একটি লিঙ্ক তালিকা নয় আমাদের জন্য বেশ ভালো. 

তারা সত্যিই এছাড়াও আছেন বাছা কঠিন, তাই না? একমাত্র উপায় আপনি যা করতে পারেন সত্যিই একটি লিঙ্ক তালিকা বাছাই আপনি এটি নির্মাণ করা হিসাবে এটি বাছাই করা হয়. কিন্তু আপনি যেমন এটি সাজাতে হলে এটি নির্মাণ, আপনি আর আছেন আর দ্রুত সন্নিবেশ করে. আপনি শুধু tacking করছি না সামনে সম্মুখের জিনিষ. আপনি খুঁজে বের করতে হবে ডান স্পট লাগাতে, এবং তারপর আপনার সন্নিবেশ শুধু সম্পর্কে হিসাবে খারাপ হয়ে একটি অ্যারের মধ্যে ঢোকাতে. তাই লিঙ্ক তালিকা না হয় তথ্য বাছাইয়ের জন্য এত বড়. 

তারা খুবই ছোট, আকার-জ্ঞানী আছেন. দ্বিগুণ সামান্য তালিকা লিঙ্ক একেলা লিঙ্ক তালিকা চেয়ে বড়, যা সামান্য বড় হয় অ্যারে তুলনায়, কিন্তু এটা না বরবাদ স্থান বিপুল পরিমাণ. যদি তাই স্থান একটি প্রিমিয়াম, কিন্তু না সত্যিই একটি তীব্র প্রিমিয়াম, এই দিক থেকে ঠিক পন্থা হতে পারে. 

হ্যাশ টেবিল. একটি হ্যাশ টেবিল মধ্যে সন্নিবেশ মোটামুটি সহজবোধ্য. এটা একটি দুটি পদক্ষেপে প্রক্রিয়া. আমরা প্রথমে মাধ্যমে আমাদের তথ্য চালানোর প্রয়োজন একটি হ্যাশ ফাংশন একটি হ্যাশ কোড পেতে, এবং পরে আমরা উপাদান প্রবেশ যে হ্যাশ কোড অবস্থানে হ্যাশ টেবিল. 

লিঙ্ক তালিকা অনুরূপ মুছে ফেলার আগে,, আপনি উপাদান খুঁজে একবার সহজ. আপনি, প্রথমে এটি খুঁজে বের করতে হবে কিন্তু তারপর আপনি এটি মুছে ফেলার জন্য, আপনি শুধু বিনিময় করতে হবে পয়েন্টার একটি দম্পতি, যদি আপনি পৃথক chaining ব্যবহার করছেন. আপনি অনুসন্ধান ব্যবহার করছেন, অথবা আপনি না হন তাহলে লিখে সব chaining আপনার হ্যাশ টেবিল, মুছে ফেলার আসলে সত্যিই সহজ. আপনাকে যা করতে হবে তা হল হ্যাশ তথ্য, এবং তারপর যে অবস্থান যান. আর অভিমানী আপনি না কোনো দুর্ঘটনায় আছে আপনি খুব দ্রুত মুছে ফেলতে সক্ষম হবেন. 

এখন, লুকআপ যেখানে কিছু হয় একটু বেশি জটিল. এটা ভাল গড় উপর লিঙ্ক তালিকা তুলনায়. আপনি chaining ব্যবহার করছেন, আপনি এখনও একটি তালিকা সংযুক্ত আছে, যা আপনি এখনও আছে মানে অনুসন্ধান একটি লিঙ্ক তালিকা অমঙ্গলের. আপনি গ্রহণ করছেন কারণ কিন্তু আপনার লিঙ্ক তালিকা এবং 100 বা 1,000 বিভাজন বা n আপনার হ্যাশ টেবিল উপাদান, আপনি আছেন লিঙ্ক তালিকা আকার n তম সব এক. তারা সব যথেষ্ট ছোট করছি. আপনি এন পরিবর্তে তালিকা লিঙ্ক আছে আকার n এক লিঙ্ক তালিকা. 

আর তাই এই বাস্তব বিশ্বের ধ্রুবক সাধারণত আমরা যা ফ্যাক্টর, সময় জটিলতা সম্পর্কে কোনো কথা বলবেন না, এটা আসলে এখানে একটি পার্থক্য আছে. যাতে লুকআপ এখনও রৈখিক আপনি chaining ব্যবহার করছেন অনুসন্ধান, কিন্তু তালিকার দৈর্ঘ্য আপনি মাধ্যমে অনুসন্ধান করছেন তুলনা করে খুব, খুব ছোট. আবার, আপনার শ্রেণীবিভাজন হয় তাহলে এখানে লক্ষ্য, হ্যাশ টেবিল এর সম্ভবত সঠিক পথ যেতে না. শ্রেণীবিভাজন যদি শুধু একটি অ্যারের ব্যবহার আপনি সত্যিই গুরুত্বপূর্ণ. 

তারা মাপ স্বরগ্রাম চালাতে পারেন. এটি একটি কিনা বলা কঠিন হ্যাশ টেবিল, ছোট বা বড় হয় এটা সত্যিই উপর নির্ভর করে, কারণ কত বড় আপনার হ্যাশ টেবিল. আপনি শুধুমাত্র সংরক্ষণ করা চলুন আপনার হ্যাশ টেবিল পাঁচটি উপাদান, এবং আপনি একটি হ্যাশ টেবিল আছে এটা 10,000 উপাদানের সঙ্গে, আপনি সম্ভবত স্থান অনেক নষ্ট করছি. তুলনা করুন, এছাড়াও আপনি করতে পারেন হচ্ছে খুব কম্প্যাক্ট হ্যাশ টেবিল আছে কিন্তু ছোট আপনার হ্যাশ টেবিল, পায় যারা সংযুক্ত তালিকা প্রতিটির দৈর্ঘ্য পায়. তাই সত্যিই সংজ্ঞায়িত করার কোন উপায় আছে ঠিক একটি হ্যাশ টেবিল আকার, কিন্তু এটা সম্ভবত নিরাপদ এটি সাধারণত বলতে একটি লিঙ্ক চেয়ে বড় হতে যাচ্ছে একই তথ্য সংরক্ষণকারী তালিকা, একটি trie তুলনায় কিন্তু ছোট. 

এবং চেষ্টা চতুর্থ হয় এই কাঠামোর যে আমরা যে বিষয়ে কথা বলা হয়েছে. একটি trie মধ্যে ঢোকাতে জটিল. গতিশীল একটি অনেক আছে মেমরি বরাদ্দ, বিশেষত শুরুতে, আপনি নির্মাণ শুরু করছেন হিসাবে. কিন্তু এটা ধ্রুব সময়. এটি শুধুমাত্র মানুষের উপাদান এখানে এটি চতুর করে তোলে. নাল পয়েন্টার সম্মুখীন করা হচ্ছে, যদি malloc স্থান, সম্ভবত malloc স্থান সেখানে যান সেখান থেকে আবার. ভীতিপ্রদর্শন ফ্যাক্টর সাজানোর ডাইনামিক মেমরি বরাদ্দ পয়েন্টার পরিষ্কার হার্ডল হয়. কিন্তু আপনি এটা সাফ করেছি, সন্নিবেশ আসলে, বেশ সহজ আসে এবং এটা অবশ্যই ধ্রুব সময়. 

বিলোপে সহজ. আপনাকে যা করতে হবে তা হল নিচে চলাচল হয় একটি পয়েন্টার এবং বিনামূল্যে নোড স্বামী ও স্ত্রী, তাই যে বেশ ভাল. অনুসন্ধান প্রশংসনীয় দ্রুত. এটা শুধুমাত্র উপর ভিত্তি করে এর আপনার তথ্য দৈর্ঘ্য. আপনার সব তথ্য যদি তাই পাঁচটি অক্ষর স্ট্রিং, উদাহরন স্বরূপ, আপনি পাঁচটি সংরক্ষণ করছেন আপনার trie অক্ষর স্ট্রিং, এটা শুধুমাত্র পাঁচটি পদক্ষেপ নেয় আপনি যা খুঁজছেন তা খুঁজে পেতে. পাঁচ, তাই শুধু একটি ধ্রুবক ফ্যাক্টর আবার, সন্নিবেশ, অপসারণ, এবং লুকআপ এখানে কার্যকরভাবে, সব সময় ধ্রুবক হয়. 

আরেকটি বিষয় আপনার trie হয় আসলে ধরনের ইতিমধ্যে অধিকার, সাজানো? আমরা করছি কিভাবে শক্তি কর্মদক্ষতার দ্বারা ঢোকাতে উপাদান, এর বর্ণের পর বর্ণ যাচ্ছে দ্বারা কী ডাক দ্বারা কী, বা ডাক, সাধারণত, আপনার trie হচ্ছে শেষ পর্যন্ত আপনি এটি নির্মাণ হিসাবে ধরনের সাজানো. এটা সত্যিই তোলে না অর্থে শ্রেণীবিভাজন সম্পর্কে ভাবতে একই ভাবে আমরা মনে এটা অ্যারে, বা লিঙ্ক তালিকা সঙ্গে, অথবা হ্যাশ টেবিল. কিন্তু কিছু অর্থে, আপনার আপনি যেতে হিসাবে trie সাজানো হয়. 

downside হয়, অবশ্যই, যে হয় একটি trie দ্রুত বিপুল হয়ে. ভাষার জংশন পয়েন্ট থেকে, তবে আপনাকে আপনার কী সংখ্যা নিয়ে গঠিত হলে থাকতে, আপনি অন্যান্য 10 আছে জায়গা আপনি যেতে পারেন, যা প্রতিটি নোডের যে মানে তথ্য রয়েছে তথ্য সম্পর্কে আপনি সংরক্ষণ করতে ইচ্ছুক যে নোড, প্লাস 10 পয়েন্টার এ. যা CS50, আইডিই তে, 80 বাইট. তাই এটি জন্য অন্তত 80 বাইট এর আপনার তৈরি করা প্রতিটি নোডের, এবং যে এমনকি ডাটা গণনা না. আর আপনার নোড যদি পরিবর্তে ডিজিটের অক্ষর, এখন আপনি 26 পয়েন্টার আছে প্রতি পাঁচ থেকে. এবং 26 বার 8 সম্ভবত 200 বাইট, বা যে ভালো কিছু. আর আপনি মূলধন আছে এবং আপনি যা করতে পারেন lowercase-- আমি এই সাথে যাচ্ছি যেখানে ডান, দেখতে? তোমার নোড সত্যিই পেতে পারেন বড়, এবং তাই Trie নিজেই, সামগ্রিকভাবে, করতে পারেন খুব, সত্যিই বড় পেতে. স্থান একটি উচ্চ হয় তাহলে তাই আপনার সিস্টেমে কোন ফিংগার প্রিমিয়াম, একটি trie সঠিক ভাবে নাও হতে পারে এমনকি তার অন্যান্য সুবিধা যদিও, যেতে খেলার মধ্যে আসা. আমি ডগ লয়েড আছি. এটি CS50.