संतुलित वितरण एल्गोरिदम

Question

मैं कुछ ढीले युग्मित क्लस्टर के लिए कुछ कोड पर काम कर रहा हूं। नौकरियों के दौरान इष्टतम प्रदर्शन प्राप्त करने के लिए, जब भी कोई बच्चा प्रवेश करता है या बाहर निकलता है, तो क्लस्टर अपने डेटा को रीमेप करता है। यह अंततः वैकल्पिक बना दिया जाएगा, लेकिन अभी के लिए यह डिफ़ॉल्ट रूप से अपने डेटा संतुलन प्रदर्शन करता है। मेरा संतुलन मूल रूप से यह सुनिश्चित कर रहा है कि प्रत्येक बच्चे के पास प्रति मशीन फ़ाइलों की औसत संख्या से अधिक नहीं है, साथ ही एक। यदि विभाजन साफ़ नहीं है तो प्लस वन शेष के लिए है। और शेष के बाद से हमेशा बच्चों की संख्या की तुलना में कम हो जाएगा [0 मामले को छोड़कर, लेकिन हम उस बाहर कर सकते हैं], एक संतुलन के बाद बच्चों सबसे औसत पर होगा + 1.

सब कुछ ठीक लग रहा है जब तक मुझे एहसास हुआ मेरा एल्गोरिदम ओ (एन!) है। बच्चों की सूची नीचे जाएं, औसत, शेष खोजें, जिनके पास बहुत अधिक है और जिनके पास बहुत कम है। बहुत से सूची में प्रत्येक बच्चे के लिए, सूची के माध्यम से जाएं, प्रत्येक बच्चे को भेजें जो बहुत कम है।

क्या इसका कोई बेहतर समाधान है? मुझे लगता है कि वहां होना चाहिए।

संपादित करें: यहाँ दिखाने के लिए मैं कैसे हे प्राप्त कुछ psuedocode है (एन):

foreach (child in children) { 
    if (child.dataLoad > avg + 1) { 
     foreach (child2 in children) { 
      if (child != child2 && child2.dataLoad < avg) { 
       sendLoad(child, child2) 
      } 
     } 
    } 
} 

संपादित करें: O (n^2)। Foreach n, n => n * n => n^2। मुझे लगता है कि आज सुबह मेरे पास पर्याप्त कॉफी नहीं थी! ;)

भविष्य में मैं एक अधिक लचीला और लचीला वितरण विधि [वजन और ह्यूरिस्टिक] में जाना चाहता हूं, लेकिन अभी के लिए, डेटा कार्यों का एक समान वितरण।

Answer 1

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

See previous answer

अंतिम चरण कुछ ऐसा दिखाई देगा:

दूसरे चरण में child2 में औसत काम का बोझ कम से कम के साथ पहला आइटम के लिए सूचक रखने (आवश्यकता को रोकने के लिए एक डबल लिंक सूची के लिए)।

for each child in list { 
    if child2 == nil then assert("Error in logic"); 
    while child.workload > avg + 1 { 
    sendwork(child, child2, min(avg + 1 - child2.workload, child.workload - (avg + 1))) 
    if child2.workload == avg + 1 then child2 = child2.next; 
    } 
} 

Answer 2

मुझे लगता है कि अपने विश्लेषण गलत है:

• पता लगाने के लिए औसत हे है (एन)
• बहुत अधिक या बहुत कम डेटा मात्रा के साथ बच्चों की सूचियां बनाने के भी है सूची के माध्यम से चल रहा हे (एन)
• डेटा ले जाने कैसे आप हे करने के लिए आए डेटा

की राशि के लिए आनुपातिक है (एन!)?

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

Answer 3

आपके द्वारा पोस्ट किया गया कोड जटिलता ओ (एन^2) है। फिर भी, इसे रैखिक समय में करना संभव है क्योंकि मैलाच ने देखा है, जहां एन बच्चों की सूची में वस्तुओं की संख्या है।

विचार करें: आंतरिक पाश में एन पुनरावृत्तियों हैं, और इसे पर एन बार निष्पादित किया गया है। एन * एन = एन^2।

Answer 4

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

विषय के लिए एक अपेक्षाकृत आसान परिचय के लिए यहाँ देखें: http://www8.org/w8-papers/2a-webserver/caching/paper2.html

(वहाँ गहरा कागजात उपलब्ध रूप में अच्छी तरह कर रहे हैं, Karger एट अल के साथ शुरू)

मैं लगातार हैशिंग की एक काम कार्यान्वयन बनाया है Erlang आप यदि आप चाहें तो जांच कर सकते हैं कि:

http://distributerl.googlecode.com/svn/trunk/chash.erl