Cách nhanh nhất để tìm kiếm danh sách từ rất dài cho khớp trong ActionScript 3 là gì?

Question

Vì vậy, tôi có một danh sách các từ (toàn bộ từ điển tiếng Anh).

Đối với trò chơi kết hợp từ, khi người chơi di chuyển một đoạn, tôi cần kiểm tra toàn bộ từ điển để xem từ mà người chơi có tồn tại trong từ điển hay không. Tôi cần phải làm điều này càng nhanh càng tốt. chỉ đơn giản là lặp qua từ điển là quá chậm.

Thuật toán nhanh nhất trong AS3 để tìm kiếm danh sách dài như thế này cho phù hợp và loại dữ liệu gì tôi nên sử dụng? (ví dụ: mảng, đối tượng, Từ điển, v.v.)

Answer 1

Lần đầu tiên tôi đi với một đối tượng, đó là một bảng băm (ít nhất, lưu trữ khôn ngoan).

Vì vậy, đối với mỗi từ trong danh sách của bạn, hãy tạo một mục trong từ điển của bạn Object và lưu trữ true dưới dạng giá trị của nó.

Sau đó, bạn chỉ cần kiểm tra xem một từ đã cho có phải là một từ khóa trong từ điển của bạn để biết từ mà người dùng đã chọn có hợp lệ hay không.

này hoạt động rất nhanh trong thử nghiệm đơn giản này (với 10.000.000 entries):

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

Phải mất lâu hơn một chút để xây dựng từ điển, nhưng tra cứu là gần như tức thời.

Thông báo trước duy nhất là bạn sẽ phải xem xét một số khóa nhất định sẽ vượt qua kiểm tra và không nhất thiết phải là một phần trong danh sách từ của bạn. Các từ như toString, prototype, vv Chỉ có một vài trong số chúng, nhưng hãy nhớ điều đó.

Tôi sẽ thử một cái gì đó như thế này với bộ dữ liệu thực của bạn. Nếu nó hoạt động tốt, sau đó bạn có một giải pháp thực sự dễ dàng. Đi uống bia (hoặc bất cứ thứ gì bạn thích).

Bây giờ, nếu phần trên không thực sự hoạt động sau khi thử nghiệm với dữ liệu thực (thông báo tôi đã xây dựng danh sách với các số được tạo thành chuỗi để đơn giản), sau đó là một số tùy chọn, ngoài đầu của tôi:

1) Phân vùng dict đầu tiên thành một bộ từ điển. Vì vậy, thay vì có tất cả các từ trong dict, có từ điển cho các từ bắt đầu bằng 'a', từ khác cho 'b', v.v. Sau đó, trước khi tra cứu một từ, hãy kiểm tra char đầu tiên để biết tìm kiếm từ nào .

Cái gì như:

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

Sau cùng, bạn có thể phân vùng lại nếu cần thiết. I.e, tạo dict['a'] trỏ đến một bộ từ điển khác được lập chỉ mục bởi hai ký tự đầu tiên. Vì vậy, bạn sẽ có dict['a']['b'][wordToSearch]. Có một số biến thể có thể có trong ý tưởng này (bạn cũng phải đưa ra một số chiến lược để đối phó với các từ của hai chữ cái, chẳng hạn như "be").

2) Thử một số binary search. Vấn đề với nó là trước tiên bạn sẽ phải sắp xếp danh sách, trả trước. Bạn phải làm điều đó chỉ một lần, vì nó không có ý nghĩa để loại bỏ các từ từ dict của bạn. Nhưng với hàng triệu từ, nó có thể sâu hơn.

3) Hãy thử một số cấu trúc dữ liệu ưa thích từ các thư viện mã nguồn mở như:

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

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

Nhưng một lần nữa, như tôi đã nói ở trên, đầu tiên tôi muốn thử các giải pháp dễ nhất và đơn giản và kiểm tra xem nó có hoạt động với bộ dữ liệu thực không.

Added

Một cách đơn giản để đối phó với các từ khóa được sử dụng để đối tượng tích hợp trong tính:

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

Bây giờ, chỉ cần thêm một kiểm tra thêm cho built-in đạo cụ trong checkWords chức năng:

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

Answer 2

Đây không phải là đặc trưng cho ActionScript, nhưng Trie là cấu trúc dữ liệu phù hợp để lưu trữ từ.