algorithm - কম্পিউটার সায়েন্সে বাছাই করা বনাম 'রিয়েল' ওয়ার্ল্ডে বাছাই করা




sorting time-complexity (8)

প্রতিটি নোডের কিছু ওভারহেড দিয়ে (কোনও মান বা পদ্ধতি নোডের প্রতিটিটিতে লাগানো) তালিকার ক্রমটি 'চাপিয়ে দেওয়া' কি সম্ভব হবে?

আমরা যখন কম্পিউটার প্রোগ্রামগুলি ব্যবহার করে বাছাই করি তখন আমরা মানগুলি বাছাই করার একটি সম্পত্তি নির্বাচন করি। এটি সাধারণত সংখ্যা বা বর্ণানুক্রমিক ক্রমের পরিমাণ।

সেন্ট্রিফিউজের মতো কিছু, যেখানে কেবলমাত্র প্রতিটি উপাদান স্থানের তুলনামূলকভাবে তার অবস্থান সম্পর্কিত (অন্য নোডের সাথে সম্পর্কিত) যত্ন করে

এই সাদৃশ্যটি যথাযথভাবে আমাকে সহজ বুদ্বুদ সাজানোর কথা মনে করিয়ে দেয়। প্রতিটি পুনরাবৃত্তিতে কত ছোট সংখ্যা বুদ্বুদ হয়। আপনার সেন্ট্রিফিউজ যুক্তি পছন্দ করুন।

সুতরাং এর উত্তর দেওয়ার জন্য, আমরা আসলে সফ্টওয়্যার ভিত্তিক বাছাইতে সেই ধরণের কিছু করি না?

আমি সফ্টওয়্যারে অ্যালগরিদম বাছাই করার বিষয়ে ভাবছিলাম এবং সম্ভাব্য উপায়গুলি যে কোনও O(nlogn) যেতে পারে। ব্যবহারিক অর্থে দ্রুত সাজানো সম্ভব বলে আমি মনে করি না, সুতরাং দয়া করে মনে করবেন না যে আমি এটি করি।

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

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

প্রতিটি নোডের কিছু ওভারহেড দিয়ে (কোনও মান বা পদ্ধতি নোডের প্রতিটিটিতে লাগানো) তালিকার ক্রমটি 'চাপিয়ে দেওয়া' কি সম্ভব হবে? সেন্ট্রিফিউজের মতো কিছু, যেখানে কেবলমাত্র প্রতিটি উপাদান স্থানের তুলনামূলকভাবে সম্পর্কিত (অন্যান্য নোডের সাথে সম্পর্কিত) যত্ন করে। বা, এটি গণনার ক্ষেত্রে কিছু নিয়ম লঙ্ঘন করে?

আমি মনে করি যে এখানে উত্থাপিত বড় পয়েন্টগুলির মধ্যে একটি হ'ল প্রকৃতির কোয়ান্টাম মেকানিকাল প্রভাব এবং কীভাবে তারা একই সাথে সমস্ত কণার সমান্তরালে প্রয়োগ করে।

সম্ভবত ধ্রুপদী কম্পিউটারগুলি অন্তর্নিহিতভাবে O(nlogn) ডোমেন O(nlogn) এর ডোমেনে বাছাইকে সীমাবদ্ধ করে, যেখানে কোয়ান্টাম কম্পিউটারগুলি সমান্তরালভাবে কাজ করে O(logn) অ্যালগরিদমগুলিতে সেই প্রান্তিক প্রান্তটি অতিক্রম করতে সক্ষম হতে পারে।

মূলত একটি সমান্তরাল বুদ্বুদ সাজানোর কেন্দ্রীভূত হওয়া বিষয়টি সঠিক বলে মনে হয়, যা O(n) এর একটি সময়ের জটিলতা।

আমার অনুমান যে পরবর্তী চিন্তাটি হ'ল প্রকৃতি যদি O(n) বাছাই করতে পারে তবে কম্পিউটার কেন পারবে না?


আইএমএইচও, লোকেরা লগ (এন) কে উড়িয়ে দেয়। ও (এনলগ (এন)) কার্যত ও (এন)। এবং আপনার কেবলমাত্র ডেটা পড়তে ও (এন) দরকার।

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

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

মন্তব্য থেকে:

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

  2. এ সম্পর্কে ভাবার আর একটি উপায় হ'ল বলুন যে আপনার প্রতিটি সংখ্যার সাথে একটি ছোট প্রসেসর সংযুক্ত রয়েছে এবং প্রতিটি প্রসেসর তার প্রতিবেশীদের সাথে যোগাযোগ করতে পারে, আপনি ও (লগ (এন)) সময়ে এই সংখ্যাটি বাছাই করতে পারেন।


আর একটি দৃষ্টিভঙ্গি হ'ল আপনি সেন্ট্রিফিউজের সাথে যা বর্ণনা করছেন তা "স্প্যাগেটি সাজানো" ( https://en.wikipedia.org/wiki/Spaghetti_sort ) নামে অভিহিত to বলুন যে আপনার কাছে বিভিন্ন দৈর্ঘ্যের রান্না করা স্প্যাগেটি রডগুলির একটি বাক্স রয়েছে। এগুলি আপনার মুঠিতে ধরে রাখুন এবং আপনার হাতটি উল্লম্বভাবে নীচে নামাতে আলগা করুন যাতে প্রান্তগুলি সমস্ত একটি অনুভূমিক টেবিলের উপর বিশ্রাম করে। গর্জন করা, গম্ভীর শব্দ করা, উন্নতি হত্তয়া! তারা উচ্চতা অনুসারে বাছাই করা হয়। ও (ধ্রুবক) সময়। (বা ও (এন) আপনি যদি উচ্চতা অনুসারে রডগুলি বাছাই করে এবং একটি স্প্যাগেটি র্যাকের মধ্যে রাখেন তবে আমার ধারণা?)

আপনি সেখানে লক্ষ রাখতে পারেন যে এটি স্প্যাগেটির টুকরো সংখ্যায় ও (ধ্রুবক), তবে, স্প্যাগেটির মধ্যে সীমাবদ্ধ গতির কারণে এটি দীর্ঘতম স্ট্র্যান্ডের দৈর্ঘ্যে ও (এন)। সুতরাং কিছুই নিখরচায় আসে না।


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

"সাজানোর" জন্য, ড্রোনগুলি একটি নির্দিষ্ট ক্রমে একটি লাইন বা প্যাটার্ন গঠনের জন্য প্রোগ্রাম করা যেতে পারে, প্রাথমিকভাবে যেকোন অনুগমন বা আকারে প্রকাশ করা হত এবং সম্মিলিতভাবে এবং সমান্তরালে তারা দ্রুত অর্ডার করা রেখা বা প্যাটার্ন গঠন করে।

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

প্রতিটি উপাদান অবস্থান জানুন

টেপ বাছাইয়ের ক্ষেত্রে, প্রতিটি উপাদান (রেকর্ড) এর অবস্থান কেবল কম্পিউটারে নয় "টেপ" এর কাছে "পরিচিত"। একটি টেপ ভিত্তিক সাজানোর জন্য কেবল একবারে দুটি উপাদানের সাথে কাজ করা প্রয়োজন, এবং কোনও টেপ (ফাইল চিহ্ন বা বিভিন্ন আকারের একটি রেকর্ড) দিয়ে রান সীমানা বোঝানোর উপায়।


গণনামূলক জটিলতা সর্বদা কিছু গণনার মডেলকে সম্মান করে সংজ্ঞায়িত করা হয়। উদাহরণস্বরূপ, একটি সাধারণ কম্পিউটারে ( এন ) এর একটি অ্যালগরিদম Brainfuck প্রয়োগ করা হলে (2 এন ) হতে পারে।

সেন্ট্রিফিউজ কম্পিউটিং মডেলের কিছু আকর্ষণীয় বৈশিষ্ট্য রয়েছে; উদাহরণ স্বরূপ:

  • এটি নির্বিচারে সমান্তরালতা সমর্থন করে; সমাধানে কতগুলি কণা রয়েছে তা বিবেচনা না করে সেগুলি একসাথে বাছাই করা যায়।
  • এটি ভর দ্বারা একটি কঠোর রৈখিক ধরণের কণা দেয় না, বরং একটি খুব কাছাকাছি (স্বল্প-শক্তি) সমীকরণ।
  • ফলস্বরূপ পৃথক কণা পরীক্ষা করা সম্ভব হয় না।
  • বিভিন্ন বৈশিষ্ট্য দ্বারা কণা বাছাই করা সম্ভব নয়; শুধুমাত্র ভর সমর্থন করা হয়।

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


প্রথমত, আপনি দুটি পৃথক প্রসঙ্গে তুলনা করছেন, একটি হ'ল যুক্তি (কম্পিউটার) এবং অন্যটি পদার্থবিজ্ঞান যা (এখনও অবধি) প্রমাণিত হয়েছে যে আমরা গাণিতিক সূত্রগুলি ব্যবহার করে এর কিছু অংশ মডেল করতে পারি এবং প্রোগ্রামার হিসাবে আমরা এই সূত্রগুলি অনুকরণের জন্য ব্যবহার করতে পারি (কিছু অংশ) যুক্তিবিদ্যায় পদার্থবিজ্ঞান (যেমন গেম ইঞ্জিনে পদার্থবিজ্ঞান ইঞ্জিন)।

দ্বিতীয় আমাদের কম্পিউটার (যুক্তি) বিশ্বে কিছু সম্ভাবনা রয়েছে যা পদার্থবিদ্যায় প্রায় অসম্ভব উদাহরণস্বরূপ আমরা মেমরিটি অ্যাক্সেস করতে পারি এবং প্রতিটি সময়ে প্রতিটি সত্তার সঠিক অবস্থান খুঁজে পাই তবে পদার্থবিদ্যায় এটি হিজেনবার্গের অনিশ্চয়তার নীতি

তৃতীয় আপনি যদি কম্পিউটারের জগতে সেন্ট্রিফিউজ এবং এর ক্রিয়াকলাপের মানচিত্র তৈরি করতে চান তবে এটি এমন একজনের (Godশ্বর) আপনাকে পদার্থবিদ্যার সমস্ত নিয়ম প্রয়োগ করে একটি সুপার কম্পিউটার দিয়েছে এবং আপনি এটিতে আপনার ছোট্ট বাছাই করছেন ( সেন্ট্রিফিউজ ব্যবহার করে) এবং এই বলে যে আপনার বাছাইয়ের সমস্যাটি ও (এন) এ সমাধান করা হয়েছে আপনি ব্যাকগ্রাউন্ডে চলছে বিশাল পদার্থবিজ্ঞানের সিমুলেশন উপেক্ষা করছেন ...


বিবেচনা করুন: "সেন্ট্রিফিউজ সাজান" কি আসলে স্কেলিং আরও ভাল? স্কেল আপ করার সাথে সাথে কী ঘটে যায় তা ভেবে দেখুন।

  • টেস্ট টিউবগুলি আরও দীর্ঘতর হতে হবে।
  • ভারী জিনিসগুলি নীচে যেতে আরও এবং আরও ভ্রমণ করতে হবে।
  • জড়তার মুহুর্তটি আরও বাড়ে এবং গতির বাছাইয়ের গতি বাড়ানোর জন্য আরও বেশি সময় প্রয়োজন।

এটি কেন্দ্রীভূত বাছাই সহ অন্যান্য সমস্যাগুলি বিবেচনা করার মতো। উদাহরণস্বরূপ, আপনি কেবল একটি সরু আকারের স্কেলে পরিচালনা করতে পারেন। একটি কম্পিউটার বাছাই অ্যালগরিদম পূর্ণ 1 থেকে 2 ^ 1024 এবং এর বাইরে, কোনও ঘাম নয় handle এমন একটি হাইড্রোজেন পরমাণুর চেয়ে 2 ^ 1024 গুণ ওজনের একটি সেন্টিফিউজে রেখে দিন এবং এটি একটি ব্ল্যাকহোল এবং ছায়াপথটি ধ্বংস হয়ে গেছে। অ্যালগরিদম ব্যর্থ হয়েছে।

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


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

একটি কেন্দ্রীভূত একটি বাছাই প্রক্রিয়া প্রয়োগ করে যা উপাদানগুলির মধ্যে তুলনা করে সত্যই কাজ করে না, তবে বাস্তবে বিচ্ছিন্নতার প্রতিটি উপাদানকে সম্পত্তি ('কেন্দ্রীভূত শক্তি') দ্বারা কার্যকর করা হয়। কিছু বাছাই করা অ্যালগরিদম এই থিমের মধ্যে পড়ে বিশেষত রেডিক্স বাছাই । যখন এই বাছাই করা অ্যালগরিদমটি সমান্তরাল হয় তখন এটি সেন্ট্রিফিউজের উদাহরণের সাথে যোগাযোগ করা উচিত।

কিছু অন্যান্য তুলনামূলক বাছাই করা অ্যালগরিদম হ'ল বালতি বাছাই এবং গণনা অনুসারে বাছাই করুন । আপনি দেখতে পাবেন যে বালতি বাছাই একটি সেন্ট্রিফিউজের সাধারণ ধারণার সাথেও খাপ খায় (ব্যাসার্ধটি একটি বিনের সাথে সামঞ্জস্য করতে পারে)।

আরেকটি তথাকথিত 'বাছাই অ্যালগরিদম' যেখানে প্রতিটি উপাদান বিচ্ছিন্ন হিসাবে বিবেচনা করা হয় হ'ল স্লিপ সাজান । এখানে সময়কেন্দ্রিক বা বলের পরিবর্তে বাছাইয়ের জন্য ব্যবহৃত পরিধি হিসাবে কাজ করে।





time-complexity