algorithm - एक ढेर से मोजे को कुशलता से कैसे जोड़ा जाए?




sorting language-agnostic (20)

एक व्यावहारिक समाधान के रूप में:

  1. आसानी से आसानी से अलग करने योग्य मोजे के ढेर बनाओ। (रंग से कहो)
  2. प्रत्येक ढेर Quicksort और तुलना के लिए सॉक की लंबाई का उपयोग करें। एक इंसान के रूप में आप एक काफी तेज़ निर्णय ले सकते हैं जो विभाजन के लिए उपयोग करने के लिए सदमे का सबसे बुरा मामला बचाता है। (आप समानांतर में एकाधिक मोजे देख सकते हैं, अपने लाभ के लिए इसका उपयोग करें!)
  3. जब वे थ्रेसहोल्ड पर पहुंचे तो ढेर को छूना बंद करें, जहां आप स्पॉट जोड़े और अनपेक्षित मोजे तुरंत ढूंढने में सहज महसूस करते हैं

यदि आपके पास 8 रंग और औसत वितरण के साथ 1000 मोजे हैं, तो आप सी * एन समय में प्रत्येक 125 मोजे के 4 ढेर बना सकते हैं। 5 मोजे की सीमा के साथ आप प्रत्येक ढेर को 6 रनों में क्रमबद्ध कर सकते हैं। (दाएं ढेर पर एक साक फेंकने के लिए 2 सेकंड की गणना करना यह आपको 4 घंटे से कम समय ले जाएगा।)

यदि आपके पास केवल 60 मोजे हैं, 3 रंग और 2 प्रकार के मोजे (आपकी / आपकी पत्नी) आप 10 मोजे के प्रत्येक ढेर को 1 रन में क्रमबद्ध कर सकते हैं (फिर थ्रेसहोल्ड = 5)। (2 सेकंड की गणना करने से आपको 2 मिनट लगेंगे)।

शुरुआती बाल्टी सॉर्टिंग आपकी प्रक्रिया को तेज करेगी, क्योंकि यह आपके एन मोजे को c*n समय में के बाल्टी में विभाजित करती है, इसलिए आपको केवल c*n*log(k) काम करना होगा। (थ्रेसहोल्ड खाते में नहीं लेना)। तो आप सब कुछ n*c*(1 + log(k)) करते हैं, जहां सी ढेर पर एक साक फेंकने का समय है।

यह दृष्टिकोण c*x*n + O(1) किसी भी c*x*n + O(1) विधि की तुलना में अनुकूल होगा जब तक log(k) < x - 1

कंप्यूटर विज्ञान में यह सहायक हो सकता है: हमारे पास एन चीजों का संग्रह है, उन पर एक आदेश (लंबाई) और एक समानता संबंध (अतिरिक्त जानकारी, उदाहरण के लिए मोजे का रंग)। समकक्ष संबंध हमें मूल संग्रह का विभाजन करने की अनुमति देता है, और प्रत्येक समकक्ष वर्ग में हमारा आदेश अभी भी बनाए रखा जाता है। इसकी समकक्ष कक्षा में किसी चीज का मैपिंग ओ (1) में किया जा सकता है, इसलिए प्रत्येक आइटम को कक्षा में असाइन करने के लिए केवल ओ (एन) की आवश्यकता होती है। अब हमने अपनी अतिरिक्त जानकारी का उपयोग किया है और हर वर्ग को क्रमबद्ध करने के लिए किसी भी तरह से आगे बढ़ सकता है। लाभ यह है कि डेटा सेट पहले से ही काफी छोटे हैं।

विधि को घोंसला भी दिया जा सकता है, अगर हमारे पास एकाधिक समकक्ष संबंध हैं -> लंबाई पर सॉर्ट करने के बजाय, बनावट पर प्रत्येक ढेर विभाजन के भीतर रंगीन ढेर बनाएं। कोई समकक्ष संबंध जो कि 2 से अधिक तत्वों के साथ एक विभाजन बनाता है, जिसमें आकार भी है, क्रमबद्ध करने पर गति सुधार लाएगा (बशर्ते हम सीधे अपने ढेर पर एक सॉक असाइन कर सकें), और सॉर्टिंग छोटे डेटा सेट पर बहुत तेज़ी से हो सकती है।

कल मैं साफ कपड़े धोने से मोजे जोड़ रहा था और जिस तरह से मैं कर रहा था यह पता लगाया कि यह बहुत ही कुशल नहीं है। मैं एक बेवकूफ खोज कर रहा था - अपनी जोड़ी खोजने के लिए एक साक उठाकर ढेर को "पुनरावृत्त" कर रहा था। इसके लिए औसतन एन / 2 * एन / 4 = एन 2/8 मोजे पर पुनरावृत्ति की आवश्यकता होती है।

एक कंप्यूटर वैज्ञानिक के रूप में मैं सोच रहा था कि मैं क्या कर सकता था? सॉर्टिंग (आकार / रंग / ... के अनुसार) एक ओ (एनएलओएनएन) समाधान प्राप्त करने के लिए ध्यान में आया।

हैशिंग या अन्य जगहों पर समाधान एक विकल्प नहीं हैं, क्योंकि मैं अपने मोजे को डुप्लिकेट करने में सक्षम नहीं हूं (हालांकि यह अच्छा हो सकता है अगर मैं कर सकता था)।

तो, सवाल मूल रूप से है:

मोजे के n जोड़े के ढेर को देखते हुए, जिसमें 2n तत्व होते हैं (मान लें कि प्रत्येक सॉक में वास्तव में एक मिलान करने वाली जोड़ी है), लॉगरिदमिक अतिरिक्त स्थान तक कुशलतापूर्वक उन्हें जोड़ने के लिए सबसे अच्छा तरीका क्या है? (मुझे विश्वास है कि अगर आवश्यक हो तो मुझे उस राशि की जानकारी याद हो सकती है।)

मैं एक ऐसे उत्तर की सराहना करता हूं जो निम्नलिखित पहलुओं को संबोधित करता है:

  • बड़ी संख्या में मोजे के लिए एक सामान्य सैद्धांतिक समाधान।
  • मोजे की वास्तविक संख्या इतना बड़ी नहीं है, मुझे विश्वास नहीं है कि मेरे पति / पत्नी और मेरे पास 30 से अधिक जोड़े हैं। (और मेरे मोजे और उसके बीच अंतर करना काफी आसान है; क्या इसका भी उपयोग किया जा सकता है?)
  • क्या यह तत्व विशिष्टता समस्या के बराबर है ?

चूंकि मानव मस्तिष्क का आर्किटेक्चर आधुनिक सीपीयू से बिल्कुल अलग है, इसलिए यह सवाल कोई व्यावहारिक समझ नहीं लेता है।

मनुष्य इस तथ्य का उपयोग कर सीपीयू एल्गोरिदम पर जीत सकते हैं कि "मिलान करने वाली जोड़ी ढूंढना" एक सेट के लिए एक ऑपरेशन हो सकता है जो बहुत बड़ा नहीं है।

मेरा एल्गोरिदम:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

कम से कम यही वह है जो मैं वास्तविक जीवन में उपयोग कर रहा हूं, और मुझे यह बहुत ही कुशल लगता है। नकारात्मकता यह एक सपाट सतह की आवश्यकता है, लेकिन यह आमतौर पर प्रचुर मात्रा में है।


यह गलत सवाल पूछ रहा है। पूछने का सही सवाल यह है कि, मैं सॉर्ट सॉर्टिंग समय क्यों खर्च कर रहा हूं? जब आप अपनी पसंद के एक्स मौद्रिक इकाइयों के लिए अपना खाली समय मानते हैं, तो सालाना आधार पर इसका कितना खर्च होता है?

और अक्सर नहीं, यह सिर्फ कोई खाली समय नहीं है, सुबह का खाली समय है, जिसे आप बिस्तर पर खर्च कर सकते हैं, या अपनी कॉफी पी सकते हैं, या थोड़ा जल्दी छोड़कर यातायात में पकड़े नहीं जा सकते हैं।

एक कदम वापस लेने के लिए अक्सर अच्छा होता है, और समस्या के चारों ओर एक रास्ता सोचते हैं।

और एक रास्ता है!

आपको पसंद है एक साक खोजें। सभी प्रासंगिक विशेषताओं को ध्यान में रखें: विभिन्न प्रकाश स्थितियों में रंग, समग्र गुणवत्ता और स्थायित्व, विभिन्न जलवायु स्थितियों में आराम, और गंध अवशोषण। यह भी महत्वपूर्ण है कि उन्हें भंडारण में लोच नहीं खोना चाहिए, इसलिए प्राकृतिक कपड़े अच्छे हैं, और उन्हें प्लास्टिक के लपेटने में उपलब्ध होना चाहिए।

बाएं और दाएं पैर मोजे के बीच कोई अंतर नहीं है, लेकिन यह महत्वपूर्ण नहीं है। यदि मोजे बाएं-दाएं सममित होते हैं, तो एक जोड़ी ढूंढना ओ (1) ऑपरेशन होता है, और मोजे को सॉर्ट करना ओ (एम) ऑपरेशन अनुमानित होता है, जहां एम आपके घर में स्थानों की संख्या है, जिसे आपने मोजे से भंग कर दिया है, आदर्श रूप से कुछ छोटे निरंतर संख्या।

यदि आपने अलग-अलग बाएं और दाएं साक के साथ एक फैंसी जोड़ी चुना है, तो बाएं और दाएं पैर बाल्टी के लिए एक पूर्ण बाल्टी प्रकार कर ओ (एन + एम) लेते हैं, जहां एन मोजे की संख्या है और एम ऊपर जैसा ही है। कोई और पहली जोड़ी ढूंढने के औसत पुनरावृत्तियों के लिए सूत्र दे सकता है, लेकिन अंधेरे खोज के साथ एक जोड़ी खोजने के लिए सबसे खराब मामला एन / 2 + 1 है, जो उचित एन के लिए खगोलीय रूप से असंभव मामला बन जाता है। इसे उन्नत छवि का उपयोग करके बढ़ाया जा सकता है एमके 1 आईबॉल के साथ बिना छिद्रित मोजे के ढेर को स्कैन करते समय पहचान एल्गोरिदम और हेरिस्टिक्स।

तो, ओ (1) सॉक युग्मन दक्षता प्राप्त करने के लिए एक एल्गोरिदम (सममित सॉकेट मानना) है:

  1. आपको यह अनुमान लगाने की ज़रूरत है कि आपके बाकी जीवन के लिए आपको कितने मोजे की आवश्यकता होगी, या शायद जब तक आप सेवानिवृत्त न हो जाएं और गर्म मौसम में जाएं, बिना किसी मोजे पहनने की आवश्यकता हो। यदि आप जवान हैं, तो आप अनुमान लगा सकते हैं कि हमारे घरों में सभी को सॉक-सॉर्टिंग रोबोट होने से पहले कितना समय लगता है, और पूरी समस्या अप्रासंगिक हो जाती है।

  2. आपको यह पता लगाना होगा कि आप अपने चुने हुए सॉक को थोक में कैसे ऑर्डर कर सकते हैं, और इसका कितना खर्च होता है, और वे वितरित करते हैं।

  3. मोजे आदेश!

  4. अपने पुराने मोजे से छुटकारा पाएं।

एक वैकल्पिक चरण 3 में वर्षों में एक ही समय में कुछ जोड़े जोड़े जाने और मोजे को सॉर्ट करने की लागत जोड़ने की लागत की तुलना करने की लागत शामिल होगी, लेकिन इसके लिए मेरा शब्द लें: थोक में खरीदारी सस्ता है! इसके अलावा, स्टॉक मूल्य मुद्रास्फीति की दर से मूल्य में भंडारण में मोजे बढ़ते हैं, जो आपको कई निवेशों से अधिक है। फिर फिर भी भंडारण लागत है, लेकिन मोजे वास्तव में एक कोठरी के शीर्ष शेल्फ पर ज्यादा जगह नहीं लेते हैं।

समस्या सुलझ गयी। तो, बस नए मोजे प्राप्त करें, अपने पुराने लोगों को फेंक दें / दान करें, और यह जानकर खुशी से रहें कि आप अपने पूरे जीवन के लिए हर दिन पैसे और समय बचा रहे हैं।


यह सवाल वास्तव में गहरा दार्शनिक है। दिल में यह है कि लोगों की समस्याओं को हल करने की शक्ति (हमारे दिमाग का "गीलावेयर) क्या है जो एल्गोरिदम द्वारा पूरा किया जा सकता है।

सॉक सॉर्टिंग के लिए एक स्पष्ट एल्गोरिदम है:

Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
  if s matches a sock t in N
    remove t from N, bundle s and t together, and throw them in the basket
  else
    add s to N

अब इस समस्या में कंप्यूटर विज्ञान सभी चरणों के बारे में है

  1. "अगर एन में एक सॉक टी के साथ जोड़े हैं"। हमने अब तक जो कुछ देखा है, उसे हम कितनी जल्दी याद कर सकते हैं?
  2. "एन से टी हटाएं" और "एस से एन जोड़ें"। हमने जो देखा है उसका ट्रैक रखने में कितना महंगा है?

इन प्रभावों को प्रभावित करने के लिए मनुष्य विभिन्न रणनीतियों का उपयोग करेंगे। मानव स्मृति सहयोगी है , कुछ हैश टेबल की तरह है जहां संग्रहीत मूल्यों के फीचर सेट को संबंधित मानों के साथ जोड़ दिया जाता है। उदाहरण के लिए, सभी लाल कारों के लिए "लाल कार" मानचित्रों की अवधारणा एक व्यक्ति याद रखने में सक्षम है। एक परिपूर्ण स्मृति वाले किसी व्यक्ति के पास एक आदर्श मैपिंग है। अधिकांश लोग इस संबंध में अपूर्ण हैं (और अधिकांश अन्य)। सहयोगी मानचित्र की सीमित क्षमता है। मैपिंग विभिन्न परिस्थितियों (एक बियर भी बहुत से) के तहत अस्तित्व से बाहर हो सकती है, त्रुटि में दर्ज की जा सकती है ("हालांकि मेरा नाम बेट्टी था, नेटी नहीं"), या कभी भी ओवरराइट नहीं किया गया है, भले ही हम देखते हैं कि सत्य बदल गया है ("पिताजी कार "नारंगी फायरबर्ड" evokes "जब हम वास्तव में पता था कि वह लाल कैमरो के लिए व्यापार किया था)।

मोजे के मामले में, सही याद करने का मतलब है कि एक सॉक की तलाश हमेशा निरंतर समय में t का पता लगाने के लिए पर्याप्त जानकारी (जहां यह इस्त्री बोर्ड पर है) सहित अपने भाई t की याददाश्त उत्पन्न करती है। फोटोग्राफिक मेमोरी वाला एक व्यक्ति बिना किसी विफलता के निरंतर समय में 1 और 2 दोनों को पूरा करता है।

सही मेमोरी से कम वाला कोई व्यक्ति ट्रैक करने की क्षमता के भीतर सुविधाओं के आधार पर कुछ कॉमन्सेंस समकक्ष वर्गों का उपयोग कर सकता है: आकार (पिताजी, माँ, बच्चा), रंग (हरा, लाल, आदि), पैटर्न (argyle, plain, आदि) , शैली (फूटी, घुटने-उच्च, आदि)। इसलिए इस्त्री बोर्ड श्रेणियों के लिए वर्गों में विभाजित किया जाएगा। यह आमतौर पर श्रेणी को स्मृति द्वारा स्थिर समय में स्थित होने की अनुमति देता है, लेकिन फिर "बाल्टी" श्रेणी के माध्यम से एक रैखिक खोज की आवश्यकता होती है।

कोई भी स्मृति या कल्पना के साथ बिल्कुल (माफ करना) मोजे को एक ढेर में रखेगा और पूरे ढेर की रैखिक खोज करेगा।

एक साफ सनकी जोड़े के लिए संख्यात्मक लेबल का उपयोग कर सकता है जैसा कि किसी ने सुझाव दिया था। यह कुल ऑर्डरिंग का दरवाजा खुलता है, जो मनुष्य को उसी सीपीयू के साथ उसी एल्गोरिदम का उपयोग करने की अनुमति देता है: बाइनरी सर्च, पेड़, हैश इत्यादि।

तो "सर्वश्रेष्ठ" एल्गोरिदम गीलेवेयर / हार्डवेयर / सॉफ़्टवेयर के गुणों पर निर्भर करता है जो इसे चला रहा है और जोड़ों पर कुल आदेश लगाकर "धोखा" की हमारी इच्छा पर निर्भर करता है। निश्चित रूप से एक "सर्वश्रेष्ठ" मेटा- एल्गोरिदम दुनिया के सर्वश्रेष्ठ सॉक-सॉर्टर को किराए पर लेना है: एक व्यक्ति या मशीन जो एक विशाल सेट को एक्वायर और त्वरित रूप से संग्रहीत कर सकती है एन सॉक एट्रिब्यूट सेट को 1-1 एसोसिएटिव मेमोरी में निरंतर समय लुकअप, डालने, और हटाएं। इस तरह के दोनों लोगों और मशीनों की खरीद की जा सकती है। यदि आपके पास कोई है, तो आप एन जोड़े के लिए ओ (एन) समय में सभी मोजे जोड़ सकते हैं, जो इष्टतम है। कुल ऑर्डर टैग आपको मानव या हार्डवेयर कंप्यूटर के साथ एक ही परिणाम प्राप्त करने के लिए मानक हैशिंग का उपयोग करने की अनुमति देता है।


सॉर्टिंग समाधान प्रस्तावित किए गए हैं, लेकिन सॉर्टिंग थोड़ा अधिक है : हमें ऑर्डर की आवश्यकता नहीं है; हमें केवल समानता समूहों की आवश्यकता है

तो हैशिंग पर्याप्त (और तेज) होगा।

  1. मोजे के प्रत्येक रंग के लिए, एक ढेर बनाओ । अपनी इनपुट टोकरी में सभी मोजे पर इटरेट करें और उन्हें रंगीन ढेर पर वितरित करें
  2. प्रत्येक ढेर पर इटरेट करें और इसे किसी अन्य मीट्रिक (उदाहरण के लिए पैटर्न) द्वारा ढेर के दूसरे सेट में वितरित करें
  3. इस योजना को दोबारा लागू करें जब तक कि आप सभी मोजे को बहुत छोटी ढेर पर वितरित नहीं करते हैं जिन्हें आप तुरंत देख सकते हैं

इस प्रकार का रिकर्सिव हैश विभाजन वास्तव में SQL सर्वर द्वारा किया जा रहा है जब इसे हैश में शामिल होने की आवश्यकता है या विशाल डेटा सेट पर हैश कुल है। यह अपने विभाजन इनपुट स्ट्रीम को कई विभाजनों में वितरित करता है जो स्वतंत्र हैं। यह योजना डेटा की मनमानी मात्रा और कई CPUs रैखिक रूप से स्केल करती है।

यदि आप एक वितरण कुंजी (हैश कुंजी) पा सकते हैं तो आपको रिकर्सिव विभाजन की आवश्यकता नहीं है जो पर्याप्त बाल्टी प्रदान करता है कि प्रत्येक बाल्टी बहुत जल्दी संसाधित होने के लिए पर्याप्त छोटा है। दुर्भाग्यवश, मुझे नहीं लगता कि मोजे की ऐसी संपत्ति है।

यदि प्रत्येक सॉक में "PairID" नामक एक पूर्णांक होता है तो उसे आसानी से PairID % 10 (अंतिम अंक) के अनुसार 10 बाल्टी में वितरित कर सकता है।

सबसे अच्छा असली दुनिया विभाजन मैं सोच सकता हूं कि ढेर का आयत बना रहा है: एक आयाम रंग है, दूसरा पैटर्न है। एक आयताकार क्यों? क्योंकि हमें ओ (1) यादृच्छिक-पहुंच ढेर की आवश्यकता है। (एक 3 डी cuboid भी काम करेगा, लेकिन यह बहुत व्यावहारिक नहीं है।)

अद्यतन करें:

समांतरता के बारे में क्या? क्या कई इंसान मोजे से तेजी से मेल खाते हैं?

  1. सबसे सरल समांतरता रणनीति है कि कई श्रमिक इनपुट टोकरी से लें और मोजे को ढेर पर रखें। यह केवल इतना ही बढ़ाता है - कल्पना करें कि 100 लोग 10 ढेर से लड़ रहे हैं। सिंक्रनाइज़ेशन लागत (स्वयं को टकराव और मानव संचार के रूप में प्रकट करना) दक्षता और गति को नष्ट कर देता है ( सार्वभौमिक स्केलेबिलिटी लॉ देखें !)। क्या यह deadlocks के लिए प्रवण है? नहीं, क्योंकि प्रत्येक कार्यकर्ता को केवल एक समय में एक ढेर तक पहुंचने की आवश्यकता होती है। केवल एक "ताला" के साथ एक डेडलॉक नहीं हो सकता है। इंसान कैसे ढेर तक पहुंच को समन्वयित करते हैं, इस पर निर्भर करता है कि लाइवेलॉक्स संभव हो सकता है। वे केवल नेटवर्क कार्ड जैसे यादृच्छिक बैकऑफ का उपयोग कर सकते हैं, यह निर्धारित करने के लिए कि कौन सा कार्ड नेटवर्क तार तक पहुंच सकता है, यह निर्धारित करने के लिए भौतिक स्तर पर करता है। यदि यह NICs लिए काम करता है, तो इसे मनुष्यों के लिए भी काम करना चाहिए।
  2. यदि प्रत्येक कार्यकर्ता के पास ढेर का सेट होता है तो यह लगभग अनिश्चित काल तक स्केल करता है। श्रमिक इनपुट टोकरी से मोजे के बड़े हिस्से ले सकते हैं (बहुत कम विवाद क्योंकि वे इसे शायद ही कभी कर रहे हैं) और उन्हें मोजे वितरित करते समय सिंक्रनाइज़ करने की आवश्यकता नहीं है (क्योंकि उनके पास थ्रेड-स्थानीय ढेर हैं)। अंत में, सभी श्रमिकों को अपने ढेर-सेटों को संघबद्ध करने की आवश्यकता होती है। मेरा मानना ​​है कि ओ में किया जा सकता है (लॉग (कार्यकर्ता गिनती * प्रति कार्यकर्ता ढेर)) यदि मजदूर एकत्रीकरण वृक्ष बनाते हैं।

तत्व विशिष्टता समस्या के बारे में क्या? जैसा कि लेख बताता है, O(N) में तत्व विशिष्टता समस्या हल हो सकती है। मोजे की समस्या के लिए यह वही है ( O(N) , यदि आपको केवल एक वितरण चरण की आवश्यकता है (मैंने केवल कई चरणों का प्रस्ताव दिया क्योंकि मनुष्य गणनाओं में खराब हैं - यदि आप md5(color, length, pattern, ...) पर वितरित करते हैं तो एक कदम पर्याप्त है md5(color, length, pattern, ...) , यानी सभी विशेषताओं का एक परिपूर्ण हैश ))।

जाहिर है, कोई O(N) से तेज़ नहीं जा सकता है, इसलिए हम इष्टतम निचले बाउंड तक पहुंच गए हैं।

यद्यपि आउटपुट बिल्कुल समान नहीं हैं (एक मामले में, केवल एक बूलियन। दूसरे मामले में, मोजे के जोड़े), एसिम्प्टोटिक जटिलताएं समान होती हैं।


आप गलत समस्या को हल करने की कोशिश कर रहे हैं।

समाधान 1: हर बार जब आप अपनी कपड़े धोने की टोकरी में गंदे मोजे डालते हैं, तो उन्हें थोड़ा गाँठ में बांध दें। इस तरह आपको धोने के बाद कोई सॉर्टिंग नहीं करना पड़ेगा। इसके बारे में सोचें जैसे मोंगो डेटाबेस में एक इंडेक्स पंजीकृत करना। भविष्य में कुछ सीपीयू बचत के लिए थोड़ा सा काम आगे बढ़ता है।

समाधान 2: यदि यह सर्दी है, तो आपको मिलान करने वाले मोजे पहनने की ज़रूरत नहीं है। हम प्रोग्रामर हैं। जब तक यह काम करता है, तब तक किसी को भी जानने की जरूरत नहीं है।

समाधान 3: काम फैलाओ। आप UI को अवरुद्ध किए बिना, इस तरह की एक जटिल CPU प्रक्रिया को असंकालिक रूप से निष्पादित करना चाहते हैं। मोजे के ढेर ले लो और उन्हें एक बैग में सामान। जब आपको आवश्यकता हो तो केवल एक जोड़ी की तलाश करें। इस तरह से काम की मात्रा बहुत कम ध्यान देने योग्य है।

उम्मीद है की यह मदद करेगा!


प्रकरण 1 : सभी मोजे समान हैं (यही वह है जो मैं वास्तविक जीवन में करता हूं)।

एक जोड़ी बनाने के लिए उनमें से किसी एक को चुनें। लगातार समय

प्रकरण 2 : संयोजनों की निरंतर संख्या (स्वामित्व, रंग, आकार, बनावट इत्यादि) हैं।

रेडिक्स सॉर्ट का प्रयोग करें। यह केवल रैखिक समय है क्योंकि तुलना की आवश्यकता नहीं है।

प्रकरण 3 : संयोजनों की संख्या अग्रिम (सामान्य मामला) में ज्ञात नहीं है।

हमें यह जांचने के लिए तुलना करना है कि दो मोजे जोड़ी में आते हैं या नहीं। O(n log n) तुलना-आधारित सॉर्टिंग एल्गोरिदम में से एक चुनें।

हालांकि वास्तविक जीवन में जब मोजे की संख्या अपेक्षाकृत छोटी (स्थिर) होती है, तो ये सैद्धांतिक रूप से इष्टतम एल्गोरिदम अच्छी तरह से काम नहीं करेंगे। अनुक्रमिक खोज से अधिक समय लग सकता है, जिसे सैद्धांतिक रूप से वर्गिक समय की आवश्यकता होती है।


असली दुनिया दृष्टिकोण:

जितनी जल्दी हो सके, एक समय में बिना छिद्रित ढेर से मोजे हटा दें और आपके सामने ढेर में रखें। ढेर को कुछ हद तक अंतरिक्ष-कुशलता से व्यवस्थित किया जाना चाहिए, सभी मोजे एक ही दिशा को इंगित करते हैं; ढेर की संख्या उस दूरी से सीमित है जहां आप आसानी से पहुंच सकते हैं। एक ढेर को चुनने के लिए जिस पर एक सॉक डालना चाहिए - जितनी जल्दी हो सके - मोजे की तरह ढेर पर एक साँस डालकर; कभी-कभी प्रकार I (एक ढेर पर एक सॉक डालने से संबंधित नहीं होता है) या टाइप II (मोजे की मौजूदा ढेर होने पर अपने स्वयं के ढेर में एक सॉक डालना) त्रुटि सहन की जा सकती है - सबसे महत्वपूर्ण विचार गति है। एक बार जब सभी मोजे ढेर में होते हैं, तो तेजी से मल्टी-सॉक ढेर के माध्यम से जोड़े बनाते हैं और उन्हें हटाते हैं (ये दराज के लिए जा रहे हैं)। यदि ढेर में गैर-मेल खाने वाले मोजे हैं, तो उन्हें अपने सर्वश्रेष्ठ (जितनी तेजी से संभव बाधा के भीतर) ढेर में फिर से ढेर करें। जब सभी मल्टी-सॉक ढेर संसाधित किए जाते हैं, तो शेष जोड़ी योग्य मोजे से मेल खाते हैं जिन्हें टाइप II त्रुटियों के कारण जोड़ा नहीं गया था। हुओश, आप कर चुके हैं - और मेरे पास बहुत सारे मोजे हैं और उन्हें तब तक धोना नहीं जब तक कि एक बड़ा अंश गंदा न हो। एक अन्य व्यावहारिक नोट: मैं अपने लोचदार गुणों का लाभ उठाते हुए, मोजे की एक जोड़ी में से एक के ऊपर एक तरफ फिसलता हूं, इसलिए वे दराज में ले जा रहे हैं और दराज में रहते हुए एक साथ रहते हैं।


मैं एक और समाधान के साथ बाहर आया जो कम परिचालन का वादा नहीं करेगा, न ही कम समय की खपत, लेकिन यह देखने की कोशिश की जानी चाहिए कि क्या यह अच्छी तरह से पर्याप्त हो सकता है कि यह बड़ी मात्रा में सॉक जोड़ी में कम समय की खपत प्रदान करे।

पूर्व शर्त: कोई गारंटी नहीं है कि एक ही मोजे हैं। यदि वे एक ही रंग के हैं तो इसका मतलब यह नहीं है कि उनके पास समान आकार या पैटर्न है। मोजे यादृच्छिक रूप से shuffled हैं। मोजे की विषम संख्या हो सकती है (कुछ गायब हैं, हम नहीं जानते कि कितने हैं)। एक चर "सूचकांक" को याद रखने के लिए तैयार करें और इसे 0 पर सेट करें।

परिणाम में एक या दो ढेर होंगे: 1. "मिलान" और 2. "गायब"

अनुमानी:

  1. सबसे विशिष्ट सॉक पाएं।
  2. अपना मैच ढूंढें
  3. यदि कोई मैच नहीं है, तो इसे "लापता" ढेर पर रखें।
  4. 1 से दोहराएं जब तक कि कोई और अधिक विशिष्ट मोजे न हों।
  5. यदि 6 मोजे कम हैं, तो 11 पर जाएं।
  6. अपने पड़ोसी को अंधेरे से सभी मोजे जोड़े (इसे पैक न करें)
  7. सभी मिलान किए गए जोड़े खोजें, इसे पैक करें और पैक किए गए जोड़े को "मिलान" ढेर में ले जाएं; यदि कोई नया मैच नहीं था - 1 से वृद्धि "सूचकांक"
  8. यदि "इंडेक्स" बड़ा होता है तो 2 (यह सॉक नंबर पर निर्भर मूल्य हो सकता है क्योंकि अधिक संख्या में मोजे उन्हें अंधाधुंध जोड़ने की संभावना कम होती हैं) 11 पर जाएं
  9. बाकी को घुमाओ
  10. 1 पर जाएं
  11. "इंडेक्स" भूल जाओ
  12. एक साक उठाओ
  13. अपनी जोड़ी खोजें
  14. यदि सॉक के लिए कोई जोड़ी नहीं है, तो इसे "लापता" ढेर पर ले जाएं
  15. अगर मैच में जोड़ी मिलती है, तो जोड़ी को पैक करें और इसे "मिलान" ढेर में ले जाएं
  16. यदि अभी भी अधिक हैं तो एक मोजे 12 पर जाते हैं
  17. अगर सिर्फ एक ही बचा है 14 पर जाएं
  18. मुस्कान संतुष्ट :)

इसके अलावा, क्षतिग्रस्त मोजे के लिए भी जांच की जा सकती है, जैसे कि उनको हटाने। इसे 2 और 3 के बीच और 13 से 14 के बीच डाला जा सकता है।

मैं किसी भी अनुभव या सुधार के बारे में सुनना चाहता हूं।


मैंने अभी अपने मोजे को जोड़ना समाप्त कर दिया है, और मैंने पाया कि ऐसा करने का सबसे अच्छा तरीका निम्न है:

  • मोजे में से एक चुनें और इसे दूर रखें (उस जोड़ी के लिए 'बाल्टी' बनाएं)
  • यदि अगला वाला पिछला एक जोड़ी है, तो उसे मौजूदा बाल्टी में डाल दें, अन्यथा नया बनाएं।

सबसे बुरे मामले में इसका मतलब है कि आपके पास एन / 2 अलग-अलग बाल्टी होंगे, और आपके पास एन-2 निर्धारण होंगे कि उस बाल्टी में वर्तमान सॉक की जोड़ी है। जाहिर है, अगर आपके पास कुछ जोड़े हैं तो यह एल्गोरिदम अच्छी तरह से काम करता है; मैंने इसे 12 जोड़े के साथ किया।

यह इतना वैज्ञानिक नहीं है, लेकिन यह अच्छी तरह से काम करता है :)


मोजे, असली या कुछ समान डेटा संरचना, जोड़े में आपूर्ति की जाएगी।

सबसे आसान जवाब जोड़ी को अलग करने की अनुमति देने से पहले है, जोड़ी के लिए एक डेटा संरचना शुरू की जानी चाहिए जिसमें बाएं और दाएं सॉकेट के लिए एक पॉइंटर शामिल था, इस प्रकार मोजे को सीधे या उनकी जोड़ी के माध्यम से संदर्भित किया जा सकता था। अपने साथी को पॉइंटर रखने के लिए एक सॉक भी बढ़ाया जा सकता है।

यह किसी भी कम्प्यूटेशनल जोड़ी समस्या को अमूर्तता की परत से हटाकर हल करता है।

मोजे को जोड़ने की व्यावहारिक समस्या के लिए एक ही विचार को लागू करना, स्पष्ट उत्तर यह है: अपने मोजे को कभी भी असुरक्षित होने की अनुमति न दें। मोजे एक जोड़ी के रूप में प्रदान किए जाते हैं, एक जोड़ी के रूप में पहने हुए एक जोड़ी (शायद उन्हें एक साथ गेंदबाजी करके) के रूप में दराज में डाल दिया जाता है। लेकिन जिस बिंदु पर अप्रत्याशित संभव है वॉशर में है, इसलिए जो कुछ आवश्यक है वह एक भौतिक तंत्र है जो मोजे को एक साथ रहने और कुशलता से धोने की अनुमति देता है।

दो शारीरिक संभावनाएं हैं:

एक 'जोड़ी' ऑब्जेक्ट के लिए जो प्रत्येक सॉक को पॉइंटर रखता है, हमारे पास एक कपड़ा बैग हो सकता है जिसे हम मोजे को एक साथ रखने के लिए उपयोग करते हैं। यह भारी ऊपरी भाग की तरह लगता है।

लेकिन प्रत्येक सॉक के लिए दूसरे के संदर्भ में रहने के लिए, एक साफ समाधान होता है: एक पॉपर (या यदि आप अमेरिकी हैं तो 'स्नैप बटन'), जैसे कि:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

फिर आप जो भी करते हैं, उन्हें अपने मोजे को एक साथ खींचते हैं और उन्हें अपनी धोने की टोकरी में डाल देते हैं, और फिर आपने 'जोड़ी' अवधारणा के भौतिक अमूर्तता के साथ अपने मोजे को जोड़ने की आवश्यकता की समस्या को हटा दिया है।


यदि "चाल" ऑपरेशन काफी महंगा है, और "तुलना" ऑपरेशन सस्ता है, और आपको वैसे भी पूरे सेट को एक बफर में स्थानांतरित करने की आवश्यकता है जहां खोज मूल भंडारण की तुलना में बहुत तेज़ है ... केवल अनिवार्य रूप से सॉर्टिंग को एकीकृत करें चलते हैं।

मैंने सूखने के लिए फांसी में छंटनी की प्रक्रिया को एकीकृत करने में पाया है, यह हवा बनाता है। मुझे वैसे भी प्रत्येक सॉक लेने की जरूरत है, और इसे लटकाएं (आगे बढ़ें) और यह मुझे तारों पर एक विशिष्ट स्थान पर लटका देने के लिए कुछ भी नहीं लेता है। अब सिर्फ पूरे बफर (तार) की खोज को मजबूर नहीं करना है, मैं रंग / छाया द्वारा मोजे लगाने का विकल्प चुनता हूं। डार्कर बाएं, उज्ज्वल दाएं, अधिक रंगीन मोर्चे इत्यादि। अब मैं प्रत्येक सॉक को लटकने से पहले, अगर यह पहले से मौजूद है तो मैं इसके "दाएं आस-पास" में देखता हूं - यह 2-3 अन्य मोजे तक "स्कैन" को सीमित करता है - और यदि यह है , मैं इसके आगे एक और लटका लटका। फिर जब मैं सूख जाता हूं, तारों से हटाते समय मैं उन्हें जोड़ों में डाल देता हूं।

अब यह शीर्ष उत्तरों द्वारा सुझाए गए "रंगों द्वारा ढेर बनाने" से अलग नहीं लगता है, लेकिन पहले, अलग-अलग ढेरों को चुनकर नहीं, लेकिन मुझे "बैंगनी" लाल "या" नीला "ढेर में वर्गीकृत करने में कोई समस्या नहीं है; यह सिर्फ बीच में चला जाता है। और फिर लटकते समय सॉर्टिंग के ओवरहेड को दो ऑपरेशंस (सूखे और सॉर्ट करने के लिए लटका) को एकीकृत करके अलग-अलग सॉर्टिंग के 10% की तरह है।


लागत: मोजे चलाना -> उच्च, खोज / खोज मोजे लाइन में -> छोटा

हम क्या करना चाहते हैं चाल की संख्या को कम करना, और खोजों की संख्या के साथ क्षतिपूर्ति करना। इसके अलावा, हम अवरोही कैश में अधिक चीजें रखने के लिए होमो सेपियंस के बहुसंख्यक वातावरण का उपयोग कर सकते हैं।

एक्स = आपका, वाई = आपके पति / पत्नी

ढेर से सभी मोजे में से एक:

दो मोजे उठाएं, एक्स लाइन में संबंधित एक्स सॉक रखें, और वाई उपलब्ध लाइन पर वाई लाइन में वाई सॉक करें।

जब तक ए खाली नहीं है।

प्रत्येक पंक्ति एक्स और वाई के लिए

  1. लाइन में पहला सॉक चुनें, लाइन के साथ खोज करें जब तक कि यह संबंधित सॉक न पाएं।

  2. मोजे की इसी तरह की लाइन में रखो।

  3. वैकल्पिक जबकि आप लाइन खोज रहे हैं और वर्तमान सॉक जो आप देख रहे हैं वह पिछले जैसा है, इन मोजे के लिए चरण 2 करें।

वैकल्पिक रूप से एक कदम उठाने के लिए, आप दो की बजाय उस रेखा से दो सॉक उठाते हैं, क्योंकि कैशिंग मेमोरी काफी बड़ी है, हम जल्दी से पहचान सकते हैं कि क्या आपके द्वारा देखे जा रहे लाइन पर वर्तमान में सॉक मेल खाता है या नहीं। यदि आप तीन हथियार रखने के लिए भाग्यशाली हैं, तो आप संभवतः एक ही समय में तीन मोजे पार्स कर सकते हैं क्योंकि विषय की स्मृति काफी बड़ी है।

तब तक करें जब तक एक्स और वाई दोनों खाली न हों।

किया हुआ

हालांकि, चूंकि इसमें चयन प्रकार के रूप में सिमिलर जटिलता है, इसलिए I / O (चलती मोजे) की गति और खोज (एक सॉक के लिए रेखा खोजना) की गति के कारण लिया गया समय बहुत कम है।


मोजे के अपने एन जोड़े को सॉर्ट करने की समस्या ओ (एन) है । कपड़े धोने की टोकरी में फेंकने से पहले , आप बायीं तरफ दाहिनी तरफ थ्रेड करते हैं। उन्हें बाहर निकालने पर, आप धागे को काटते हैं और प्रत्येक जोड़ी को अपने दराज में डालते हैं - एन जोड़े पर 2 ऑपरेशन, इसलिए ओ (एन)।

अब अगला सवाल यह है कि आप अपना खुद का कपड़े धोते हैं और आपकी पत्नी उसे करती है। समस्याओं की एक पूरी तरह से अलग डोमेन में यह एक समस्या है । :)


एक हैश तालिका बनाएं जिसका उपयोग हैश के रूप में पैटर्न का उपयोग करके बेजोड़ मोजे के लिए किया जाएगा। मोजे पर एक-एक करके Iterate। यदि सॉक के पास हैश टेबल में एक पैटर्न मैच है, तो टेबल से सॉक लें और एक जोड़ी बनाएं। यदि सॉक के पास कोई मिलान नहीं है, तो उसे टेबल में रखें।


जब भी आप एक साक उठाते हैं, इसे एक ही स्थान पर रखें। फिर अगला सॉक आप उठाते हैं, अगर यह पहले सॉक से मेल नहीं खाता है, तो इसे पहले के बगल में सेट करें। अगर ऐसा होता है, तो एक जोड़ी है। इस तरह यह वास्तव में कोई फर्क नहीं पड़ता कि कितने संयोजन हैं, और आपके द्वारा चुने गए प्रत्येक सॉक के लिए केवल दो संभावनाएं हैं - या तो यह एक मैच है जो पहले से ही आपके मोजे की सरणी में है, या ऐसा नहीं है, जिसका मतलब है कि आप इसे सरणी में किसी स्थान पर जोड़ें।

इसका यह भी अर्थ है कि आप निश्चित रूप से सरणी में अपने सभी मोजे कभी नहीं पाएंगे, क्योंकि मिलान किए जाने पर मोजे हटा दिए जाएंगे।


तुलनात्मक मॉडल में एक ओमेगा (एन लॉग एन) निचला बाध्य है। (एकमात्र वैध ऑपरेशन दो मोजे की तुलना कर रहा है।)

मान लीजिए कि आप जानते हैं कि आपके 2 एन मोजे इस तरह व्यवस्थित हैं:

पी 1 पी 2 पी 3 ... पी एन पी एफ (1) पी एफ (2) ... पी एफ (एन)

जहां एफ सेट {1,2, ..., n} का अज्ञात क्रमपरिवर्तन है। यह जानना समस्या को कठिन नहीं बना सकता है। वहां नहीं! संभावित आउटपुट (पहले और दूसरे छमाही के बीच मिलान), जिसका अर्थ है कि आपको लॉग (एन!) = ओमेगा (एन लॉग एन) तुलना की आवश्यकता है। यह सॉर्टिंग द्वारा उपलब्ध है।

चूंकि आप तत्व विशिष्टता समस्या के संबंध में रूचि रखते हैं: तत्व विशिष्टता के लिए बाध्य ओमेगा (एन लॉग एन) को साबित करना कठिन है, क्योंकि आउटपुट बाइनरी हां / नहीं है। यहां, उत्पादन को एक मिलान होना चाहिए और संभावित आउटपुट की संख्या को सभ्य बाध्य करने के लिए पर्याप्त होना चाहिए। हालांकि, तत्व विशिष्टता से जुड़ा एक संस्करण है। मान लीजिए कि आपको 2 एन मोजे दिए गए हैं और आश्चर्य है कि क्या उन्हें विशिष्ट रूप से जोड़ा जा सकता है। आप ( 1 , एक 2 , ..., एक एन ) (एक 1 , एक 1 , एक 2 , एक 2 , ..., एक एन , एन ) भेजकर ईडी से कमी प्राप्त कर सकते हैं । (मूल रूप से, ईडी की कठोरता का प्रमाण बहुत दिलचस्प है,टोपोलॉजी के माध्यम से ।)

मुझे लगता है कि यदि आप समानता परीक्षणों की अनुमति देते हैं तो मूल समस्या के लिए ओमेगा (एन 2 ) बाध्य होना चाहिए । मेरा अंतर्ज्ञान है: एक ग्राफ पर विचार करें जहां आप परीक्षण के बाद किनारे जोड़ते हैं, और तर्क देते हैं कि यदि ग्राफ घना नहीं है तो आउटपुट विशिष्ट रूप से निर्धारित नहीं होता है।


पहले सॉक उठाओ और इसे एक टेबल पर रखें। अब एक और साक उठाओ; यदि यह पहले उठाए गए मैच से मेल खाता है, तो इसे पहले के शीर्ष पर रखें। यदि नहीं, तो इसे पहले टेबल से छोटी दूरी पर रखें। एक तीसरा साक उठाओ; यदि यह पिछले दो में से किसी एक से मेल खाता है, तो इसे अपने ऊपर रखें या अन्यथा इसे तीसरे स्थान से थोड़ी दूरी पर रखें। जब तक आप सभी मोजे उठा नहीं लेते हैं दोहराएं।


मेरा समाधान आपकी आवश्यकताओं के अनुरूप नहीं है, क्योंकि इसे औपचारिक रूप से O(n)"अतिरिक्त" स्थान की आवश्यकता होती है। हालांकि, मेरी परिस्थितियों पर विचार करना यह मेरे व्यावहारिक अनुप्रयोग में बहुत ही कुशल है। इस प्रकार मुझे लगता है कि यह दिलचस्प होना चाहिए।

अन्य कार्य के साथ मिलें

मेरे मामले में विशेष स्थिति यह है कि मैं सुखाने की मशीन का उपयोग नहीं करता, बस अपने कपड़े को साधारण कपड़े ड्रायर पर लटकता हूं। कपड़े लटकाने के लिए O(n)परिचालन की आवश्यकता होती है (वैसे, मैं हमेशा बिन पैकिंग समस्या पर विचार करता हूं ) और इसकी प्रकृति की समस्या को रैखिक "अतिरिक्त" स्थान की आवश्यकता होती है। जब मैं बाल्टी से एक नया साक लेता हूं तो यह जोड़ी पहले से लटका हुआ है, उसे अपनी जोड़ी के बगल में लटकने की कोशिश करें। यदि यह एक नई जोड़ी से एक साक है तो मैं इसके आगे कुछ जगह छोड़ देता हूं।

ओरेकल मशीन बेहतर है ;-)

यह स्पष्ट रूप से जांच करने के लिए कुछ अतिरिक्त काम की आवश्यकता है कि मिलान करने वाला सॉक पहले से कहीं लटक रहा है या नहीं और यह कंप्यूटर के लिए O(n^2)गुणांक के साथ समाधान प्रदान करेगा 1/2। लेकिन इस मामले में "मानव कारक" वास्तव में एक लाभ है - मैं आम तौर पर बहुत जल्दी (लगभग O(1)) मिलान करने वाले सॉक की पहचान कर सकता हूं अगर यह पहले से ही लटका हुआ था (शायद कुछ अस्थिर इन-मस्तिष्क कैशिंग शामिल है) - इसे एक तरह का मानें ओरेकल मशीन में सीमित " ऑरैकल " ;-) हम, मनुष्यों के पास कुछ मामलों में डिजिटल मशीनों पर इन फायदे हैं ;-)

इसे लगभग O(n)करो!

इस प्रकार लटकते कपड़ों की समस्या के साथ मोजे को जोड़ने की समस्या को जोड़ना मुझे O(n)मुफ्त में "अतिरिक्त जगह" मिलती है , और O(n)समय के बारे में एक समाधान है , सरल लटकते कपड़ों की तुलना में थोड़ा और काम की आवश्यकता होती है और तुरंत पूरी जोड़ी तक पहुंचने की अनुमति देती है सोमवार की सुबह बहुत बुरी तरह मोजे ... ;-)


मोजे के पी जोड़े के लिए मैं वास्तव में ऐसा करता हूं ( एन = 2 पी व्यक्तिगत मोजे):

  • ढेर से यादृच्छिक रूप से एक सॉक पकड़ो।
  • पहले सॉक के लिए, या यदि पहले से चुने गए मोजे जोड़े गए हैं, तो बस अपने सामने अनपेक्षित मोजे के "सरणी" के पहले "स्लॉट" में सॉक रखें।
  • यदि आपके पास एक या अधिक चयनित अनपेक्षित मोजे हैं, तो सरणी में सभी unpaired मोजे के खिलाफ अपने वर्तमान सॉक की जांच करें।
    • अपने सरणी का निर्माण करते समय मोजे को अलग-अलग वर्गों या प्रकारों (सफेद / काला, टखने / चालक दल, एथलेटिक / ड्रेस) में अलग करना संभव है, और "ड्रिल-डाउन" की तरह ही तुलना करें।
    • यदि आपको एक स्वीकार्य मिलान मिलता है, तो दोनों मोजे एक साथ रखें और उन्हें सरणी से हटा दें।
    • यदि आप नहीं करते हैं, तो मौजूदा सॉक को सरणी में पहले खुले स्लॉट में रखें।
  • हर सॉक के साथ दोहराएं।

इस योजना का सबसे खराब मामला यह है कि मोजे की हर जोड़ी काफी अलग है कि इसे ठीक से मिलान किया जाना चाहिए, और आपके द्वारा चुने गए पहले एन / 2 मोजे सभी अलग हैं। यह आपका (एन 2 ) परिदृश्य है, और यह बेहद असंभव है। यदि अद्वितीय प्रकार के सॉक टी की संख्या पी = एन / 2 की संख्या से कम है , और प्रत्येक प्रकार के मोजे पर्याप्त रूप से पर्याप्त होते हैं (आमतौर पर पहनने से संबंधित शब्दों में) कि उस प्रकार के किसी भी प्रकार को किसी के साथ जोड़ा जा सकता है अन्य, तो जैसा कि मैंने ऊपर लगाए गए अनुमान, क्या तुमने कभी की तुलना करना होगा मोज़े की अधिकतम संख्या है टी , जिसके बाद अगले एक आप खींच इच्छाunpaired मोजे में से एक मैच। यह परिदृश्य सबसे खराब मामले की तुलना में औसत सॉक ड्रॉवर में अधिक संभावना है, और (एन * टी) में सबसे बुरी स्थिति जटिलता को कम करता है जहां आमतौर पर << n





matching