Каков подходящий метод поиска/извлечения для очень длинного списка строк?

Если список меняется с течением времени, я бы поместил его в базу данных.

Если список не изменится, я бы поставил его в отсортированный файл и делать двоичный поиск для каждого запроса.

в обоих случаях я бы использовал Bloom filter чтобы минимизировать ввод-вывод, и я бы прекратил использовать строки и использовал двоичное представление с четырьмя ulongs (чтобы избежать ссылочной стоимости объекта).

если у вас больше 16 ГБ (2*64*4/3*100м, предполагая Base64 кодировка) пощадить, вариант, чтобы сделать набор&ltstring> и быть счастливым. Конечно, он поместится менее чем в 7 ГБ, если вы используете двоичное представление.

Дэвид Хейни показывает нам, что стоимость памяти не так легко вычислить.

С <gcAllowVeryLargeObjects>, вы можете иметь массивы, которые намного крупнее. Почему бы не преобразовать эти ASCII-представления 256-битных хэш-кодов в пользовательскую структуру, которая реализует IComparable<T>? Это будет выглядеть так:

struct MyHashCode: IComparable<MyHashCode>
{
    // make these readonly and provide a constructor
    ulong h1, h2, h3, h4;

    public int CompareTo(MyHashCode other)
    {
        var rslt = h1.CompareTo(other.h1);
        if (rslt != 0) return rslt;
        rslt = h2.CompareTo(other.h2);
        if (rslt != 0) return rslt;
        rslt = h3.CompareTo(other.h3);
        if (rslt != 0) return rslt;
        return h4.CompareTo(other.h4);
    }
}

затем вы можете создать массив из них, который будет занимать примерно 3,2 ГБ. Вы можете искать его достаточно легко с массив.BinarySearch.

конечно, вам нужно будет преобразовать ввод пользователя из ASCII в один из этих хэш-кодов структуры, но это достаточно легко.

Что касается производительности, это не будет так быстро, как хэш-таблица, но это, безусловно, будет быстрее, чем поиск базы данных или операции с файлами.

подумайте об этом, вы могли бы создать HashSet<MyHashCode>. Вам придется переопределить Equals метод on MyHashCode, но это действительно легко. Насколько я помню,HashSet стоит что-то вроде 24 байт на запись, и у вас будет добавленная стоимость более крупной структуры. Рисунок пять или шесть гигабайт, Итого, если бы вы использовали HashSet. Больше памяти, но все еще выполнимо, и вы получаете O(1) Поиск.

эти ответы не учитывают строковую память в приложении. строки не являются 1 char == 1 байт в. NET. Каждый строковый объект требует константы 20 байт для данных объекта. И буфер требует 2 байта на символ. Таким образом: оценка использования памяти для экземпляра строки составляет 20 + (2 * Длина) байт.

давайте посчитаем.

• 100,000,000 уникальных строк
• SHA256 = 32 байта (256 бит)
• размер каждой строки = 20 + (2 * 32 байта) = 84 байта
• общая требуемая память: 8,400,000,000 байт = 8,01 гигабайт

Это можно сделать, но это не будет хорошо храниться в памяти .NET. Ваша цель должна состоять в том, чтобы загрузить все эти данные в форму, к которой можно получить доступ/подкачать, не удерживая все это в памяти сразу. Для этого я бы использовал Lucene.net который будет хранить ваши данные на диске и разумно искать его. Напишите строку поиска в индекс и поиск по индексу строки. Теперь у вас есть масштабируемое приложение, которое может справиться с этой проблемой; вашим единственным ограничением будет дисковое пространство (и потребуется много строк, чтобы заполнить терабайтный диск). Кроме того, поместите эти записи в базу данных и запросите их. Вот почему существуют базы данных: для сохранения вещей за пределами ОЗУ. :)

для максимальной скорости, держите их в оперативной памяти. Это всего лишь ~3 ГБ данных, плюс любые накладные расходы, необходимые вашей структуре данных. А HashSet<byte[]> должно работать нормально. Если вы хотите снизить накладные расходы и давление GC, включите используйте один byte[] и HashSet<int> с пользовательским компаратором для индексирования в него.

для быстрого и низкого использования памяти, храните их в дисковой хэш-таблице. Для простоты сохраните их в базе данных.

все, что вы да, вы должны хранить их как простые двоичные данные, а не строки.

hashset разбивает ваши данные на сегменты (массивы). На 64-битной системе, ограничение размера массива составляет 2 ГБ, которая составляет примерно 2,000,000,000 байт.

поскольку строка является ссылочным типом и поскольку ссылка занимает восемь байт (предполагая 64-разрядную систему), каждый блок может содержать приблизительно 250 000 000 (250 миллионов) ссылок на строки. Кажется, это намного больше, чем вам нужно.

при этом, как отметил Тим С., Это маловероятно, что у вас будет необходимая память для хранения самих строк, даже если ссылки будут вписываться в хэш-набор. База данных мне гораздо лучше подходит для этого.

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

явный победитель здесь должен использовать некоторую форму базы данных. Либо база данных SQL, либо есть несколько NoSQL, которые были бы уместны.

SQL server уже разработан и оптимизирован для отслеживания больших объемов данных, индексирование его и поиск и запрос по этим индексам. Он предназначен для того, чтобы делать именно то, что вы пытаетесь сделать, так что действительно было бы лучшим способом пойти.

для повышения производительности вы можете использовать встроенную базу данных, которая будет работать в вашем процессе и сохранять результирующие затраты на связь. Для Java я мог бы рекомендовать базу данных Derby для этой цели, я не знаю эквивалентов C# достаточно, чтобы сделать рекомендацию там, но я думаю, что подходящие базы данных существовать.

может потребоваться некоторое время (1), чтобы сбросить все записи в (кластеризованной индексированной) таблице (предпочтительно использовать их значения, а не их строковое представление (2)) и позволить SQL выполнять поиск. Он будет обрабатывать двоичный поиск для вас, он будет обрабатывать кэширование для вас, и это, вероятно, самая простая вещь для работы, если вам нужно внести изменения в список. И я почти уверен, что запрос вещей будет так же быстро (или быстрее), чем создание собственного.

(1): для загрузки данных посмотрите на объект SqlBulkCopy, такие вещи, какADO.NET или Entity Framework будут слишком медленными, поскольку они загружают данные строка за строкой.

(2): SHA-256 = 256 бит, поэтому двоичный файл(32) будет делать; что составляет только половину из 64 символов, которые вы используете сейчас. (Или четверть его, если вы используете Unicode numbers =P) опять же, если у вас в настоящее время есть информация в обычном текстовом файле, вы все равно можете пойти по пути char (64) и просто сбросить данные в таблица с использованием bcp.исполняемый. База данных будет больше, запросы немного медленнее (так как требуется больше ввода-вывода + кэш содержит только половину информации для того же объема оперативной памяти) и т. д... Но это довольно просто сделать, и если вы не довольны результатом, вы все равно можете написать свой собственный загрузчик базы данных.

Если набор постоянен, то просто сделайте большой отсортированный хэш-список (в формате raw, 32 байта каждый). Храните все хэши так, чтобы они соответствовали секторам диска (4 КБ), и что начало каждого сектора также является началом хэша. Сохраните первый хэш в каждом N-м секторе в специальном индексном списке, который легко поместится в память. Используйте двоичный поиск в этом списке индексов, чтобы определить начальный сектор кластера секторов, где должен быть хэш, а затем используйте другой двоичный поиск в этом списке сектор кластера, чтобы найти свой хэш. Значение N должно определяться на основе измерений с использованием данных испытаний.

EDIT: альтернативой было бы реализовать свою собственную хэш-таблицу на диске. Таблица должна использовать открыть решении стратегия, и последовательность зонда должна быть ограничена к такому же участку диска как можно больше. Пустой слот должен быть отмечен специальным значением (например, все нули), поэтому это специальное значение должно быть специально обработано при запросе на существование. Избегать коллизии таблица должна быть не менее 80% заполнена значениями, поэтому в вашем случае со 100 миллионами записей размером 32 байта это означает, что таблица должна иметь не менее 100M/80%= 125 миллионов слотов и иметь размер 125M*32= 4 ГБ. Вам нужно только создать функцию хэширования, которая преобразует домен 2^256 в 125M и некоторую хорошую последовательность зондирования.

вы можете попробовать Суффиксное Дерево этот вопрос идет над тем, как это сделать в C#

или вы можете попробовать поиск, как так

var matches = list.AsParallel().Where(s => s.Contains(searchTerm)).ToList();

AsParallel поможет ускорить процесс, поскольку он создает распараллеливание запроса.

1. храните хэши как UInt32[8]

2а. Использовать отсортированный список. Чтобы сравнить два хэша, сначала сравните их первые элементы; если они равны, то сравните вторые и так далее.

2В. Использовать префикс дерево

прежде всего, я бы действительно рекомендовал вам использовать сжатие данных для минимизации потребления ресурсов. Пропускная способность кэша и памяти обычно является самым ограниченным ресурсом в современном компьютере. Независимо от того, как вы реализуете это самое большое узкое место будет ждать данных.

также я бы рекомендовал использовать существующий компонент database engine. Многие из них имеют встроенное сжатие, и любая база данных будет использовать доступную вам оперативную память. Если у вас есть приличная операционная система, системный кэш будет хранить столько файла, сколько он может. Но большинство баз данных имеют свою собственную подсистему кэширования.

Я не могу сказать, какой двигатель БД будет лучше для вас, вы должны попробовать их. Лично я часто использую H2, которые имеют приличную производительность и могут использоваться как в памяти, так и в файловой базе данных, а также имеют встроенное прозрачное сжатие.

Я вижу, что некоторые заявили, что импорт ваших данных в базу данных и создание индекса поиска может занять больше времени, чем некоторые пользовательские решения. Это может быть правдой, но импорт, как правило, то, что довольно редко. Я собираюсь предположить, что вы больше заинтересованы в быстрых поисках, поскольку они, вероятно, являются наиболее распространенной операцией.

кроме того, почему базы данных SQL являются надежными и довольно быстрыми, вы можете рассмотреть базы данных NoSQL. Попробуйте несколько альтернатив. Единственный способ узнать, какое решение даст вам лучшую производительность, - это сопоставить их.

также вы следует рассмотреть, если хранение списка в виде текста имеет смысл. Возможно, вам следует преобразовать список в числовые значения. Это будет использовать меньше места и, следовательно, дать вам более быстрые запросы. Импорт базы данных может быть значительно медленнее, но запросы могут стать значительно быстрее.

Если вы хотите действительно быстро, а элементы более или менее неизменны и требуют точных соответствий, вы можете построить что-то, что работает как антивирусный сканер: установите область для сбора минимального количества потенциальных элементов, используя любые алгоритмы, соответствующие вашим записям и критериям поиска, а затем повторите эти элементы, проверяя элемент поиска с помощью RtlCompareMemory.. Вы можете вытащить элементы с диска, если они довольно смежны и сравнить, используя что-то вроде это:

    private Boolean CompareRegions(IntPtr hFile, long nPosition, IntPtr pCompare, UInt32 pSize)
    {
        IntPtr pBuffer = IntPtr.Zero;
        UInt32 iRead = 0;

        try
        {
            pBuffer = VirtualAlloc(IntPtr.Zero, pSize, MEM_COMMIT, PAGE_READWRITE);

            SetFilePointerEx(hFile, nPosition, IntPtr.Zero, FILE_BEGIN);
            if (ReadFile(hFile, pBuffer, pSize, ref iRead, IntPtr.Zero) == 0)
                return false;

            if (RtlCompareMemory(pCompare, pBuffer, pSize) == pSize)
                return true; // equal

            return false;
        }
        finally
        {
            if (pBuffer != IntPtr.Zero)
                VirtualFree(pBuffer, pSize, MEM_RELEASE);
        }
    }

Я бы изменил этот пример, чтобы захватить большой буфер, полный записей,и перебрать их. Но управляемый код может быть не таким, как нужно.. Fastest всегда ближе к вызовам, которые выполняют фактическую работу, поэтому драйвер с доступом в режиме ядра, построенный на прямом C, будет намного быстрее..

во-первых, вы говорите, что строки действительно хэши SHA256. Обратите внимание, что 100 million * 256 bits = 3.2 gigabytes, поэтому можно поместить весь список в память, предполагая, что вы используете эффективную для памяти структуру данных.

Если вы прощаете случайные ложные срабатывания, вы можете использовать меньше памяти, чем это. См. bloom filters http://billmill.org/bloomfilter-tutorial/

в противном случае используйте отсортированную структуру данных для быстрого выполнения запросов (временная сложность O (log северный.))

---

Если вы действительно хотите сохранить данные в памяти (потому что вы часто запрашиваете и нуждаетесь в быстрых результатах), попробуйте Redis. http://redis.io/

Redis-это хранилище с открытым исходным кодом, лицензированное BSD, расширенное хранилище ключей. Его часто называют Data structure server так как ключи могут содержать строки, хэши, списки, наборы и сортированные наборы.

Он имеет заданный тип данных http://redis.io/topics/data-types#sets

наборы Redis представляют собой неупорядоченную коллекцию строк. Можно добавлять, удалять и проверять наличие элементов в O(1) (постоянное время независимо от количества элементов, содержащихся внутри набора).

---

в противном случае используйте базу данных, которая сохраняет данные на диске.

простое дерево бинарного поиска ванили даст отличную производительность поиска в больших списках. Однако, если вам действительно не нужно хранить строки, а простое членство-это то, что вы хотите знать, фильтр Bloom может быть прекрасным решением. Фильтры Bloom-это компактная структура данных, которую вы тренируете со всеми строками. По окончании обучения, он может быстро сказать вам, если он видел перед. Он редко сообщает.ложные срабатывания, но никогда не сообщает о ложных негативах. В зависимости от применения, они может производить удивительные результаты быстро и с относительно небольшой памятью.

Я разработал решение, похожее на Инста это подход, но с некоторыми отличиями. По сути, это очень похоже на его решение с кусками массива. Однако вместо простого разделения данных мой подход строит индекс фрагментов и направляет поиск только на соответствующий фрагмент.

Способ построения индекса очень похож на хэш-таблицу, причем каждое ведро является отсортированным массивом, который можно искать с помощью двоичного поиска. Тем не менее, я понял, что есть мало смысла в вычислении хэша хэша SHA256, поэтому вместо этого я просто беру префикс значения.

интересная вещь об этом методе заключается в том, что вы можете настроить его, удлинив длину ключей индекса. Более длинный ключ означает больший индекс и меньшие ведра. Мой тестовый случай из 8 бит, вероятно, на небольшой стороне; 10-12 бит, вероятно, будет более эффективным.

Я попытался проверить этот подход, но у него быстро закончилась память, поэтому я не смог увидеть ничего интересного с точки зрения производительности.

Я тоже писал на Си. Реализация C также не смогла справиться с набором данных указанного размера (тестовая машина имеет только 4 ГБ оперативной памяти), но ей удалось несколько больше. (Целевой набор данных на самом деле не был такой уж большой проблемой в этом случае, это были тестовые данные, которые заполнили ОЗУ.) Я не смог найти хороший способ бросить данные на него достаточно быстро, чтобы действительно увидеть его производительность проверенный.

хотя мне нравилось писать это, я бы сказал, что в целом это в основном свидетельствует в пользу аргумента, что вы не должны пытаться сделать это в памяти с помощью C#.

public interface IKeyed
{
    int ExtractKey();
}

struct Sha256_Long : IComparable<Sha256_Long>, IKeyed
{
    private UInt64 _piece1;
    private UInt64 _piece2;
    private UInt64 _piece3;
    private UInt64 _piece4;

    public Sha256_Long(string hex)
    {
        if (hex.Length != 64)
        {
            throw new ArgumentException("Hex string must contain exactly 64 digits.");
        }
        UInt64[] pieces = new UInt64[4];
        for (int i = 0; i < 4; i++)
        {
            pieces[i] = UInt64.Parse(hex.Substring(i * 8, 1), NumberStyles.HexNumber);
        }
        _piece1 = pieces[0];
        _piece2 = pieces[1];
        _piece3 = pieces[2];
        _piece4 = pieces[3];
    }

    public Sha256_Long(byte[] bytes)
    {
        if (bytes.Length != 32)
        {
            throw new ArgumentException("Sha256 values must be exactly 32 bytes.");
        }
        _piece1 = BitConverter.ToUInt64(bytes, 0);
        _piece2 = BitConverter.ToUInt64(bytes, 8);
        _piece3 = BitConverter.ToUInt64(bytes, 16);
        _piece4 = BitConverter.ToUInt64(bytes, 24);
    }

    public override string ToString()
    {
        return String.Format("{0:X}{0:X}{0:X}{0:X}", _piece1, _piece2, _piece3, _piece4);
    }

    public int CompareTo(Sha256_Long other)
    {
        if (this._piece1 < other._piece1) return -1;
        if (this._piece1 > other._piece1) return 1;
        if (this._piece2 < other._piece2) return -1;
        if (this._piece2 > other._piece2) return 1;
        if (this._piece3 < other._piece3) return -1;
        if (this._piece3 > other._piece3) return 1;
        if (this._piece4 < other._piece4) return -1;
        if (this._piece4 > other._piece4) return 1;
        return 0;
    }

    //-------------------------------------------------------------------
    // Implementation of key extraction

    public const int KeyBits = 8;
    private static UInt64 _keyMask;
    private static int _shiftBits;

    static Sha256_Long()
    {
        _keyMask = 0;
        for (int i = 0; i < KeyBits; i++)
        {
            _keyMask |= (UInt64)1 << i;
        }
        _shiftBits = 64 - KeyBits;
    }

    public int ExtractKey()
    {
        UInt64 keyRaw = _piece1 & _keyMask;
        return (int)(keyRaw >> _shiftBits);
    }
}

class IndexedSet<T> where T : IComparable<T>, IKeyed
{
    private T[][] _keyedSets;

    public IndexedSet(IEnumerable<T> source, int keyBits)
    {
        // Arrange elements into groups by key
        var keyedSetsInit = new Dictionary<int, List<T>>();
        foreach (T item in source)
        {
            int key = item.ExtractKey();
            List<T> vals;
            if (!keyedSetsInit.TryGetValue(key, out vals))
            {
                vals = new List<T>();
                keyedSetsInit.Add(key, vals);
            }
            vals.Add(item);
        }

        // Transform the above structure into a more efficient array-based structure
        int nKeys = 1 << keyBits;
        _keyedSets = new T[nKeys][];
        for (int key = 0; key < nKeys; key++)
        {
            List<T> vals;
            if (keyedSetsInit.TryGetValue(key, out vals))
            {
                _keyedSets[key] = vals.OrderBy(x => x).ToArray();
            }
        }
    }

    public bool Contains(T item)
    {
        int key = item.ExtractKey();
        if (_keyedSets[key] == null)
        {
            return false;
        }
        else
        {
            return Search(item, _keyedSets[key]);
        }
    }

    private bool Search(T item, T[] set)
    {
        int first = 0;
        int last = set.Length - 1;

        while (first <= last)
        {
            int midpoint = (first + last) / 2;
            int cmp = item.CompareTo(set[midpoint]);
            if (cmp == 0)
            {
                return true;
            }
            else if (cmp < 0)
            {
                last = midpoint - 1;
            }
            else
            {
                first = midpoint + 1;
            }
        }
        return false;
    }
}

class Program
{
    //private const int NTestItems = 100 * 1000 * 1000;
    private const int NTestItems = 1 * 1000 * 1000;

    private static Sha256_Long RandomHash(Random rand)
    {
        var bytes = new byte[32];
        rand.NextBytes(bytes);
        return new Sha256_Long(bytes);
    }

    static IEnumerable<Sha256_Long> GenerateRandomHashes(
        Random rand, int nToGenerate)
    {
        for (int i = 0; i < nToGenerate; i++)
        {
            yield return RandomHash(rand);
        }
    }

    static void Main(string[] args)
    {
        Console.WriteLine("Generating test set.");

        var rand = new Random();

        IndexedSet<Sha256_Long> set =
            new IndexedSet<Sha256_Long>(
                GenerateRandomHashes(rand, NTestItems),
                Sha256_Long.KeyBits);

        Console.WriteLine("Testing with random input.");

        int nFound = 0;
        int nItems = NTestItems;
        int waypointDistance = 100000;
        int waypoint = 0;
        for (int i = 0; i < nItems; i++)
        {
            if (++waypoint == waypointDistance)
            {
                Console.WriteLine("Test lookups complete: " + (i + 1));
                waypoint = 0;
            }
            var item = RandomHash(rand);
            nFound += set.Contains(item) ? 1 : 0;
        }

        Console.WriteLine("Testing complete.");
        Console.WriteLine(String.Format("Found: {0} / {0}", nFound, nItems));
        Console.ReadKey();
    }
}