अद्वितीय पूर्णांक/तेजी से compairson

Question

के लिए तार से अधिक लंबे हैश कुंजी पीढ़ी मैं उत्सुक कैसे दूसरों को इस समस्या का समाधान है, और अनुभवहीन समाधान के पीछे क्या समस्याओं घात में रहना हो सकता है कर रहा हूँ:

मैं एक प्रणाली है जो शेयर बाजार डाटा को संसाधित करता है। संबंधित कीमतों/आकारों के साथ हजारों प्रतीकों हैं, जो प्रत्येक हजार मिलीसेकंद की दर से सिस्टम में बहती हैं।

प्रत्येक टिक पर होने वाली बुनियादी परिचालनों में से एक स्ट्रिंग तुलना है यह देखने के लिए कि क्या आने वाले प्रतीक में हम रुचि रखते हैं। ऐसी उच्च आवृत्ति पर, इन स्ट्रिंग तुलनाओं का अनुकूलन प्रदर्शन में एक मापनीय अंतर कर सकता है पूरी प्रणाली का।

मैं प्रतीक स्ट्रिंग का हैश उत्पन्न करने और रिकॉर्ड के साथ संग्रहीत करने के बारे में सोच रहा हूं। बाद की तुलना के लिए, सिस्टम को इस हैश का उपयोग करना चाहिए (एक इंट या लम्बा होने के कारण, तुलना एक स्ट्रिंग के प्रत्येक चरित्र के माध्यम से पुनरावृत्ति करने के बजाए एक एकल ऑपरेशन होना चाहिए, जब तक कि कोई मेल नहीं मिला हो)।

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

संपादित करें: मैं जावा में यह कोड लिखूंगा। हैशकोड की गति (टकराव) गुणवत्ता या उस गति के बारे में सुनिश्चित नहीं है जिसके साथ इसकी गणना की जाती है।

Answer 1

शायद हैश फ़ंक्शन यहां सबसे अच्छा तरीका नहीं हैं। यदि आपको टिकर प्रतीक प्राप्त हो रहा है (और टिकर प्रतीक का हैश नहीं है) तो आपको हर बार इसके लिए हैश की गणना करने की आवश्यकता होगी। यदि कोई टकराव के साथ एक हैशिंग एल्गोरिदम है, तो आपको वैसे भी प्रतीक के हर चरित्र को देखना होगा। तो आप सीधे वर्णों की तुलना भी कर सकते हैं।

मैं सभी टिकर में आपकी रुचि है की एक Trie डेटा संरचना के निर्माण के सुझाव देते हैं। (http://en.wikipedia.org/wiki/Trie देखें)। प्रत्येक प्रतीक के लिए पेड़ को पार करें और यदि आप मैच खोजने के बिना टिकर के अंत तक पहुंच जाते हैं, तो यह एक दिलचस्प टिकर नहीं है।

हैशिंग साथ

, आप दिलचस्प टिकर के सभी हैश मूल्यों के दस्तावेज़ में वैसे भी इस ट्रेवर्सल करना होगा।

Answer 2

आप पूलिंग आप तो .equals() की तुलना में उपयोग कर सकते हैं == बल्कि String.intern() या अपने खुद के स्ट्रिंग का उपयोग करते हैं - मैं इसी तरह के प्रदर्शन महत्वपूर्ण कोड में यह कर दिया है और यह एक बड़ा अंतर बना दिया है। डिफ़ॉल्ट स्ट्रिंग में पहले से ही हैशकोड() है जो काफी प्रभावी ढंग से काम करता है।

मुझे अभी पता चला है कि यह जावा प्रश्न नहीं था, लेकिन यह भी लागू होता है। हां, हैशिंग और फिर पहचान जांच का उपयोग समय बचा सकता है। जावा हैशिंग एल्गोरिथ्म का उपयोग करता:

 
    s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1] 

Answer 3

आम क्रिप्टोग्राफिक हैश कार्यों SHA-1 आउटपुट की तरह 20 बाइट (160 बिट)। आपके स्टॉक प्रतीक कितने समय तक हैं? अगर हम ticker symbols जैसे "डब्लूएमटी" (वॉलमार्ट), "केओ" (कोका-कोला) इत्यादि के बारे में बात कर रहे हैं, तो वे केवल बाइट्स के कुछ ही लंबे प्रतीत होते हैं - इस प्रकार उन्हें सीधे तुलना करने के लिए तेज़ी से होना चाहिए एक 20 बाइट हैश से निपटना। आप हैश टकराव का जिक्र करते हैं - मैं उनके बारे में चिंता नहीं करता, खासकर जब इनपुट हैश आउटपुट से बहुत छोटा होता है।

आप एक int या long प्रोग्रामिंग भाषा और मंच पर निर्भर करता है में बाइट्स कास्ट करने के लिए सक्षम हो सकता है और फिर इन "संख्या" एक सीपीयू अनुदेश में के बीच तुलना करते हैं। (मैं आधुनिक compilers memcmp के लिए एक कॉल के साथ समान रूप से तेजी से बाइट्स का एक समूह की तुलना कर सकते, तो पता नहीं है?)

Answer 4

आप एक Perfect hash function उपयोग करने पर विचार करना चाहिए, मैं इसे अपनी आवश्यकताओं के

Answer 5

आप हैश उत्पन्न कर सकता है फिट बैठता है लगता है स्ट्रिंग को आधार -27 संख्या के रूप में मानकर (मानते हैं कि प्रतीकों में केवल अक्षर हैं)। यह उस विशिष्टता को उत्पन्न करेगा जो आप खोज रहे हैं। उदाहरण के लिए:

(कोई पत्र नहीं) = 0, ए = 1, बी = 2, ...जेड = 26

ए.ए. = (1 x 27) + (1 x 27) = 28

एएए = (1 x 27) + (1 एक्स) + (1 x 27) = 757

बीबीबी = (2 x 27) + (2 एक्स) + (2 x 27) = 1514

GOOG = (7 x 27) + (15 x 27) + (15 x 27) + (7 x 27) = 149128

यह एक 32-बिट int में 6 अक्षर को ठीक ऊपर काम करेंगे।

Answer 6

कोई सभ्य हैश फ़ंक्शन टक्कर को अच्छी तरह से संभालता है। असल में, यदि हैश का परिणाम एक हिट में होता है जिसके लिए कई उत्तर मौजूद होते हैं, तो उस बाल्टी में संभावित समाधानों की एक लिंक्ड सूची होती है, और आवश्यकता होती है, सही उत्तर खोजने में चीजें धीमी होती हैं (यदि कोई मौजूद है)।

लेकिन अपने स्वयं के हैश फंक्शन नहीं लिखते, एक कि है वहाँ बाहर का उपयोग करें।

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

Answer 7

संपादित करें: मेरे अपने से बेहतर टिप्पणियों पर फेंक रहे थे (और पुराने), खदान में सबसे अच्छा निरर्थक बना रही है।

Answer 8

आप जो चाहते हैं वह एक तेज हैश फ़ंक्शन है जिसमें अच्छी भेदभाव शक्ति है। प्रत्येक स्ट्रिंग के लिए, संबंधित हैश फ़ंक्शन की गणना करें और इसे स्ट्रिंग के साथ स्टोर करें। फिर एक तुलना, कोड के लिए : अगर (हैश (S1) == हैश (s2) & & एस 1 == s2) तो {...} वास्तविक स्ट्रिंग तुलना घटित नहीं होगा जब तक कि हैश से मेल खाते हैं, जो अभ्यास में तभी होता है जब तार मिलान होता है।

कुछ लोग आपको एक परिपूर्ण हैश लागू करने के लिए बताएंगे।आप केवल कर सकते हैं कि जब स्ट्रिंग्स का सेट आप हैश को आकारबद्ध करना चाहते हैं, आमतौर पर केवल 10-1000। आप तारों की मनमाने ढंग से बड़ी शब्दावली के लिए ऐसा नहीं कर सकते हैं। चूंकि आप ऐसा नहीं कर सकते हैं, इसलिए आपको वास्तव में समानता निर्धारित करने के लिए तारों की तुलना करना होगा।

क्रिप्टोग्राफिक हैश महान भेदभाव की शक्ति है, लेकिन नहीं बनाया गया है तेजी से किया जाना है। क्या आम तौर पर बहुत तेज है और अच्छा भेदभाव शक्ति है सीआरसी कार्य हैं, और सबसे भाषाओं आसानी से पुस्तकालयों कि इन जल्दी से गणना (बाइट्स पर एक मेज देखने तकनीक का उपयोग कर) मिल गया है। हम सीआरसी -32 का उपयोग करते हैं और यह इसके लिए बहुत प्रभावी है (मूल रूप से 2^32 में 1 मौका है कि हैश टकराव होगा, जब तार मेल नहीं खाते हैं)। आप सीआरसी -64 का उपयोग कर सकते हैं, लेकिन अतिरिक्त भेदभाव शक्ति यह प्रदान करता है जो वास्तव में कोई वास्तविक कार्यक्षमता नहीं जोड़ता है।

Answer 9

मैं दूसरा इस मामले के लिए सबसे अच्छा तरीका के रूप में एक Trie संरचना के ऊपर सुझाव। कम्प्यूटेशनल रूप से एक परिपूर्ण हैश के बराबर है, लेकिन अवधारणात्मक रूप से बहुत सुंदर है। यह माना जाता है कि आपके प्रतीक लंबाई में बंधे हैं।

Answer 10

Fwiw, पिछले उच्च डेटा मात्रा परियोजना मैं पर था पर, हम छानने पाया, योग और कुछ भारी-देखते सी कोड का उपयोग कर पूर्व वर्गीकृत डेटा महत्वपूर्ण था। हमारी सभी फीड इस प्री-प्रोसेसर में गईं और प्रोसेसिंग के लिए हमारे जावा-आधारित सिस्टम में डेटा के बड़े हिस्से को पार करने से पहले सरल डेटा सफाई का ख्याल रखा। असल में प्री-प्रोसेसर ने जो कुछ भी पूछा है वह किया: रुचि के रिकॉर्ड की पहचान करना, सत्यापित करना कि वे पूर्ण थे और डुप्लिकेट और खालीियां हटा रहे थे। चोटी के समय के दौरान प्री-प्रोसेसर 8 एम तक 20% तक खत्म कर सकता है या ऐसे रिकॉर्ड जो हमें प्रति घंटा मिलेंगे (संभवतः मुझे लगता है कि वॉल्यूम फ़ीड्स से आपको लगता है कि काफी मात्रा नहीं है)। हमारा मूल जावा संस्करण भाग्यशाली था कि वह आधा हो (लेकिन यह कम से कम "सुरुचिपूर्ण" था!) ​​

Answer 11

यदि आपको 4-अक्षर टिकर प्रतीकों को प्राप्त हो रहा है, तो प्रत्येक पत्र को एक बाइट के रूप में प्रस्तुत किया जाना चाहिए। 32-बिट int, और voila में सभी 4 को एक साथ पैक करें, आपके पास "हैश" है। अब आप एक मशीन निर्देश का उपयोग कर संदर्भ के खिलाफ इसकी तुलना कर सकते हैं।

यदि आप जावा का उपयोग नहीं कर रहे थे, तो यह है।

मैं वास्तव में कुछ भी गति-महत्वपूर्ण के लिए जावा का उपयोग करने का सुझाव नहीं दूंगा, विशेष रूप से हजारों स्ट्रिंग तुलना प्रति मिलीसेकंड नहीं।

संपादित करें: यदि आप 64-बिट कोड का उपयोग करना चाहता है, तो आप लंबे समय तक पूर्णांक प्रति 8 अक्षर को बांध सकता है और उसके बाद 1 अनुदेश में की तुलना करें।

Answer 12

इसके लायक के लिए क्या। मैंने इस समस्या को सीएमएस (एनवाईएसई) और सीक्यूएस (NASDAQ) symbology के लिए विशिष्ट हल किया। प्रतीक जड़ें अधिकतम 6 वर्ण लंबी होंगी और अपरकेस होगी।

• डाटा डेटा एक हैश मूल्य की गणना प्राप्त करने पर अज्ञात प्रतीक
• के लिए आएंगे
• कंप्यूट मूल्य एक बार की तुलना के लिए प्रयोग की जाने वाली, भविष्य तुलना के लिए एक नक्शे में मूल्य की दुकान: मेरी आवश्यकताओं इस प्रकार थे
• मूल्य तुलना समानता
• मूल्य तुलना एक सीमा के खिलाफ हो जाएगा हो जाएगा।

उदाहरण के लिए यदि GOOG के लिए डेटा आता है तो इसे प्रतीक सीमा [एफ-HAA] में प्रक्रियाओं में संसाधित और वितरित करने की आवश्यकता होगी। (एफ < = GOOG < = HAA)। मैंने एक श्रेणी वर्ग का उपयोग किया जिसमें कम मूल्य (एफ) और उच्च मूल्य (एचएए) है।माई हैश फ़ंक्शन अवधारणा वर्णों को बाइट्स में पैक करने के समान है लेकिन लॉगिंग, नेटवर्क और एंडियन उद्देश्यों के लिए मैंने अपने स्टोरेज प्रकार के रूप में लंबे समय तक हस्ताक्षर किए हैं। इस समारोह को कॉल करने से पहले प्रतीक '@' चरित्र के साथ गद्देदार हैं। (आईबीएम @@@)

unsigned long long SymbolToVal(std::string& str) 
{ 
size_t maxlen = 6; // Symbology constraint 
if (str.length() != maxlen) return 0; 
unsigned long long val; 
unsigned long long retval=0; 
int expon = maxlen*2; // ASCII val range (65-90) 
double factor = std::pow(10.0,expon); 
expon-=2; 
for (size_t i = 0; i < maxlen; i++) 
{ 
    val = (unsigned long long)factor * str[i]; 
    retval += val; 
    factor = (unsigned long long) std::pow(10.0,expon); 
    expon-=2; 
    } 
    return retval; 
} 

एक जानवर बल विधि सभी संभव प्रतीकों उन्हें ठीक से सॉर्ट और उन्हें तो एक पूर्णांक आवंटित उन्हें एक नक्शे में स्टोर गणना करने के लिए किया जाएगा। यदि आने वाले डेटा में केवल कुल डोमेन का एक छोटा सा हिस्सा होता है (जो सामान्य मामला है) तो अधिक हो सकता है।