कन्ववे के 'गेम ऑफ लाइफ' को अनुकूलित करना

Question

प्रयोग करने के लिए, मैंने (बहुत पहले) Conway के Game of Life को लागू किया है (और मुझे this संबंधित प्रश्न से अवगत है!)।

मेरा कार्यान्वयन बूलियन के 2 सरणी को रखकर, 'अंतिम राज्य' का प्रतिनिधित्व करते हुए और 'राज्य को अद्यतन किया जा रहा है' (प्रत्येक पुनरावृत्ति पर 2 एरे बदल दिए गए) का पालन करके काम किया। हालांकि यह काफी तेज़ है, मैंने अक्सर यह सोचने के बारे में सोचा है कि इसे कैसे अनुकूलित किया जाए।

एक विचार है, उदाहरण के लिए, यात्रा पर precompute होगा एन क्षेत्रों है कि यात्रा पर संशोधित किया जा सकता है (N + 1) (ताकि अगर एक सेल इस तरह के एक क्षेत्र से संबंधित नहीं है, ऐसा नहीं होगा पुनरावृत्ति में संशोधन के लिए भी विचार किया जाना चाहिए (एन + 1))। मुझे पता है कि यह बहुत अस्पष्ट है, और मैंने विवरण में जाने के लिए समय नहीं लिया ...

क्या आपके पास अनुकूलन (गति के लिए) जीवन के खेल के बारे में कोई विचार (या अनुभव!) है पुनरावृत्तियों?

Answer 1

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

Answer 2

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

यदि आपका क्षेत्र प्रारंभ में खाली है, तो यह बहुत तेज़ होगा। आप शायद कुछ संतुलन बिंदु पा सकते हैं जिस पर बफर को बनाए रखना सभी कोशिकाओं को संसाधित करने से अधिक महंगा है।

Answer 3

इसके लिए टेबल-संचालित समाधान हैं जो प्रत्येक तालिका लुकअप में एकाधिक सेल्स को हल करते हैं। एक Google क्वेरी आपको कुछ उदाहरण देनी चाहिए।

Answer 4

कुछ सुपर-फास्ट कार्यान्वयन हैं जो (स्मृति से) 8 या उससे अधिक आसन्न वर्गों की कोशिकाओं को बिट पैटर्न के रूप में प्रस्तुत करते हैं और एक सेल के रूप में एक मशीन निर्देश में निर्धारित करने के लिए पूर्व निर्धारित मूल्यों की एक बड़ी श्रृंखला में इंडेक्स के रूप में उपयोग करते हैं लाइव या मृत है

चेक यहाँ से बाहर:

http://dotat.at/prog/life/life.html

इसके अलावा

XLife:

http://linux.maruhn.com/sec/xlife.html

Answer 5

मैं दूसरे प्रश्न से मेरा उत्तर उद्धृत करने के लिए, क्योंकि अध्याय मैं उल्लेख कुछ बहुत ही दिलचस्प है जा रहा हूँ और ठीक-ठीक समाधान। कार्यान्वयन विवरण में से कुछ, हाँ ग और/या विधानसभा में हैं, लेकिन सबसे अधिक भाग के लिए एल्गोरिदम किसी भी भाषा में काम कर सकते हैं:

अध्याय 17 और माइकल अब्राश के Graphics Programmer's Black Book की 18 सबसे दिलचस्प में से एक हैं पढ़ता है कि मैंने कभी किया था। यह बॉक्स के बाहर सोचने में एक सबक है। पूरी किताब बहुत अच्छी है, लेकिन अंतिम गेम जीवन के खेल के समाधान प्रोग्रामिंग के अविश्वसनीय बिट्स हैं।

Answer 6

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

प्रत्येक बार पूरे सेल ग्रिड के माध्यम से पुन: प्रयास करने के बजाय, आपके द्वारा परिवर्तित की जाने वाली सभी कोशिकाओं की एक प्रति रखें।

इससे प्रत्येक पुनरावृत्ति पर आपके द्वारा किए जाने वाले कार्यों को कम कर दिया जाएगा।

Answer 7

दो विचारों:

(1) कई विन्यास में ज्यादातर खाली जगह है। जीवित कोशिकाओं की एक लिंक्ड सूची (जरूरी नहीं, इसमें अधिक समय लगेगा) रखें, और अपडेट के दौरान, केवल लाइव कोशिकाओं के आसपास अपडेट करें (यह आपके अस्पष्ट सुझाव के समान है, OysterD :)

(2) एक अतिरिक्त सरणी रखें जो 3 पदों (बाएं-मध्य-दाएं) की प्रत्येक पंक्ति में लाइव कोशिकाओं के # स्टोर करती है। अब जब आप किसी सेल के नए मृत/लाइव मान की गणना करते हैं, तो आपको केवल 4 रीड ऑपरेशंस (शीर्ष/नीचे पंक्तियां और केंद्र-पक्ष की स्थिति) की आवश्यकता होती है, और 4 लिखने के संचालन (3 प्रभावित पंक्ति सारांश मान अपडेट करें, और मृत/नए सेल का लाइव वैल्यू)। यह 8 पढ़ने और 1 लिखने में मामूली सुधार है, मानते हैं कि लिखने से लिखने की कोई धीमी गति नहीं है। मुझे लगता है कि आप इस तरह के विन्यास के साथ और अधिक चालाक हो सकते हैं और इन लाइनों के साथ एक बेहतर सुधार पर पहुंच सकते हैं।

Answer 8

आपको अंतिम अनुकूलन Hashlife पर देखना चाहिए। यह quadtree दृष्टिकोण का उपयोग करता है जो त्वचा का उल्लेख करता है।

Answer 9

एल्गोरिदम स्वयं स्वाभाविक रूप से समांतर है। एक unoptimized CUDA कर्नेल में एक ही डबल-बफर विधि का उपयोग करके, मुझे 4096x4096 लिपटे दुनिया में प्रति पीढ़ी लगभग 25 मिलीमीटर मिल रहा है।

Answer 10

सबसे कुशल अल्गो मुख्य रूप से प्रारंभिक स्थिति पर निर्भर करता है।

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

मेरी राय है कि यह पहली बार पूरी तरह से मृत स्थान की जांच करने के लिए समझ में आ सकता है, जब आपका प्रारंभिक राज्य "यादृच्छिक, लेकिन 5% से कम जीवन के लिए मौका" जैसा होता है।

मैं मैट्रिक्स को हिस्सों में विभाजित कर दूंगा और पहले बड़े लोगों को जांचना शुरू कर दूंगा।

इसलिए यदि आपके पास 10,000 * 10,000 का क्षेत्र है, तो आप पहले 5,000 * 5,000 की ऊपरी बाएं तिमाही के राज्यों को जमा करेंगे।

और यदि पहली तिमाही में राज्यों की राशि शून्य है, तो आप पूरी तरह से इस पहली तिमाही को अनदेखा कर सकते हैं और अगले जीवन के लिए ऊपरी दाएं 5,000 * 5,000 की जांच कर सकते हैं।

यदि इसके राज्यों की संख्या> 0 है, तो आप अब दूसरी तिमाही को 4 टुकड़ों में विभाजित कर देंगे - और इन सब स्पेस के लिए जीवन के लिए इस चेक को दोहराएं।

आप 8 * 8 या 10 * 10 के सबफ्रेम पर जा सकते हैं (सुनिश्चित नहीं है कि अब सबसे ज्यादा समझ में आता है)।

जब भी आपको जीवन मिल जाए, तो आप इन सबस्पेस को "जीवन है" के रूप में चिह्नित करते हैं।

केवल रिक्त स्थान जिनके पास "जीवन है" को छोटे उप-स्थानों में विभाजित करने की आवश्यकता है - खाली वाले को छोड़ा जा सकता है।

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

आपको लगता है कि 8 * 8 के उप-स्थानों में 10,000 * 10,000 स्पाई को विभाजित करना बहुत अधिक काम है - लेकिन उनके राज्य मूल्यों को जमा करना वास्तव में बहुत अधिक है, प्रत्येक सेल प्लस के लिए गोएल अलगो करने से बहुत कम कंप्यूटिंग कार्य उनके 8 पड़ोसियों के साथ-साथ संख्या की तुलना और शुद्ध पुनरावृत्ति के लिए नए राज्य को संग्रहित करना ...

लेकिन जैसा कि मैंने उपरोक्त कहा है, 30% आबादी के साथ एक यादृच्छिक init स्थिति के लिए यह बहुत समझ में नहीं आता है, क्योंकि वहां नहीं होगा कई पूरी तरह मृत 8 * 8 सबस्पेस ढूंढने के लिए (अकेले मृत 256 * 256 उप-स्थान छोड़ दें)

और निश्चित रूप से, सही अनुकूलन का तरीका अंतिम रहेगा लेकिन कम से कम आपकी भाषा पर निर्भर नहीं होगा।

-110

Answer 11

मैं सी # में यह लागू किया: सभी कक्ष, एक स्थान है एक पड़ोसी, गिनती एक राज्य, और शासन के लिए उपयोग। 1. सरणी ए में सरणी बी में सभी लाइव कोशिकाओं को रखें 2. सरणी में सभी कक्षों को पड़ोसियों की पड़ोसी गिनती में जोड़ें। 3. सरणी ए में सभी कोशिकाएं स्वयं और उनके पड़ोसियों को सरणी बी में डाल दें 4. नियम और उनके राज्य के अनुसार ऐरे बी अपडेट में सभी कक्ष। 5. सभी सरणी बी में कोशिकाओं 0.

को अपने पड़ोसियों के सेट सकारात्मक: 1. उपेक्षा कोशिकाओं है कि अद्यतन करने की

विपक्ष की जरूरत नहीं है: 1. 4 सरणियों: के लिए एक 2d सरणी सक्रिय कोशिकाओं के लिए ग्रिड, लाइव कोशिकाओं के लिए एक सरणी, और एक सरणी । 2. नियम बी 0 को संसाधित नहीं कर सकता। 3. कोशिकाओं को एक-एक करके संसाधित करता है। 1. सेल भी एक "अद्यतन" मान है, वे केवल अपडेट किया जाता है यदि वे नहीं वर्तमान टिक में अपडेट, सरणी बी की आवश्यकता नहीं पड़ती: 4. प्रकोष्ठों सिर्फ

संभावित सुधार बूलियन्स नहीं हैं जैसा ऊपर बताया गया है 2. सरणी बी के बजाय रहने वाले पड़ोसियों के साथ, सरणी बी कोशिकाएं बिना हो सकती है, और नियम बी 0 के लिए जांच कर सकते हैं।

Answer 12

जावास्क्रिप्ट में कम से कम कार्यान्वयन एक :)

A Game of Life engine Demo in 126 bytes

/* The Game of Life function */ 
// @param s: current state of the grid 
// @param d: size of the grid (d*d) 
// @param n: placeholder 
// @param k: placeholder 
// @param m: placeholder 
// @param i: placeholder 
// @param j: placeholder 
function(s, d, n, k, m, i, j){ 
    for(
    n = [],       // Initialize next state 
    m = [d + 1, d, d - 1, 1],   // Initialize the upper half of the neighbours indexes 
    i = d * d;      // For each cell 
    i--; 
    n[i] = k == 3 || s[i] && k == 2, // Set next state (live if it has 3 neighbours or lives and has 2 neighbours) 
    k = 0        // Reset the count of living neighbours 
) 
    for(j in m)       // for each neighbour position 
    k += s[i + m[j]] + s[i - m[j]] // count the living neighbours 
    return(n)       // return the next state 
}