從.NET中的10000個項目中自動完成

我有一個內存約10K對象的集合。我想讓用戶能夠鍵入部分項目名稱或描述並顯示自動完成列表。什麼是有效的方法來做到這一點？我真的需要儘可能快的響應時間，用戶速度非常快。從.NET中的10000個項目中自動完成

非常感謝，瑪麗

2011-01-22 Mary Shields

UI是用什麼構建的？ Windows Forms，WPF，一個來自ASP.Net的Web應用程序？ – 2011-01-22 23:16:05

這是ASP MVC應用程序，網頁將通過控制器在按鍵JSONP上請求。 – 2011-01-23 00:27:48

這不是一個.net特定的答案，但通常解決此問題的方法是創建一個索引並預先計算自動完成列表，這些列表存儲在maps-of-maps-map- of-of-maps-of-lists結構（見下文）。它基本上是一個執行trie。

基本上，你有一個哈希映射（REAL散列映射，以O（1）的實現），其中鍵是可能的子串。對於每個鍵字符串「XYZ」，它指向包含所有包含「XYZ」的對象的數據的映射;使用鍵「XYZA」，「XYZB」等...然後，一旦您達到N個字符（N個地圖深），您的最後一個地圖值就是包含該N個字符串的所有實際對象的列表。

然後你回顧一下你的集合，並且爲每個對象計算長度爲M到N的所有可能的子字符串（我假設你只想在輸入> = M個字符時自動完成;太長的子字符串是無用的）地圖。

的數據結構如下：

TopMap => { 
      'A' => Map_for_A 
      'B' => Map_for_B 
       ... 
      } 

Map_For_A => { 
      'AA' => Map_for_AA 
      'AB' => Map_for_AB 
       ... 
      } 
Map_For_AB => { 
      'ABC' => Map_for_ABC 
      'ABD' => Map_for_ABD 
       ... 
      } 
Map_For_ABD => { 
      'ABDE' => List_For_ABDE 
      'ABDX' => List_For_ABDX 
      }

來源

2011-01-22 23:22:10 DVK

安排您的數據作爲Trie。

來源

2011-01-22 23:18:27

具體而言，如果需要全文搜索，則使用後綴樹：http://en.wikipedia.org/wiki/Suffix_tree – 2011-01-22 23:22:16

的最快方式是使用例如字面控制下降這些值在一個網頁的JavaScript變量（字符串數組）說，然後使用這樣的：

http://docs.jquery.com/Plugins/autocomplete#Example

來源

2011-01-22 23:19:31 Luis

10'000個對象確實不多。

以下就足夠了。

foreach(cItem Item in ItemList) 
{ 
    if(regex.match(Item.Name, "expression")) 
     //Add Item to autocomplete results; 


     //Break if more than 10 matches 

} 



for(i = 0; i < 10 && i < autocomplete_results.Length; ++i) 
{ 
      // display first 10 matches 
}

來源

2011-01-22 23:19:40

通常你不希望給用戶，例如每一種可能的選擇 - 如果項目的列表是一組名稱，輸入字母「E」，並在其中獲得每一個名字用E在下拉菜單中對於用戶而言既不高效也不快速執行。您是否考慮過僅在用戶輸入3個（或更多）字符時提示結果？

如果這組項目是靜態的，這將（可能）允許您預先計算每個獨特的3或4個字符集的項目集，並將它們存儲在列表字典中，如下所示：

Dictionary<String, List<Item>> itemsByKey;

來源

2011-01-22 23:19:43

您可以使用Trie數據結構（或前綴樹）來保存項目的名稱。請參閱維基百科上非常詳細的article，其中描述了此數據結構的原理並提供了一些基準測試結果。

Trie樹的每個節點可以被實現爲對應於各個數據串的第N位置時，其中N是節點的深度字符的排序列表。然後您可以使用binary search高效地執行數據查找。

，使其在工作你的情況，只是一味地對應於先前輸入前綴的最後一個節點。當用戶鍵入下一個字母時，只需搜索相應的直接子。各自的子樹內

一切都是可能的匹配，因此可以提供給用戶。爲了使自動填充更加智能化，您可以跟蹤各個數據項的頻率並僅顯示最常見的數據項。

來源

2011-01-22 23:21:08

你沒有說你正在使用的用戶界面。如果您使用ASP.NET Web表單，則可以使用AjaxControlToolkit中的「自動完成」控件。

在這裏你可以找到一個演示：http://www.asp.net/ajax/ajaxcontroltoolkit/Samples/AutoComplete/AutoComplete.aspx

來源

2011-01-22 23:22:30

從.NET中的10000個項目中自動完成

回答

相關問題