Flashsort
ফ্ল্যাশসোর্ট হল একটি ডিস্ট্রিবিউশন সার্টিং অ্যালগরিদম যা অভিন্নভাবে বিতরণকৃত ডেটা সেট এবং তুলনামূলকভাবে সামান্য অতিরিক্ত মেমরির প্রয়োজনীয়তার জন্য রৈখিক গণনামূলক জটিলতা দেখায়। মূল কাজটি 1998 সালে কার্ল-ডিয়েট্রিচ নিউবার্ট দ্বারা প্রকাশিত হয়েছিল। কনসেপ্ট ফ্ল্যাশসোর্ট হল হিস্টোগ্রাম সাজানোর একটি দক্ষ প্রয়োগ, যা নিজেই এক ধরনের বালতি সাজানো। এটি প্রতিটি ইনপুট উপাদানকে একটি বালতিতে বরাদ্দ করে, বালতিগুলি সঠিক ক্রমে রাখার জন্য দক্ষতার সাথে ইনপুটটি পুনর্বিন্যাস করে, তারপর প্রতিটি বালতি বাছাই করে। মূল অ্যালগরিদম একটি ইনপুট অ্যারেকে নিম্নরূপ সাজায়ঃ ইনপুট বা অগ্রাধিকার জ্ঞানের উপর প্রথম পাস ব্যবহার করে, ন্যূনতম এবং সর্বাধিক বাছাই কীগুলি খুঁজে বের করুন। রৈখিকভাবে পরিসীমাটিকে বালতিতে ভাগ করুন। প্রতিটি বালতিতে থাকা উপাদানগুলির সংখ্যা গণনা করে ইনপুটটির উপর দিয়ে একটি পাস করুন। (নিউবার্ট বালতিগুলিকে "শ্রেণী" এবং তাদের বালতিতে উপাদানগুলির বরাদ্দকে "শ্রেণীবিভাগ" বলে অভিহিত করেন।) প্রতিটি বালতির উপাদানগুলির গণনাকে একটি উপসর্গ যোগফল-এ রূপান্তর করুন, যেখানে বালতির উপাদানগুলির সংখ্যা বা তার কম। (এবং।) ইনপুটটি পুনর্বিন্যাস করুন যাতে প্রতিটি বালতির সমস্ত উপাদানগুলি যেখানে থাকে সেখানে সংরক্ষণ করা হয়। সন্নিবেশ সাজানো ব্যবহার করে প্রতিটি বালতি বাছাই করুন। ধাপ 1-3 এবং 6 যে কোনও বালতি সাজানোর ক্ষেত্রে সাধারণ, এবং সাধারণ থেকে বালতি সাজানোর কৌশল ব্যবহার করে উন্নত করা যেতে পারে। বিশেষত, লক্ষ্য হল বালতিগুলি প্রায় সমান আকারের (প্রতিটি উপাদান) হতে হবে, যার আদর্শ হল কোয়ান্টাইলে ভাগ করা। যদিও মৌলিক অ্যালগরিদমটি একটি রৈখিক ইন্টারপোলেশন সাজানো, যদি ইনপুট বিতরণটি অ-অভিন্ন হিসাবে পরিচিত হয়, তবে একটি অ-রৈখিক বিভাগ এই আদর্শটিকে আরও ঘনিষ্ঠভাবে অনুমান করবে। একইভাবে, চূড়ান্ত বাছাই একটি পুনরাবৃত্তিমূলক ফ্ল্যাশ বাছাই সহ বেশ কয়েকটি কৌশল ব্যবহার করতে পারে। ফ্ল্যাশ সার্টকে যা আলাদা করে তা হল ধাপ 5: শুধুমাত্র অতিরিক্ত মেমরির শব্দ ব্যবহার করে সঠিক আপেক্ষিক ক্রমে প্রতিটি বালতির উপাদানগুলি একত্রিত করার জন্য একটি দক্ষ ইন-প্লেস অ্যালগরিদম। স্মৃতি দক্ষ বাস্তবায়ন ফ্ল্যাশসোর্ট পুনর্বিন্যাস পর্যায়টি চক্রগুলিতে কাজ করে। উপাদানগুলি "শ্রেণীবদ্ধ নয়" থেকে শুরু হয়, তারপর সঠিক বালতিতে স্থানান্তরিত হয় এবং "শ্রেণীবদ্ধ" হিসাবে বিবেচিত হয়। মূল পদ্ধতিটি হল একটি শ্রেণীবদ্ধ নয় এমন উপাদান নির্বাচন করা, তার সঠিক বালতি খুঁজে বের করা, সেখানে একটি শ্রেণীবদ্ধ নয় এমন উপাদানের সাথে এটি বিনিময় করা (যা অবশ্যই বিদ্যমান থাকতে হবে, কারণ আমরা প্রতিটি বালতির আকার সময়ের আগে গণনা করেছি), এটিকে শ্রেণীবদ্ধ হিসাবে চিহ্নিত করুন এবং তারপরে কেবল-বিনিময় করা শ্রেণীবদ্ধ নয় এমন উপাদান দিয়ে পুনরাবৃত্তি করুন। অবশেষে, উপাদানটি নিজের সাথে বিনিময় হয় এবং চক্রটি শেষ হয়। প্রতি বালতিতে দুটি (শব্দ-আকারের) ভেরিয়েবল ব্যবহার করে বিশদটি বোঝা সহজ। চতুর অংশটি হল সেই ভেরিয়েবলগুলির মধ্যে একটি অপসারণ, যা দ্বিগুণ বালতি ব্যবহার করার অনুমতি দেয় এবং তাই চূড়ান্ত বাছাইয়ের জন্য অর্ধেক সময় ব্যয় করে। প্রতি বালতিতে দুটি ভেরিয়েবল দিয়ে এটি বোঝার জন্য, ধরে নিন যে অতিরিক্ত শব্দের দুটি অ্যারে রয়েছেঃ বালতি (এবং) এর (নির্দিষ্ট) উপরের সীমা, যখন বালতিতে একটি (চলমান) সূচক, তাই। আমরা লুপটি অপরিবর্তনীয় রাখি যে প্রতিটি বালতি একটি শ্রেণীবদ্ধ উপসর্গ (কারণ এখনও তাদের লক্ষ্য বালতিতে সরানো হয়নি) এবং একটি শ্রেণীবদ্ধ প্রত্যয়ে (কারণ সমস্ত সঠিক বালতিতে রয়েছে এবং আবার সরানো হবে না) বিভক্ত করা হয়। প্রাথমিকভাবে এবং সমস্ত উপাদান শ্রেণীবদ্ধ নয়। বাছাই এগিয়ে যাওয়ার সাথে সাথে, সমস্ত এবং সমস্ত উপাদান সঠিক বালতিতে শ্রেণীবদ্ধ না হওয়া পর্যন্ত হ্রাস করা হয়। প্রতিটি রাউন্ড শুরু হয় প্রথম অসম্পূর্ণ শ্রেণীবদ্ধ বালতি (যা রয়েছে) খুঁজে বের করে এবং সেই বালতিতে প্রথম শ্রেণীবদ্ধ উপাদানটি নিয়ে। (নিউবার্ট এটিকে "সাইকেল লিডার" বলে অভিহিত করেছেন।) একটি অস্থায়ী চলকের মধ্যে অনুলিপি করুন এবং পুনরাবৃত্তি করুনঃ যে বালতিটির সাথে সম্পর্কিত তা গণনা করুন। যেখানে সংরক্ষণ করা হবে সেই স্থানটি হতে দিন। বিনিময় করুন, অর্থাৎ। পূর্ববর্তী মান আনার সময় সঞ্চয় করুন যার ফলে স্থানচ্যুত হয়। অবনতি সেই সত্যকে প্রতিফলিত করে যা এখন সঠিকভাবে শ্রেণীবদ্ধ করা হয়েছে। যদি, নতুন দিয়ে এই লুপটি পুনরায় চালু করুন। যদি, এই রাউন্ডটি শেষ হয়ে যায় এবং একটি নতুন প্রথম শ্রেণীবদ্ধ নয় এমন উপাদান খুঁজে পান। যখন আর কোনও শ্রেণীবদ্ধ উপাদান থাকে না, তখন বালতিতে বিতরণ সম্পূর্ণ হয়। এইভাবে প্রতি বালতিতে দুটি ভেরিয়েবল দিয়ে প্রয়োগ করা হলে, প্রতিটি রাউন্ডের শুরুর বিন্দুর পছন্দ আসলে নির্বিচারে হয়; যে কোনও শ্রেণীবদ্ধ উপাদান চক্রের নেতা হিসাবে ব্যবহার করা যেতে পারে। একমাত্র প্রয়োজনীয়তা হল সাইকেল নেতাদের দক্ষতার সাথে খুঁজে পাওয়া যায়। যদিও পূর্ববর্তী বর্ণনাটি চক্রের নেতৃত্ব খুঁজে বের করার জন্য ব্যবহার করা হয়, বাস্তবে এটি ছাড়া এটি করা সম্ভব, যার ফলে পুরো-শব্দের অ্যারেটি বাদ দেওয়া যায়। (বন্টন সম্পূর্ণ হওয়ার পরে, বালতির সীমানা পাওয়া যাবে।) ধরুন যে আমরা সমস্ত উপাদানকে শ্রেণীবদ্ধ করেছি এবং একটি সম্ভাব্য নতুন চক্র নেতা হিসাবে বিবেচনা করছি। এর লক্ষ্য বালতি গণনা করা সহজ। লুপ অপরিবর্তনীয় দ্বারা, এটি যদি শ্রেণীবদ্ধ করা হয়, এবং যদি সেই সীমার বাইরে হয় তবে শ্রেণীবদ্ধ করা হয় না। প্রথম বৈষম্য পরীক্ষা করা সহজ, কিন্তু দ্বিতীয়টির মান প্রয়োজন বলে মনে হয়। দেখা যাচ্ছে যে, সমস্ত উপাদানকে শ্রেণীবদ্ধ করা হয়েছে বলে যে অনুমান করা হয়েছে তা বোঝায় যে, তাই দ্বিতীয় বৈষম্য পরীক্ষা করার প্রয়োজন নেই। বালতিটি কোন অবস্থানে পড়ে তা বিবেচনা করুন। অর্থাৎ,। ইন্ডাকশন হাইপোথিসিস অনুসারে, নীচের সমস্ত উপাদান, যার মধ্যে সমস্ত বালতি রয়েছে, সম্পূর্ণরূপে শ্রেণীবদ্ধ। আই. ই. সেই বালতিতে থাকা কোনও উপাদান বাকি অ্যারেতে থাকে না। অতএব, তা সম্ভব নয়। একমাত্র অবশিষ্ট কেস হল, যা বোঝায়, কিউ. ই. ডি। এটিকে অন্তর্ভুক্ত করে, ফ্ল্যাশসোর্ট ডিস্ট্রিবিউশন অ্যালগরিদমটি উপরে বর্ণিত এবং দিয়ে শুরু হয়। তারপর এগিয়ে যানঃ যদি বিতরণ সম্পূর্ণ হয়। দেওয়া আছে, এটি যে বালতিতে রয়েছে তা গণনা করুন। যদি, তাহলে শ্রেণীবদ্ধ নয়। এটি একটি অস্থায়ী পরিবর্তনশীল হিসাবে অনুলিপি করুন এবংঃ যেখানে সংরক্ষণ করা হবে সেই স্থানটি হতে দিন। বিনিময় করুন, অর্থাৎ। পূর্ববর্তী মান আনার সময় সঞ্চয় করুন যার ফলে স্থানচ্যুত হয়। অবনতি সেই সত্যকে প্রতিফলিত করে যা এখন সঠিকভাবে শ্রেণীবদ্ধ করা হয়েছে। যদি, বালতিটি গণনা করুন এবং নতুনটির সাথে এই (অভ্যন্তরীণ) লুপটি পুনরায় চালু করুন। এখন সঠিকভাবে শ্রেণীবদ্ধ করা হয়েছে। (বাইরের) লুপটি বাড়ান এবং পুনরায় চালু করুন। মেমোরি সংরক্ষণ করার সময়, ফ্ল্যাশসোর্টের একটি অসুবিধা রয়েছে যে এটি ইতিমধ্যে শ্রেণীবদ্ধ অনেক উপাদানের জন্য বালতিটি পুনরায় গণনা করে। এটি ইতিমধ্যে প্রতি উপাদান দু 'বার করা হয় (একবার বালতি-গণনা পর্যায়ে এবং দ্বিতীয়বার প্রতিটি উপাদান সরানোর সময়), তবে প্রথম শ্রেণীবদ্ধ নয় এমন উপাদানটির অনুসন্ধানের জন্য বেশিরভাগ উপাদানের জন্য তৃতীয় গণনার প্রয়োজন হয়। এটি ব্যয়বহুল হতে পারে যদি বালতিগুলি সহজ রৈখিক ইন্টারপোলেশনের চেয়ে আরও জটিল সূত্র ব্যবহার করে বরাদ্দ করা হয়। একটি বৈকল্পিক চক্র নেতা হিসাবে একটি অসম্পূর্ণ বালতিতে শেষ শ্রেণীবদ্ধ উপাদানটি গ্রহণ করে গণনার সংখ্যা প্রায় থেকে সর্বাধিক হ্রাস করেঃ প্রথম অসম্পূর্ণ-শ্রেণীবদ্ধ বালতি সনাক্তকারী একটি পরিবর্তনশীল বজায় রাখুন। শুরু করা যাক, এবং কখন, বিতরণ সম্পূর্ণ হয়। যাক। যদি, এই লুপটি বৃদ্ধি করুন এবং পুনরায় চালু করুন। (.) যে বালতিটি রয়েছে তা গণনা করুন। যদি, তারপর এবং আমরা বালতি দিয়ে সম্পন্ন করা হয়। এই লুপটি বাড়ান এবং পুনরায় চালু করুন। যদি, শ্রেণীবিভাগটি তুচ্ছ হয়। এই লুপটি হ্রাস করুন এবং পুনরায় চালু করুন। যদি, তাহলে শ্রেণীবদ্ধ নয়। পূর্ববর্তী কেসের মতো একই শ্রেণীবিভাগ লুপ সম্পাদন করুন, তারপর এই লুপটি পুনরায় চালু করুন। বেশিরভাগ উপাদানের বালতি শুধুমাত্র দু 'বার গণনা করা হয়, প্রতিটি বালতির চূড়ান্ত উপাদান ব্যতীত, যা নিম্নলিখিত বালতির সমাপ্তি সনাক্ত করতে ব্যবহৃত হয়। শ্রেণীবদ্ধ নয় এমন উপাদানগুলির গণনা বজায় রেখে এবং শূন্যে পৌঁছলে তা বন্ধ করে দিয়ে আরও সামান্য হ্রাস অর্জন করা যেতে পারে। কর্মক্ষমতা শুধুমাত্র অতিরিক্ত মেমরির প্রয়োজনীয়তা হল বালতি সীমা সংরক্ষণের জন্য সহায়ক ভেক্টর এবং ব্যবহৃত অন্যান্য চলকের ধ্রুবক সংখ্যা। উপরন্তু, প্রতিটি উপাদান শুধুমাত্র একবার সরানো হয় (একটি অস্থায়ী বাফারের মাধ্যমে, তাই দুটি অপারেশন সরানো হয়)। যাইহোক, এই মেমরি দক্ষতাটি অসুবিধাজনক যে অ্যারেটি এলোমেলোভাবে অ্যাক্সেস করা হয়, তাই পুরো অ্যারের চেয়ে ছোট ডেটা ক্যাশের সুবিধা নিতে পারে না। সমস্ত বালতি ধরণের মতো, পারফরম্যান্স বালতির ভারসাম্যের উপর সমালোচনামূলকভাবে নির্ভর করে। একটি ভারসাম্যপূর্ণ ডেটা সেটের আদর্শ ক্ষেত্রে, প্রতিটি বালতি প্রায় একই আকারের হবে। যদি ইনপুট আকারে বালতির সংখ্যা রৈখিক হয়, তবে প্রতিটি বালতির একটি ধ্রুবক আকার থাকে, তাই সন্নিবেশ বাছাইয়ের মতো অ্যালগরিদম দিয়ে একটি বালতি বাছাই করার জটিলতা রয়েছে। অতএব, চূড়ান্ত সন্নিবেশ প্রকারের চলমান সময় হল। বালতির সংখ্যার জন্য একটি মান নির্বাচন করা, উপাদানগুলিকে (উচ্চ) শ্রেণীবদ্ধ করতে ব্যয় করা সময় এবং চূড়ান্ত সন্নিবেশ বাছাই ধাপে (নিম্ন) ব্যয় করা সময়। উদাহরণস্বরূপ, যদি এর সাথে আনুপাতিকভাবে বেছে নেওয়া হয়, তবে চূড়ান্ত সন্নিবেশ প্রকারের চলমান সময় হল। সবচেয়ে খারাপ পরিস্থিতিতে যেখানে প্রায় সমস্ত উপাদান কয়েকটি বালতিতে থাকে, অ্যালগরিদমের জটিলতা চূড়ান্ত বালতি-বাছাই পদ্ধতির কার্যকারিতা দ্বারা সীমাবদ্ধ থাকে, তাই হ্রাস পায়। অ্যালগরিদমের বৈচিত্র্যগুলি একটি নির্দিষ্ট আকারের সীমা অতিক্রম করে এমন বালতিতে কুইকসোর্ট বা পুনরাবৃত্তিমূলক ফ্ল্যাশসোর্টের মতো আরও ভাল-পারফর্মিং ধরণের ব্যবহার করে সবচেয়ে খারাপ-কেস পারফরম্যান্সের উন্নতি করে। কারণ অভিন্নভাবে বিতরণ করা র্যান্ডম ডেটার ক্ষেত্রে, ফ্ল্যাশসোর্ট সকলের জন্য হিপসোর্টের চেয়ে দ্রুত এবং দ্রুততার জন্য দ্রুততর। এটি দ্রুতগতির তুলনায় প্রায় দ্বিগুণ দ্রুত হয়ে যায়। লক্ষ্য করুন যে এই পরিমাপগুলি 1990-এর দশকের শেষের দিকে নেওয়া হয়েছিল, যখন স্মৃতির শ্রেণিবিন্যাস ক্যাশেিংয়ের উপর অনেক কম নির্ভরশীল ছিল। ফ্ল্যাশসোর্ট তার শ্রেণীবিভাগ প্রক্রিয়ায় যে ইন সিটু ক্রমবিন্যাস সম্পাদন করে, তার কারণে ফ্ল্যাশসোর্ট স্থিতিশীল নয়। যদি স্থায়িত্বের প্রয়োজন হয়, তবে দ্বিতীয় অ্যারে ব্যবহার করা সম্ভব যাতে উপাদানগুলিকে ক্রমানুসারে শ্রেণীবদ্ধ করা যায়। তবে, এই ক্ষেত্রে, অ্যালগরিদমের জন্য অতিরিক্ত মেমরির প্রয়োজন হবে। আরও দেখুন ইন্টারপোলেশন অনুসন্ধান, তথ্যসূত্র বাছাই করার পরিবর্তে অনুসন্ধানের জন্য আইটেমগুলির বিতরণ ব্যবহার করে বাহ্যিক লিঙ্কগুলি বড় সমান্তরাল যন্ত্রগুলিতে এলোমেলো বাছাইয়ের বাস্তবায়ন (1992) সমান্তরাল অ্যালগরিদমগুলির বাস্তবায়ন (1992) ফ্ল্যাশসোর্ট বাছাই অ্যালগরিদমগুলির ভিজ্যুয়ালাইজেশন