Раз нет ограничений по памяти и надо максимально быстро, то можно разложить весь массив в дерево таблиц переходов с шагом в один символ на таблицу. Самый быстрый и самый затратный по памяти. Таблица на каждый символ - 256 байт. Скорость поиска зависит только от размера строки и не зависит от объема данных: один символ - один переход в таблице к следующей таблице или конец поиска, если ноль. Я так уже делал: использовать имеет смысл на объемах примерно от 4 гигабайт данных (чем больше объем - тем меньше затраты на каждый символ). Но, если память позволяет и цель именно в скорости - то вполне нормальная плата памятью за скорость. Можно сократить расход памяти, если перекодировать строки в кодировку по числу используемых символов. Тогда таблица переходов будет в несколько раз меньше. Более экономный и более медленный вариант - дерево массивов/списков с шагом в 2/4/8 символов, при этом в поиске сравнение не по символам делать, а сразу по 2/4/8 байт: т.е., работаем со строкой как с массивом байтов и получаем оттуда uint16/uint32/uint64 и их и сравниваем, ибо процессору все равно какую инструкцию выполнять - один байт сравнить или 8. Возможно, конечно, оптимизатор в поиске по строке это все и оптимизирует. Я давно уже не смотрю на результаты его работы - так что тут только опытным путем. Ну и щас еще других вариантов накидают с деревьями тоже.
UPD1:
Можно все несколько упростить (или усложнить - смотря с какой стороны смотреть), если перекодировать строки из стандартной кодировки во что-то более компактное либо самостоятельно сделать кодировку под набор данных.
Еще можно ускорить, если искать в несколько потоков, разбив весь набор данных на несколько групп.
UPD2:
Таки нашел немного времени и откопал исходники для шарпа и провел несколько тестов по расходу памяти.
Число строк / общий размер данных / итоговый размер дерева
5 символов:
1000000 / 55.9MB / 13.2GB
2000000 / 111.6MB / 25.2GB
10 символов:
100000 / 8.1MB / 4.1GB
200000 / 16.1MB / 8GB
300000 / 24.2MB / 11.9GB
400000 / 32.2MB / 15.7GB
500000 / 40.3MB / 19.5GB
15 символов:
100000 / 10.5MB / 6.6GB
200000 / 21MB / 13.1GB
300000 / 31.5MB / 19.5GB
400000 / 42MB / 25.8GB
20 символов:
100000 / 13MB / 9.1GB
200000 / 25.9MB / 18.1GB
300000 / 38.9MB / 27GB
Максимальный размер дерева для глубины в 5 символов на платформе х64:
- Для диапазона 0-255 - до 8Тб и до 4 311 810 305 узлов
- Для диапазона 0-70 - до 13.5Гб и до 24 357 971 узлов
Максимальный размер дерева для глубины в 4 символа для диапазона 0-255: ~17Гб и ~33Гб для х86 и для х64 соответственно и лимит в 16 843 009 узлов. Ну и в коде есть функция для вычисления максимального числа узлов и размера дерева.
Как видно по результатам - чем выше объем и короче строки, т.е., плотность, тем выше эффективность размещения на единицу памяти. Скорость поиска в таком дереве зависит лишь от числа символов в слове/строке и всегда константа независимо от объема. ТС имеет смысл оптимизировать алгоритм под свои данные, если там обычный текст - то вероятно имеет смысл сделать индекс слов, подобрать компактную кодировку, а далее уже список строк с этим словом. Т.е., сначала идет поиск в дереве по слову, а далее уже по списку строк. И можно будет хоть в гигабайтах искать мгновенно, но памяти там надо будет уже терабайты.
И соответственно код:
https://github.com/VoidVolker/search-tree/tree/master (предупреждаю сразу: код старый, по сути экспериментальный, не вылизанный и вероятно приведет кого-то в ужас). Но, главное, что работает.
код
Тестовый код:
static Random rnd = new Random();
static string[] GenStrings(int cnt, int strLen)
{
string[] arr = new string[cnt];
var i = 0;
while (i < cnt)
{
var sb = new StringBuilder();
for (var j = 0; j < strLen; j++)
{
sb.Append(rnd.Next(0, 256));
//sb.Append(TAbc[rnd.Next(0, TAbc.Length)]);
}
arr[i++] = sb.ToString();
}
return arr;
}
var arraySize = 300000;
var stringSize = 20;
var GCStartArr = GC.GetTotalMemory(true);
var strings = GenStrings(arraySize, stringSize);
var GCEndArr = GC.GetTotalMemory(true);
var GCStart = GC.GetTotalMemory(true);
var tree = new ArrayTree<string>();
foreach (string s in strings)
{
tree.Add(Encoding.UTF8.GetBytes(s), s);
}
var GCEnd = GC.GetTotalMemory(true);
Console.WriteLine("Array x string size / Array memory used / Tree memory used");
Console.WriteLine($"{arraySize} х {stringSize} / {BytesToString(GCEndArr - GCStartArr)} / {BytesToString(GCEnd - GCStart)}");
