c++ - pseudocódigo - pseudocodigo a codigo c

¿Una forma más eficiente de escribir este algoritmo?

Question

Actualmente trabajando en una tarea de simulador de biblioteca. Todo funciona bien, pero me gustaría saber algo solo por saberlo.

En este programa hay 3 clases: Libro, Patrón y Biblioteca. La clase de biblioteca contiene 3 miembros de datos privados: un vector de punteros a libros, un vector a punteros de usuario y una fecha actual int.

La función en cuestión es a continuación:

void Library::incrementCurrentDate()
{
  currentDate++;

  for (int i = 0; i < members.size(); i++)
  {
    vector<Book*> ptr = members.at(i)->getCheckedOutBooks();

     for (int j = 0; j < ptr.size(); j++)
      {
        if (currentDate > ptr.at(j)->getCheckOutLength())
            members.at(i)->amendFine(.10);
      }
  }
} 

Los requisitos para la función son los siguientes:

incrementar fecha actual; aumente las multas de cada usuario en 10 centavos por cada libro vencido que hayan verificado (utilizando AmendFine)

La forma en que lo he escrito arriba funciona bien ahora. Ya que estoy en el primer semestre de mi programa de informática, no podemos usar nada que no hayamos cubierto, lo que sé es mucho. Dicho esto, ¿habría una manera más eficiente de implementar esta función utilizando métodos de programación de c ++ más avanzados?

Answer 1

1. Use std::vector si el tamaño no es extremadamente grande.

Los punteros siempre tienen un costo asociado a ellos debido a la indirección involucrada. Es posible que buscar una dirección y acceder a ella en la memoria no pueda ser optimizado por el compilador y por lo tanto implicará costos con el acceso a la memoria. El acceso a la memoria es a menudo el cuello de botella para el rendimiento en los sistemas, por lo que es mejor tratar de poner las cosas cerca unas de otras en la memoria y tratar de estructurar sus programas para que tenga menos acceso a la memoria.

2. Utilice un sistema de base de datos, como SQL, si los datos son extremadamente grandes.

Por otro lado, podemos renunciar a todo el trabajo sucio y utilizar una biblioteca o programa de base de datos establecido. Algo como MySQL puede administrar fácilmente una gran cantidad de datos con un gran lenguaje de programación para acceder y administrarlos también. Ciertas bases de datos, como PostgreSQL, pueden escalar a grandes conjuntos de datos. Familiarizarse con esto también puede ser muy útil. Incluso algunas aplicaciones móviles pueden usar MySQL para Android, por ejemplo.

3. Utilice la versión moderna de C ++ 11 o superior for sintaxis de iteración de bucle.

La corriente for sintaxis de bucle es bastante opaca y puede tener una gran cantidad de cruft. C ++ 11 introdujo un limpiador for sintaxis de bucle para iterar en contenedores de bibliotecas estándar como map o vector . Utilice: for(auto it : vector_name) . Si necesita modificar cada uno, use un calificador de referencia para el iterador.

4. Use la sintaxis de incremento previo para una aceleración mínima posible.

++i y i++ son ligeramente diferentes. ++i Simplemente modifico directamente el objeto donde aparece en una expresión antes de continuar evaluándolo. i++ crea una copia del objeto, lo devuelve e incrementa el original. Crear una copia de un valor u objeto tiene un costo en C ++, por lo que evitar esto puede ser útil en ciertos casos y es una buena convención hacerlo de todos modos.

5. Pasar por const & . No solo por referencia regular.

Los argumentos de función se pasan por valor de forma predeterminada en C ++. Esto significa que C ++ simplemente hace una copia del objeto. Sin embargo, cuando hay mutaciones aplicadas repetidamente a un objeto, como, por ejemplo, usar una función para cambiar el valor de un entero a lo largo del tiempo, es posible que desee pasar por referencia. Las referencias básicamente pasan el objeto "real", lo que significa que cualquier cambio que realice en la referencia se realiza en el objeto "real".

Ahora, ¿por qué pasar un objeto no modificable? Porque puede llevar a mejores optimizaciones. Al pasar por una referencia constante, el compilador puede hacer suposiciones más sólidas sobre su código (por ejemplo, debido a que la referencia no puede cambiar en el curso del programa, hacer referencia a la misma referencia varias veces en la función no requiere que se vuelva a cargar el argumento). otra vez porque no debería cambiar mientras está dentro de una función).

6. Utilice un std::unique_ptr o std::shared_ptr .

Los punteros inteligentes también son una buena característica que se introdujo con C ++ 11 e involucran punteros que se asignan automáticamente al vincular su vida útil al alcance. En otras palabras, no es necesario usar new o delete solo cree los punteros y no debería tener que estar atento a cuándo liberar la memoria. Esto puede complicarse en ciertas situaciones, pero en general, el uso de punteros inteligentes conduce a una mayor seguridad y menos cambios de tener problemas de administración de memoria, por lo que, en primer lugar, se incorporaron a la biblioteca estándar.

Answer 2

Ahora mismo está modificando las multas en O (n) (n siendo getCheckOutLength (). Size ()) pero puede hacerlo en O (log (n)) ya que solo necesita un número de libros atrasados ​​y no sus objetos para multar , si tiene ese número, multiplíquelo por .01 y use una función de corrección de corrección para hacerlo todo.

Así que aquí está la forma en que sugiero:
Si mantiene getCheckedOutBooks () ordenados por su getCheckOutLength () en un vector, entonces puede encontrar qué fechas son más que las fechas actuales al encontrar std :: upper_bound en el vector que le da el primer elemento que es mayor que la fecha actual, por lo que El índice de elementos al final del vector es el número de libros que deben ser multados, aquí está el código:

int checkedDateComparator(Patron & leftHand, Patron & rightHand){
    return leftHand.getCheckedOutLength() < rightHand.getCheckOutLength();  
}
bool operator==(Patron & a, Patron & b){
    return a.getCheckedOutLength() < b.getCheckOutLength();
}
void Library::incrementCurrentDate()
{
    currentDate++;

    for (int i = 0; i < members.size(); i++)
    {
        vector<Book*> ptr = members.at(i)->getCheckedOutBooks();
        Book dummy; //dummy used for find the fines 
        dummy.setCheckedOutLength(currentDate);
        int overdue = ptr.end() - upper_bound(ptr.begin(), ptr.end(), dummmy, checkedDateComparator);
        members.at(i)->amendFine(overdue* .01);
   }
} 

Answer 3

Demos un paso atrás y veamos los requisitos. Cuando vaya a la biblioteca y tenga algunos libros que hayan sido retirados tarde, probablemente le pregunte al bibliotecario lo que debe. El bibliotecario busca su cuenta y le dice. Es en ese punto que debes calcular las tarifas. Lo que está haciendo ahora es recalcular las tarifas cada medianoche (supongo). Esa es la parte que es ineficiente.

Vamos a tener este caso de uso:

1. El bibliotecario intenta revisar los libros de un patrón
2. El sistema calcula las tarifas.
3. El cliente paga las tarifas pendientes
4. El bibliotecario revisa los libros

La parte relevante para su pregunta sería el paso # 2. Aquí está el pseudocódigo:

float CalculateFees(Patron patron)
{
    float result = 0;
    foreach(checkedOutBook in patron.GetCheckedOutBooks())
    {
        result += CalculateFee(checkedOutBook.CheckOutDate(), today);
    }
    return result;
}

float CalculateFee(Date checkOutDate, Date today)
{
    return (today.Day() - checkOutDate.Day()) * 0.10;
}

Todo el caso de uso podría ser tan simple como:

void AttemptCheckout(Patron patron, BookList books)
{
    float fees = CalculateFees(patron);
    if(fees == 0 || (fees > 0 && PatronPaysFees(patron, fees)))
    {
        Checkout(patron, books);
    }
    else
    {
        RejectCheckout(patron);
    }
}

He escrito esto de una manera que facilita el cambio de la fórmula de la tarifa. Algunos tipos de materiales acumulan multas de manera diferente a otros tipos de materiales. Las multas se pueden limitar a una cierta cantidad.

Answer 4

Ha pasado un tiempo desde que uso C ++, pero casi siempre las bibliotecas estándar serán más rápidas que su propia implementación. Para su referencia, consulte las funciones estándar que están asociadas con std::vector (este sitio es extremadamente útil).

Es posible que pueda reducir el ptr.size() través de alguna otra lógica de filtrado para que no tenga que iterar sobre las personas que no tienen libros atrasados ​​(¿quizás una clasificación de libros y sus fechas de vencimiento?)

Answer 5

Hay un par de preguntas para responder aquí, creo. El primero es: ¿puede este algoritmo ser más eficiente? Y el otro es: ¿puede mi implementación del algoritmo en c ++ ser más eficiente?

A la primera pregunta, respondería que no. Según el problema, me parece que no tiene más información que le permita hacerlo mejor que O (n ^ 2).

Como se mencionó en los comentarios, puede iterar sobre cada persona y ordenar sus libros por fecha de vencimiento. En la práctica, esto podría ahorrar algo de tiempo, pero en la búsqueda de libros teóricos aún sería tiempo lineal, O (n). Además, agrega la sobrecarga de clasificación haciendo que su algoritmo sea ahora O (mnlog (n)) donde m es el número de usuarios y n es el número de libros. Si sabe que tiene pocos usuarios con muchos libros cada uno, entonces la clasificación podría ser beneficiosa. Si tiene muchos usuarios con pocos libros, sería mucho menos beneficioso.

En cuanto a la segunda pregunta: hay algunos ajustes pequeños (y algunos ajustes grandes) que podrían hacer que su código sea más eficiente, aunque yo diría que la mayoría de las veces no serían necesarios. Una cosa importante que observo es que usted recrea un objeto vectorial en cada iteración de usted primero para el bucle. Al hacer esto, estás creando una sobrecarga innecesaria. Pruebe en su lugar este pseudo-código:

currentDate++;
vector<Book*> ptr = members.at(i)->getCheckedOutBooks();
for(....)

Otra optimización que podría ser una gran revisión sería abandonar la biblioteca de vectores. Un vector en c ++ tiene la capacidad de redimensionarse sobre la marcha, así como otros gastos generales innecesarios (para su tarea). El simple uso de una matriz sería más eficiente en memoria, aunque equivalente en tiempo.

Mencionó estar en su primer semestre, por lo que probablemente aún no haya sido introducido a la notación Big O.

Answer 6

Podría considerar reemplazar el vector con un contenedor std::map . Los mapas se almacenan como árboles ordenados. Si define una función de comparación que compara la longitud de pago (o la "fecha de caducidad" más probable), no necesita escanear la lista completa cada vez.

Una solución más complicada almacenaría todos los libros en un único árbol de punteros ordenados por su tiempo de caducidad. Entonces no tendrías que iterar sobre los miembros en absoluto. En vez de eso, repase los libros hasta que encuentre un libro que aún no haya vencido.

Esto es más complicado porque ahora agregar / eliminar libros para cada miembro (o incluso iterar sobre todos los libros que posee un miembro) es más difícil y puede requerir mantener un vector de punteros para cada usuario como su enfoque actual (además del mapa global de libros). ).

Answer 7

Si esa es la única operación que está optimizando, mantenga un vector de la tuple <int, Book *, Patron * > ordenado por el int representa la fecha de vencimiento de cada libro extraído. Luego, itere hasta que la fecha de vencimiento sea mayor que la fecha actual. Multas a los patrocinadores asociados.

Answer 8

Si tiene n libros revisados, m de los cuales están vencidos, su algoritmo toma O(n) tiempo para agregar las multas. Esto se debe a que su estructura de datos almacena información como esta

member -> list(checked out books)
book -> check-out length // presumably the due date for returning the book

Si además de su colección de members , también almacena la siguiente información:

check-out length -> list(checked out books with that due date)
book -> member who checked it out

luego puede usar un árbol ordenado que almacena todos los libros retirados antes de su fecha de vencimiento para buscar todos los libros vencidos en O(log n) . Por lo tanto, el tiempo de ejecución asintótico total de su algoritmo se reduciría de O(n) a O(log n + m) .