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




sorting language-agnostic matching (25)

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

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

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

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

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

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

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

Answers

मैंने ओ (1) समय लेने की प्रक्रिया में अपने प्रयास को कम करने के लिए सरल कदम उठाए हैं।

मेरे इनपुट को दो प्रकार के मोजे (मनोरंजन के लिए सफेद मोजे, काम के लिए काले मोजे) में से एक को कम करके, मुझे केवल यह निर्धारित करने की आवश्यकता है कि मेरे पास कौन से दो मोजे हैं। (तकनीकी रूप से, चूंकि वे कभी भी धोए नहीं जाते हैं, इसलिए मैंने प्रक्रिया को ओ (0) समय में घटा दिया है)

वांछनीय मोजे खोजने के लिए कुछ और प्रयासों की आवश्यकता है, और अपने मौजूदा मोजे की आवश्यकता को खत्म करने के लिए पर्याप्त मात्रा में खरीदना आवश्यक है। जैसा कि मैंने काले मोजे की मेरी आवश्यकता से पहले यह किया था, मेरा प्रयास न्यूनतम था, लेकिन माइलेज भिन्न हो सकता है।

इस तरह के एक पूर्व प्रयास बहुत लोकप्रिय और प्रभावी कोड में कई बार देखा गया है। उदाहरणों में कई दशमलव तक # परिभाषित पीआई शामिल हैं (अन्य उदाहरण मौजूद हैं, लेकिन यह वही है जो अभी दिमाग में आता है)।


List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}

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

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

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


मुझे आशा है कि मैं इस समस्या के लिए कुछ नया योगदान दे सकता हूं। मैंने देखा कि सभी उत्तरों इस तथ्य को उपेक्षा करते हैं कि आपके कुल कपड़े धोने के प्रदर्शन को धीमा किए बिना, दो बिंदुएं हैं जहां आप प्रीप्रोकैसिंग कर सकते हैं ।

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

  1. लोग बिन के उसी क्षेत्र में मोटे तौर पर अपने दोनों मोजे टॉस करते हैं,
  2. बिन किसी भी बिंदु पर यादृच्छिक नहीं है, और इसलिए
  3. इस बिन के शीर्ष से लिया गया कोई भी सबसेट आमतौर पर एक जोड़ी के दोनों मोजे होते हैं।

चूंकि मुझे पता है कि सभी वाशिंग मशीनों को आकार में सीमित किया गया है (भले ही आपको कितने मोजे धोना है), और वास्तविक यादृच्छिकता वाशिंग मशीन में होती है, इससे कोई फर्क नहीं पड़ता कि हमारे पास कितने मोजे हैं, हमारे पास हमेशा छोटे सबसेट होते हैं जिनमें लगभग कोई नहीं होता है एकमात्र।

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

Put_socks_on_line () के लिए एल्गोरिदम यहां दिया गया है:

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

अपने समय को मोजे के चारों ओर घूमने या सबसे अच्छे मैच की तलाश में बर्बाद न करें, यह सब ओ (एन) में किया जाना चाहिए, जिसे हमें उन्हें बिना किसी लाइन पर डालने की आवश्यकता होगी। मोजे अभी तक जोड़े नहीं गए हैं, हमारे पास लाइन पर कई समानता क्लस्टर हैं। यह सहायक है कि हमारे यहां मोजे का एक सीमित सेट है, क्योंकि इससे हमें "अच्छे" क्लस्टर बनाने में मदद मिलती है (उदाहरण के लिए, यदि मोजे के सेट में केवल काले मोजे हैं, तो रंगों से क्लस्टरिंग जाने का रास्ता नहीं होगा)

Take_socks_from_line () के लिए एल्गोरिदम यहां दिया गया है:

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

मुझे यह इंगित करना चाहिए कि शेष चरणों की गति में सुधार करने के लिए, बुद्धिमानी से अगले सॉक को चुनना बुद्धिमानी नहीं है, लेकिन क्रमशः प्रत्येक क्लस्टर से सॉक के बाद सॉक लेना बुद्धिमानी है। प्रीप्रोकैसिंग चरणों में दोनों मोजे को लाइन या टोकरी में डालने से ज्यादा समय नहीं लगता है, जिसे हमें कोई फर्क नहीं पड़ता है, इसलिए इसे कपड़े धोने के प्रदर्शन में काफी वृद्धि करना चाहिए।

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

Sort_remaining_clusters () के लिए एल्गोरिदम यहां दिया गया है:

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

उसके बाद, केवल कुछ मोजे बाकी हैं। यह वह जगह है जहां मैं सिस्टम में पहले unpaired मोजे पेश करता हूं और बिना किसी विशेष एल्गोरिदम के शेष शेष मोजे को संसाधित करता हूं - शेष मोजे बहुत कम होते हैं और उन्हें बहुत तेजी से संसाधित किया जा सकता है।

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

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

समांतरता के बारे में: जब तक आप एक ही बिन में दोनों मोजे टॉस करते हैं, तो आप उन सभी चरणों को आसानी से समानांतर कर सकते हैं।


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

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

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

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

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

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


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

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

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

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

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

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

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


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

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

  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 ढेर में विभाजित करें,
  2. फिर रंगों का उपयोग करें (रंगों के लिए कोई ऑर्डर हो सकता है, उदाहरण के लिए रंगीन नाम से वर्णानुक्रम) - उन्हें रंग से ढेर में विभाजित करें (उसी ढेर में सभी मोजे के लिए चरण 1 से प्रारंभिक क्रम रखना याद रखें)
  3. तो साक की लंबाई,
  4. फिर बनावट, ....

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


जब मैं मोजे को सॉर्ट करता हूं, तो मैं एक अनुमानित रेडिक्स सॉर्ट करता हूं , उसी रंग / पैटर्न प्रकार के अन्य मोजे के पास मोजे छोड़ देता हूं । इस मामले को छोड़कर जब मैं स्थान पर / उसके आस-पास एक सटीक मिलान देख सकता हूं, तो मैं उस बिंदु पर जोड़ी निकालने के लिए सोक छोड़ने जा रहा हूं।

लगभग सभी अन्य एल्गोरिदम ( usr द्वारा शीर्ष स्कोरिंग उत्तर सहित ) सॉर्ट करें, फिर जोड़े हटा दें। मुझे लगता है कि, एक इंसान के रूप में, एक समय में मोजे की संख्या को कम करने के लिए बेहतर है।

मैं यह करता हूं:

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

यह ओ (1) समय में अस्पष्ट-मिलान की मानव क्षमता का लाभ उठाता है, जो कुछ कंप्यूटिंग डिवाइस पर हैश-मैप की स्थापना के बराबर है।

पहले विशिष्ट मोजे खींचकर, आप उन सुविधाओं पर "ज़ूम" करने के लिए स्थान छोड़ देते हैं, जिनके साथ शुरू करने के लिए कम विशिष्ट हैं।

फ्लूरो रंग को खत्म करने के बाद, पट्टियों के साथ मोजे, और लंबे मोजे के तीन जोड़े, आप ज्यादातर सफेद मोजे के साथ समाप्त हो सकते हैं, वे कितने पहने हुए हैं।

कुछ बिंदु पर, मोजे के बीच अंतर इतना छोटा होता है कि अन्य लोगों को अंतर दिखाई नहीं देगा, और किसी और मिलान प्रयास की आवश्यकता नहीं है।


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

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


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

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

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 एसोसिएटिव मेमोरी में निरंतर समय लुकअप, डालने, और हटाएं। इस तरह के दोनों लोगों और मशीनों की खरीद की जा सकती है। यदि आपके पास कोई है, तो आप एन जोड़े के लिए ओ (एन) समय में सभी मोजे जोड़ सकते हैं, जो इष्टतम है। कुल ऑर्डर टैग आपको मानव या हार्डवेयर कंप्यूटर के साथ एक ही परिणाम प्राप्त करने के लिए मानक हैशिंग का उपयोग करने की अनुमति देता है।


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

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


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

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

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

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

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

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

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


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


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

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


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

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

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

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

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

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

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

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

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

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

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

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

किया हुआ

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


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

पूर्व शर्त: कोई गारंटी नहीं है कि एक ही मोजे हैं। यदि वे एक ही रंग के हैं तो इसका मतलब यह नहीं है कि उनके पास समान आकार या पैटर्न है। मोजे यादृच्छिक रूप से 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 के बीच डाला जा सकता है।

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


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

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

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

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) Walmart और उन्हें सफेद के 10-एन पैकेट और काले रंग के पैकेट के पैकेट द्वारा खरीदें। रोजमर्रा की जिंदगी में अन्य रंगों की कोई ज़रूरत नहीं है।

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

एल्गोरिदमिक उत्तर:

इस बात पर विचार करें कि क्या आप मोजे के दूसरे ढेर के लिए केवल एक झटका खींचते हैं, जैसा कि आप कर रहे हैं, एक बेवकूफ खोज में मिलान करने वाले सॉक को ढूंढने की आपकी संभावनाएं काफी कम हैं।

  • तो उनमें से पांच यादृच्छिक रूप से उठाओ, और उनके आकार या उनकी लंबाई याद रखें।

पांच क्यों? आम तौर पर मनुष्य अच्छे काम कर रहे स्मृति में पांच से सात विभिन्न तत्वों के बीच याद कर रहे हैं - एक RPN स्टैक के मानव समकक्ष की तरह थोड़ा - पांच एक सुरक्षित डिफ़ॉल्ट है।

  • 2 एन -5 के ढेर से एक उठाओ।

  • अब जब आप एक नहीं पाते हैं, तो एक मैच (विज़ुअल पैटर्न मिलान - इंसान एक छोटे से ढेर के साथ अच्छे होते हैं), यदि आपको कोई नहीं मिलता है, तो उसे अपने पांच में जोड़ें।

  • स्टैक से बेतरतीब ढंग से मोजे उठाएं और एक मैच के लिए अपने 5 + 1 मोजे की तुलना करें। जैसे ही आपका ढेर बढ़ता है, यह आपके प्रदर्शन को कम करेगा लेकिन आपकी बाधाओं को बढ़ाएगा। काफी तेज।

एक मैच के 50% बाधाओं के लिए आपको कितने नमूने आकर्षित करना है, इसकी गणना करने के लिए सूत्र को लिखने के लिए स्वतंत्र महसूस करें। आईआईआरसी यह एक हाइपरजैमेट्रिक कानून है।

मैं हर सुबह ऐसा करता हूं और शायद ही कभी तीन से अधिक ड्रॉ की आवश्यकता होती है - लेकिन मेरे पास m आकार के सफेद मोजे के समान जोड़े (लगभग 10, हार गए या लेते हैं) हैं। अब आप स्टॉक के अपने ढेर के आकार का अनुमान लगा सकते हैं :-)

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


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

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

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

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

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


आकार 'एन' की हैश-टेबल पर विचार करें।

यदि हम सामान्य वितरण मानते हैं, तो अनुमान लगाया गया है कि 'बाधाओं' की अनुमानित संख्या कम से कम एक सॉकेट को एक बाल्टी में मैप किया गया है, नलॉगन (यानी, सभी बाल्टी भर चुकी हैं)

मैंने इसे एक और पहेली के हिस्से के रूप में लिया था, लेकिन मुझे गलत साबित होने में खुशी होगी। यहां मेरा ब्लॉग आलेख है

चलो 'एन' आपके पास मौजूद मोजे के अद्वितीय रंग / पैटर्न की संख्या की संख्या के अनुमानित ऊपरी-बाध्य से मेल खाते हैं।

एक बार टक्कर हो जाने के बाद (उर्फ: एक मैच) बस मोजे की उस जोड़ी को हटा दें। NlogN मोजे के अगले बैच के साथ एक ही प्रयोग दोहराएं। इसकी सुंदरता यह है कि मानव मन के तरीके के कारण आप नोलॉग समानांतर तुलना (टकराव-संकल्प) बना सकते हैं। :-)


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

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


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

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

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

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

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

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

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

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

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

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

  3. मोजे आदेश!

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

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

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


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

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


आप डॉ। द्वारा बड़े पैमाने पर जेनोम अनुक्रम प्रोसेसिंग पर एक नज़र डालना चाहते हैं। Kasahara और Morishita।

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





algorithm sorting language-agnostic matching