¿Cómo puedo saber rápidamente si una lista contiene una lista?

Question

Hay varias preguntas relacionadas, pero yo estoy buscando una solución específica a mi caso. Hay una gran variedad de (generalmente) 14 números enteros, cada uno en el rango de 1 a 34. ¿Cómo puedo saber si cada uno de forma rápida en un int específica, lista estática aparece al menos una vez en esta serie?

A modo de referencia, actualmente estoy usando el código, que fue escrito para parecerse a la espec lo más cerca posible, lo que sin duda se puede mejorar enormemente:

if (array.Count < 13) {
    return;
}

var required = new int[] {
    0*9 + 1,
    0*9 + 9,
    1*9 + 1,
    1*9 + 9,
    2*9 + 1,
    2*9 + 9,                
    3*9 + 1,
    3*9 + 2,
    3*9 + 3,
    3*9 + 4,
    3*9 + 5,
    3*9 + 6,
    3*9 + 7,
};

IsThirteenOrphans = !required.Except (array).Any ();

La lista requerida no es dinámica, es decir, que siempre será el mismo durante el tiempo de ejecución. Mediante LINQ es opcional, el aspecto principal es el rendimiento.

Editar:

• La matriz de entrada no está ordenada.
• Los valores de entrada pueden aparecer varias veces.
• La matriz de entrada contendrá al menos 14 elementos, es decir, 1 más de la matriz requerido.
• Sólo hay 1 array requerido y es estático.
• Los valores en requerido son distintos.
• Usted puede asumir que un histograma es barato para crear.

Actualización:. También estoy interesado en una solución para una matriz de entrada ordenada

Answer 1

Idea 1
Si es necesario comparar con varias listas required entonces es posible ordenar la lista de entrada y luego simplemente compararlo por iteración. Sin embargo, la clasificación es, por supuesto, no demasiado rápido, pero tampoco demasiado lento. Pero si se compara con varias listas a que la sobrecarga de la clasificación podría ser amortizado rápidamente.

Una vez se ordena la matriz de comparación es trivial:

for(int i = 0; i < 14; i++)
  if(arr[i] != required[i]) return false;

return true;

Idea 2
O si los 14 números enteros son distintos / única que puede simplemente hacer required un HashSet y hacer

input.Count(i => required.Contains(i)) == 14

Pero no sé sin llegar a probar que si eso es más rápido que la clasificación.

Idea 3
Calcular un hash rápido, que es invariante ante permutaciones más de los 14 enteros y compararlo con el valor conocido de require. Sólo si los partidos de hash hacer la comparación más caro.

//Prepare/precalculated
int[] hashes = new int[34];
Random random = new Random();
for(int i = 0; i < 34; i++)
  hashes[i] = random.NextInt();

//On each list
int HashInts(int[] ints)
{
  int result = 0;
  foreach(int i in ints)
    result += hashes[i - 1];

  return result;
}

Una sabia elección de valores para hashes podría mejorar un poco, pero los valores aleatorios debe estar bien.

Idea 4
Crear un histograma:

int[] CreateHistogram(int[] ints)
{
  int[] counts = new int[34];
  foreach(int i in ints)
  {
    counts[i - 1]++;
  }

  return counts;
}

Se puede evitar la creación de la matriz mediante la reutilización de una matriz existente si el rendimiento es realmente importante.

Answer 2

Si usted tiene un bit de tipo integral 34+ disponibles, y el estilo C bit operaciones, entonces usted podría calcular un número entero tal V de la lista de variables (si la lista es v [0], v [1], ... entonces V es (1 << v [0]) | (1 << v [1]) ... donde 1 es del mismo tipo que V) y tienen una tal S número entero predefinido para la lista estática, calculada de forma análoga. La prueba para ver si la lista estática está contenida en la lista de variables es entonces (S & ~ V) == 0.

Answer 3

Una posibilidad es cambiar la forma en que se almacenan los datos. Puesto que el rango de valores posibles se limita a 1-34, en lugar de almacenar una lista de números, podría almacenar los cargos de cada número actual:

int[] counts = new int[34];

Si su lista tiene 1 uno y dos 3s, cuenta entonces [0] == 1 && conteos [2] = 2 (que podría utilizar alternativamente la indexación basada en 1 si eso hace las cosas más rápido (menos sustracciones.))

Ahora para evaluar que cada int en una lista aparece al menos una vez, simplemente índice en la matriz de forma secuencial para cada x y verificar que todos los cargos [x]> 0. Habrá sobrecarga asociada con la transformación de los datos de los recuentos forma a la forma de lista, pero eso es sólo un problema si también necesita con frecuencia para ver los datos en forma de lista. Otra ventaja de este formato de almacenamiento es que la adición / eliminación de los recuentos nunca involucrar a más de un único elemento de la matriz; en forma de lista, la eliminación de un elemento en el medio de la lista implica una copia de varios elementos.

Answer 4

Si desea manera rápida no se debe utilizar LINQ, si una lista de todos los elementos dados son abajo 35 puede quitar if (lst[i] < 35) La lista de la poligonal respuesta abajo a lo sumo una vez, y actúa como counting sort :

public bool FindExactMatch(int[] array, List<int> lst)
{
    bool[] a34 = new bool[35];

    foreach(var item in array)
    {
        a34[item] = true;
    }

    int exact = 0;

    for (int i = 0; i < lst.Count; i++)
    {
        if (a34[lst[i]])
        {
            exact++;
            if (exact == array.Length) return true;

            a34[lst[i]] = false;
        }
    }

    return false;
}

de lista ordenada si el tamaño de la lista es grande se puede hacer lst.BinarySearch(array[i]) que tiene 14 * log (n) * c1 como máximo, y yo creo que es lo suficientemente eficiente como también si la aplicación puede convertirse más rápido, y no lo hice la prueba búsqueda binaria con mi propia implementación, pero Min, Max, ordenar en LINQ es más lenta que (entre 4 y 10 veces) su (buena) la implementación. Y si el tamaño de lista ordenada es pequeño yo prefiero usar el algoritmo como el anterior porque c1 constante es pequeña en el algoritmo anterior y puede ser más grande en el algoritmo de búsqueda binaria.

Answer 5

Esto parece un buen candidato para operaciones bit a bit, ya que los valores de la requerida son distintos, estática, y entre 1 y 34. En lugar de guardar requerido como una matriz, guardarlo como un const ulong. En las matrices para comprobar, crear un nuevo ulong poblado por la izquierda turnos cada valor y el bit a bit o.

const ulong comparator = (1UL << 1) | (1UL << 9) | (1UL << 10) | (1UL << 18) | (1UL << 19) | (1UL << 27) | (1UL << 28) | (1UL << 29) | (1UL << 30) | (1UL << 31) | (1UL << 32) | (1UL << 33) | (1UL << 34);

public static bool ContainsDistinct13Values(int[] array)
{
    ulong word = 0;
    foreach (int i in array)
    {
        word |= (1UL << i);
    }
    return word == comparator;
}

Answer 6

Editar Así entendí su pregunta y probablemente tienen alguna solución agradable demasiado complicado. Otra pregunta es, ¿un buen rendimiento que tiene.

static void Main(string[] args)
{
    var required = new int[]
                       {
                           0*9 + 1,
                           0*9 + 9,
                           1*9 + 1,
                           1*9 + 9,
                           2*9 + 1,
                           2*9 + 9,
                           3*9 + 1,
                           3*9 + 2,
                           3*9 + 3,
                           3*9 + 4,
                           3*9 + 5,
                           3*9 + 6,
                           3*9 + 7,
                       };

    precomputed = required.Select((x, i) => new { Value = x, Offset = (UInt16)(1 << i) }).ToDictionary(x => x.Value, x => x.Offset);

    for (int i = 0; i < required.Length; i++)
    {
        precomputedResult |= (UInt16)(1 << i);
    }

    int[] array = new int[34]; // your array goes here..
    Console.WriteLine(ContainsList(array));

    Console.ReadKey();
}

// precompute dictionary
private static Dictionary<int, UInt16> precomputed;
// precomputed result
private static UInt16 precomputedResult = 0;

public static bool ContainsList(int[] values)
{
    UInt16 result = 0;
    for (int i = 0; i < values.Length; i++)
    {
        UInt16 v;
        if (precomputed.TryGetValue(values[i], out v))
            result |= v;
    }

    return result == precomputedResult;
}

Answer 7

Desde aquí se puede recorrer los elementos y averiguar ¿hay algún elemento faltante. Por su ejemplo, comprendo que sólo quería saber si hay algún elemento del requerido no se encuentra en la matriz. por lo que podría escribir

bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;
    }

    if (notContains == false) break;
}

Esto es mucho más rápido que su enfoque. Echa un vistazo al siguiente código con temporizador añadió. Su enfoque tomó 5 ms, pero la nueva toma 0 ms

System.Diagnostics.Stopwatch aTimer = new System.Diagnostics.Stopwatch();
aTimer.Start();

var IsThirteenOrphans = !required.Except(array).Any();
aTimer.Stop();

System.Diagnostics.Stopwatch bTimer = new System.Diagnostics.Stopwatch();
bTimer.Start();
bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;            
    }

    if (notContains == false) break;
}

bTimer.Stop();