सीयूडीए

Question

में 3 पूर्णांक कुंजी लुकअप मैं लगभग दस लाख अंकों के बड़े डेटा सेट में 3 पूर्णांक (यानी [1 2 3]) देखना चाहता हूं। 1 लाख अंक * 55 हमें 55 सेकंड = -

key = sprintf('%d ', [1 2 3]);  % 23 us 
% key = '1 2 3 ' 
result = lookup_map(key);   % 32 us 

यह काफी समय लगता है, हालांकि:

मैं वर्तमान में MATLAB के मानचित्र (hashmap) का उपयोग कर रहा है, और प्रत्येक बिंदु के लिए मैं निम्नलिखित कर रहा हूँ।

मैं इसे सीयूडीए का उपयोग करके जीपीयू में ले जाना चाहता हूं, लेकिन मुझे यह सुनिश्चित करने का सबसे अच्छा तरीका नहीं है।

मैं चार सरणी - key1, key2, key3, result स्थानांतरित कर सकता हूं, और उसके बाद कुंजी पर बाइनरी खोज कर सकता हूं, लेकिन इसमें 20 पुनरावृत्तियों (2^20 = 1048576) प्रति कुंजी लगेगी। तो मुझे प्रत्येक धागे से समवर्ती स्मृति पहुंच के कारण देरी भी होगी।

क्या सीयूडीए में समानांतर (ओ (1), आदर्श) एकाधिक कुंजी लुकअप के लिए अनुकूलित डेटा संरचना है?

---

प्रश्न: तीन पूर्णांकों की सीमा क्या हैं? और क्या डेटा देखा जाता है?

पूर्णांक कुंजी वर्तमान में 0 और ~ 75,000 के बीच हो सकती है, लेकिन भविष्य में बड़ी (200,000+) हो सकती है।

इस प्रश्न के प्रयोजनों के लिए, हम मान सकते हैं कि result डेटा सेट के 0 और आकार के बीच एक पूर्णांक है।

---

प्र: आप एक 64 बिट संख्या में सभी तीन नंबर पैक नहीं है (संख्या के अनुसार 21 बिट्स आप 0-2,097,152 की एक श्रृंखला देता है)। और इसका उपयोग एक स्पैस सरणी में इंडेक्स करने के लिए करें?

>> A = uint64(ones(10)); 
>> sparse_A = sparse(A) 
??? Undefined function or method 'sparse' for input arguments of type 'uint64'. 

>> A = int64(ones(10)); 
>> sparse_A = sparse(A) 
??? Undefined function or method 'sparse' for input arguments of type 'int64'. 

ऐसा लगता है कि मेरी matlab 64-बिट संख्या के विरल सरणियों का समर्थन नहीं करता।

function [key] = to_key(face) 
    key = uint64(bitsll(face(1), 42) + bitsll(face(2), 21) + rand(face(3),1)); 
end 

---

प्रश्न::

मामले में यह किसी और में मदद करता है, मैं तीन < 2^21 अहस्ताक्षरित पूर्णांकों से एक 64-बिट कुंजी बनाने के लिए एक त्वरित समारोह लिखा @Dennis से - क्यों तार्किक अनुक्रमण का उपयोग नहीं करते?

चलिए इसका परीक्षण करें!

% Generate a million random integers between 0 and 1000 
>> M = int32(floor(rand(10000000,4)*1000)); 
% Find a point to look for 
>> search = M(500000,1:3)    
search = 
     850   910   581 
>> tic; idx = M(:,1)==search(1) & M(:,2)==search(2)&M(:,3)==search(3); toc; 
Elapsed time is 0.089801 seconds. 
>> M(idx,:) 
ans = 
     850   910   581   726 

दुर्भाग्य से यह 89801us लेता है, जो कि मेरे मौजूदा समाधान (55us) से 1632x धीमा है! इसे दस लाख बार चलाने में 2.5 घंटे लगेंगे!

हम प्रत्येक खोज के बाद M छानने की कोशिश कर सकते:

>> tic; idx1=M(:,1)==search(1); N=M(idx1,:); idx2=N(:,2)==search(2); N2=N(idx2,:); idx3 = N2(:,3)==search(3); toc; 
Elapsed time is 0.038272 seconds. 

यह एक छोटे से तेजी से होता है, लेकिन अभी भी 696x मानचित्र का उपयोग कर की तुलना में धीमी।

---

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

Answer 1

मुझे लगता है कि यह प्रश्न आपके previous question से संबंधित है tetrahedron चेहरे के बारे में। मैं अभी भी सुझाव है कि आप उस उद्देश्य के लिए sparse भंडारण और विरल मैट्रिक्स वेक्टर गुणा प्रयास करना चाहिए:

size(spA) 
ans = 

1244810  1244810 

tic; 
vv = spA*v; 
idx = find(vv); 
toc; 

Elapsed time is 0.106581 seconds. 

यह सिर्फ विश्लेषण समय है, कैसे अपने मामले में इसे लागू करने के बारे में मेरे पिछले जवाब देखें। आप सीयूडीए में जाने से पहले और जटिल चीजें करने से पहले, सरल विकल्प देखें।

Answer 2

ध्यान इस सवाल पहले से ही प्राप्त हुआ है यह लगता है इस जवाब की तरह बहुत आसान है, लेकिन क्यों आप सिर्फ इस तरह यह मत करो देखते हुए:

M=[1:6; 2:7; 3:8; 4:9]'; %Some matrix that contains key 1 2 3, corresponding value is 4 
idx=M(:,1)==1&M(:,2)==2&M(:,3)==3; 
M(idx,4) 

यह काफी तेजी से मूल्यांकन करना चाहिए, भले ही M है 1 मिलियन x 4.