Contando las ocurrencias de los números de cuenta bancaria para el desafío SPOJ -- ++ campo con performance campo con programming-challenge campo con hash-map camp codereview Relacionados El problema

Counting the occurrences of bank account numbers for SPOJ challenge


5
vote

problema

Español

Estoy resolviendo una problema en SPOJ y actualmente estoy insatisfecho con mi tiempo de envío, dado que mi tiempo más rápido es 0.28s (que me clasifica 123/5037) y la presentación líder es de 0.04s.

El problema es bastante simple: dada una lista de números de cuenta bancaria, imprima el número de cuenta bancaria junto con la frecuencia a la que se repite.

entrada

t [el número de pruebas & lt; = 5]
n [el número de cuentas y lt; = 100 000]

[Lista de cuentas]
[Línea vacía]
[Casos de prueba siguientes]

Salida

[Lista ordenada de cuentas con el número de cuentas repetidas]
[Línea vacía]
[Otros resultados]

Ejemplo:

  Input: 2 6 03 10103538 2222 1233 6160 0142  03 10103538 2222 1233 6160 0141  30 10103538 2222 1233 6160 0141  30 10103538 2222 1233 6160 0142  30 10103538 2222 1233 6160 0141  30 10103538 2222 1233 6160 0142   5 30 10103538 2222 1233 6160 0144  30 10103538 2222 1233 6160 0142  30 10103538 2222 1233 6160 0145  30 10103538 2222 1233 6160 0146  30 10103538 2222 1233 6160 0143   Output: 03 10103538 2222 1233 6160 0141 1 03 10103538 2222 1233 6160 0142 1 30 10103538 2222 1233 6160 0141 2 30 10103538 2222 1233 6160 0142 2  30 10103538 2222 1233 6160 0142 1 30 10103538 2222 1233 6160 0143 1 30 10103538 2222 1233 6160 0144 1 30 10103538 2222 1233 6160 0145 1 30 10103538 2222 1233 6160 0146 1   

Para resolver esto, estoy usando un mapa donde la clave es la cuenta bancaria y el valor es la frecuencia de repetición. Sin embargo, primero estoy cargando las cuentas bancarias en un vector, y estoy bastante seguro de que este es un área donde estoy perdiendo eficiencia. He intentado evitar usar el vector, pero mi eficiencia se reduce enormemente.

¿Cuáles son algunas cosas que puedo hacer para mejorar mi algoritmo, o tal vez aumentar mi velocidad de E / S?

  #include <iostream> #include <map> #include <string> #include <vector>  int main() {   std::ios_base::sync_with_stdio(false);   std::cin.tie(NULL);   int t;   std::cin >> t;   while (t--) {     int n, i;     std::cin >> n;     std::cin.ignore();     std::vector<std::string> accounts(n);     for (i = 0; i < n; ++i) {       std::getline(std::cin, accounts[i]);     }     std::cout << " ";     std::map<std::string, int> count;     for (i = 0; i < accounts.size(); ++i) {       auto map_it(count.find(accounts[i]));       if (map_it != count.end()) {         map_it->second++;       } else {         count[accounts[i]] = 1;       }     }     for (auto it = count.begin(); it != count.end(); ++it) {       std::cout << it->first << it->second << " ";     }     if (t != 0) {       std::string blank;       std::getline(std::cin, blank);     }   }   return 0; }   
Original en ingles

I am solving a problem on SPOJ and am currently unsatisfied with my submission time, given that my fastest time is 0.28s (which ranks me 123/5037) and the leading submission is 0.04s.

The problem is pretty simple: Given a list of bank account numbers, print the bank account number along with the frequency at which it is repeated.

Input

t [the number of tests <= 5]
n [the number of accounts<= 100 000]

[list of accounts]
[empty line]
[next test cases]

Output

[sorted list of accounts with the number of repeated accounts]
[empty line]
[other results]

Example:

Input: 2 6 03 10103538 2222 1233 6160 0142  03 10103538 2222 1233 6160 0141  30 10103538 2222 1233 6160 0141  30 10103538 2222 1233 6160 0142  30 10103538 2222 1233 6160 0141  30 10103538 2222 1233 6160 0142   5 30 10103538 2222 1233 6160 0144  30 10103538 2222 1233 6160 0142  30 10103538 2222 1233 6160 0145  30 10103538 2222 1233 6160 0146  30 10103538 2222 1233 6160 0143   Output: 03 10103538 2222 1233 6160 0141 1 03 10103538 2222 1233 6160 0142 1 30 10103538 2222 1233 6160 0141 2 30 10103538 2222 1233 6160 0142 2  30 10103538 2222 1233 6160 0142 1 30 10103538 2222 1233 6160 0143 1 30 10103538 2222 1233 6160 0144 1 30 10103538 2222 1233 6160 0145 1 30 10103538 2222 1233 6160 0146 1 

In order to solve this, I am using a map where the key is the bank account and the value is the frequency of repetition. However, I am first loading the bank accounts into a vector, and I am pretty sure this is one area where I am losing efficiency. I have tried to avoid using the vector, but my efficiency is greatly reduced.

What are some things that I can do to either improve my algorithm, or perhaps increase my I/O speed?

#include <iostream> #include <map> #include <string> #include <vector>  int main() {   std::ios_base::sync_with_stdio(false);   std::cin.tie(NULL);   int t;   std::cin >> t;   while (t--) {     int n, i;     std::cin >> n;     std::cin.ignore();     std::vector<std::string> accounts(n);     for (i = 0; i < n; ++i) {       std::getline(std::cin, accounts[i]);     }     std::cout << "\n";     std::map<std::string, int> count;     for (i = 0; i < accounts.size(); ++i) {       auto map_it(count.find(accounts[i]));       if (map_it != count.end()) {         map_it->second++;       } else {         count[accounts[i]] = 1;       }     }     for (auto it = count.begin(); it != count.end(); ++it) {       std::cout << it->first << it->second << "\n";     }     if (t != 0) {       std::string blank;       std::getline(std::cin, blank);     }   }   return 0; } 
           

Lista de respuestas

2
 
vote
vote
La mejor respuesta
 

Un área de ineficiencia está aquí:

  IApiService6  

Estás leyendo cada número de cuenta, almacenándolos y luego regresar a través de los datos para obtener los conteos. La clase MAP permite una clave que no existe para crear una entrada sobre la marcha. El uso de esto eliminará el segundo bucle:

  IApiService7  
 

One area of inefficiency is here:

for (i = 0; i < n; ++i) {   std::getline(std::cin, accounts[i]); } std::cout << "\n"; std::map<std::string, int> count; for (i = 0; i < accounts.size(); ++i) {   auto map_it(count.find(accounts[i]));   if (map_it != count.end()) {     map_it->second++;   } else {     count[accounts[i]] = 1;   } } 

You're reading each account number, storing them then going back through the data to get the counts. The map class allows for a key that doesn't exist to create an entry on the fly. Using this will eliminate the second loop:

std::string temp = ""; std::map<std::string, int> count; for (i = 0; i < n; ++i) {   std::getline(std::cin, temp);   count[temp]++;  } std::cout << "\n"; 
 
 
1
 
vote

Esta es una implementación directa bastante fácil de leer, lo cual es agradable de ver. Aquí hay algunas cosas que podrías hacer para mejorarlo:

Naming

Algunos de sus nombres como accounts son buenos, pero otros de sus nombres son muy básicos y esencialmente sin sentido. Uso de i Para un iterador de bucle está bien, pero 9988776655544332 y t3 No me diga nada sobre lo que representan. Iría al cambiar el nombre t a numTests n to numAccounts para que sea más claro. También enline las definiciones de mi bucle iterador, ya que no las estás usando fuera de los bucles, como este:

  for (int i = 0; i < numAccounts; ++i) {   

Los nombres it y i0 son realmente confusos. i1 podría ser cualquier cosa. Dado que es un iterador, tal vez 2 caracteres más para hacerlo i2 en su lugar? Prefiero usar i3 donde "lo que sea" es lo que está iterando. En este caso, sería i4 .

Performance

@tinstaafl tuvo una buena sugerencia para mejorar el rendimiento en su respuesta. Hay algunos temas comunes con estos tipos de problemas. Una cosa que ha ayudado en otras pruebas como esta que he revisado o hecho mismo es ordenar las cosas antes de contarlas. No sé si eso sería más rápido en este caso o no, pero vale la pena intentarlo.

Qué tipo de clasificación es mucho más fácil de contar, y mejora la coherencia de la CPU Cache. Terminas con una matriz que parece algo así:

  i5  

Ahora siempre está trabajando con un artículo hasta que haya contado todas las instancias, y luego pase a la siguiente, y haga lo mismo. No estás saltando de un lado a otro en la matriz de cuentas o en la matriz de conteos. Este tipo de acceso a la memoria es considerablemente más rápido para una CPU.

Puede hacer una especie de inserción a medida que los lee desde la entrada (probablemente no la manera más rápida), o podría usar un orden más rápido después del hecho.

Lo que hagas, perfila tu código para ver qué es lo que te está desacelerando. A menudo te sorprenderás por el resultado. Podría ser E / S; Podría ser el conteo; Pero no lo sabrás hasta que realmente lo mérs.

 

This is a fairly easy to read straightforward implementation, which is nice to see. Here are a few things you could do to improve it:

Naming

Some of your names like accounts are good, but others of your names are very basic and essentially meaningless. Using i for a loop iterator is fine, but n and t tell me nothing about what they stand for. I would rename t to numTests and n to numAccounts to make it clearer. I would also inline my loop iterator definitions since you're not using them outside of the loops, like this:

for (int i = 0; i < numAccounts; ++i) { 

The names it and map_it are really confusing. it could be anything. Since it's an iterator, maybe 2 more characters to make it iter instead? I prefer to use next<whatever> where "whatever" is the thing you are iterating over. In this case it would be nextAccount.

Performance

@tinstaafl had a good suggestion for improving performance in their answer. There are some common themes with these types of problems. One thing that has helped in other tests like this that I've reviewed or done myself is to sort things before counting them. I don't know whether that would be faster in this case or not, but it's worth trying.

What sorting does is makes it much easier to count, and it improves CPU cache coherency. You end up with an array that looks something like this:

a, a, a, b, b, c, c, c, c, c, d, e, e, ... etc. 

Now you're always working with one item until you've counted all instances, and then you move on to the next one, and do the same. You're not jumping back and forth in either the array of accounts or the array of counts. This type of memory access is considerably faster for a CPU.

You could either do an insertion sort as you read them from the input (probably not the fastest way), or you could use a faster sort after-the-fact.

Whatever you do, profile your code to see what it is that's slowing you down. You will often be surprised by the result. It could be I/O; it could be the counting; but you won't know until you actually measure it.

 
 

Relacionados problema

5  Finanzas familiares - seguimiento e informes  ( Family finances tracking and reporting ) 
Estoy buscando una forma limpia de acumular montos dentro de un conjunto de datos de entrada. En este ejemplo, hay 18 filas de datos, y la salida es de 3 fila...

4  Un programa para mostrar, actualizar y guardar un diccionario como .csv  ( A program to display update and save a dictionary as csv ) 
Ahora estoy buscando comentarios en v2.0 de este programa en su lugar. Me gustaría algunos comentarios sobre mi código. ¿Qué malos hábitos tengo? ¿Qué c...

2  Tabla hash implementada por JavaScript  ( Hash table implemented by javascript ) 
Recientemente intenté implementar una tabla simple usando JavaScript. ¿Alguien podría ayudarme a revisar mi implementación? AssetClass6 En mi implement...

4  Encuentra y reemplaza la optimización del método  ( String find and replace method optimization ) 
Estoy tratando de encontrar una cadena de encabezado específica de diferentes mapas ( 9988777665544330 , LEDES98BIheaders1 y LEDES98BI_V2headers ) En un e...

0  Base de datos de estudiantes  ( Database of students ) 
Al principio, tuve 9988777665544332 para contener std::list<Student> students , pero como hay más de 2000 estudiantes, la búsqueda de estudiantes no debe h...

7  Holding registros utilizando diccionario  ( Holding records using dictionary ) 
¿Puedes por favor ayudarme con el siguiente script? En este momento, el script está tomando hasta 20 minutos para ejecutar, dependiendo de la cantidad de da...

0  Acelerar el código basado en el mapa con vectores como valores  ( Speed up code based on map with vectors as values ) 
Siguiendo es la pieza de código que representa el cuello de botella de mi aplicación: #include <iostream> #include <chrono> #include <unordered_map> #inclu...

3  Compara los dictos y récord de cambios  ( Compare dicts and record changes ) 
Mi objetivo es actualizar continuamente un objeto y registrar cualquier cambio y las veces que se hicieron. La entrada debe ser JSON, pero el formato de salid...

5  Producto cartesiano de Python en un dictnario limitado  ( Python cartesian product in a constrained dictonary ) 
Quiero calcular el producto cartesiano de n Copias de una lista pequeña, 9988777665544331 . Quiero usar estas tites de productos cartesianos como llaves en...

6  Hosth de descarga en columnas  ( Dump hash in columns ) 
Intenté responder a la pregunta "¿Cómo imprimir un hash en Perl, de modo que se imprimen 3 pares de valor clave en cada línea? " como este . Como obtuve u...




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