लक्ष्यएक सॉर्टऑर्डर को दूसरे में परिवर्तित करने के लिए पूर्ण न्यूनतम परिवर्तनों की गणना कैसे करें?
कैसे डेटा है कि एक एक आदेश से संभव बाइट की न्यूनतम राशि का उपयोग कर अन्य आदेश पर बताता है कि कैसे करने के लिए फिर से आदेश में एक स्थिर सूची एन्कोड करने के लिए?
मूल प्रेरणा
मूल रूप से इस समस्या पैदा हुई है, जबकि महंगा उपग्रह संचार का उपयोग कर संवेदक डेटा रिले करना एक समस्या पर काम कर रहा। एक डिवाइस में लगभग 1,000 सेंसर की एक सूची थी जो वे निगरानी कर रहे थे। सेंसर सूची बदल नहीं सका। प्रत्येक सेंसर में एक अद्वितीय आईडी थी। अंतिम विश्लेषण के लिए सभी डेटा आंतरिक रूप से लॉग इन किए जा रहे थे, केवल एक चीज जो उपयोगकर्ताओं को रोज़ाना जरूरी थी, उस क्रम में कौन सा सेंसर निकाल दिया गया था।
पूरी परियोजना को तोड़ दिया गया था, लेकिन यह समस्या अनदेखा करने के लिए बहुत दिलचस्प लगती है। इसके अलावा मैंने पहले "स्वैप" के बारे में बात की थी क्योंकि मैं सॉर्टिंग एल्गोरिदम के बारे में सोच रहा था, लेकिन वास्तव में यह एकमात्र आदेश है जो महत्वपूर्ण है, उस क्रम में आने के लिए आवश्यक कदम शायद इससे कोई फर्क नहीं पड़ता।
कैसे डेटा
आदेश दिया गया था एसक्यूएल संदर्भ में तो आप इसे इस के बारे में सोच सकता है।
**Initial Load**
create table sensor (id int, last_detected datetime, other stuff)
-- fill table with ids of all sensors for this location
Day 0: Select ID from Sensor order by id
(initially data is sorted by the sensor.id because its a known value)
Day 1: Select ID from Sensor order by last_detected
Day 2: Select ID from Sensor order by last_detected
Day 3: Select ID from Sensor order by last_detected
अनुमान
- शुरू कर सूची और न खत्म होने वाली सूची आइटम की सटीक एक ही सेट से बना है
- प्रत्येक सेंसर में एक विशिष्ट आईडी (32 बिट पूर्णांक) है
- आकार सूची में लगभग 1,000 आइटम
- प्रत्येक सेंसर कई बार प्रति मिनट कई बार आग लग सकता है या नहीं
- केवल आईडी सॉर्ट ऑर्डर में परिवर्तन को रिले किया जाना चाहिए।
- इष्टतम समाधान लगाने के लिए गणना संसाधन सस्ते/असीमित
- डेटा लागत महंगा है, लगभग प्रति किलो प्रति किलो।
- डेटा केवल पूरे बाइट (ओकटेट) के रूप में भेजा जा सकता है
- दिवस 0 आदेश प्रेषक और प्राप्तकर्ता से जाना जाता है
- साथ शुरू करने के लिए अभी के लिए पूरी तरह से प्रणाली कार्यों मान वृद्धि कर देता है और कोई त्रुटि जाँच की आवश्यकता है
जैसा कि मैंने कहा था कि परियोजना/हार्डवेयर अब और नहीं है, इसलिए यह अब सिर्फ एक अकादमिक समस्या है।
चुनौती!
एक एनकोडर
- को देखते हुए ए डे एन सॉर्ट क्रम
- को देखते हुए बी दिवस एन 1 सॉर्ट क्रम
- वापसी सी परिभाषित करेंकि कैसे संभव बाइट्स की कम से कम संख्या का उपयोग कर बी करने के लिए एक कन्वर्ट करने के लिए का वर्णन बाइट्स का एक संग्रह
एक डिकोडर
परिभाषित- को देखते हुए ए डे एन सॉर्ट क्रम
- बी का एक संग्रह को देखते हुए बाइट्स
- वापसी सी डे एन 1 सॉर्ट क्रम
मज़ा हर किसी को है।
क्या आप वाकई एक सॉर्टिंग समस्या है? यदि मैं सही ढंग से पढ़ता हूं, तो यह एक संपीड़न समस्या की तरह लगता है - आप जानना चाहते हैं कि न्यूनतम संग्रहण का उपयोग करते समय, किस डिवाइस को निकाल दिया गया था। साथ ही, अगर मैं सचमुच पढ़ता हूं, तो मैं स्पष्ट हूं कि आप "सॉर्ट ऑर्डर" के रूप में संदर्भित कर रहे हैं। ऐसा लगता है कि आप पूछ रहे हैं कि डेटा को कैसे सॉर्ट किया जाना चाहिए, लेकिन मुझे सॉर्टिंग मामलों के बारे में कोई निर्देश नहीं दिख रहा है - जब कुछ निकाल दिया जाता है, कितनी बार इसे निकाल दिया जाता है, आदि यह जानने के बिना कि हम किस प्रकार का आउटपुट देख रहे हैं के लिए, आपको यह बताने में बहुत मुश्किल है कि हम इसे कैसे क्रमबद्ध करेंगे। – atk
यह diffing की तरह बहुत लगता है। जिसे आप "सॉर्ट ऑर्डर" कहते हैं, वास्तव में सेंसर-आईडी की मनमानी सूची है। –
दूसरे शब्दों में, सूची को एक टेक्स्ट फ़ाइल में रखें; आपका एन्कोडर 'diff' है और आपका डिकोडर' पैच' है। हालांकि आपको पसंद है पैच को संपीड़ित करें। एसओ पर अलग-अलग एल्गोरिदम के बारे में सैकड़ों प्रश्न हैं, लेकिन विकिपीडिया बेहतर पढ़ सकता है। http://en.wikipedia.org/wiki/Diff#Algorithm –