Hashing, ordenamiento y PriorityQueue en C#

Esta parte trata sobre los contenedores, y sobre las partes de la biblioteca estándar de C# que los artículos de concursos suelen equivocar porque son anteriores a ellas.

Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la ejecución.

Patrón 26 — Contar cosas

Cuatro maneras, en orden creciente de lo que cuestan.

using System.Runtime.InteropServices;

int[] a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];

// The version everyone writes. Two hash lookups per item.
Dictionary<int, int> plain = [];
foreach (int x in a) plain[x] = plain.GetValueOrDefault(x) + 1;

// One lookup. The ref points into the dictionary's own storage.
Dictionary<int, int> fast = [];
foreach (int x in a)
{
    ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(fast, x, out _);
    slot++;
}

// .NET 9 and later. Shortest to write, allocates an enumerable.
var counted = a.CountBy(x => x).OrderBy(kv => kv.Key);

Console.WriteLine($"plain   : {string.Join(" ", plain.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"ref     : {string.Join(" ", fast.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"CountBy : {string.Join(" ", counted.Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"all agree: {plain.OrderBy(k => k.Key).SequenceEqual(fast.OrderBy(k => k.Key))}");

// When the keys are small and dense, skip hashing altogether.
int[] tally = new int[10];
foreach (int x in a) tally[x]++;
Console.WriteLine($"array   : [{string.Join(", ", tally)}]   <- no hashing at all");

Imprime:

plain   : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
ref     : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
CountBy : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
all agree: True
array   : [0, 2, 1, 2, 1, 3, 1, 0, 0, 1]   <- no hashing at all

dict[x] = dict.GetValueOrDefault(x) + 1 hashea la clave dos veces — una para leer, otra para escribir. CollectionsMarshal.GetValueRefOrAddDefault te devuelve un ref directo al almacenamiento del diccionario, así que el incremento ocurre en el lugar después de una sola búsqueda. En un bucle apretado sobre un millón de elementos esa es una diferencia real, y son tres líneas.

CountBy llegó en .NET 9. Es lo más corto de escribir y asigna un enumerable, que es la compensación correcta fuera de un bucle caliente.

Y cuando las claves son enteros pequeños no negativos, un simple int[] les gana a todos. Sin hashing, sin colisiones, memoria contigua. Si el problema dice que los valores están entre 1 y 10⁶, ese arreglo pesa 4MB y casi seguro es la respuesta correcta.

Úsalo cuando — siempre, pero elige el correcto. Claves pequeñas y densas significan un arreglo. Un bucle caliente significa el ref. En cualquier otro caso, escribe el legible.

Patrón 27 — Agrupar por una firma

Agrupa palabras que son anagramas entre sí.

Todo el patrón consiste en elegir una firma: algo idéntico para todo lo que está dentro de un grupo y distinto para todo lo que está fuera de él.

string[] words = ["eat", "tea", "tan", "ate", "nat", "bat"];

// The signature has to be identical for anagrams and different for anything
// else. Sorted letters is the obvious one.
static string SortedKey(string w)
{
    char[] c = w.ToCharArray();
    Array.Sort(c);
    return new string(c);
}

// For a fixed alphabet, a count vector is O(n) instead of O(n log n).
static string CountKey(string w)
{
    int[] n = new int[26];
    foreach (char c in w) n[c - 'a']++;
    return string.Join(",", n);
}

foreach (var g in words.GroupBy(SortedKey))
    Console.WriteLine($"key \"{g.Key}\"  ->  [{string.Join(", ", g)}]");

Console.WriteLine();
Console.WriteLine($"both keys agree on the grouping: " +
    $"{words.GroupBy(SortedKey).Count() == words.GroupBy(CountKey).Count()}");
Console.WriteLine($"SortedKey(\"eat\") = \"{SortedKey("eat")}\"");
Console.WriteLine($"CountKey(\"eat\")  = \"{CountKey("eat")}\"");

Imprime:

key "aet"  ->  [eat, tea, ate]
key "ant"  ->  [tan, nat]
key "abt"  ->  [bat]

both keys agree on the grouping: True
SortedKey("eat") = "aet"
CountKey("eat")  = "1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0"

Las letras ordenadas son la firma obvia y cuestan O(m log m) por palabra. Para un alfabeto fijo, un conteo de cada letra es O(m) y funciona igual de bien — la salida confirma que ambas producen la misma agrupación.

Los casos interesantes son aquellos donde la firma obvia está sutilmente mal. Para «¿estos dos árboles tienen la misma forma?», la firma también tiene que codificar los nulls, o dos árboles distintos chocan. Lograr que la firma sea exactamente tan fuerte como la equivalencia que quieres es todo el trabajo.

Úsalo cuando el problema dice agrupar, encontrar duplicados o cuántos distintos.

Patrón 28 — Comparadores, y el ordenamiento que reordena elementos iguales

Ordena por puntaje descendente, luego por nombre ascendente.

(string Name, int Score)[] people =
[
    ("ada", 90), ("grace", 85), ("alan", 90), ("edsger", 85), ("barbara", 90)
];

// Score descending, then name ascending. One comparer, two keys.
var byScoreThenName = Comparer<(string Name, int Score)>.Create((x, y) =>
{
    int c = y.Score.CompareTo(x.Score);       // reversed operands = descending
    return c != 0 ? c : string.CompareOrdinal(x.Name, y.Name);
});

var arr = people.ToArray();
Array.Sort(arr, byScoreThenName);
foreach (var p in arr) Console.WriteLine($"  {p.Name,-8} {p.Score}");

// Array.Sort is NOT stable, and here is exactly where that starts to show.
Console.WriteLine($"\n{"n",4}  {"Array.Sort keeps input order?",32}");
foreach (int n in new[] { 8, 16, 17, 32 })
{
    var items = Enumerable.Range(0, n).Select(i => (Id: i, Key: i % 2)).ToArray();

    var viaSort = items.ToArray();
    Array.Sort(viaSort, (x, y) => x.Key.CompareTo(y.Key));

    var viaOrderBy = items.OrderBy(p => p.Key).ToArray();

    Console.WriteLine($"{n,4}  {viaSort.SequenceEqual(viaOrderBy),32}");
}

Console.WriteLine("\n.NET's introsort drops to insertion sort for 16 elements or fewer,");
Console.WriteLine("and insertion sort happens to be stable. At 17 it partitions, and does not.");

Imprime:

  ada      90
  alan     90
  barbara  90
  edsger   85
  grace    85

   n     Array.Sort keeps input order?
   8                              True
  16                              True
  17                             False
  32                             False

.NET's introsort drops to insertion sort for 16 elements or fewer,
and insertion sort happens to be stable. At 17 it partitions, and does not.

El comparador de varias claves es rutinario: compara por la primera clave, y solo pasa a la segunda cuando la primera empata. Descendente significa invertir los operandos — y.CompareTo(x) — no negar el resultado, que se rompe con int.MinValue.

La segunda mitad es la parte que atrapa a la gente.

Array.Sort no es estable. OrderBy sí. Y mira dónde empieza a importar: n = 16 coincide, n = 17 no. El introsort de .NET baja a insertion sort para particiones de 16 elementos o menos, y insertion sort resulta preservar el orden. Por encima de eso particiona, y los elementos iguales se mueven.

Un bug de estabilidad pasa limpio con dieciséis elementos y falla con diecisiete. Ese no es un tamaño que alguien elija para un caso de prueba.

Si el orden entre elementos iguales importa, usa OrderBy/ThenBy, o agrega un desempate al comparador para que nunca haya dos elementos que comparen iguales. Lo segundo es lo que hace el código de concursos, porque Array.Sort sobre un arreglo crudo es más rápido y no asigna nada.

Úsalo cuando ordenes por algo distinto al orden natural. Y siempre que los elementos iguales tengan que conservar su orden de entrada.

Patrón 29 — Compresión de coordenadas

Valores de hasta un millón, pero solo un puñado de distintos. Quieres un arreglo indexado por valor, y necesitaría un millón de celdas.

Los valores solo se usan para compararse. Así que tíralos y quédate con sus rangos.

int[] a = [1_000_000, 5, 300, 5, 99_999, 300];

// The values matter only by their ORDER, so replace each with its rank.
int[] sorted = a.Distinct().Order().ToArray();
Dictionary<int, int> rank = sorted
    .Select((v, i) => (v, i))
    .ToDictionary(t => t.v, t => t.i);

int[] compressed = a.Select(v => rank[v]).ToArray();

Console.WriteLine($"original   : [{string.Join(", ", a)}]");
Console.WriteLine($"distinct   : [{string.Join(", ", sorted)}]");
Console.WriteLine($"compressed : [{string.Join(", ", compressed)}]");
Console.WriteLine();
Console.WriteLine($"an array indexed by value would need {a.Max() + 1:N0} cells");
Console.WriteLine($"an array indexed by rank needs      {sorted.Length:N0}");
Console.WriteLine();

// Order is preserved, which is the only property that had to survive.
for (int i = 0; i < a.Length; i++)
    for (int j = 0; j < a.Length; j++)
        if (a[i].CompareTo(a[j]) != compressed[i].CompareTo(compressed[j]))
            throw new Exception("order not preserved");
Console.WriteLine("every pairwise comparison gives the same answer as before: True");

// And it is reversible.
Console.WriteLine($"decompressed: [{string.Join(", ", compressed.Select(r => sorted[r]))}]");

Imprime:

original   : [1000000, 5, 300, 5, 99999, 300]
distinct   : [5, 300, 99999, 1000000]
compressed : [3, 0, 1, 0, 2, 1]

an array indexed by value would need 1,000,001 cells
an array indexed by rank needs      4

every pairwise comparison gives the same answer as before: True
decompressed: [1000000, 5, 300, 5, 99999, 300]

La verificación del medio es toda la justificación: cada comparación por pares da la misma respuesta después de comprimir que antes. Nada de lo que el algoritmo dependía se perdió. Y la última línea muestra que es reversible — guarda el arreglo ordenado de valores distintos y puedes mapear cualquier rango de vuelta.

Costo: O(n log n) por el ordenamiento, O(n) después.

Úsalo cuando los valores son enormes o dispersos pero la cantidad de ellos es pequeña — árboles de segmentos sobre coordenadas, líneas de barrido, «contar distintos en un rango», cualquier cosa con marcas de tiempo.

Patrón 30 — PriorityQueue<TElement, TPriority>

Esto llegó en .NET 6. Mucho material de programación competitiva en C# es más viejo, y sortea su ausencia con un SortedSet y una clave de desempate. Eso ya no es necesario.

Vale la pena saber dos cosas antes de usarlo.

Es un min-heap: la prioridad más baja sale primero. Y el elemento está separado de la prioridad, que es lo que hace legible a Dijkstra en la parte 8 — encolas un nodo con una distancia, en vez de empacar ambos en una tupla y escribir un comparador.

Para quedarte con los k valores más grandes, usa un min-heap de tamaño k. Suena al revés y no lo es: la raíz es el más débil de tus sobrevivientes actuales, que es exactamente el valor que un recién llegado tiene que superar, y el único contra el que vale la pena comparar.

int[] a = [5, 1, 9, 3, 7, 2, 8];
int k = 3;

// PriorityQueue is a MIN-heap: the smallest priority comes out first.
// To keep the k LARGEST, hold a min-heap of size k and evict its smallest.
PriorityQueue<int, int> topK = new();

foreach (int x in a)
{
    if (topK.Count < k)
    {
        topK.Enqueue(x, x);
        Console.WriteLine($"{x}  heap not full, keep it        -> [{string.Join(",", topK.UnorderedItems.Select(t => t.Element).Order())}]");
    }
    else if (x > topK.Peek())
    {
        // One operation instead of Dequeue then Enqueue: one sift, not two.
        int evicted = topK.EnqueueDequeue(x, x);
        Console.WriteLine($"{x}  beats the smallest ({evicted}), swap  -> [{string.Join(",", topK.UnorderedItems.Select(t => t.Element).Order())}]");
    }
    else
    {
        Console.WriteLine($"{x}  loses to the smallest ({topK.Peek()})   -> unchanged");
    }
}

List<int> result = [];
while (topK.Count > 0) result.Add(topK.Dequeue());
Console.WriteLine($"\ntop {k} largest, ascending: [{string.Join(", ", result)}]");

// Priority and element are separate, which is what makes Dijkstra readable.
PriorityQueue<string, int> tasks = new();
tasks.Enqueue("write tests", 2);
tasks.Enqueue("fix the bug", 1);
tasks.Enqueue("refactor", 3);
Console.WriteLine();
while (tasks.TryDequeue(out string? task, out int p))
    Console.WriteLine($"  priority {p}: {task}");

Imprime:

5  heap not full, keep it        -> [5]
1  heap not full, keep it        -> [1,5]
9  heap not full, keep it        -> [1,5,9]
3  beats the smallest (1), swap  -> [3,5,9]
7  beats the smallest (3), swap  -> [5,7,9]
2  loses to the smallest (5)   -> unchanged
8  beats the smallest (5), swap  -> [7,8,9]

top 3 largest, ascending: [7, 8, 9]

  priority 1: fix the bug
  priority 2: write tests
  priority 3: refactor

EnqueueDequeue es el detalle que vale la pena robar. Empujar y luego sacar tamiza el heap dos veces; EnqueueDequeue lo hace en una sola, porque sabe que el nuevo elemento va a compararse con la raíz de todos modos.

Dos cosas que no tiene. No hay DecreaseKey, y por eso Dijkstra en C# usa el enfoque perezoso — empuja duplicados, salta los obsoletos a la salida. Y UnorderedItems es exactamente lo que dice: orden de heap, no orden ordenado. Sirve para inspeccionar, no sirve para la salida.

Costo: O(log n) por cada push y pop, O(n) de espacio. Top-k sobre n elementos es O(n log k).

Úsalo cuando necesites repetidamente «el menor que queda» — Dijkstra, fusión de k vías, planificación de tareas, top-k.

Qué recordar

• GetValueOrDefault y luego asignar hashea la clave dos veces. CollectionsMarshal.GetValueRefOrAddDefault lo hace una sola vez y te devuelve un ref.

• Las claves enteras pequeñas y densas no necesitan un diccionario. Un int[] es más rápido, más simple, y normalmente la solución prevista.

• Una agrupación vale lo que vale su firma. Tiene que ser idéntica dentro de un grupo y distinta fuera de él — ni más débil, ni más fuerte.

• Descendente significa invertir los operandos, no negar el resultado. La negación se rompe con int.MinValue.

• Array.Sort es inestable por encima de 16 elementos. Exactamente 16 es estable por accidente. Usa OrderBy, o haz imposibles los empates con una clave de desempate.

• La compresión conserva el orden y descarta la magnitud, que es todo lo que estos problemas usaban. Guarda el arreglo ordenado de valores distintos y es reversible.

• PriorityQueue es un min-heap, y para los k más grandes eso es justo lo que quieres. Usa EnqueueDequeue para tamizar una vez en lugar de dos, y recuerda que no hay DecreaseKey.

La parte 7 comienza con grafos, y abre con la representación — porque List<List<int>> es lo que usan la mayoría de las soluciones de concursos en C#, y también es la razón por la que se pasan del límite de tiempo.