在C#内存中实现文本索引

Question

我有一个性能敏感的任务,我正在考虑存储内存中大约100,000个项目的所有对象.(持久于ms sql,但在内存中复制以提高复杂的搜索性能)

按键搜索工作得足够快,但按文本搜索,例如.包含相对较慢 - 每个查询大约需要30毫秒,如下所示:

IEnumerable<Product> result =
   products.Where(p =>
   p.Title.Contains(itemnames[rnd.Next(itemnames.Length)]));

我已经尝试使用内存数据库db4o,但性能更差 - 在100K项目中每次搜索大约1.5秒.

有什么选择,以便不审查每个对象标题并更快地执行此操作？

我可以用什么内存数据库来解决这个任务？

Answer 1

您可以选择更改存储产品的数据结构吗？加快 Contains 搜索速度的一种方法是将每个可能的Product.Title子字符串存储在Dictionary<string, List<Product>>. 这将使您的搜索时间复杂度为 O(1) 而不是 O(n)。

您可以像这样生成每个子字符串：

public static IEnumberable<string> AllSubstrings(this string value)
{
    int index = 0;
    while(++index <= value.Length)
    {
        yield return value.Substring(0, index);
    }

    index = 0;
    while(++index <= value.Length - 1)
    {
        yield return value.Substring(index);
    }
}

然后你可以像这样填充你的字典：

var titleIndex = new Dictionary<string, List<Product>>();

foreach(Product product in products)
{
    foreach(string substring in product.Title.AllSubstrings())
    {
        if(titleIndex.ContainsKey(substring))
        {
            index[substring].Add(product);
        }
        else
        {
            index[substring] = new List<Product> { product };
        }
    }
}

最后，您可以像这样执行搜索：

string searchString = itemnames[rnd.Next(itemnames.Length)];

if(titleIndex.ContainsKey(searchString))
{
    List<Product> searchResults = titleIndex[searchString];
}

注意： 正如您可能已经猜到的那样，这样存储数据需要预先花费更多的 CPU 时间并使用更多的 RAM。