Optimización del método de la persona que llama Bingo -- # campo con performance campo con programming-challenge camp codereview Relacionados El problema

Optimizing Bingo Caller Method


5
vote

problema

Español

Soy Dong Un problema de programación competitiva que he aprobado todas las pruebas. Pero mi programa se sale. Necesito ayuda para optimizar mi código para que pueda funcionar más rápido.


Tarea:

  • Método de acabado: BingoCaller.GetNumber()

  • Devuelve todos los números en el rango de 1 hasta 75 una vez y en orden aleatorio

  • Si no queda números, devuelva una cadena vacía

  • Los números se devuelven uno por uno en el estilo de bingo:

    "I27", "N40", "B5", "B12", "I28", "O69", "B1", ...

  • Estos son los rangos que debe seguir:

    • Un número dentro del rango de 1 a 15 comienza con un 'B'

    • Un número dentro del rango de 16 a 30 comienza con un 'i'

    • Un número dentro del rango de 31 a 45 comienza con un 'n'

    • Un número dentro del rango de 46 a 60 comienza con un 'g'

    • Un número dentro del rango 61 a 75 comienza con una 'O'

  • Uso public class SearchModel { private int _pagesize = 50; public int pagesize { get { return _pagesize; } set { _pagesize =value; } } private int _pageNo = 1; public int pageNo { get { return _pageNo; } set { _pageNo = value; } } private Enum.SortingCriteria _criteria = Enum.SortingCriteria.New; public Enum.SortingCriteria criteria { get { return _criteria; } set { _criteria = value; } } private List<FiltersViewModel> _filter = null; public List<FiltersViewModel> filter { get { return _filter ; } set { _filter = value; } } } 0 Para generar sus números aleatorios. Pase a través del constructor para fines de prueba.


Mi código a continuación
  public class SearchModel {     private int _pagesize = 50;      public int pagesize     {         get { return _pagesize; }         set { _pagesize =value; }     }      private int _pageNo = 1;      public int pageNo     {         get { return _pageNo; }         set { _pageNo = value; }     }      private Enum.SortingCriteria _criteria = Enum.SortingCriteria.New;      public Enum.SortingCriteria criteria     {         get { return _criteria; }         set { _criteria = value; }     }      private List<FiltersViewModel> _filter = null;      public List<FiltersViewModel> filter     {         get { return _filter ; }         set { _filter  = value; }     }   } 1  
Original en ingles

I am dong a competitive programming problem I have passed all the tests. but my program times out. I need help optimizing my code so it can run faster.


Task:

  • Finish method: BingoCaller.GetNumber()

  • Return all numbers in the range of 1 until 75 once and in random order

  • If there are no numbers left, return an empty string

  • The numbers are returned one by one in Bingo style:

    "I27", "N40", "B5", "B12", "I28", "O69", "B1", ...

  • These are the ranges that you must follow:

    • A number within range 1 to 15 starts with a 'B'

    • A number within range 16 to 30 starts with an 'I'

    • A number within range 31 to 45 starts with an 'N'

    • A number within range 46 to 60 starts with a 'G'

    • A number within range 61 to 75 starts with an 'O'

  • Use System.Random to generate your random numbers. Pass via the constructor for testing purposes.


My code below
       using System;        using System.Collections.Generic;         public class BingoCaller         {              private Random random;               static List<int> List = new List<int>();               public BingoCaller(Random random)             {                 this.random = random;              }              public string GetNumber()             {              Start:               var item = random.Next(75);                   if (List.Contains(item))                 {                   goto Start;                 }                 else                 {                     List.Add(item);                      if (item >= 61)                     {                         return "O" + item;                     }                     else if (item >= 46)                     {                         return "G" + item;                     }                     else if (item >= 31)                     {                         return "N" + item;                     }                     else if (item >= 16)                     {                         return "I" + item;                     }                     else                     {                         return "B" + item;                     }                  }               }         } 
        
   
   

Lista de respuestas

4
 
vote
vote
La mejor respuesta
 

El truco es usar un 9988776665544338 para rastrear números dibujados que tiene una búsqueda de O(n) y a deja de dibujar números nuevos si los 75 números ya han sido Dibujado Porque las llamadas al método def read_test_case(lines_amount): return [input() for _ in range(lines_amount)] 0 son caros y el tiempo de ejecución aumenta innecesariamente.

El def read_test_case(lines_amount): return [input() for _ in range(lines_amount)] 1 'S def read_test_case(lines_amount): return [input() for _ in range(lines_amount)] 2 Método def read_test_case(lines_amount): return [input() for _ in range(lines_amount)] 3 Si se podría agregar un valor para que podamos usarlo con un def read_test_case(lines_amount): return [input() for _ in range(lines_amount)] 4 < / Código> Loop hasta que encontremos el siguiente número no dibujado.

  def read_test_case(lines_amount):     return [input() for _ in range(lines_amount)] 5  

Esta solución pasa las 19 pruebas y se ejecuta en aproximadamente 620 ms.

Recuerde agregar def read_test_case(lines_amount): return [input() for _ in range(lines_amount)] 6 Para que el def read_test_case(lines_amount): return [input() for _ in range(lines_amount)] 7 trabaje.


Desafortunadamente La versión C # 7 no funciona en los codenemas, pero también se ve bien

  def read_test_case(lines_amount):     return [input() for _ in range(lines_amount)] 8  

y con una función local podríamos encapsular el área def read_test_case(lines_amount): return [input() for _ in range(lines_amount)] 9 :

  def main():     while True:         lines, columns = map(int, input().split())         if not lines:             return         field = read_test_case(lines)         # ... 0  
 

The trick is to use a HashSet<int> for tracking drawn numbers that has a lookup of O(n) and to stop drawing new numbers if all 75 numbers has already been drawn because calls to the Next(..) method are expensive and the execution time unnecessarily increases.

The HashSet's Add method returns true if a value could be added so we can use it with a while loop until we find the next not yet drawn number.

private HashSet<int> _drawn = new HashSet<int>();  private int? NextNumber() {     var i = default(int?);     while (_drawn.Count < 75 && !_drawn.Add((int)(i = random.Next(1, 76))));     return i; }  public string GetNumber() {     var i = NextNumber();     if (i.HasValue)     {         if (i <= 15) return $"B{i}";         if (i <= 30) return $"I{i}";         if (i <= 45) return $"N{i}";         if (i <= 60) return $"G{i}";         if (i <= 75) return $"O{i}";     }     return string.Empty; } 

This solution passes all 19 tests and executes in about 620ms.

Remember to add using System.Collections.Generic; so that the HashSet<int> work.


Unfortuantelly the C# 7 version does not work on Codewars but it looks nice too

public string GetNumber() {     switch (NextNumber())     {                     case int i when i <= 15: return $"B{i}";         case int i when i <= 30: return $"I{i}";         case int i when i <= 45: return $"N{i}";         case int i when i <= 60: return $"G{i}";         case int i when i <= 75: return $"O{i}";         default: return string.Empty;     } } 

and with one local function we could encapsulate the while condition:

private int? NextNumber() {     var i = default(int?);     bool CanDrawNext()      {         return              _drawn.Count < 75 &&              _drawn.Add((int)(i = random.Next(1, 76))) == false;     }             while (CanDrawNext());     return i; } 
 
 
         
         
7
 
vote

Se considera que la mala práctica use las declaraciones goto en la programación moderna porque rápidamente se pone difícil de seguir la estructura, así que evite eso. En su lugar, podría usar un bucle rubry en una especie de esta manera:

  def main():     while True:         lines, columns = map(int, input().split())         if not lines:             return         field = read_test_case(lines)         # ... 1  

  def main():     while True:         lines, columns = map(int, input().split())         if not lines:             return         field = read_test_case(lines)         # ... 2  

Esta declaración establece def main(): while True: lines, columns = map(int, input().split()) if not lines: return field = read_test_case(lines) # ... 3 a un número en el intervalo de $ [0, 75 [ $, pero se suponía que debías manejar el intervalo $ [1, 75] $


en lugar de def main(): while True: lines, columns = map(int, input().split()) if not lines: return field = read_test_case(lines) # ... 4 Es más legible escribir def main(): while True: lines, columns = map(int, input().split()) if not lines: return field = read_test_case(lines) # ... 5


Parece que def main(): while True: lines, columns = map(int, input().split()) if not lines: return field = read_test_case(lines) # ... 6 le falta una altura de parada. Se ejecutará para siempre entre def main(): while True: lines, columns = map(int, input().split()) if not lines: return field = read_test_case(lines) # ... 7 y def main(): while True: lines, columns = map(int, input().split()) if not lines: return field = read_test_case(lines) # ... 8 cuando la lista está llena. (Que puede ser su "tiempo fuera" -problem).


En lugar de la larga lista de declaraciones if-statements, podría usar la relación simple entre la posición del prefijo en la palabra "bingo" y el número aleatorio para extraerlo como:

  def main():     while True:         lines, columns = map(int, input().split())         if not lines:             return         field = read_test_case(lines)         # ... 9  

(tiene algo que ver con 15).


El patrón de llenar una lista con números encontrados tiende a ser más lento y más lento en el tiempo de respuesta, ya que el tamaño de la lista crece porque el siguiente número aleatorio es cada vez más probable que esté en la lista. Potencialmente puede ser encontrado un número válido ...

Un mejor enfoque podría ser crear la lista de los 75 números en el constructor con antelación y luego eliminarlos uno por uno de la lista cuando se encuentra por for ... in range(len(...))0 :

  for ... in range(len(...))1  

Esto disminuirá en el tiempo de respuesta y evite el bucle.


una solución podría ser:

  for ... in range(len(...))2  
 

It is considered bad practice to use goto-statements in modern programming because it quickly gets hard to follow the structure, so avoid that. Instead you could use a while-loop in a kind of this manner:

while (list.Count < 75) {   var number = random.Next(75);   if (list.Contains(number))     continue;     ... } 

var item = random.Next(75); 

This statement sets item to a number in the interval of \$[0, 75[\$, but you were supposed to handle the interval \$[1, 75]\$


instead of if (item >= 61) it is more readable to write if (item > 60)


It seems that GetNumber() is missing a stop-condition. It will run forever between goto Start and Start: when the list is full. (That may be your "time out"-problem).


Instead of the long list of if-statements, you could use the simple relation between the prefix's position in the word "BINGO" and the random number to extract it as:

string bingo = "BINGO"; // Make it a class field. int index = ... char prefix = bingo[index] 

(it has something to do with 15).


The pattern of filling a list with found numbers tends to be slower and slower in response time as the size of the list grows because the next random number is more and more likely to be in the list. Potentially a valid number may never be found...

A better approach could be to create the list of the 75 numbers in the constructor in advance and then remove them one by one from the list when found by random.Next():

... var number = list[random.Next(0, list.Count)]; list.Remove(number); ... 

This will decrease in response time and you avoid the looping.


A solution could be:

  public class BingoCaller   {     private Random random;     List<int> list;     string bingo = "BINGO";      public BingoCaller(Random random)     {       this.random = random;       list = Enumerable.Range(1, 75).ToList();     }      public string GetNumber()     {       if (list.Count == 0)         return "";        var number = list[random.Next(0, list.Count)];       list.Remove(number);       char prefix = bingo[(number - 1) / 15];       return $"{prefix}{number}";     }   } 
 
 
         
         
2
 
vote

Buscando List y vuelva a intentarlo hasta que obtenga un número no utilizado, no es eficiente
Hashset sería mejor, pero aún así no es bueno, ya que todavía vuelves a reintentar

El artículo necesita tener un +1 cuando lo devuelva

Simplemente me arrastraría una vez por adelantado: exactamente 74 llamadas a Random.Siguiente
Esto es Fisher Yates SHUFFLE: está comprobado que es una baraja correcta

  public class Bingo {     static List<string> bingoBalls = new List<string>(75);     IEnumerator bingoBallsEnumerator;     public Bingo (Random Rand)     {         CreateBingoBalls();         ShuffleBingoBalls(bingoBalls, Rand);         bingoBallsEnumerator = bingoBalls.GetEnumerator();         //foreach (string s in bingoBalls)         //    Debug.WriteLine(s);         //Debug.WriteLine("");     }     private void CreateBingoBalls()     {         char[] BINGO = "BINGO".ToCharArray();         for (int i = 1; i <= 75; i++)         {             string next = BINGO[(i-1) / 15] + i.ToString();             //Debug.WriteLine(next);             bingoBalls.Add(next);         }     }     private void ShuffleBingoBalls(List<string> BingoBalls, Random Rand)     {         for(int i = BingoBalls.Count-1; i > 0 ; i--)         {             int j = rand.Next(i + 1);             if(j != i)             {                 string temp = BingoBalls[i];                 BingoBalls[i] = BingoBalls[j];                 BingoBalls[j] = temp;             }          }            }     public string GetNextBingoBall()     {         if (bingoBallsEnumerator.MoveNext())         {             return bingoBallsEnumerator.Current.ToString();         }         else         {             return string.Empty;         }     } }   

me sorprendió, pero esto es más rápido

  public class Bingo2 {     private List<int> bingoBalls = Enumerable.Range(1, 75).ToList();     private Random rand;     public Bingo2(Random Rand)     {         rand = Rand;     }     private int ballIndex;     private int ballCount;     private char[] BINGO = "BINGO".ToCharArray();     public string GetNextBingoBall()     {         ballCount = bingoBalls.Count;         if (ballCount == 0)             return string.Empty;         if (ballCount == 1)         {             ballIndex = bingoBalls[0];             bingoBalls.Clear();             return BINGO[(ballIndex - 1) / 15] + ballIndex.ToString();         }         ballIndex = bingoBalls[random.Next(ballCount)];         bingoBalls.Remove(ballIndex);         return BINGO[(ballIndex - 1) / 15] + ballIndex.ToString();     } }   

 

Searching List and retry until you get an unused number is not efficient
HashSet would be better but still not good as you still retry

Item needs to have a +1 when you return it

I would just shuffle once up front - exactly 74 calls to Random.Next
This is Fisher Yates shuffle - it is proven to be a correct shuffle

public class Bingo {     static List<string> bingoBalls = new List<string>(75);     IEnumerator bingoBallsEnumerator;     public Bingo (Random Rand)     {         CreateBingoBalls();         ShuffleBingoBalls(bingoBalls, Rand);         bingoBallsEnumerator = bingoBalls.GetEnumerator();         //foreach (string s in bingoBalls)         //    Debug.WriteLine(s);         //Debug.WriteLine("");     }     private void CreateBingoBalls()     {         char[] BINGO = "BINGO".ToCharArray();         for (int i = 1; i <= 75; i++)         {             string next = BINGO[(i-1) / 15] + i.ToString();             //Debug.WriteLine(next);             bingoBalls.Add(next);         }     }     private void ShuffleBingoBalls(List<string> BingoBalls, Random Rand)     {         for(int i = BingoBalls.Count-1; i > 0 ; i--)         {             int j = rand.Next(i + 1);             if(j != i)             {                 string temp = BingoBalls[i];                 BingoBalls[i] = BingoBalls[j];                 BingoBalls[j] = temp;             }          }            }     public string GetNextBingoBall()     {         if (bingoBallsEnumerator.MoveNext())         {             return bingoBallsEnumerator.Current.ToString();         }         else         {             return string.Empty;         }     } } 

Surprised me but this is faster

public class Bingo2 {     private List<int> bingoBalls = Enumerable.Range(1, 75).ToList();     private Random rand;     public Bingo2(Random Rand)     {         rand = Rand;     }     private int ballIndex;     private int ballCount;     private char[] BINGO = "BINGO".ToCharArray();     public string GetNextBingoBall()     {         ballCount = bingoBalls.Count;         if (ballCount == 0)             return string.Empty;         if (ballCount == 1)         {             ballIndex = bingoBalls[0];             bingoBalls.Clear();             return BINGO[(ballIndex - 1) / 15] + ballIndex.ToString();         }         ballIndex = bingoBalls[random.Next(ballCount)];         bingoBalls.Remove(ballIndex);         return BINGO[(ballIndex - 1) / 15] + ballIndex.ToString();     } } 
 
 
2
 
vote

Todas las respuestas se centran en usar Random en el método 9988777665544334 , que no es necesario.

Podemos acelerar esto eliminando todo el Método al azar.

¿Cuál es la verdad absoluta sobre nuestra tarea deseada? El orden nunca cambiará . Podemos crear el orden de nuestros números en el constructor, y crear un campo de índice en lugar de todo el código en el método 9988776665544335 .

También podemos hacer esta ejecución en el tiempo de $ O (n) $ (en este momento no tiene tiempo de ejecución en BIG-O, su método podría estar funcionando infinitamente).

Código:

  class BingoCaller {     private int[] _numbers;     private int _index;     private const string _letterMap = "BINGO";      public BingoCaller(Random rand)     {         _numbers = Enumerable.Range(1, 75).OrderBy(x => rand.Next()).ToArray();     }      public string GetNumber()     {         if (_numbers.Length > _index)         {             var num = _numbers[_index++];             return _letterMap[(num - 1) / 15].ToString() + num;         }         return string.Empty;     } }   

Mi prueba:

  void Main() {     var lastNumber = string.Empty;     var bingoCaller = new BingoCaller(new Random(0));     var numbers = new List<string>();      while ((lastNumber = bingoCaller.GetNumber()) != string.Empty)     {         Console.WriteLine($"Number: {lastNumber}");         numbers.Add(lastNumber);     }      Console.WriteLine($"Unique numbers: {numbers.GroupBy(x => x).Count()}"); }   

Salida:

  Number: I16 Number: N37 Number: I24 Number: I30 Number: O65 Number: N43 Number: G49 Number: O67 Number: N31 Number: G55 Number: B5 Number: O62 Number: O70 Number: G50 Number: N44 Number: B10 Number: B11 Number: N33 Number: I20 Number: G47 Number: N39 Number: N38 Number: G51 Number: B8 Number: N32 Number: G48 Number: B12 Number: B14 Number: O72 Number: G54 Number: N41 Number: I26 Number: I29 Number: B4 Number: B6 Number: G53 Number: O61 Number: B13 Number: N35 Number: O68 Number: O73 Number: I19 Number: G60 Number: I28 Number: I25 Number: N42 Number: G52 Number: O74 Number: B1 Number: G58 Number: N36 Number: B3 Number: G46 Number: O75 Number: I21 Number: B2 Number: G57 Number: O69 Number: O66 Number: I22 Number: G59 Number: I17 Number: G56 Number: O63 Number: O64 Number: B7 Number: N45 Number: I27 Number: N40 Number: B9 Number: B15 Number: N34 Number: I23 Number: I18 Number: O71 Unique numbers: 75   

La línea 'números únicos' imprime 75, lo que significa que no teníamos duplicados.

Ahora no garantizaré que esto pase sus pruebas. Podrían estar pasando un 99887766655544339 específico y esperando un orden específico, pero esto devolverá un orden consistente cada vez.

 

All the answers focus on using Random in the GetNumber() method, which isn't necessary.

We can speed this up by eliminating the random from that method entire.

What's the one, absolute truth about our desired task? The order will never change. We can build the order of our numbers in the constructor, and create an index field instead of all the code being in the GetNumber() method.

We can also make this run in \$O(n)\$ time (right now you have no big-O run-time, your method could be running infinitely).

Code:

class BingoCaller {     private int[] _numbers;     private int _index;     private const string _letterMap = "BINGO";      public BingoCaller(Random rand)     {         _numbers = Enumerable.Range(1, 75).OrderBy(x => rand.Next()).ToArray();     }      public string GetNumber()     {         if (_numbers.Length > _index)         {             var num = _numbers[_index++];             return _letterMap[(num - 1) / 15].ToString() + num;         }         return string.Empty;     } } 

My test:

void Main() {     var lastNumber = string.Empty;     var bingoCaller = new BingoCaller(new Random(0));     var numbers = new List<string>();      while ((lastNumber = bingoCaller.GetNumber()) != string.Empty)     {         Console.WriteLine($"Number: {lastNumber}");         numbers.Add(lastNumber);     }      Console.WriteLine($"Unique numbers: {numbers.GroupBy(x => x).Count()}"); } 

Output:

Number: I16 Number: N37 Number: I24 Number: I30 Number: O65 Number: N43 Number: G49 Number: O67 Number: N31 Number: G55 Number: B5 Number: O62 Number: O70 Number: G50 Number: N44 Number: B10 Number: B11 Number: N33 Number: I20 Number: G47 Number: N39 Number: N38 Number: G51 Number: B8 Number: N32 Number: G48 Number: B12 Number: B14 Number: O72 Number: G54 Number: N41 Number: I26 Number: I29 Number: B4 Number: B6 Number: G53 Number: O61 Number: B13 Number: N35 Number: O68 Number: O73 Number: I19 Number: G60 Number: I28 Number: I25 Number: N42 Number: G52 Number: O74 Number: B1 Number: G58 Number: N36 Number: B3 Number: G46 Number: O75 Number: I21 Number: B2 Number: G57 Number: O69 Number: O66 Number: I22 Number: G59 Number: I17 Number: G56 Number: O63 Number: O64 Number: B7 Number: N45 Number: I27 Number: N40 Number: B9 Number: B15 Number: N34 Number: I23 Number: I18 Number: O71 Unique numbers: 75 

The 'Unique numbers' line prints 75, which means we had no duplicates.

Now I won't guarantee that this passes their tests. They might be passing a specific Random and expecting a specific order, but this will return a consistent order each and every time.

 
 
         
         

Relacionados problema

61  Uso de funciones separadas para Project Euler 1  ( Using separate functions for project euler 1 ) 
Comencé a programar con Java y C ++, así que estoy acostumbrado a tener una función "principal" que llama a otras funciones que realizan el trabajo real. En l...

1  Codificación de Google Jam: Tienda Credit Java Solution  ( Google code jam store credit java solution ) 
Sería genial si pudiera obtener este código revisado. Me encantaría consejos sobre cómo podría mejorar mi código. problema Recibirá un crédito C en una...

6  Proyecto EULER # 7: 10001ST PRIME  ( Project euler 7 10001st prime ) 
Esta es mi implementación de Project Euler # 7 . ¿Lo he exagerado de nuevo? ¿Hay algo más que debería o no debo hacer? Se ejecuta en 9 milisegundos en mi com...

5  Cuatro cuatro para obtener cualquier número  ( Four fours to get any number ) 
Decidí resolver un problema de Código Golf llamado los cuatro cuatro . Descripción del problema: El Puzzle Four Fours es un popular rompecabezas matemát...

4  Encuentre el número de subcadenas de una cadena numérica mayor que una cadena numérica dada  ( Find the number of substrings of a numerical string greater than a given num str ) 
Pregunta: http://qa.geeksforgeeks.org/9744/vinay-queried-interesting -Problem-optimización Entrada La primera línea contiene n que denota la longitud...

6  Solución de codewars a "ascensor simple"  ( Codewars solution to simple elevator ) 
Soy nuevo en la programación (menos de un año), y me gustaría mejorar. Resolví un problema en las claquinas y copié tanto mi solución como la solución venci...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos