Реализация текстового индекса в памяти C #

Question

У меня есть задача, чувствительная к производительности, и я рассматриваю возможность хранения всех объектов, которые составляют около 100 000 элементов в памяти.(сохраняется в ms sql, но копируется в память для улучшения производительности сложного поиска)

Поиск по ключу работает достаточно быстро, но поиск по тексту, например,.Contains относительно медленно - занимает около 30 мс на каждый запрос, например так:

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

Я уже пытался использовать базу данных памяти db4o, но ее производительность еще хуже - около 1,5 секунд на поиск по 100 тыс. Элементов.*

Какие есть варианты, чтобы не просматривать каждый заголовок объекта и выполнять это быстрее?

Какую базу данных памяти я могу использовать для решения этой задачи?

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

Примечание: Как вы уже догадались, для хранения таких данных требуется больше времени ЦП и больше оперативной памяти.

Answer 2

Я бы попробовал SQLite, поскольку он имеет встроенные полнотекстовые индексы ( FTS3 ).

Answer 3

Если вам действительно нужен поиск по содержащимся словам, а не по содержанию, то создайте индекс в памяти. Создайте словарь и добавьте запись для каждого слова в заголовке в словарь. Тогда вы можете сделать быстрый поиск по отдельным словам.

Другим вариантом будет загрузка данных в базу данных SQLite в памяти и использование встроенного механизма полнотекстового поиска для выполнения поиска.

Answer 4

Попробуйте вместо этого использовать полнотекстовый поиск Sql Server: http://msdn.microsoft.com/en-us/library/ms142571.aspx
Это может быть быстрее, чем последовательный поиск в вашем примере.