दो अंकों में अलग-अलग अद्वितीय कोड उत्पन्न करना

Question

मैं अद्वितीय कोड संख्याएं उत्पन्न करना चाहता हूं (वास्तव में 7 अंकों से बना)। कोड संख्या यादृच्छिक रूप से जेनरेट की जाती है और MySQL तालिका में सहेजी जाती है।

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

एल्गोरिथ्म उत्पन्न बस काम करता है की तरह है:

1. सभी पिछले कोड को पुनः प्राप्त करता है, तो MySQL तालिका से किसी भी।
2. एक समय में एक कोड उत्पन्न करें।
3. सभी पिछले कोड के साथ जेनरेट कोड घटाएं।
4. घटाव परिणाम में गैर-शून्य अंकों की संख्या की जांच करें।
5. यदि यह> 1 है, तो जेनरेट कोड स्वीकार करें और इसे पिछले कोड में जोड़ें।
6. अन्यथा, 2.
7. अनुरोधित कोडों की संख्या के लिए 2 से 6 चरणों को दोहराएं।
8. डीबी तालिका में जेनरेट कोड सहेजें।

एल्गोरिदम ठीक काम करता है, लेकिन समस्या प्रदर्शन से संबंधित है। बड़ी संख्या में कोड उत्पन्न करने का अनुरोध करते समय कोड उत्पन्न करना बहुत लंबा लगता है: 10,000।

प्रश्न: क्या इस एल्गोरिदम के प्रदर्शन में सुधार करने का कोई तरीका है?

यदि यह मायने रखता है तो मैं उबंटू सर्वर पर perl + MySQL का उपयोग कर रहा हूं।

Answer 1

क्या आपने लुहान एल्गोरिदम का एक संस्करण माना है? लुहान का उपयोग क्रेडिट कार्ड खाता संख्या सहित कई अनुप्रयोगों में संख्याओं के तारों के लिए चेक अंक उत्पन्न करने के लिए किया जाता है। यह पहचानकर्ताओं को उत्पन्न करने के लिए आईएसओ -7812-1 मानक का हिस्सा है। यह किसी भी गलत अंक के साथ दर्ज की गई किसी भी संख्या को पकड़ लेगा, जिसका अर्थ है कि किसी भी दो मान्य संख्या कम से कम दो अंकों में भिन्न होती है।

एक पेर्ल कार्यान्वयन के लिए सीपीएएन में एल्गोरिदम :: LUHN देखें।

Answer 2

मौजूदा कोड को पुनः प्राप्त मत करो, सिर्फ एक संभावित नए कोड पैदा करते हैं और अगर वहाँ डेटाबेस में किसी भी विरोधी होते हैं देखें:

SELECT code FROM table WHERE abs(code-?) regexp '^[1-9]?0*$'; 

(जहां प्लेसहोल्डर नव उत्पन्न कोड है)।

आह, मैंने एक बार में कई सारे कोड उत्पन्न किए। इसे इस तरह से करें (पूरी तरह से अवांछित):

my @codes = existing_codes(); 

my $frontwards_index = {}; 
my $backwards_index = {}; 
for my $code (@codes) { 
    index_code($code, $frontwards_index); 
    index_code(reverse($code), $backwards_index); 
} 

my @new_codes = map generate_code($frontwards_index, $backwards_index), 1..10000; 

sub index_code { 
    my ($code, $index) = @_; 
    push @{ $index{ substr($code, 0, length($code)/2) } }, $code; 
    return; 
} 

sub check_index { 
    my ($code, $index) = @_; 
    my $found = grep { ($_^$code) =~ y/\0//c <= 1 } @{ $index{ substr($code, 0, length($code)/2 } }; 
    return $found; 
} 

sub generate_code { 
    my ($frontwards_index, $backwards_index) = @_; 

    my $new_code; 
    do { 
     $new_code = sprintf("%07d", rand(10000000)); 
    } while check_index($new_code, $frontwards_index) 
     || check_index(reverse($new_code), $backwards_index); 
    index_code($new_code, $frontwards_index); 
    index_code(reverse($new_code), $backwards_index); 
    return $new_code; 
} 

Answer 3

संवर्द्धित बाइनरी खोज पेड़ में संख्या 0 9, 9 99, 999 के माध्यम से रखें। वृद्धि उप-नोड्स की संख्या को बाईं ओर और दाईं ओर ट्रैक रखना है। तो उदाहरण के लिए जब आपका एल्गोरिदम शुरू होता है, तो शीर्ष नोड का मूल्य 5,000,000 होना चाहिए, और यह पता होना चाहिए कि इसमें बाईं ओर 5,000,000 नोड्स हैं, और दाईं ओर 4,999,999 नोड्स हैं। अब एक हैशटेबल बनाएं। आपके द्वारा पहले से उपयोग किए गए प्रत्येक मान के लिए, संवर्धित बाइनरी खोज पेड़ से अपना नोड हटा दें और हैशटेबल में मान जोड़ें। संवर्द्धन को बनाए रखना सुनिश्चित करें।

एक मूल्य प्राप्त करने के लिए, इन चरणों का पालन करें।

1. पेड़ में कितने नोड्स छोड़े गए हैं यह निर्धारित करने के लिए शीर्ष नोड का उपयोग करें। मान लें कि आपके पास एन नोड्स शेष हैं। 0 और एन के बीच यादृच्छिक संख्या चुनें। संवर्द्धन का उपयोग करके, आप लॉग (एन) समय में अपने पेड़ में nth नोड पा सकते हैं।
2. एक बार जब आप उस नोड को पा लेते हैं, तो उन सभी मानों की गणना करें जो उस नोड पर मान को अमान्य बनाते हैं। मान लीजिए कि आपके नोड का मूल्य 1,111,111 है। यदि आपके पास पहले से 2,111,111 या 3,111,111 या ... है तो आप 1,111,111 का उपयोग नहीं कर सकते हैं। चूंकि प्रति अंक और 7 अंकों के 8 अन्य विकल्प हैं, इसलिए आपको केवल 56 संभावित मानों की जांच करने की आवश्यकता है। यह देखने के लिए जांचें कि इनमें से कोई भी मान आपके हैशटेबल में है या नहीं। यदि आपने अभी तक इनमें से किसी भी मान का उपयोग नहीं किया है, तो आप अपने यादृच्छिक नोड का उपयोग कर सकते हैं। यदि आपने उनमें से किसी का उपयोग किया है, तो आप नहीं कर सकते हैं।
3. संवर्धित पेड़ से अपने नोड को हटा दें। सुनिश्चित करें कि आप संवर्धित जानकारी को बनाए रखें।
4. यदि आप उस मान का उपयोग नहीं कर सकते हैं, तो चरण 1 पर वापस जाएं।
5. यदि आप उस मान का उपयोग कर सकते हैं, तो आपके पास एक नया यादृच्छिक कोड है। इसे हैशटेबल में जोड़ें।

अब, यह देखने के लिए जांचें कि कोई मान उपलब्ध है या नहीं (ओ) समय के बजाय ओ (1) समय लेता है। इसके अलावा, जांचने के लिए एक और उपलब्ध यादृच्छिक मान ढूंढने के बजाय ओ (लॉग एन) समय लेता है ... आह ... मुझे यकीन नहीं है कि आपके एल्गोरिदम का विश्लेषण कैसे करें।

लंबी कहानी छोटी, यदि आप खरोंच से शुरू करते हैं और इस एल्गोरिदम का उपयोग करते हैं, तो आप ओ (एन लॉग एन) में मान्य कोड की पूरी सूची तैयार करेंगे। चूंकि एन 10,000,000 है, इसमें कुछ सेकंड या कुछ समय लगेगा।

क्या मैंने वहां सबको गणित किया था? मुझे बताएं कि क्या यह जांच नहीं करता है या मुझे कुछ भी स्पष्ट करने की आवश्यकता है।

Answer 4

एक हैश का उपयोग करें।

सफल कोड उत्पन्न करने के बाद (किसी भी मौजूदा कोड से विवादित नहीं), लेकिन हैश तालिका में वह कोड, और 63 अन्य कोड भी डाल दें जो हैश में बिल्कुल एक अंक से अलग हैं।

यह देखने के लिए कि क्या एक यादृच्छिक रूप से जेनरेट किया गया कोड मौजूदा कोड के साथ संघर्ष करेगा, बस जांचें कि हैश में वह कोड मौजूद है या नहीं।

Answer 5

Howabout:

पिछले एक autoincrementing से एक 6 अंकों का कोड उत्पन्न करें। पिछले एक मॉड 10 को बढ़ाकर 1 अंक कोड उत्पन्न करें। दोनों को दोबारा संयोजित करें।

प्रेस्टो, दो अंकों में भिन्न होने की गारंटी है। : डी

(हां, थोड़ा सा मुखर होना। मुझे लगता है कि 'यादृच्छिक' या कम से कम अर्ध-यादृच्छिक आवश्यक है। इस मामले में, 6 अंकों की यादृच्छिक कुंजी उत्पन्न करें, तब तक दोहराएं जब तक यह डुप्लिकेट न हो (यानी बनाना कॉलम अद्वितीय, जब तक सम्मिलन बाधा में विफल नहीं होता है तब तक दोहराएं), फिर पहले से कहा गया कोई चेक अंक उत्पन्न करें।)