उद्देश्य-सी में तारों के माध्यम से खोज करने का सबसे तेज़ तरीका क्या है?

Question

मैं एक आईओएस ऐप के लिए एक तरह का स्वत: पूर्ण कार्यान्वित कर रहा हूं। डेटा जो मैं स्वत: पूर्ण मानों के लिए उपयोग कर रहा हूं वह लगभग 100,000 तारों वाला अल्पविराम से अलग टेक्स्ट फ़ाइल है। यह अब मैं क्या कर रहा हूँ है:

1. पाठ फ़ाइल पढ़ें, और 100000 NSString के साथ एक NSArray पैदा करते हैं।
2. उपयोगकर्ता प्रकार के रूप में, [array containsObject:text]

निश्चित रूप से वहाँ एक बेहतर/तेजी से इस देखने करने के लिए जिस तरह से है। कोई विचार?

Answer 1

बिल्कुल, वहाँ है! यह "उद्देश्य-सी" में नहीं है हालांकि: सबसे अधिक संभावना है, आपको इसे स्वयं कोड करना होगा।

विचार स्ट्रिंग की अपनी सूची को suffix tree में परिवर्तित करना है, एक डेटा संरचना जो आपको उपसर्ग द्वारा बहुत तेज़ी से खोज करने देती है। एक प्रत्यय पेड़ में संभव समापन के लिए खोज बहुत तेज़ हैं, लेकिन संरचना स्वयं निर्माण करना आसान नहीं है। इंटरनेट पर एक त्वरित खोज से पता चला कि उद्देश्य सी में कोई आसानी से उपलब्ध कार्यान्वयन नहीं है, लेकिन आप port an implementationin another language, use a C implementation, या यहां तक ​​कि यदि आप विशेष रूप से समय के लिए दबाए नहीं जाते हैं तो खुद को भी लिख सकते हैं।

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

Answer 2

शायद सबसे आसान बाइनरी खोज है। -[NSArray indexOfObject:inSortedRange:options:usingComparator:] देखें।

आप सरणी, संभवतः @selector(compare:) लोड करते हैं (यदि आप इसके बारे में चिंतित हैं कि आप फ़ाइल को बचाने के

• पूर्व प्रकार सरणी:

  विशेष रूप से, मैं कुछ इस तरह की कोशिश करता हूँ गलती से छोड़े जा रहे हैं या कुछ किनारे के मामलों के लिए यूनिकोड सॉर्ट ऑर्डर बदल रहा है)। यह लगभग ओ (एन) होना चाहिए मानना ​​है कि सरणी ज्यादातर पहले से ही क्रमबद्ध है।

• पहला संभावित मिलान खोजने के लिए, [array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
• सरणी को तब तक चलाएं जब तक कि प्रविष्टियों में कोई उपसर्ग के रूप में खोज न हो। ,

यह नहीं "सही ढंग से" सभी स्थानों संभाल सकता है (विशेष रूप से तुर्की) (NSWidthInsensitiveSearch | NSCaseInsensitiveSearch | | NSDiacriticInsensitiveSearch NSAnchoredSearch) आप शायद मामले/विशेषक/चौड़ाई-संवेदी तुलना करने के लिए निर्धारित करने के लिए यह एक उपसर्ग है कि क्या चाहते हैं लेकिन न तो compare:localizedCompare: के साथ बदल देगा, न ही स्ट्रिंग-फोल्डिंग भंग करेगा। (यह केवल 9 लाइन लंबी है, लेकिन सही होने के लिए लगभग एक दिन का समय लगता है और इसमें लगभग 40 लाइन कोड और 200 लाइनों की परीक्षा है, इसलिए मुझे शायद इसे यहां साझा नहीं करना चाहिए।)