c# - ¿Cuál es un método de búsqueda/recuperación apropiado para una lista MUY larga de cadenas?

performance data-structures

Question

Esta no es una pregunta terriblemente infrecuente, pero todavía no pude encontrar una respuesta que realmente explicara la elección.

Tengo una lista muy grande de cadenas (representaciones ASCII de hashes SHA-256 , para ser exactos), y necesito consultar la presencia de una cadena dentro de esa lista.

Habrá más de 100 millones de entradas en esta lista, y tendré que consultar reiteradamente la presencia de una entrada muchas veces.

Dado el tamaño, dudo que pueda HashSet<string> todo en un HashSet<string> . ¿Cuál sería un sistema de recuperación apropiado para maximizar el rendimiento?

PUEDO ordenar previamente la lista, PUEDO ponerla en una tabla SQL, PUEDO ponerla en un archivo de texto, pero no estoy seguro de qué tiene más sentido dada mi aplicación.

¿Hay un ganador claro en términos de rendimiento entre estos u otros métodos de recuperación?

Answer 1

1. Guarde sus hashes como UInt32 [8]

2a. Usa la lista ordenada Para comparar dos hashes, primero compare sus primeros elementos; si son iguales, luego compara los segundos, etc.

2b. Utilice el árbol de prefijo

Answer 2

Con <gcAllowVeryLargeObjects> , puede tener matrices que son mucho más grandes. ¿Por qué no convertir esas representaciones ASCII de códigos hash de 256 bits en una estructura personalizada que implementa IComparable<T> ? Se vería así:

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

A continuación, puede crear una matriz de estos, que ocuparía aproximadamente 3,2 GB. Puedes buscarlo lo suficientemente fácil con Array.BinarySearch .

Por supuesto, necesitará convertir la entrada del usuario de ASCII a una de esas estructuras de código hash, pero eso es bastante fácil.

En cuanto al rendimiento, esto no será tan rápido como una tabla hash, pero ciertamente será más rápido que una búsqueda de base de datos u operaciones de archivos.

Ahora que lo pienso, podrías crear un HashSet<MyHashCode> . Tendría que anular el método Equals en MyHashCode , pero eso es realmente fácil. Según recuerdo, el HashSet cuesta algo así como 24 bytes por entrada, y usted tendría el costo adicional de la estructura más grande. Figura cinco o seis gigabytes, en total, si tuviera que usar un HashSet . Más memoria, pero todavía factible, y obtienes O (1) búsqueda.

Answer 3

Debe tener cuidado en este tipo de situación, ya que la mayoría de las colecciones en la mayoría de los idiomas no están realmente diseñadas ni optimizadas para ese tipo de escala. Como ya ha identificado, el uso de la memoria también será un problema.

El claro ganador aquí es usar alguna forma de base de datos. Ya sea una base de datos SQL o hay una cantidad de NoSQL que sería apropiado.

El servidor SQL ya está diseñado y optimizado para realizar un seguimiento de grandes cantidades de datos, indexarlo y buscar y consultar entre esos índices. Está diseñado para hacer exactamente lo que estás tratando de hacer, así que realmente sería la mejor manera de hacerlo.

Para el rendimiento, puede considerar el uso de una base de datos integrada que se ejecutará dentro de su proceso y guardará la sobrecarga de comunicaciones resultante. Para Java, podría recomendar una base de datos Derby para ese fin, no conozco los equivalentes de C # suficientes para hacer una recomendación allí, pero imagino que existen bases de datos adecuadas.

Answer 4

Desarrollé una solución similar al enfoque Insta''s , pero con algunas diferencias. En efecto, se parece mucho a su solución de matriz fragmentada. Sin embargo, en lugar de simplemente dividir los datos, mi enfoque construye un índice de fragmentos y dirige la búsqueda solo al fragmento apropiado.

La forma en que se genera el índice es muy similar a una tabla hash, con cada segmento siendo una matriz ordenada que se puede buscar con una búsqueda binaria. Sin embargo, pensé que no tiene mucho sentido calcular un hash de un hash SHA256, así que en su lugar simplemente tomo un prefijo del valor.

Lo interesante de esta técnica es que puedes sintonizarla extendiendo la longitud de las teclas de índice. Una clave más larga significa un índice más grande y cubos más pequeños. Mi caso de prueba de 8 bits es probablemente en el lado pequeño; 10-12 bits probablemente sería más efectivo.

Intenté comparar este enfoque, pero rápidamente se me agotó la memoria, así que no pude ver nada interesante en términos de rendimiento.

También escribí una implementación de C. La implementación de C tampoco fue capaz de manejar un conjunto de datos del tamaño especificado (la máquina de prueba solo tiene 4 GB de RAM), pero logró algo más. (El conjunto de datos de destino en realidad no era un problema en ese caso, fueron los datos de prueba los que llenaron la RAM.) No pude encontrar una buena manera de arrojar datos lo suficientemente rápido para realmente ver su rendimiento probado.

Aunque disfruté escribiendo esto, diría que, en general, proporciona evidencia a favor del argumento de que no deberías tratar de hacer esto en la memoria con 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();
}
}

Answer 5

En primer lugar, dices que las cadenas son realmente hashes SHA256. Observe que 100 million * 256 bits = 3.2 gigabytes , por lo que es posible ajustar toda la lista en la memoria, suponiendo que utilice una estructura de datos con memoria eficiente.

Si perdonas positivos falsos ocasionales, puedes usar menos memoria que eso. Ver los filtros de bloom http://billmill.org/bloomfilter-tutorial/

De lo contrario, utilice una estructura de datos ordenados para lograr consultas rápidas (complejidad de tiempo O (log n)).

Si realmente desea almacenar los datos en la memoria (porque está consultando con frecuencia y necesita resultados rápidos), intente Redis. http://redis.io/

Redis es una tienda de valor-clave avanzada con licencia BSD, de código abierto. A menudo se lo denomina servidor de estructura de datos ya que las claves pueden contener cadenas, hashes, listas, conjuntos y conjuntos ordenados.

Tiene un tipo de datos establecido http://redis.io/topics/data-types#sets

Los conjuntos Redis son una colección desordenada de cadenas. Es posible agregar, eliminar y probar la existencia de miembros en O (1) (tiempo constante independientemente de la cantidad de elementos contenidos en el Conjunto).

De lo contrario, use una base de datos que guarda los datos en el disco.

Answer 6

En primer lugar, realmente recomendaría que use la compresión de datos para minimizar el consumo de recursos. El ancho de banda de la caché y la memoria suele ser el recurso más limitado en una computadora moderna. No importa cómo implemente esto, el cuello de botella más grande estará esperando datos.

También recomendaría usar un motor de base de datos existente. Muchos de ellos tienen compresión incorporada y cualquier base de datos haría uso de la RAM que tienes disponible. Si tiene un sistema operativo decente, la memoria caché del sistema almacenará la mayor cantidad posible de archivos. Pero la mayoría de las bases de datos tienen su propio subsistema de almacenamiento en caché.

Realmente no puedo decir qué motor db será mejor para ti, tienes que probarlo. Personalmente, a menudo uso H2, que tiene un rendimiento decente y se puede utilizar como base de datos en memoria y basada en archivos, y tiene una compresión transparente.

Veo que algunos han afirmado que importar sus datos a una base de datos y crear el índice de búsqueda puede tomar más tiempo que una solución personalizada. Eso puede ser cierto, pero la importación suele ser algo bastante raro. Voy a suponer que está más interesado en búsquedas rápidas, ya que es probable que sean la operación más común.

También por qué las bases de datos SQL son confiables y bastante rápidas, es posible que desee considerar las bases de datos NoSQL. Pruebe algunas alternativas. La única forma de saber qué solución le dará el mejor rendimiento es haciendo una evaluación comparativa de ellos.

También debe considerar si tiene sentido almacenar su lista como texto. Quizás debas convertir la lista a valores numéricos. Eso usará menos espacio y por lo tanto le dará consultas más rápidas. La importación de la base de datos puede ser significativamente más lenta, pero las consultas pueden ser mucho más rápidas.

Answer 7

Estas respuestas no factorizan la memoria de cadena en la aplicación. Las cadenas no son 1 char == 1 byte en .NET. Cada objeto de cadena requiere una constante de 20 bytes para los datos del objeto. Y el buffer requiere 2 bytes por caracter. Por lo tanto, la estimación de uso de memoria para una instancia de cadena es de 20 + (2 * Longitud) bytes.

Hagamos algunas matemáticas.

• 100,000,000 cuerdas ÚNICAS
• SHA256 = 32 bytes (256 bits)
• tamaño de cada cadena = 20 + (2 * 32 bytes) = 84 bytes
• Memoria total requerida: 8,400,000,000 bytes = 8.01 gigabytes

Es posible hacerlo, pero esto no se almacenará bien en la memoria .NET. Su objetivo debe ser cargar todos estos datos en un formulario al que se pueda acceder / buscar sin tenerlo todo en la memoria a la vez. Para eso usaría Lucene.net que almacenará sus datos en el disco y lo buscará inteligentemente. Escriba cada cadena como buscable en un índice y luego busque en el índice la cadena. Ahora tiene una aplicación escalable que puede manejar este problema; su única limitación será el espacio en disco (y se necesitaría una gran cantidad de cadenas para llenar una unidad de terabyte). Alternativamente, ponga estos registros en una base de datos y busque en su contra. Es por eso que las bases de datos existen: para persistir cosas fuera de la RAM. :)

Answer 8

Para una velocidad máxima, mantenlos en RAM. Solo tiene unos 3 GB de datos, además de cualquier sobrecarga que necesite su estructura de datos. Un HashSet<byte[]> debería funcionar bien. Si desea reducir la sobrecarga y la presión del GC, encienda <gcAllowVeryLargeObjects> , utilice un solo byte[] y un HashSet<int> con un comparador personalizado para indexar en él.

Para velocidad y bajo uso de memoria, guárdelos en una tabla hash basada en disco. Para simplificar, guárdelos en una base de datos.

Hagas lo que hagas, debes almacenarlos como datos binarios simples, no como cadenas.

Answer 9

Puede tomar un tiempo (1) volcar todos los registros en una tabla (indexada en clúster) (preferiblemente use sus valores, no su representación de cadena (2)) y permita que SQL haga la búsqueda. Se encargará de la búsqueda binaria, manejará el almacenamiento en caché para usted y probablemente sea la forma más fácil de trabajar si necesita realizar cambios en la lista. Y estoy bastante seguro de que consultar las cosas será igual de rápido (o más rápido) que construir las tuyas propias.

(1): para cargar los datos, eche un vistazo al objeto SqlBulkCopy, cosas como ADO.NET o Entity Framework van a ser demasiado lentos a medida que cargan los datos fila por fila.

(2): SHA-256 = 256 bits, por lo que un binario (32) hará; que es solo la mitad de los 64 caracteres que estás usando ahora. (O una cuarta parte si usa números Unicode = P). De nuevo, si actualmente tiene la información en un archivo de texto sin formato, puede seguir el método char (64) y simplemente volcar los datos en la tabla usando bcp.exe. La base de datos será más grande, las consultas ligeramente más lentas (ya que se necesita más E / S + la memoria caché contiene solo la mitad de la información para la misma cantidad de RAM), etc. Pero es bastante sencillo de hacer, y si No estoy contento con el resultado, todavía puede escribir su propio cargador de base de datos.

Answer 10

Puedes probar un Suffix Tree , esta question cómo hacerlo en C #

O puede intentar una búsqueda como tal

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

AsParallel ayudará a acelerar las cosas ya que crea una paralelización de una consulta.

Answer 11

Si el conjunto es constante, solo haga una gran lista de hash ordenada (en formato raw, 32 bytes cada uno). Almacene todos los valores hash para que quepan en sectores de disco (4 KB) y que el comienzo de cada sector sea también el comienzo de un hash. Guarde el primer hash en cada enésimo sector en una lista de índice especial, que se ajustará fácilmente en la memoria. Utilice la búsqueda binaria en esta lista de índice para determinar el sector de inicio de un clúster de sector donde debería estar el hash, y luego use otra búsqueda binaria dentro de este grupo de sectores para encontrar su hash. El valor N debe determinarse en función de la medición con datos de prueba.

EDITAR: la alternativa sería implementar su propia tabla hash en el disco. La tabla debe usar una estrategia de direccionamiento abierto , y la secuencia de la sonda debe restringirse al mismo sector de disco tanto como sea posible. Las ranuras vacías deben marcarse con un valor especial (por ejemplo, ceros), por lo que este valor especial debe manejarse de manera especial cuando se solicite su existencia. Para evitar colisiones, la tabla no debe tener menos del 80% de valores, por lo que en su caso con 100 millones de entradas con un tamaño de 32 bytes, la tabla debe tener al menos 100M / 80% = 125 millones de ranuras, y debe tener el tamaño de 125M * 32 = 4 GB. Solo necesita crear la función hashing que convertiría 2 ^ 256 dominios a 125M, y alguna secuencia de prueba agradable.

Answer 12

Si la lista cambia con el tiempo, la colocaría en una base de datos.

Si la lista no cambia, la colocaría en un archivo ordenado y haré una búsqueda binaria para cada consulta.

En ambos casos, usaría un filtro Bloom para minimizar la E / S. Y dejaría de usar cadenas y usaría la representación binaria con cuatro ulongs (para evitar el costo de referencia del objeto).

Si tiene más de 16 GB (2 * 64 * 4/3 * 100M, asumiendo la codificación Base64 ) de sobra, una opción es hacer un Set & ltstring> y ser feliz. Por supuesto, cabría en menos de 7 GB si usa la representación binaria.

La respuesta de David Haney nos muestra que el costo de la memoria no se calcula tan fácilmente.

Answer 13

Si quiere realmente rápido, y los elementos son más o menos inmutables y requieren coincidencias exactas, puede construir algo que funcione como un escáner de virus: configure el alcance para recopilar la cantidad mínima de elementos potenciales utilizando los algoritmos que sean relevantes para sus entradas y criterios de búsqueda, luego itere a través de esos ítems, probando contra el ítem de búsqueda usando RtlCompareMemory. Puede extraer los ítems del disco si son bastante contiguos y comparar usando algo como esto:

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

Me gustaría modificar este ejemplo para tomar un gran búfer lleno de entradas y recorrerlas. Pero el código administrado puede no ser el camino a seguir. Lo más rápido es estar siempre más cerca de las llamadas que hacen el trabajo real, por lo que un controlador con acceso en modo núcleo incorporado en línea recta sería mucho más rápido.

Answer 14

Un hashset divide sus datos en cubos (matrices). En un sistema de 64 bits, el límite de tamaño para una matriz es de 2 GB , que es de aproximadamente 2,000,000,000 de bytes.

Dado que una cadena es un tipo de referencia, y dado que una referencia toma ocho bytes (suponiendo un sistema de 64 bits), cada segmento puede contener aproximadamente 250,000,000 (250 millones) de referencias a cadenas. Parece ser mucho más de lo que necesitas.

Habiendo dicho esto, como señaló Tim S., es muy poco probable que tengas la memoria necesaria para mantener las cuerdas por sí mismas, aunque las referencias encajarían en el hashset. Una base de datos me sería mucho mejor para esto.

Answer 15

Un simple árbol de búsqueda binario de vanilla dará un excelente rendimiento de búsqueda en listas grandes. Sin embargo, si realmente no necesita almacenar las cadenas y la membresía simple es lo que desea saber, un filtro Bloom puede ser una solución térmica. Los filtros Bloom son una estructura de datos compacta que entrena con todas las cadenas. Una vez entrenado, puede decirle rápidamente si ha visto una cuerda antes. Raramente informa. Positivos falsos, pero nunca informa falsos negativos. Dependiendo de la aplicación, pueden producir resultados sorprendentes rápidamente y con relativamente poca memoria.

Answer 16

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

Los resultados son bastante prometedores. Funcionan con un solo hilo. La versión hashset puede alcanzar un poco más de 1 millón de búsquedas por segundo con 7.9 GB de RAM de uso. La versión basada en arreglos usa menos RAM (4.6GB). Los tiempos de arranque entre los dos son casi idénticos (388 vs 391 segundos). El hashset intercambia RAM para el rendimiento de búsqueda. Ambos tuvieron que ser agrupados debido a restricciones de asignación de memoria.

Rendimiento de la matriz:

Hashing y adición tomaron 307408ms

La limpieza de Hash (clasificación, por lo general) tomó 81892ms

Se encontraron 30000000 elementos (esperados 30000000) en 562585ms [53k búsquedas por segundo]

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

Rendimiento de Hashset:

Hashing y adición tomaron 391105ms

La limpieza hash (clasificación, por lo general) tomó 0 ms

Se encontraron 30000000 elementos (se espera 30000000) en 74864ms [400k búsquedas por segundo]