Какой подходящий метод поиска/поиска для ОЧЕНЬ длинного списка строк?

Ответ 1

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Security.Cryptography;

namespace HashsetTest
{
    abstract class HashLookupBase
    {
        protected const int BucketCount = 16;

        private readonly HashAlgorithm _hasher;

        protected HashLookupBase()
        {
            _hasher = SHA256.Create();
        }

        public abstract void AddHash(byte[] data);
        public abstract bool Contains(byte[] data);

        private byte[] ComputeHash(byte[] data)
        {
            return _hasher.ComputeHash(data);
        }

        protected Data256Bit GetHashObject(byte[] data)
        {
            var hash = ComputeHash(data);
            return Data256Bit.FromBytes(hash);
        }

        public virtual void CompleteAdding() { }
    }

    class HashsetHashLookup : HashLookupBase
    {
        private readonly HashSet<Data256Bit>[] _hashSets;

        public HashsetHashLookup()
        {
            _hashSets = new HashSet<Data256Bit>[BucketCount];

            for(int i = 0; i < _hashSets.Length; i++)
                _hashSets[i] = new HashSet<Data256Bit>();
        }

        public override void AddHash(byte[] data)
        {
            var item = GetHashObject(data);
            var offset = item.GetHashCode() & 0xF;
            _hashSets[offset].Add(item);
        }

        public override bool Contains(byte[] data)
        {
            var target = GetHashObject(data);
            var offset = target.GetHashCode() & 0xF;
            return _hashSets[offset].Contains(target);
        }
    }

    class ArrayHashLookup : HashLookupBase
    {
        private Data256Bit[][] _objects;
        private int[] _offsets;
        private int _bucketCounter;

        public ArrayHashLookup(int size)
        {
            size /= BucketCount;
            _objects = new Data256Bit[BucketCount][];
            _offsets = new int[BucketCount];

            for(var i = 0; i < BucketCount; i++) _objects[i] = new Data256Bit[size + 1];

            _bucketCounter = 0;
        }

        public override void CompleteAdding()
        {
            for(int i = 0; i < BucketCount; i++) Array.Sort(_objects[i]);
        }

        public override void AddHash(byte[] data)
        {
            var hashObject = GetHashObject(data);
            _objects[_bucketCounter][_offsets[_bucketCounter]++] = hashObject;
            _bucketCounter++;
            _bucketCounter %= BucketCount;
        }

        public override bool Contains(byte[] data)
        {
            var hashObject = GetHashObject(data);
            return _objects.Any(o => Array.BinarySearch(o, hashObject) >= 0);
        }
    }

    struct Data256Bit : IEquatable<Data256Bit>, IComparable<Data256Bit>
    {
        public bool Equals(Data256Bit other)
        {
            return _u1 == other._u1 && _u2 == other._u2 && _u3 == other._u3 && _u4 == other._u4;
        }

        public int CompareTo(Data256Bit other)
        {
            var rslt = _u1.CompareTo(other._u1);    if (rslt != 0) return rslt;
            rslt = _u2.CompareTo(other._u2);        if (rslt != 0) return rslt;
            rslt = _u3.CompareTo(other._u3);        if (rslt != 0) return rslt;

            return _u4.CompareTo(other._u4);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj))
                return false;
            return obj is Data256Bit && Equals((Data256Bit) obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                var hashCode = _u1.GetHashCode();
                hashCode = (hashCode * 397) ^ _u2.GetHashCode();
                hashCode = (hashCode * 397) ^ _u3.GetHashCode();
                hashCode = (hashCode * 397) ^ _u4.GetHashCode();
                return hashCode;
            }
        }

        public static bool operator ==(Data256Bit left, Data256Bit right)
        {
            return left.Equals(right);
        }

        public static bool operator !=(Data256Bit left, Data256Bit right)
        {
            return !left.Equals(right);
        }

        private readonly long _u1;
        private readonly long _u2;
        private readonly long _u3;
        private readonly long _u4;

        private Data256Bit(long u1, long u2, long u3, long u4)
        {
            _u1 = u1;
            _u2 = u2;
            _u3 = u3;
            _u4 = u4;
        }

        public static Data256Bit FromBytes(byte[] data)
        {
            return new Data256Bit(
                BitConverter.ToInt64(data, 0),
                BitConverter.ToInt64(data, 8),
                BitConverter.ToInt64(data, 16),
                BitConverter.ToInt64(data, 24)
            );
        }
    }

    class Program
    {
        private const int TestSize = 150000000;

        static void Main(string[] args)
        {
            GC.Collect(3);
            GC.WaitForPendingFinalizers();

            {
                var arrayHashLookup = new ArrayHashLookup(TestSize);
                PerformBenchmark(arrayHashLookup, TestSize);
            }

            GC.Collect(3);
            GC.WaitForPendingFinalizers();

            {
                var hashsetHashLookup = new HashsetHashLookup();
                PerformBenchmark(hashsetHashLookup, TestSize);
            }

            Console.ReadLine();
        }

        private static void PerformBenchmark(HashLookupBase hashClass, int size)
        {
            var sw = Stopwatch.StartNew();

            for (int i = 0; i < size; i++)
                hashClass.AddHash(BitConverter.GetBytes(i * 2));

            Console.WriteLine("Hashing and addition took " + sw.ElapsedMilliseconds + "ms");

            sw.Restart();
            hashClass.CompleteAdding();
            Console.WriteLine("Hash cleanup (sorting, usually) took " + sw.ElapsedMilliseconds + "ms");

            sw.Restart();
            var found = 0;

            for (int i = 0; i < size * 2; i += 10)
            {
                found += hashClass.Contains(BitConverter.GetBytes(i)) ? 1 : 0;
            }

            Console.WriteLine("Found " + found + " elements (expected " + (size / 5) + ") in " + sw.ElapsedMilliseconds + "ms");
        }
    }
}

Результаты довольно многообещающие. Они работают однопоточно. Версия hashset может достигать немногим более 1 миллиона поисковых запросов в секунду при использовании 7,9 ГБ оперативной памяти. На основе массива используется меньше оперативной памяти (4,6 ГБ). Время запуска между ними почти одинаково (388 против 391 секунд). Hashset торгует оперативной памятью для производительности поиска. Оба должны были быть выпущены из-за ограничений распределения памяти.

Производительность массива:

Хеширование и добавление заняли 307408мс

Очистка хэшей (сортировка, обычно) занимает 81892мс

Найдено 30000000 элементов (ожидается 30000000) в 562585ms [53k запросов в секунду]

======================================

Производительность Hashset:

Хеширование и добавление заняли 391105мс

Очистка хэшей (сортировка, обычно) заняла 0мс

Найдено 30000000 элементов (ожидается 30000000) в 74864ms [400k запросов в секунду]

Ответ 2

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

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

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

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

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

Ответ 3

С <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 ГБ. Вы можете легко найти его с помощью Array.BinarySearch.

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

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

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

Ответ 4

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

Давайте сделаем некоторую математику.

• 100 000 000 UNIQUE строк
• SHA256 = 32 байта (256 бит)
• размер каждой строки = 20 + (2 * 32 байта) = 84 байта
• Общая требуемая память: 8 400 000 000 байтов = 8.01 гигабайт

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

Ответ 5

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

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

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

Ответ 6

Для максимальной скорости держите их в ОЗУ. Это всего лишь 3 ГБ данных, плюс любые накладные расходы, необходимые для вашей структуры данных. A HashSet<byte[]> должен работать нормально. Если вы хотите снизить накладные расходы и давление газа, включите <gcAllowVeryLargeObjects> , используйте один byte[] и a HashSet<int> с пользовательским компаратором для индексации в он.

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

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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

Ответ 10

Вы можете попробовать Суффикс-дерево, этот question переходит как это сделать в С#

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

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

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

Ответ 11

• Сохраните ваши хеши как UInt32 [8]

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

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

Ответ 12

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

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

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

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

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

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

Ответ 13

Если вы хотите очень быстро, а элементы более или менее неизменяемы и требуют точных совпадений, вы можете создать что-то, что работает как вирус-сканер: установите область сбора минимального количества потенциальных элементов, используя любые алгоритмы, имеющие отношение к ваши записи и критерии поиска, затем повторите эти пункты, протестируйте их с помощью элемента поиска, используя 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);
        }
    }

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

Ответ 14

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

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

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

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

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

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

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

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

Ответ 15

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

Ответ 16

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

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

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

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

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

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

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();
    }
}