AS3 - Быстрый поиск по массиву со строками

Question

Мне нужна помощь. Я делаю что-то вроде словаря (но вы его заполняете сами). Мне нужен быстрый поиск слов в нем. Мне нужно использовать Object или Array (потому что словарь не поддерживается JSON. Существует возможность сохранения файла). У меня есть этот код, но я боюсь, что он не настолько оптимизирован для быстрого поиска, когда в массиве будет много слов. Пожалуйста помоги.

public function Search (string:String,section:String = Wordbook.NEWW):int 
    { 
     var str:String = string.toUpperCase(); 
     for (i = 0; i < NewWords.length; i++) 
     { 
      if (NewWords[i].toUpperCase.indexOf(str) > -1) 
      { 
       return i; 
      } 
     } 
     return -1;//If not found 
    } 

И пример того, как он должен работать: (SearchTxt - текстовое поле, пользователь должен ввести здесь слово ему нужно найти; WB - класс Wordbook; WB.NewWords & WB.NewWordsT - Массивы в этом классе)

var index:int = WB.Search(SearchTxt.text,Wordbook.NEWW); 
if(index>-1){ 
    WordTxt.text = WB.NewWords[index]; 
    TranslationTxt.text = WB.NewWordsT[index]; 
} else { 
    dispatchEvent(new EventWithMessage(EventWithMessage.ERROR,{error:"No match!"})); 
} 

Answer 1

Существует два решения в зависимости от ваших прецедентов.

Решение 1: Оставьте это в покое!

Если самый большой словарь, который вы собираетесь построить, это всего лишь сто слов или около того, производительность будет в порядке с линейным поиском.

Решение 2: реализовать алгоритм двоичного поиска

Если вам не нужно иметь дело с большими словарями тысяч слов, алгоритм двоичного поиска предложит улучшенную производительность. Для этого вам нужно гарантировать, что ваш массив поиска отсортирован.

Что-то вроде этого следует сделать трюк:

public function Search (string:String,section:Array = NewWords, offset:int = 0):int 
{ 
    if (section.length == 0) { 
     return -1; 
    } 
    var str:String = string.toUpperCase(); 
    var firstCharCode:int = str.charCodeAt(0); 
    var middleWord:String = section[section.length/2]; 
    var middleWordCharCode:int = middleWord.charCodeAt(0); 


    if (middleWord.substr(0,str.length) == str) { 
     return (section.length/2) + offset; 
    } else { 
     var comparison:int = str.localeCompare(middleWord); 
     if (comparison < 0) { 
      return Search(string, section.splice(0, section.length/2), offset); 
     } else { // then comparison > 0 
      var newOffset:int = offset + section.length/2; 
      return Search(string, section.splice(section.length/2, section.length-1), newOffset); 
     } 
    } 
}