Necesito ayuda sobre un algoritmo

Question

Necesito ayuda sobre un algoritmo. He generado números aleatoriamente con 6 dígitos. Me gusta;

hay aproximadamente 1 millón de ellos se guardan en un archivo línea por línea. Tengo que filtrarlos de acuerdo con la regla que trato de describir a continuación.

Tome un número, compárelo con todos los demás dígito por dígito. Si aparece un número con un dígito con un valor mayor en uno al número comparado, entonces bórrelo. Déjame mostrarlo usando números.

Nuestro número es: 123456 Aumente el primer dígito con 1, por lo que el número pasa a ser: 223456. Borre todos los 223456 del archivo. Aumente el segundo dígito en 1, el número pasa a ser: 133456. Elimine todos los 133456 del archivo, y así sucesivamente ...

Puedo hacerlo tal como lo describo pero necesito que sea "RÁPIDO".

Entonces, ¿alguien me puede ayudar en esto?

Gracias.

Answer 1

Este algoritmo mantendrá una gran cantidad de números en la memoria, pero procesará el archivo un número cada vez, por lo que no es necesario que lo lea todo a la vez. Solo necesita suministrar un IEnumerable<int> para que funcione.

public static IEnumerable<int> FilterInts(IEnumerable<int> ints) 
    { 
     var removed = new HashSet<int>(); 

     foreach (var i in ints) 
     { 
      var iStr = i.ToString("000000").ToCharArray(); 

      for (int j = 0; j < iStr.Length; j++) 
      { 
       var c = iStr[j]; 

       if (c == '9') 
        iStr[j] = '0'; 
       else 
        iStr[j] = (char)(c + 1); 

       removed.Add(int.Parse(new string(iStr))); 

       iStr[j] = c; 
      } 

      if (!removed.Contains(i)) 
       yield return i; 
     } 
    } 

Usted puede utilizar este método para crear una IEnumerable<int> del archivo:

public static IEnumerable<int> ReadIntsFrom(string path) 
    { 
     using (var reader = File.OpenText(path)) 
     { 
      string line; 
      while ((line = reader.ReadLine()) != null) 
       yield return int.Parse(line); 
     } 
    } 

Answer 2

Para empezar, simplemente leería todos los números en una matriz.

Cuando finalmente termine, vuelva a escribir el archivo.

Answer 3

Tome todos los números desde el archivo a un arrayList, entonces:

tomar el número de hilos como el número de dígitos

de la subasta el primer dígito del número en primer hilo, en segundo lugar en la segunda hilo y luego se compara con el resto de los números,

sería rápido, ya que será sometido por el procesamiento en paralelo ...

Answer 4

parece que la regla que está describiendo es para el número de destino que abdcef quiero encontrar un ll números que contienen a + 1, b + 1, c + 1, d + 1, e + 1, o f + 1 en el lugar apropiado. Puede hacer esto en O (n) haciendo un bucle sobre las líneas del archivo y comparando cada uno de los seis dígitos con el dígito en el número objetivo si no hay coincidencia de dígitos, escriba el número en un archivo de salida.

Answer 5

En primer lugar, dado que es alrededor de 1Million, es mejor ejecutar el algoritmo en la RAM, no en el disco, es decir, primero cargar los contenidos en una matriz, modificar la matriz y luego volver a pegar los resultados .

Sugeriría el siguiente algoritmo: uno directo. Precalcular todos los números de destino, en este caso 223456, 133456, 124456, 123556, 123466, 123457. Ahora pase la matriz y si el número NO es ninguno de ellos, escríbalo en otra matriz. Alternativamente, si es uno de estos números, elimínelo (se recomienda si su estructura de datos tiene O (1) eliminar)

Answer 6

Esto suena como un caso potencial para una matriz multidimensional, y posiblemente también un código C# inseguro para que pueda usar el puntero matemática para iterar a través de una gran cantidad de números.

Tendría que profundizar más en ello, pero probablemente también usaría un diccionario para búsquedas no lineales, si está comparando números que no están en secuencia.

Answer 7

Lea todos los números del archivo y guárdelos en un mapa donde el número sea la clave y un valor booleano que indique que el valor no se ha eliminado. (El verdadero medio existe, falso significa eliminado).

A continuación, repita con las teclas. Para cada tecla, establezca el mapa en falso para los valores que eliminaría de la lista.

Iterate a través de tu lista una vez más y obtienes todas las claves donde el valor es verdadero. Esta es la lista de los números restantes.

public List<int> FilterNumbers(string fileName) 
{ 
    StreamReader sr = File.OpenTest(fileName); 
    string s = ""; 
    Dictionary<int, bool> numbers = new Dictionary<int, bool>(); 
    while((s = sr.ReadLine()) != null) 
    { 
     int number = Int32.Parse(s); 
     numbers.Add(number,true); 
    } 
    foreach(int number in numbers.Keys) 
    { 
     if(numbers[number]) 
     { 
      if(numbers.ContainsKey(100000+number)) 
       numbers[100000+number]=false; 
      if(numbers.ContainsKey(10000+number)) 
       numbers[10000+number]=false; 
      if(numbers.ContainsKey(1000+number)) 
       numbers[1000+number]=false; 
      if(numbers.ContainsKey(100+number)) 
       numbers[100+number]=false; 
      if(numbers.ContainsKey(10+number)) 
       numbers[10+number]=false; 
      if(numbers.ContainsKey(1+number)) 
       numbers[1+number]=false; 
     } 
    } 

    List<int> validNumbers = new List<int>(); 
    foreach(int number in numbers.Keys) 
    { 
     validNumbers.Add(number); 
    } 
    return validNumbers; 
} 

Esto puede necesitar ser examinada, ya que no tengo un compilador de C# en este equipo y estoy un poco oxidado. El algoritmo tomará un poco de bit de memoria que se ejecuta en tiempo lineal.

** EDIT ** Esto tiene problemas siempre que uno de los números sea 9. Actualizaré el código más tarde.

Answer 8

Todas las sugerencias (hasta ahora) requerir seis comparaciones por línea de entrada, que no es necesario. Los números vienen como cadenas, por lo tanto, use comparaciones de cadenas.

de inicio con la idea de @Armen Tsirunyan:

precalcular todos los números de destino, en este caso 223456, 133456, 124456, 123556 , 123466, 123457.

Pero en lugar de una sola comparaciones, hacer eso en una cadena:

string arg = "223456 133456 124456 123556 123466 123457"; 

Luego lea la entrada (ya sea desde un archivo o en memoria). Pseudocódigo:

foreach (string s in theBigListOfNumbers) 
    if (arg.indexOf(s) == -1) 
     print s; 

Esta es sólo una comparación por línea de entrada, no hay diccionarios, mapas, iteradores, etc.

Editado para añadir:

En los procesadores conjunto de instrucciones x86 (no sólo el Marca Intel), las búsquedas de subcadenas como esta son muy rápido. Buscar un personaje dentro de una cadena, por ejemplo, es solo una instrucción de máquina.

Tendré que pedirle a otros que evalúen las arquitecturas alternativas.

Answer 9

Qué tal esto. Usted procesa los números uno por uno. Los números se almacenarán en tablas hash NumbersOK y NumbersNotOK.

1. Tome un número
2. Si no está en NumbersNotOK lugar en un hash de NumbersOK
3. Cómo es varianzas de incrementos de números individuales en picadillo - NumbersNotOK.
4. Elimina todos los miembros NumbersOK si coinciden con alguna de las varianzas.
5. Repita desde 1, hasta el final del archivo
6. Guarde NumbersOK en el archivo.

De esta forma, pasarás la lista solo una vez. La tabla hash está hecha solo para este tipo de propósitos y será muy rápida (sin métodos de comparación costosos).

Este algoritmo no es en su totalidad, ya que no maneja cuando hay algunos números que se repiten, pero puede ser manejado con algunos ajustes ...

Answer 10

todavía suena como una pregunta tarea ... el más rápido ordenar en un millón de números será n log (n) que es 1000000log (1000000) que es 6 * 1000000, que es lo mismo que comparar 6 números para cada uno de los millones de números. Por lo tanto, una comparación directa será más rápida que ordenarla y eliminarla, ya que después de ordenarla, todavía tiene que compararla para eliminarla. A menos que, por supuesto, mis cálculos hayan pasado completamente por alto el objetivo.

Algo más viene a la mente. Cuando recoges el número, léelo como hexadecimal y no como base 10. entonces quizás algunos operadores bit a bit puedan ayudar de alguna manera. Todavía pensando en qué se puede hacer al usar esto. Se actualizará si funciona

EDITAR: actualmente pensando en las líneas de código gris. 123456 (nuestro número original) y 223456 o 133456 estarán apagados solo por un dígito y un convertidor de código gris lo atrapará rápidamente. Es tarde para la noche aquí, así que si alguien más lo encuentra útil y puede dar una solución ...