在动作3中搜索一个很长的单词列表的最快方法是什么？

Question

所以我有一个单词列表(整个英语词典).

对于单词匹配游戏,当玩家移动一个棋子时,我需要检查整个词典,看看玩家所做的单词是否存在于词典中.我需要尽快做到这一点.简单地遍历字典太慢了.

什么是AS3中最快的算法来搜索匹配的长列表,以及我应该使用什么数据类型？(即数组,对象,字典等)

Answer 1

我首先使用Object,这是一个哈希表(至少是存储方式).

因此,对于列表中的每个单词,在您的字典对象中创建一个条目并将true存储为其值.

然后,您只需检查给定单词是否是您的词典中的键,以了解用户选择的单词是否有效.

这个简单的测试(10,000,000个条目)非常快:

var dict:Object = {};
for(var i:int = 0; i < 10000000; i++) {
    dict[i] = true;
}
var btn:Sprite = new Sprite();
btn.graphics.beginFill(0xff0000);
btn.graphics.drawRect(0,0,50,50);
btn.graphics.endFill();
addChild(btn);
btn.addEventListener(MouseEvent.CLICK,checkWord);

var findIt:Boolean = true;
function checkWord(e:MouseEvent):void {
    var word:String;
    if(findIt) {
        word = "3752132";
    } else {
        word = "9123012456";
    }

    if(dict[word]) {
        trace(word + " found");
    } else {
        trace(word + " not found");
    }
    findIt = !findIt;
}

构建字典需要更长的时间,但查找几乎是即时的.

唯一需要注意的是,您必须考虑通过支票的某些键,而不一定是您的单词列表的一部分.诸如toString,prototype等等词语只有少数几个,但要牢记这一点.

我会用你真实的数据集尝试这样的东西.如果它工作正常,那么你有一个非常简单的解决方案.去喝啤酒(或者你喜欢什么).

现在,如果在使用真实数据测试之后上面的内容确实不起作用(请注意我为了简单起见将构建的数字列为字符串),那么我可以选择几个选项:

1)将第dict一个分区为一组词典.因此,不是包含所有单词,而是dict使用以'a'开头的单词的字典,使用'b'的单词的字典等.然后,在查找单词之前,检查第一个字符以了解查找位置.

就像是:

var word:String     = "hello";
var dictKey:String  = word.charAt(0);
// actual check
if(dict[dictKey][word]) {
    trace("found");
} else {
    trace("not found");
}

如有必要,您最终可以重新分区.即,dict['a']指出由前两个字符索引的另一组字典.所以,你会有的dict['a']['b'][wordToSearch].这个想法有很多可能的变化(你还需要提出一些策略来处理两个字母的单词,例如"be").

2)尝试二进制搜索.它的问题是你首先必须预先对列表进行排序.你必须只做一次,因为从你的词典中删除单词是没有意义的.但有数百万字,可能会更加密集.

3)从开源库中尝试一些奇特的数据结构,例如:

http://sibirjak.com/blog/index.php/collections/as3commons-collections/

http://lab.polygonal.de/ds/

但是,正如我上面所说,我首先尝试最简单,最简单的解决方案,并检查它是否与真实数据集相对应.

添加

处理用于Object的内置属性的关键字的简单方法:

var dict:Object = {};
var keywordsInDict:Array = [];

function buildDictionary():void {
    //  let's assume this is your original list, retrieved 
    //  from XML or other external means
    //  it contains "constructor", which should be dealt with
    //  separately, as it's a built-in prop of Object
    var sourceList:Array = ["hello","world","foo","bar","constructor"];
    var len:int = sourceList.length;
    var word:String;
    //  just a dummy vanilla object, to test if a word in the list 
    //  is already in use internally by Object
    var dummy:Object = {};

    for(var i:int = 0; i < len; i++) {
        //  also, lower-casing is a good idea
        //  do that when you check words as well
        word = sourceList[i].toLowerCase();
        if(!dummy[word]) {
            dict[i] = true;
        } else {
            //  it's a keyword, so store it separately
            keywordsInDict.push(word);
        }
    }
}

现在,只需在checkWords函数中添加对内置道具的额外检查:

function checkWord(e:MouseEvent):void {
    var word:String;
    if(findIt) {
        word = "Constructor";
    } else {
        word = "asdfds";
    }
    word = word.toLowerCase();
    var dummy:Object = {};
    //  check first if the word is a built-in prop 
    if(dummy[word]) {
        //  if it is, check if that word was in the original list
        //  if it was present, we've stored it in keywordsInDict
        if(keywordsInDict.indexOf(word) != -1) {
            trace(word + " found");
        } else {
            trace(word + " not found");
        }
    // not a built-in prop, so just check if it's present in dict 
    } else {
        if(dict[word]) {
            trace(word + " found");
        } else {
            trace(word + " not found");
        }
    }
    findIt = !findIt;
}