Schwartzian transform
কম্পিউটার প্রোগ্রামিং-এ, শোয়ার্জিয়ান ট্রান্সফর্ম হল একটি কৌশল যা আইটেমগুলির একটি তালিকা বাছাই করার দক্ষতা উন্নত করতে ব্যবহৃত হয়। এই প্রবাদটি তুলনা-ভিত্তিক বাছাইয়ের জন্য উপযুক্ত যখন ক্রমটি আসলে উপাদানগুলির একটি নির্দিষ্ট বৈশিষ্ট্যের (কী) ক্রমের উপর ভিত্তি করে হয়, যেখানে সেই বৈশিষ্ট্যটি গণনা করা একটি নিবিড় ক্রিয়া যা ন্যূনতম সংখ্যক বার সম্পাদন করা উচিত। শোয়ার্জিয়ান রূপান্তরটি উল্লেখযোগ্য যে এটি নামযুক্ত অস্থায়ী অ্যারে ব্যবহার করে না। শোয়ার্জিয়ান রূপান্তর একটি লিস্প প্রবাদের একটি সংস্করণ যা ডেকোরেট-টাইপ-আনডেকরেট নামে পরিচিত, যা অস্থায়ীভাবে ইনপুট আইটেমগুলির সাথে সংযুক্ত করে সাজানো কীগুলি পুনরায় গণনা করা এড়িয়ে চলে। এই পদ্ধতিটি অনুরূপ, যা একটি নির্দিষ্ট ইনপুট মানের সাথে সম্পর্কিত কী-এর গণনার পুনরাবৃত্তি এড়িয়ে চলে। তুলনামূলকভাবে, এই প্রবাদটি আশ্বাস দেয় যে প্রতিটি ইনপুট আইটেমের কী ঠিক একবার গণনা করা হয়, যার ফলে ইনপুট ডেটাতে ডুপ্লিকেট আইটেম থাকলে কিছু গণনা পুনরাবৃত্তি হতে পারে। এই প্রবাদটির নামকরণ করা হয়েছে র্যান্ডাল এল. শোয়ার্জ-এর নামে, যিনি 1994 সালে পার্ল 5-এর মুক্তির পরপরই পার্ল-এ প্রথম এটি প্রদর্শন করেছিলেন। "শোয়ার্জিয়ান ট্রান্সফর্ম" শব্দটি বেশ কয়েক বছর ধরে শুধুমাত্র পার্ল প্রোগ্রামিং-এর ক্ষেত্রে প্রয়োগ করা হয়েছিল, কিন্তু পরে এটি অন্যান্য ভাষার কিছু ব্যবহারকারী, যেমন পাইথন, সেই ভাষাগুলির অনুরূপ প্রবাদগুলিকে বোঝাতে গ্রহণ করেছে। যাইহোক, অ্যালগরিদমটি ইতিমধ্যে অন্যান্য ভাষায় ব্যবহৃত হয়েছিল (কোনও নির্দিষ্ট নামে নয়) এটি শোয়ার্জ দ্বারা সেই নির্দিষ্ট প্রবাদের আকারে পার্ল সম্প্রদায়ের মধ্যে জনপ্রিয় হওয়ার আগে। "শোয়ার্জিয়ান ট্রান্সফর্ম" শব্দটি একটি নির্দিষ্ট প্রবাদকে নির্দেশ করে, সাধারণভাবে অ্যালগরিদমকে নয়। উদাহরণস্বরূপ, শব্দের দৈর্ঘ্য অনুযায়ী শব্দের তালিকা ("আয়া", "আ", "আ") সাজানোর জন্যঃ প্রথমে তালিকা তৈরি করুন (["আয়া", 4], ["এ", 1], ["আ", 2]), তারপর সংখ্যাসূচক মান অনুযায়ী সাজান (["এ", 1], ["আ", 2], ["আ", 4]), তারপর সংখ্যাগুলি কেটে ফেলুন এবং আপনি ("এ", "আ", "আ") পাবেন। এটি সাধারণভাবে অ্যালগরিদম ছিল, তাই এটি একটি রূপান্তর হিসাবে গণনা করা হয় না। এটিকে একটি সত্যিকারের শোয়ার্জিয়ান রূপান্তর করতে, এটি পার্ল-এ এইভাবে করা হবেঃ @sorted = মানচিত্র {$_-> [0]} সাজানো {$a-> [1] <= $b-> [1] বা $a-> [0] cmp $b-> [0]} #সংখ্যাসূচক তুলনা ব্যবহার করুন, মূল মানচিত্রে স্ট্রিং সার্টে ফিরে আসুন {[$_, দৈর্ঘ্য ($_)]} #স্ট্রিংয়ের দৈর্ঘ্য গণনা করুন @unsorted; পার্ল প্রবাদটি শোয়ার্জিয়ান রূপান্তরের সাধারণ রূপটি হলঃ @sorted = মানচিত্র {$_-> [0]] সাজানো {$a-> [1] cmp ডান থেকে বাম দিকে (বা নীচে থেকে উপরে) পড়াঃ মূল তালিকা @unsorted একটি মানচিত্র অপারেশনে দেওয়া হয় যা প্রতিটি আইটেমকে একটি (একটি বেনামী 2-উপাদানের রেফারেন্স) অ্যারেতে মোড়া করে এবং গণনা করা মান যা তার সাজানো ক্রম নির্ধারণ করবে (আইটেমের তালিকাটি [আইটেম, মান]-এর একটি তালিকা হয়ে যায়); তারপর মানচিত্র দ্বারা উত্পাদিত তালিকার তালিকা সাজানো হয়, যা এটিকে পূর্বে গণনা করা মান অনুযায়ী সাজানো হয় ([আইটেম, মান]-এর তালিকা [আইটেম, মান]-এর সাজানো তালিকা); অবশেষে, আরেকটি মানচিত্র অপারেশন বাছাইয়ের জন্য ব্যবহৃত মানগুলি (বেনামী অ্যারে থেকে) উন্মোচন করে, মূল তালিকার আইটেমগুলি সাজানো ক্রমে (আইটেম, মূল্যের সাজানো তালিকা) তৈরি করে। বেনামী অ্যারেগুলির ব্যবহার নিশ্চিত করে যে বাছাই করার পরপরই পার্ল আবর্জনা সংগ্রাহক দ্বারা মেমরি পুনরুদ্ধার করা হবে। দক্ষতা বিশ্লেষণ শোয়ার্জিয়ান রূপান্তর ব্যতীত, উপরের উদাহরণের বাছাইটি পার্ল ভাষায় এইভাবে লেখা হবেঃ @sorted = সাজানো {ফো ($a) সিএমপি ফো ($b)} @unsorted; যদিও এটি কোডের চেয়ে ছোট, তবে এখানে সরল পদ্ধতিটি অনেক কম কার্যকর হতে পারে যদি মূল ফাংশনটি (উপরের উদাহরণে বলা হয়েছে) গণনা করা ব্যয়বহুল হয়। এর কারণ হল প্রতিবার দুটি উপাদানের তুলনা করার প্রয়োজন হলে বন্ধনীর অভ্যন্তরে কোডটি মূল্যায়ন করা হয়। একটি সর্বোত্তম তুলনা বাছাই ও (এন লগ এন) তুলনা করে (যেখানে এন হল তালিকার দৈর্ঘ্য), প্রতিটি তুলনার জন্য 2টি কল সহ, যার ফলে ও (এন লগ এন) কল হয়। তুলনায়, শোয়ার্জিয়ান রূপান্তর ব্যবহার করে, আমরা প্রতি উপাদান প্রতি শুধুমাত্র 1 কল করি, প্রাথমিক পর্যায়ে, মোট n কলের জন্য। যাইহোক, যদি ফাংশনটি তুলনামূলকভাবে সহজ হয়, তবে শোয়ার্জিয়ান রূপান্তরের অতিরিক্ত ওভারহেড অযৌক্তিক হতে পারে। উদাহরণস্বরূপ, ফাইলগুলির একটি তালিকা তাদের পরিবর্তনের সময় অনুসারে সাজানোর জন্য, একটি সরল পদ্ধতি নিম্নরূপ হতে পারেঃ ফাংশন নাইভকোম্পেয়ার (ফাইল এ, ফাইল বি) {রিটার্ন মোডিফিকেশনটাইম (এ) <মোডিফিকেশনটাইম (বি)}// ধরে নিন যে সাজানো (তালিকা, তুলনাপ্রণীত) দুটি উপাদানের তুলনা করার জন্য প্রদত্ত তালিকাটি// তুলনাপ্রণীত ব্যবহার করে সাজান। সাজানো অ্যারেঃ = সাজানো (ফাইল অ্যারে, নাইভকম্পেয়ার) প্রতিটি ফাইলের জন্য পরিবর্তনের সময় না হলে, এই পদ্ধতিতে প্রতিবার কোনও ফাইলের তুলনা করার সময় তাদের পুনরায় গণনা করা প্রয়োজন। শোয়ার্জিয়ান রূপান্তর ব্যবহার করে, পরিবর্তনের সময় প্রতি ফাইল শুধুমাত্র একবার গণনা করা হয়। একটি শোয়ার্জিয়ান রূপান্তর উপরে বর্ণিত কার্যকরী প্রবাদের সাথে জড়িত, যা অস্থায়ী অ্যারে ব্যবহার করে না। একই অ্যালগরিদম পদ্ধতিগতভাবে লেখা যেতে পারে যাতে এটি কীভাবে কাজ করে তা আরও ভালভাবে ব্যাখ্যা করা যায়, তবে এর জন্য অস্থায়ী অ্যারে ব্যবহার করা প্রয়োজন, এবং এটি একটি শোয়ার্জিয়ান রূপান্তর নয়। নিম্নলিখিত উদাহরণটি সিউডো-কোড অ্যালগরিদমকে এইভাবে প্রয়োগ করেঃ ফাইলের প্রতিটি ফাইলের জন্য রূপান্তরিত অ্যারে ফাংশনের শেষে অ্যারে সন্নিবেশ অ্যারে (ফাইল, পরিবর্তনের সময় (ফাইল)) সিম্পলঅ্যারে তুলনা করুন (অ্যারে a, অ্যারে b) {রিটার্ন a [2] <b [2]} রূপান্তরিত অ্যারেঃ = সাজানো (রূপান্তরিত অ্যারে, সিম্পলকম্পেয়ার) সাজানো অ্যারে ইতিহাসের শেষে রূপান্তরিত অ্যারে সন্নিবেশ ফাইলের প্রতিটি ফাইলের জন্য [1] শোয়ার্জিয়ান রূপান্তরের প্রথম পরিচিত অনলাইন উপস্থিতি 16ই ডিসেম্বর, 1994-এ র্যান্ডাল শোয়ার্জ দ্বারা comp.unix.shell ইউজনেট নিউজগ্রুপের একটি থ্রেডে পোস্ট করা হয়, যা comp.lang.perl-এ ক্রসপোস্ট করা হয়। (পার্ল টাইমলাইনের বর্তমান সংস্করণটি ভুল এবং 1995 সালের পরবর্তী তারিখকে বোঝায়।) থ্রেডটি তাদের "শেষ" শব্দ দ্বারা লাইনগুলির একটি তালিকা কিভাবে সাজানো যায় সে সম্পর্কে একটি প্রশ্ন দিয়ে শুরু হয়েছিলঃ সংযোজনঃ জোশুয়া এনজি অ্যাডকেটকঃ কালাপ টিমোথি কোওং অ্যাডমেগঃ মহালিঙ্গম গোবিয়েরামানান অ্যাডমেঃ মার্থা এল নাঙ্গালামা শোয়ার্জ উত্তর দিয়েছিলেনঃ #!/ইউএসআর/বিন/পার্লের জন্য 5 প্রয়োজন; #নতুন বৈশিষ্ট্য, নতুন বাগ! মুদ্রণ মানচিত্র {$_-> [0]} সাজানো {$a-> [1] cmp $b-> [1]] মানচিত্র {[$_,/(\S +) $/]} <>; এই কোডটি ফলাফল তৈরি করেঃ অ্যাডজেঃ মহালিঙ্গম গোবিরামানান অ্যাডকেঃ কালাপ টিমোথি কোয়ং অ্যাডজেঃ মার্থা এল. নঙ্গালামা অ্যাডজেঃ জোশুয়া এনজি শোয়ার্জ পোস্টে উল্লেখ করেছেন যে তিনি "পার্লের একটি লিস্পের সাথে কথা বলছেন", যা প্রবাদটির লিস্প উত্সের একটি রেফারেন্স। "শোয়ার্জিয়ান ট্রান্সফর্ম" শব্দটি নিজেই টম ক্রিস্টিয়ানসেন একটি ফলো-আপ উত্তরে তৈরি করেছিলেন। ক্রিস্টিয়ানসেনের পরবর্তী পোস্টগুলি স্পষ্ট করে দিয়েছিল যে তিনি নির্মাণের নাম দিতে চাননি, বরং কেবল মূল পোস্ট থেকে এটি উল্লেখ করতে চেয়েছিলেনঃ অবশেষে এটির নাম "দ্য ব্ল্যাক ট্রান্সফর্ম" রাখার তাঁর প্রচেষ্টা সফল হয়নি ("ব্ল্যাক" এখানে "শোয়ার [টি] জেড"-এর উপর একটি শ্লেষ, যার জার্মানিতে অর্থ কালো)। অন্যান্য ভাষার সাথে তুলনা কিছু অন্যান্য ভাষা শোয়ার্জিয়ান রূপান্তরের মতো একই অপ্টিমাইজেশনের জন্য একটি সুবিধাজনক ইন্টারফেস প্রদান করেঃ পাইথন 2.4 এবং তার উপরে, ফাংশন এবং ইন-প্লেস পদ্ধতি উভয়ই একটি পরামিতি গ্রহণ করে যা ব্যবহারকারীকে একটি "কী ফাংশন" প্রদান করতে দেয় (উপরের উদাহরণগুলির মতো)। পাইথন 3 এবং তার উপরে, কী ফাংশন ব্যবহার করা একটি কাস্টম বাছাই ক্রম নির্দিষ্ট করার একমাত্র উপায় (পূর্বে সমর্থিত পরামিতি যা ব্যবহারকারীকে একটি "তুলনা ফাংশন" প্রদান করার অনুমতি দেয় তা সরানো হয়েছিল)। পাইথন 2.4-এর আগে, ডেভেলপাররা লিস্প-অরিজিনেটেড ডেকোরেট-টাইপ-আনডেকরেট (ডিএসইউ) প্রবাদ ব্যবহার করতেন, সাধারণত একটি (সার্টকি, অবজেক্ট) টুপলে বস্তুগুলিকে মোড়িয়ে। রুবি 1.8.6 এবং তার উপরে, বিমূর্ত শ্রেণীতে (যার মধ্যে s রয়েছে) একটি পদ্ধতি রয়েছে, যা কোড ব্লক হিসাবে "কী ফাংশন" (উপরের উদাহরণগুলির মতো) নির্দিষ্ট করার অনুমতি দেয়। ডি 2 এবং তার উপরে, ফাংশনটি উপলব্ধ। এর জন্য কম অস্থায়ী তথ্যের প্রয়োজন হতে পারে এবং এটি পার্ল প্রবাদ বা পাইথন এবং লিস্পে উপস্থিত সাজানো-সাজানো-অলঙ্কৃত প্রবাদের চেয়ে দ্রুত হতে পারে। এর কারণ হল বাছাই করা হয় এবং শুধুমাত্র ন্যূনতম অতিরিক্ত ডেটা (রূপান্তরিত উপাদানগুলির একটি অ্যারে) তৈরি করা হয়। র্যাকেটের মূল বাছাই ফাংশন একটি #: কীওয়ার্ড আর্গুমেন্ট গ্রহণ করে একটি ফাংশন সহ যা একটি কী বের করে এবং একটি অতিরিক্ত #: ক্যাশে-কী? বাছাই করার সময় ফলাফলের মানগুলি ক্যাশে করার অনুরোধ করা হয়। উদাহরণস্বরূপ, একটি তালিকা পরিবর্তন করার একটি সুবিধাজনক উপায় হল। পিএইচপি 5.3 এবং তার উপরে রূপান্তরটি ব্যবহার করে প্রয়োগ করা যেতে পারে, যেমন। PHP.function স্পেসবলস _ সার্টে (অ্যারে & $a) অস্থির সাজানো অ্যালগরিদমগুলির সীমাবদ্ধতার চারপাশে কাজ করার জন্যঃ অকার্যকর {অ্যারে _ ওয়াক ($a, ফাংশন (& $v, $k) {$v = অ্যারে ($v, $k);}); অ্যাসর্ট ($a); অ্যারে _ ওয়াক ($a, ফাংশন (& $v, $$) {$v = $v [0];} এলিক্সিরে, এবং পদ্ধতিগুলি ব্যবহারকারীদের প্রোটোকল প্রয়োগ করে এমন যে কোনও মডিউলের জন্য একটি শোয়ার্জিয়ান রূপান্তর সম্পাদন করার অনুমতি দেয়। রাকুর মধ্যে, একজনকে একটি তুলনামূলক ল্যাম্বডা সরবরাহ করতে হবে যা হুডের নীচে একটি শোয়ার্জিয়ান রূপান্তর সম্পাদন করতে কেবল 1 টি যুক্তি নেয়ঃ @a.sort ({$a.Str}) #বা সংক্ষিপ্তঃ @a.sort (*. Str) একটি শোয়ার্জিয়ান রূপান্তর ব্যবহার করে স্ট্রিং উপস্থাপনায় বাছাই করবে, @a.sort ({$a.Str cmp $^ b.Str}) প্রতিটি তুলনার ঠিক আগে উপাদানগুলিকে তুলনা করার জন্য রূপান্তর করবে। রাস্টে, কিছুটা বিভ্রান্তিকরভাবে, পদ্ধতিটি একটি শোয়ার্জিয়ান রূপান্তর * সম্পাদন করে না কারণ এটি কীটির জন্য অতিরিক্ত স্টোরেজ বরাদ্দ করবে না, এটি প্রতিটি তুলনার জন্য প্রতিটি মানের জন্য কী ফাংশনকে কল করবে। পদ্ধতিটি প্রতি উপাদানের জন্য একবার কী গণনা করবে। রেফারেন্স বাহ্যিক লিঙ্ক র্যান্ডাল এল. শোয়ার্জ মার্ক-জেসন ডমিনাসের শোয়ার্জিয়ান ট্রান্সফর্মের সাথে বাছাই করা শোয়ার্জিয়ান ট্রান্সফর্ম http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234 পাইথন সফ্টওয়্যার ফাউন্ডেশন (2005) ব্যাখ্যা করে। 1. 5. 2 আমি একটি জটিল বিন্যাস করতে চাইঃ আপনি কি পাইথনে একটি শোয়ার্জিয়ান রূপান্তর করতে পারেন? সংগ্রহের তারিখ জুন 22,2005। মেমোইজ পার্ল মডিউল-ব্যয়বহুল ফাংশনগুলিকে তাদের ফলাফল ক্যাশে করে দ্রুততর করে তোলে। অ্যালগরিদম বাছাই করা-পার্ল কোডের উদাহরণ সহ নিবন্ধ র্যাকেট কোড পার্লের উদাহরণ সহ নিবন্ধ