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


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

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

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

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

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

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

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

3507
2018-01-19 15:34


मूल


मैं कपड़े धोने के ढेर से बिल्कुल एक जोड़ी करने के लिए कबूतर छेद सिद्धांत का उपयोग करता हूं। मेरे पास मोजे के 3 अलग-अलग रंग हैं (लाल, नीला और हरा) और प्रत्येक रंग के 2 जोड़े। मैं हर बार 4 मोजे उठाता हूं और मैं हमेशा एक जोड़ी बना देता हूं और काम करता हूं। - Srinivas
फिर भी एक और कबूतर छेद सिद्धांत: यदि आप एन / 2 +1 मोजे का सबसेट लेते हैं, तो वहां होना चाहिए इस सबसेट में कम से कम एक जोड़ी। - wildplasser
महान सवाल! आपको संबंधित लेख पर मेरे लेख में रूचि हो सकती है, जो ढेर से दो मिलान किए गए मोजे खींचने की संभावना की चर्चा है: blogs.msdn.com/b/ericlippert/archive/2010/03/22/... - Eric Lippert
एक बच्चे को क्यों न उतारो और waitpid ताकि, माता-पिता के रूप में, आप स्वयं को किसी भी मोजे को सॉर्ट नहीं कर रहे हैं? - Mxyk
मैंने केवल सफेद घुटने-उच्च मोजे के मालिक होने से इस समस्या को हल किया। वे सभी मेल खाते हैं। मैं ढेर से यादृच्छिक रूप से किसी भी दो मोजे पकड़ सकता था और वे मिलेंगे। मैं मोजे को जोड़कर समस्या को और सरल बना देता हूं। मेरे पास एक सॉक ड्रॉवर है कि मैं बस अपने सभी मोजे फेंक दिया, unpaired। मैं हर सुबह दराज से यादृच्छिक रूप से दो पकड़ता हूं। मैंने इसे ओ (0) तक सरल बना दिया है। इससे कहीं आसान नहीं हो सकता है। :) - Lee


जवाब:


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

इसलिए hashing पर्याप्त (और तेज़) होगा।

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

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

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

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

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


अद्यतन करें:

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

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

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

जाहिर है, कोई भी तेज़ नहीं जा सकता है O(N), तो हम पहुंचे हैं इष्टतम निचले बाध्य

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


2180
2017-10-19 20:47



यह वही है जो मैं करता हूं! मैं सॉक के उद्घाटन की शैली पर निर्भर ढेर बनाता हूं (मेरे पास केवल सफेद है), जो मुझे उन सभी में से जल्दी से मिलान करने के लिए पर्याप्त "बाल्टी" देता है। - Scott Chamberlain
मैंने अपने मोजे के साथ यह कोशिश की है (मुझे आसानी से 30+ जोड़े मिल गए हैं) और आदमी यह तेज़ है। मुझे मिली एक समस्या यह है कि जब मेरे पास पर्याप्त पर्याप्त हैश एल्गोरिदम नहीं हो सकता है (मुझे बिना किसी पैटर्न के बहुत सारे सफेद मोजे मिल गए हैं) तो यह मुश्किल हो जाता है। उस स्थिति में, ऐसा करने का सबसे अच्छा तरीका क्या होगा? - NothingsImpossible
@Nothings असंभव है कि कैसे हैश टकराव के हमलों एक खराब वेब सर्वर के लिए लग रहा है! क्या कुछ मोज़े से सफेद मोजे अलग-अलग हैं? ऐसा कुछ होना चाहिए जिसे आप उन्हें वितरित कर सकें। अन्यथा, आप मनमाने ढंग से जोड़ों को बना सकते हैं। - usr
यह एक रेडिक्स सॉर्ट है, जो मैं मानता हूं कि सही जवाब है। @MarkPeters मुझे नहीं लगता कि आपको एक लुकअप टेबल की आवश्यकता है। मोजे पर एक रैखिक पास मोजे को संख्या वैक्टर में परिवर्तित कर सकता है, जिससे "सॉक सेगमेंट" का मानचित्रण बाल्टी को छोटा कर देता है। मोजे स्ट्रिंग के साथ वैक्टर से बंधे जा सकते हैं ताकि आपको अंत में एक और रैखिक पास की आवश्यकता न हो। - Pointy
एक लड़का जो वास्तव में कॉलेज में गया था, वास्तव में पैरीड्स था। यह धागे के साथ मोजे की प्रत्येक जोड़ी पर सिलवाया गया था: 1, 2, 3, 4 ... - Ryan Lundy


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

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

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

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);
}

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


523
2018-05-27 19:13



चूंकि मोजे की संख्या बढ़ जाती है, मानव सिम एक सीपीयू से बेहतर नहीं बनता है। - Lie Ryan
सबसे अच्छा जवाब, आईएमओ। हालांकि यह एक कंप्यूटर एल्गोरिदम में दिन-प्रति-दिन की समस्या को कम करने के लिए मजेदार और चालाक (और एसओ के लिए उपयुक्त है), यह ~ 60 मोजे के रूप में छोटे सेट के लिए मनुष्य की आंख / मस्तिष्क की रिज़ॉल्यूशन शक्ति का उपयोग करने के लिए और अधिक समझ में आता है। - drug_user841417
@LieRyan यदि मोजे समान रूप से वितरित होते हैं, तो आप जन्मदिन के विरोधाभास के कारण मोजे के किसी भी पर्याप्त छोटे सेट में एक जोड़ी को ध्यान में रखेंगे (जब तक कि आप रंगों को मनमाने ढंग से परिशुद्धता में अंतर नहीं कर सकते), तो यहां बाधा नहीं होगी मानव रंग मिलान एल्गोरिदम लेकिन फैलाने वाला कदम। - Thomas
@ dpc.ucore.info नहीं, क्योंकि उनके पास अलग बुने हुए कफ पैटर्न, कफ लंबाई, समग्र लंबाई और काले रंग के रंग होते हैं (मेरी पत्नी शायद मुझे अंतिम रूप से शारीरिक रूप से चोट पहुंचाएगी)। - Christian
आपको बेहतर उम्मीद थी कि आपके पास मोजे की संख्या भी है, अन्यथा आप लंबे समय तक मोजे फोल्ड करने जा रहे हैं ... - Patrick James McDougle


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

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

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

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

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

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

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


231



> अनुक्रमिक खोज से भी अधिक समय लग सकता है, जिसके लिए सिद्धांत में वर्गिक समय की आवश्यकता होती है। हाँ, यही कारण है कि मुझे ऐसा करने से नफरत है, शायद मुझे अपने सभी मोजे फेंकना चाहिए और मामले 1 से शुरू करना चाहिए। - Nils
मुझे सभी समान मोजे भी मिलना आसान लगता है। जब वे बिक्री पर होते हैं और मेरे सभी पुराने मोजे फेंकते हैं तो हर दो साल में मैं मोजे के 6 पैक में से 10 पैक खरीदता हूं। समान मोजे से मेल खाना आसान है और वे पुराने पवित्र मोजे बेहतर दिखते हैं। इसके साथ, ढेर के ऊपर से केवल एक सरल पहले मेरे लिए सबसे तेज़ है। - Michael D. Kirkpatrick
सभी समान मोजे रखने का निचला पक्ष यह है कि वे अलग-अलग दरों पर उम्र देते हैं। तो आप अभी भी उनसे मेल खाने की कोशिश कर रहे हैं कि वे कितने पहने हुए हैं। (जो पैटर्न से मेल खाने से कठिन है) - SDC
समान मोजे के 60 जोड़े होने में समस्या "क्योंकि यह जोड़ों को आसान बनाता है" यह है कि यह लोगों को इंप्रेशन देता है जो आप कंप्यूटर के साथ काम करते हैं। - Steve Ives
मामला एक जब कोई ऑपरेशन शामिल होता है, तो स्थिर समय नहीं होता है, जैसे जोड़ों को एक साथ जोड़ना। इस मामले में, यह सबसे छोटे स्थिर कारक के साथ रैखिक समय है (जिसका सबूत पाठक के लिए एक अभ्यास के रूप में छोड़ दिया जाता है)। एक एक जोड़ी और मोजे से भरा एक बाल्टी तह करने के लिए संभवतः एक ही समय नहीं ले सकता है। हालांकि, यह रैखिक रूप से तराजू। अमाहल के कानून से, इसमें असीमित गति है, ओवरहेड को अनदेखा कर रहा है। गुस्ताफसन के कानून से, आप कई जोड़ों को जोड़ सकते हैं क्योंकि एक जोड़ी को पर्याप्त श्रमिकों (जो राशि पाठक के लिए अभ्यास के रूप में छोड़ दी जाती है) को छोड़कर ओवरहेड को अनदेखा कर दिया जाता है। - acelent


गैर-एल्गोरिदमिक उत्तर, अभी भी "कुशल" जब मैं इसे करता हूं:

  • चरण 1) अपने सभी मौजूदा मोजे को त्यागें

  • चरण 2) पर जाएं वॉल-मार्ट और उन्हें 10-एन पैकेट के पैकेट द्वारा खरीदते हैं काले और सफेद के एम पैकेट। रोज़मर्रा के अन्य रंगों की आवश्यकता नहीं है जिंदगी।

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

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

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

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

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

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

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

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

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

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

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


144



'गैर-एल्गोरिदमिक' उत्तर के लिए उपरोक्त। यह वही है जो मैं करता हूं और यह अद्भुत काम करता है। प्रतिस्थापन समस्या कोई समस्या नहीं है यदि आप अपने सॉक स्टॉक को पीछे में धोए हुए मोजे रखकर सुबह में दराज के सामने से खींचकर 'घुमाएं'। सभी मोजे समान रूप से पहनते हैं। जब मैं एक पहनने पर कुछ पहनना शुरू करता हूं, तो मैंने मोज़े की पूरी कक्षा को पूरी तरह से बदलने के लिए खरीदारी सूची डाल दी। पुराने मोजे के लिए, मैं गुडविल को सर्वश्रेष्ठ 20% देता हूं (एक किराने की थैली में बंधे ताकि वे मिश्रित न हों) और बाकी को पिच करें। आप मोजे बर्बाद नहीं कर रहे हैं, इस बिंदु पर, 80% के पास केवल 6 महीने शेष हैं। - FastAl
बीटीडब्लू (1) अपने मोजे को बाध्य करने के परिणामस्वरूप लोचदार एक को संग्रहित किया जा रहा है और यह असफल हो जाएगा। आपके द्वारा चुने गए अद्वितीय मोजे के प्रकारों को सीमित करने से बाध्यकारी बना दिया जाता है। (2) अद्वितीय मोजे को सीमित करने का एक नुकसान यह है कि कुछ फैशन चिंताओं वाले लोगों के लिए, विधि अनुपयुक्त हो सकती है। - FastAl
मैं यहां विशेष रूप से आपके "गैर-एल्गोरिदमिक" उत्तर पोस्ट करने आया था। वास्तविक कंप्यूटर विज्ञान के रूप में, अधिकांश लोग डेटा और इसकी संरचना पर पर्याप्त ध्यान नहीं देते हैं। - bkconrad
मैं हर सुबह इस एल्गोरिदमिक दृष्टिकोण का उपयोग करता हूं और यह एक आकर्षण की तरह काम करता है! इसके अतिरिक्त, मैंने बाद में फेंकने के लिए मोजे को एक अलग ढेर में पहना था (दुर्भाग्य से वे इसे कचरा करने के लिए समय खोजने से पहले मूल ढेर में फिर से पहुंचने में कामयाब रहे)। - Donatas Olsevičius
«काले रंग के सफेद और एम पैकेट के एन पैकेट। रोजमर्रा की जिंदगी में अन्य रंगों की कोई ज़रूरत नहीं »आसान सॉक चयन के लिए एक अच्छा मानक नियम वास्तव में है कि उन्हें आपके पतलून के रंग या अपने बेल्ट के रंग से मेल खाना चाहिए। इस कारण से, सबसे अधिक इस्तेमाल किए जाने वाले रंग काले, नीले, भूरे और कुछ भूरे रंग की संभावना होगी। यह विश्वास करना मुश्किल है कि किसी को कई सफेद मोजे की जरूरत है। - Andrea Lazzarotto


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

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

यह मानते हुए कि मोजे के लिए एकमात्र ऑपरेशन समानता के लिए तुलना करना है, यह एल्गोरिदम मूल रूप से अभी भी एक एन है2 एल्गोरिदम, हालांकि मुझे औसत मामले के बारे में पता नहीं है (इसकी गणना करने के लिए कभी नहीं सीखा)।

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

इसके अलावा, मैं कुछ भी नहीं सोच सकता, लेकिन यह विधि वास्तविक जीवन में बहुत ही कुशल प्रतीत होती है। :)


92



यह भी मैं करता हूं, (ध्यान दें कि यदि आप केवल रिक्त स्थान छोड़ते हैं तो आवेषण भी ओ (1) हैं, लेकिन यह सैद्धांतिक रूप से बड़ी संख्या में मोजे के साथ खराब पैमाने पर स्केल करता है। - Mooing Duck
सैद्धांतिक रूप से बड़ी संख्या के साथ खराब पैमाने पर के प्रकार मोज़े - Steven Lu
@StevenLu - जैसा कि मैंने कहा - यह n * n या nLogn है, इस पर निर्भर करता है कि आप इसे सॉर्ट करते हैं या नहीं। तो यह किसी भी सॉर्टिंग एल्गोरिदम के रूप में खराब के रूप में scales। यदि आप तेज़ी से चाहते हैं, तो उन्हें नंबर दें और रेडिक्स सॉर्ट का उपयोग करें। - Vilx-
यह अनिवार्य रूप से हैश-आधारित लुकअप में पाया गया-मिलान-मिलान मोजे संग्रहीत नहीं कर रहा है। एक आदर्श हैश के साथ यह ओ (एन) है, लेकिन यदि आपके पास पर्याप्त मोजे संग्रहीत हैं कि हैश खराब हो जाना शुरू हो जाता है, तो यह तदनुसार अधिक जटिल हो जाता है। - Jon Hanna
मोजे जोड़ने के लक्ष्य को 2 अन्य मोजे के बीच एक साक डालने में क्या मूल्य है? मोजे की कोई कार्डिनिटी नहीं है। :-एक्स - JoeBrockhaus


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

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

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

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

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

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

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

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

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

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

  3. मोजे आदेश!

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

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

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


50



एक जीवनकाल (75 वर्ष मानते हुए) मोजे की आपूर्ति (मानते हुए कि आप 4 जोड़े / महीने निकालें, जो 3600 जोड़े बनाता है) उठाएगा (लगता है कि मोजे की एक नई जोड़ी 20 घन इंच लेती है) कुल 1 1/2 क्यूबिक गज। यह अंतरिक्ष की एक बड़ी मात्रा है। मान लीजिए कि वे आपको उस बॉक्स में पहुंचाते हैं जो मोटे तौर पर एक घन है, वह टुकड़ा एक तरफ लगभग 3 फीट 4 इंच होगा। - AJMansfield
@AJMansfield वैध चिंता। हालांकि, मैं आपकी कुछ संख्याओं से असहमत हूं। मैं सिर्फ 40 वर्षों का समय लेता हूं (25 ... 65) (माता-पिता / छात्रावास / आदि में रहने के बीच का समय और सेवानिवृत्त, ऊपर देखें)। साथ ही, मुझे लगता है कि एक जोड़ी मूल पैकेजिंग में 0,5x4x6 इंच की तरह लेती है। ये संख्याएं आपके अंतरिक्ष अनुमान को काफी नीचे लाती हैं! - hyde
चरण 4 अनावश्यक रूप से अपर्याप्त है, -1। - Dan Bechard
AJMansfield के मापों से भ्रमित हो सकते हैं, जो मेट्रिक में अनुवाद हो सकता है: »ले जाएगा (मोजे की एक नई जोड़ी 327 सेमी³ लेती है) कुल 1.14 एम³। यह अंतरिक्ष की एक बड़ी मात्रा है। मान लीजिए कि वे आपको उस बॉक्स में पहुंचाते हैं जो मोटे तौर पर एक घन है, वह टुकड़ा एक तरफ 1.04 मीटर होगा। « - Joey


सैद्धांतिक सीमा ओ (एन) है क्योंकि आपको प्रत्येक सॉक को छूने की आवश्यकता है (जब तक कि कुछ पहले से ही किसी भी तरह से जोड़ा नहीं जाता है)।

आप ओ (एन) के साथ प्राप्त कर सकते हैं रेडिक्स सॉर्ट करें। आपको बाल्टी के लिए कुछ विशेषताओं को चुनने की जरूरत है।

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

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


47



मोजे अक्सर 4-पैक और बड़े होते हैं, क्योंकि यह सस्ता है, लेकिन यह उन्हें अलग-अलग बनाता है। इसका मुकाबला करने के लिए, मेरी पत्नी मोजे की प्रत्येक नई जोड़ी पर एक छोटा निशान लगाती है। यदि वह रंगों से बाहर हो जाती है तो प्रत्येक जोड़ी, या एक अलग आकार के लिए चिह्न एक अलग रंग का होता है। इस दृष्टिकोण के साथ आपको विशेषताओं के सीमित सेट की भी आवश्यकता नहीं है। बस प्रत्येक जोड़ी पर एक अद्वितीय संख्या सीना। :) अतिरिक्त अंक के लिए, बाइनरी का उपयोग करें। - Vilx-
@ विल्क्स- क्यों?! क्या यह पूरा मुद्दा नहीं है कि वे अलग-अलग हैं? - flup
@flup - मुझे लगता है कि पूरा बिंदु बड़े बंडलों में बेचना है। :) मेरे लिए, यह उन्हें जोड़े में पहनने में मदद करता है। अन्यथा मैं तीन बहुत पहने हुए मोजे और एक ब्रांड के साथ समाप्त कर सकता हूं। किंडा मूर्खतापूर्ण - Vilx-
मैं ओ (एन) की गणना से असहमत हूं। $ K $ क्या है? $ k $ गुणों की संख्या है। मैं तर्क दूंगा कि $ k $ $ O (लॉग n) $ है क्योंकि यह प्रत्येक जोड़ी को विशिष्ट रूप से पहचानने के लिए पर्याप्त होना चाहिए। यदि आपके पास 2 जोड़े (काला और सफेद) हैं, तो रंग ($ k = 1, n = 2 $) पर्याप्त है। यदि आपके पास एक जोड़ी काला, छोटी है; काला, लंबी की एक जोड़ी; सफेद की एक जोड़ी, छोटी; और सफेद की एक जोड़ी, लंबी - फिर $ के = 2, एन = 4 $। फिर यदि हम $ k $ को सीमित करते हैं, तो हम एक ही समय में $ n $ को सीमित करते हैं। अगर हम $ n $ को सीमित करने जा रहे हैं तो ऑर्डर गणना अब और समझ में नहीं आती है। - emory
@emory, मुझे लगता है कि आप बैकटिक की तलाश में हैं, नहीं $ चरित्र, अपनी सामग्री को कोड-वाई बनाने के लिए। - Xymostech


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

  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) लगभग लंबे समय तक विधि log(k) < x - 1


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

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


31



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