actionscript-3 - 在 actionscript 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) 尝试 binary search 。它的问题在于您首先必须预先对列表进行排序。你只需要做一次，因为从你的字典中删除单词是没有意义的。但是对于数百万个单词，它可能会比较密集。

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 函数中添加对内置 Prop 的额外检查:

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;
}