एल्गोरिदम?

Question

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

क्या कोई अन्य क्षेत्र हैं जहां एसएसडी में आने वाले संक्रमण से एल्गोरिदमिक प्रदर्शन में संभावित लाभ मिलेगा? मैं तर्क के बजाय एक चीज कैसे काम करूंगा, इस कारण तर्क को देखना चाहूंगा; मैं नहीं चाहता कि यह विवादास्पद हो।

Answer 1

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

एक उदाहरण शतरंज स्थिति डेटाबेस है। मेरे पास 50 जीबी से अधिक हैश की स्थिति है। हैश में एक-दूसरे के पास समूह से संबंधित पदों को समूहबद्ध करने का प्रयास करने के लिए जटिल कोड है, इसलिए मैं एक समय में तालिका के 10 एमबी में पेज कर सकता हूं और आशा करता हूं कि इसमें से कुछ समान स्थिति प्रश्नों के लिए पुन: उपयोग करें। इस कुशल बनाने के लिए कोड और जटिलता का एक टन है।

एसएसडी के साथ बदलकर, मैं क्लस्टरिंग की सभी जटिलताओं को छोड़ने में सक्षम था और वास्तव में गूंगा यादृच्छिक हश का उपयोग करता हूं। मुझे प्रदर्शन में भी वृद्धि हुई है क्योंकि मैं केवल डिस्क से आवश्यक डेटा प्राप्त करता हूं, न कि बड़े 10 एमबी भाग। विलंबता वास्तव में बड़ी है, लेकिन नेट स्पीडअप महत्वपूर्ण है .. और सुपर-क्लीन कोड (20 लाइनें, 800+ नहीं), शायद यह भी अच्छी है।

Answer 2

अपने आप को बच्चा मत बनो। सिस्टम मेमोरी की तुलना में एसएसडी अभी भी बहुत धीमी हैं। हार्ड डिस्क पर सिस्टम मेमोरी का उपयोग करने के लिए चुनने वाला कोई भी एल्गोरिदम अभी भी बहुत तेज़ होगा, अन्य सभी चीजें बराबर होंगी।

Answer 3

एसएसडी यादृच्छिक पहुंच के लिए केवल काफी तेज़ हैं। डिस्क पर अनुक्रमिक पहुंच वे मुख्यधारा घूर्णन ड्राइव के रूप में केवल दो बार कलाकार के रूप में हैं। here वर्णित अनुसार कई एसएसडी में कई परिदृश्यों में खराब प्रदर्शन होता है।

जबकि एसएसडी सुई को काफी आगे बढ़ाते हैं, वे अभी भी सीपीयू संचालन और भौतिक स्मृति की तुलना में बहुत धीमे हैं। आपके 4 जीबी हैश टेबल उदाहरण के लिए, आप यादृच्छिक हैश टेबल बाल्टी तक पहुंचने के लिए एसएसडी के 250+ एमबी/एस को बनाए रखने में सक्षम हो सकते हैं। एक घूर्णन ड्राइव के लिए, आप एक अंक एमबी/एस को तोड़ने के लिए भाग्यशाली होंगे। यदि आप इस 4 जीबी हैश टेबल को मेमोरी में रख सकते हैं, तो आप इसे गीगाबाइट्स के दूसरे स्थान पर एक्सेस कर सकते हैं - एक बहुत तेज़ एसएसडी से भी तेज।

संदर्भित आलेख में एसएसडी पर चलते समय विंडोज 7 के लिए किए गए कई बदलावों की सूची दी गई है, जो आपको ऐसे बदलावों का विचार दे सकती हैं जिन्हें आप बनाने पर विचार कर सकते हैं। सबसे पहले, डिस्क से डेटा को प्रीफ़ेट करने के लिए सुपरफ़ेच अक्षम है - यह एसएसडी द्वारा कम किए गए डिस्क के लिए धीमे यादृच्छिक एक्सेस समय प्राप्त करने के लिए डिज़ाइन किया गया है। Defrag अक्षम है, क्योंकि डिस्क पर बिखरे हुए फाइलें एसएसडी के लिए प्रदर्शन हिट नहीं हैं।

Answer 4

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

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

Answer 5

एसएसडी यादृच्छिक पढ़ने के लिए बहुत तेज है, अनुक्रमिक पढ़ने के लिए थोड़ा और लिखने के लिए ठीक से धीमा (यादृच्छिक या नहीं)।

तो डिस्कबैस्ड हैशटेबल एसएसडी के साथ उपयोगी नहीं है, क्योंकि अब इसे अपडेट करने में काफी समय लगता है, लेकिन डिस्क खोजना (सामान्य एचडीडी की तुलना में) बहुत सस्ता हो जाता है।