c# - 使预测文本算法运行得更快

Question

我正在开发一个 Windows Phone 拨号器应用程序，我已经在我的应用程序中实现了预测文本。当用户点击键盘时，会生成与输入匹配的联系人。预测太慢，它也阻塞了我的主线程，这就是为什么我实现了 BackGroundWorker 但仍然存在性能问题我的代码是:

private void dialer_TextChanged(object sender, TextChangedEventArgs e)
    {
        MainPage.DialerText = dialer.Text;
        if(!bw1.IsBusy)
        bw1.RunWorkerAsync();
     }
 void bw1_DoWork(object sender, DoWorkEventArgs e)
    {
        try
        {
            var digitMap = new Dictionary<int, string>() {
    { 1, "" },
    { 2, "[abcABC]" },
    { 3, "[defDEF]" },
    { 4, "[ghiGHI]" },
    { 5, "[jklJKL]" },
    { 6, "[mnoMNO]" },
    { 7, "[pqrsPQRS]" },
    { 8, "[tuvTUV]" },
    { 9, "[wxyzWXYZ]" },
    { 0, "" },
};
            var enteredDigits = DialerText;
            var charsAsInts = enteredDigits.ToCharArray().Select(x => int.Parse(x.ToString()));
            var regexBuilder = new StringBuilder();

            foreach (var val in charsAsInts)
            regexBuilder.Append(digitMap[val]);
            MainPage.pattern = regexBuilder.ToString();

            MainPage.pattern = ".*" + MainPage.pattern + ".*";


        }
        catch (Exception f)
        {
            //  MessageBox.Show(f.Message);
        }

    }
void bw1_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
    {
        SearchListbox.ItemsSource = listobj.FindAll(x => x.PhoneNumbers.Any(a=>a.Contains(MainPage.DialerText)) | Regex.IsMatch(x.FirstName, MainPage.pattern));
    }

BackGroundWorker 也阻塞了我的主线程，因此当我点击键盘时，输入值被添加到 TextBox 时会出现延迟。我想无延迟地向 TextTox 添加输入，该怎么做？谢谢。

Answer 1

您可以通过摆脱对整个词表的详尽搜索并将您的词放入更高效的数据结构中来真正加快速度。

为了在任何大小的单词列表上快速查找(但在内存方面更昂贵)，您应该构建一个包含整个单词列表的树结构。

根节点代表调用零的数字，它连接到(最多)十个节点，其中连接节点的边代表 0 到 9 可能按下的数字之一。

然后每个节点包含可能的词，这些词可以从根节点穿过树的路径形成，其中路径代表按下的数字。

这意味着搜索不再需要迭代整个单词列表，只需很少的操作即可完成。

以下是 370000 word-list 的实践概念我在网上找到的。在我的桌面上搜索大约需要 0.02 毫秒。又好又快。似乎占用大约 50MB 的内存。

void Main()
{
    var rootNode = new Node();

    //probably a bad idea, better to await in an async method
    LoadNode(rootNode).Wait(); 

    //let's search a few times to get meaningful timings    
    for(var i = 0; i < 5; ++i)
    {
        //"acres" in text-ese (specifically chosen for ambiguity)
        var searchTerm = "22737";
        var sw = Stopwatch.StartNew();
        var wordList = rootNode.Search(searchTerm);
        Console.WriteLine("Search complete in {0} ms", 
                        sw.Elapsed.TotalMilliseconds);
        Console.WriteLine("Search for {0}:", searchTerm);
        foreach(var word in wordList)
        {
            Console.WriteLine("Found {0}", word);
        }   
    }
    GC.Collect();
    var bytesAllocated = GC.GetTotalMemory(true);
    Console.WriteLine("Allocated {0} bytes", bytesAllocated);
}

async Task LoadNode(Node rootNode)
{
    var wordListUrl = 
    "https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt";
    Console.WriteLine("Loading words from {0}", wordListUrl);
    using(var httpClient = new HttpClient())
    using(var stream = await httpClient.GetStreamAsync(wordListUrl))
    using(var reader = new StreamReader(stream))
    {
        var wordCount = 0;
        string word;
        while( (word = await reader.ReadLineAsync()) != null )
        {
            word = word.ToLowerInvariant();
            if(!Regex.IsMatch(word,@"^[a-z]+$"))
            {
                continue;
            }
            rootNode.Add(word);
            wordCount++;
        }   
        Console.WriteLine("Loaded {0} words", wordCount);
    }
}

class Node
{
    static Dictionary<int, string> digitMap = new Dictionary<int, string>() {
        { 1, "" },
        { 2, "abcABC" },
        { 3, "defDEF" },
        { 4, "ghiGHI" },
        { 5, "jklJKL" },
        { 6, "mnoMNO" },
        { 7, "pqrsPQRS" },
        { 8, "tuvTUV" },
        { 9, "wxyzWXYZ" },
        { 0, "" }};
    static Dictionary<char,int> letterMap;
    static Node()
    {
        letterMap = digitMap
            .SelectMany(m => m.Value.Select(c=>new {ch = c, num = m.Key}))
            .ToDictionary(x => x.ch, x => x.num);
    }

    List<string> words = new List<string>();

    //the edges collection has exactly 10 
    //slots which represent the numbers [0-9]
    Node[] edges = new Node[10];

    public IEnumerable<string> Words{get{
        return words;
    }}

    public void Add(string word, int pos = 0)
    {
        if(pos == word.Length)
        {
            if(word.Length > 0)
            {
                words.Add(word);
            }
            return;
        }
        var currentChar = word[pos];
        int edgeIndex = letterMap[currentChar];
        if(edges[edgeIndex] == null)
        {
            edges[edgeIndex] = new Node();
        }
        var nextNode = edges[edgeIndex];
        nextNode.Add(word, pos+1);
    }

    public Node FindMostPopulatedNode()
    {
        Stack<Node> stk = new Stack<Node>();
        stk.Push(this);
        Node biggest = null;
        while(stk.Any())
        {
            var node = stk.Pop();
            biggest = biggest == null
               ? node
               : (node.words.Count > biggest.words.Count
                   ? node
                   : biggest);
            foreach(var next in node.edges.Where(e=>e != null))
            {
                stk.Push(next);
            }
        }
        return biggest;
    }

    public IEnumerable<string> Search(string numberSequenceString)
    {
        var numberSequence = numberSequenceString
                               .Select(n => int.Parse(n.ToString()));
        return Search(numberSequence);
    }
    private IEnumerable<string> Search(IEnumerable<int> numberSequence)
    {
        if(!numberSequence.Any())
        {
            return words;
        }
        var first = numberSequence.First();
        var remaining = numberSequence.Skip(1);
        var nextNode = edges[first];
        if(nextNode == null)
        {
            return Enumerable.Empty<string>();
        }
        return nextNode.Search(remaining);
    }
}