¿Manera eficiente de obtener el primer elemento que falta en la secuencia ordenada?

Question

Tengo una secuencia ordenada como {1, 3, 5, 6, 8, 9} Quiero obtener el primer elemento que falta (2 en el ejemplo) o max() si la secuencia no contiene elementos faltantes. Ahora lo estoy haciendo de esta manera:

public static int GetRegisterNumber<T>(this IQueryable<T> enumerable, Func<T, bool> whereFunc, Func<T, int?> selectFunc) 
{ 
    var regNums = enumerable.OrderBy(selectFunc).Where(whereFunc).ToArray(); 

    if (regNums.Count() == 0) 
    { 
     return 1; 
    } 

    for (int i = 0; i < regNums.Count(); i++) 
    { 
     if (i + 1 != regNums[i]) 
     { 
      return regNums[i].Value + 1; 
     } 
    } 

    return regNums.Last().Value + 1; 
} 

pero creo que hay métodos mucho más rápidos. ¿Alguna sugerencia?

Answer 1

Editar: Acabo de notar que enumerable es IQueryable<T> pero selectFunc y whereFunc son de tipo Func<T, _>. Esto hará que se llamen a las versiones Enumerable de OrderBy y Where, en lugar de usar llamadas a la base de datos. Probablemente desee cambiarlos a Expression<Func<T, _>> en su lugar.

Si no quiere pedir regNums en primer lugar, he aquí una solución de O (n) al estilo de golf:

var max = regNums.Max(i => (int?)i) ?? 0; 
return Enumerable.Range(1, max + 1) 
       .Except(regNums) 
       .Min(); 

Por línea:

1. Echando a int?, Max se devuelva null si regNums está vacío, unido a 0.

2. Cree una secuencia de todos los registros posibles, incluido nuestro próximo valor si está lleno.

3. Resta el conjunto actual de registros.

4. Elija la más baja.

Answer 2

Sugerencia: ejecute su código a través de un generador de perfiles. Entonces sabrás dónde está lento. Intuitivamente, Orderby es lo más lento en este programa. Pero las intuiciones sobre lo más lento a menudo son muy, muy incorrectas. Use un perfilador.

Por supuesto, también debe eliminar las enormes ineficiencias en este programa. Recuerde, Count() cuenta la secuencia volviendo a enumerarla. ¡Count() no sabe que no ha cambiado la secuencia desde la última vez que la contó! Probablemente desee almacenar el conteo en lugar de volver a calcularlo cada vez, o use Length, ya que tiene un array.

Answer 3

Probablemente veré algo como a continuación; la Where se puede hacer fuera (al igual que el selector para ser honesto):

Si tiene previsto comenzar en 1:

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable, 
    Func<T, int> selectFunc) 
{ 
    int expected = 1; 
    foreach (T item in enumerable) { 
     if (selectFunc(item) != expected) return expected; 
     expected++; 
    } 
    return expected; 
} 

Para empezar con el primer elemento de la lista:

public static int GetRegisterNumber<T>(this IEnumerable<T> enumerable, 
    Func<T, int> selectFunc) 
{ 
    bool first = true; 
    int prev = -1; 
    foreach (T item in enumerable) 
    { 
     int val = selectFunc(item); 
     if(first) { 
      prev = val; 
      first = false; 
     } else if (val != prev + 1) { 
      return prev + 1; 
     } 
     prev = val; 
    } 
    return first ? 1 : prev + 1; 
} 

No está claro cómo quería manejar nulos, por lo que no lo hice. Tenga en cuenta que esto solo itera una vez, y no almacena todo.

Answer 4

Como se mencionó, primero use un generador de perfiles para ver dónde está lento. Si la secuencia es muy grande y el orden es lento, puede usar radix sort, que es O (kn), donde k es el número máximo de dígitos yn es el número de elementos en la secuencia. Los algoritmos de clasificación basados ​​en la comparación suelen ser O (n logn).

De esta manera, el algoritmo completo será O (kn), que según n, es asintóticamente más rápido y, en consecuencia, más escalable.

Answer 5

Suponiendo que la secuencia de entrada de los valores ya está ordenado, ¿qué tal:

var upperBoundValue = values.Last() + 1; 
var firstMissingItem = Enumerable.Range(1, upperBoundValue).Except(values).First(); 

Si va a realizar esta operación de forma iterativa, se puede optimizar el proceso mediante el almacenamiento de un índice para el último lugar que usted estaba en la secuencia donde encontraste un espacio, y comienzas la siguiente iteración desde allí.

Answer 6

¿Por qué no hacer algo así como una búsqueda binaria?

Supongamos que tiene una lista de 10 elementos. Lee el primer elemento. Luego lee el quinto elemento. Si el quinto elemento no es el primer elemento + 4, entonces sabrá que falta un número; de lo contrario, sabrá que no existe. Luego solo itere así hasta que encuentre el primer elemento faltante o llegue al final de la lista.

Esto, por supuesto, supone que conoce el tamaño (que no se mencionó explícitamente en la pregunta), pero que ha convertido a una matriz, por lo que debe saber.

O (log N) en lugar de O (n)

Answer 7

Suponiendo que su OrderBy y Where ya se han aplicado:

int firstMissing = collection.TakeWhile((x, i) => x == ++i).LastOrDefault() + 1; 

Answer 8

se pone una etiqueta LinqToSql en su pregunta. Supongo que está buscando una identificación de "primera disponible", para que pueda crear un nuevo registro con esta identificación. Considere la posibilidad de activar IDENTIDAD en la base de datos.