Optimización de algoritmo de búsqueda lineal

Question

Acabo de terminar un problema de tarea para Informática 1 (sí, es tarea, pero ¡escúchame!). Ahora, la tarea está 100% completa y funcionando, por lo que no necesito ayuda. Mi pregunta involucra la eficiencia de un algoritmo que estoy usando (no estamos calificados en la eficiencia algorítmica aún, solo tengo mucha curiosidad).

La función que voy a presentar actualmente utiliza una versión modificada del algoritmo de búsqueda lineal (que yo mismo ideé) para verificar cuántos números en un boleto de lotería determinado coinciden con los números ganadores , suponiendo que tanto los números en el boleto como los números extraídos están en orden ascendente. Me preguntaba, ¿hay alguna manera de hacer que este algoritmo sea más eficiente?

/* 
* Function: ticketCheck 
* 
* @param struct ticket 
* @param array winningNums[6] 
* 
* Takes in a ticket, counts how many numbers 
* in the ticket match, and returns the number 
* of matches. 
* 
* Uses a modified linear search algorithm, 
* in which the index of the successor to the 
* last matched number is used as the index of 
* the first number tested for the next ticket value. 
* 
* @return int numMatches 
*/ 
int ticketCheck(struct ticket ticket, int winningNums[6]) 
{ 
    int numMatches = 0; 
    int offset = 0; 
    int i; 
    int j; 

    for(i = 0; i < 6; i++) 
    { 
     for(j = 0 + offset; j < 6; j++) 
     { 
      if(ticket.ticketNum[i] == winningNums[j]) 
      { 
       numMatches++; 
       offset = j + 1; 
       break; 
      } 
      if(ticket.ticketNum[i] < winningNums[j]) 
      { 
       i++; 
       j--; 
       continue; 
      } 
     } 
    } 

    return numMatches; 
} 

Answer 1

Está más o menos allí, pero no del todo. En la mayoría de las situaciones, es O (n), pero es O (n^2) si cada ticketNum es mayor que cada número ganador. (Esto es debido a que el interior j bucle no hace break cuando j==6 como debería, pero se ejecuta la siguiente iteración i en su lugar.)

usted quiere que su algoritmo para incrementar o bien ij o en cada paso, y para terminar, cuando i==6 o j==6. [. Su algoritmo casi satisface esta, como se ha dicho más arriba] Como resultado de ello, sólo es necesario un bucle:

for (i=0,j=0; i<6 && j<6; /* no increment step here */) { 
    if (ticketNum[i] == winningNum[j]) { 
     numMatches++; 
     i++; 
     j++; 
    } 
    else if (ticketNum[i] < winningNum[j]) { 
     /* ticketNum[i] won't match any winningNum, discard it */ 
     i++; 
    } 
    else { /* ticketNum[i] > winningNum[j] */ 
     /* discard winningNum[j] similarly */ 
     j++; 
    } 
} 

Es evidente que esto es O (n); en cada etapa, o incrementa i o j, por lo que la mayoría de los pasos que puede hacer es 2 * n-1. Esto tiene casi el mismo comportamiento que el algoritmo, pero es más fácil de seguir y es más fácil ver que es correcto.

Answer 2

Básicamente, está buscando el tamaño de la intersección de dos conjuntos. Dado que la mayoría de las lotas usan alrededor de 50 bolas (más o menos), puede almacenar los números como bits que se configuran en un largo sin signo. Encontrar los números comunes es entonces una simple cuestión de unir los dos juntos: commonNums = TicketNums & winningNums;.

Encontrar el tamaño de la intersección es una cuestión de contar los bits en el número resultante, un tema que ha sido covered previously (aunque en este caso, usaría números de 64 bits o un par de 32 bits números, en lugar de un solo número de 32 bits).

Answer 3

Esto es realmente solo un cambio menor en una escala como esta, pero si el segundo ciclo alcanza un número mayor que el número de ticket actual, ya puede frenar. Además, si sus segundos atraviesan números más bajos que su número de ticket, puede actualizar el desplazamiento incluso si no se encuentra ninguna coincidencia dentro de esa iteración.

PS: Sin olvidar, los resultados generales en eficiencia tienen más sentido, si consideramos que el número de bolas o el tamaño del ticket son variables. De lo contrario, depende demasiado de la máquina.

Answer 4

Sí, hay algo más rápido, pero probablemente usando más memoria. Haz una matriz llena de 0 en el tamaño de los números posibles, pon un 1 en cada número dibujado. Para cada número de ticket, agregue el valor en el índice de ese número.

int NumsArray[MAX_NUMBER+1]; 
memset(NumsArray, 0, sizeof NumsArray); 

for(i = 0; i < 6; i++) 
    NumsArray[winningNums[i]] = 1; 

for(i = 0; i < 6; i++) 
    numMatches += NumsArray[ticket.ticketNum[i]]; 

12 rondas de bucle en lugar de hasta el 36 El código que rodea deja como ejercicio.

EDITAR: También tiene la ventaja de no tener que ordenar ambos conjuntos de valores.

Answer 5

Si en lugar de comparar las matrices de números de lotería creara matrices de indicadores de dos bits, cada indicador se establecerá si su índice está en esa matriz, entonces podría realizar una configuración bit a bit y en dos el boleto de lotería y los conjuntos de números ganadores) y producen otro conjunto de bits cuyos bits eran banderas solo para números coincidentes. Luego cuente los bits establecidos.

Para muchas loterías, 64 bits serían suficientes, por lo que uint64_t debería ser lo suficientemente grande como para cubrir esto. Además, algunas arquitecturas tienen instrucciones para contar los bits establecidos en un registro, que algunos compiladores podrían reconocer y optimizar.

La eficiencia de este algoritmo se basa tanto en el rango de los números de lotería (M) como en el número de lotería por boleto (N). El ajuste si las banderas es O (N), mientras que el and-ing de las matrices de dos bits y el conteo de los bits podría ser O (M), dependiendo de si su M (rango de número de lotería) es mayor que el tamaño que el La CPU objetivo puede realizar estas operaciones directamente. Sin embargo, lo más probable es que M sea pequeño y su impacto sea probablemente menor que el de N en el rendimiento.