更有效的方法来编写这个算法？

目前正致力于图书馆模拟器任务.一切都很好,但我想知道一些只是为了了解它.

在这个程序中有3个类:书,赞助人和图书馆.库类包含3个私有数据成员:指向书籍的指针向量,指向顾客指针的向量和currentDate int.

有问题的功能如下:

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

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

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

功能的要求是这样的:

增加当前日期; 将每个Patron的罚款增加10美分,用于他们已经签出的每张逾期账簿(使用modificationFine)

我上面写的方式现在工作正常.由于我刚刚进入计算机科学课程的第一学期,我们不能使用任何我们未涵盖的内容,我知道这很多.话虽如此,是否有更高效的方法使用更高级的c ++编程方法实现此功能？

1> CinchBlue..：

---

使用std::vector如果规模不是非常大.

由于所涉及的间接性,指针总是具有与它们相关的成本.查找地址并在内存中访问它可能无法由编译器优化,因此将涉及访问内存的成本.内存访问通常是系统性能的瓶颈,因此最好尝试将内容放在内存中并尝试构建程序,以便最少地访问内存.

如果数据非常大,请使用数据库系统,如SQL.

另一方面,我们可以放弃所有脏工作并使用已建立的数据库库或程序.像MySQL这样的东西可以使用优秀的编程语言轻松管理大量数据,以便访问和管理它.某些数据库(如PostgreSQL)可以扩展到大型数据集.熟悉它也很有帮助.例如,甚至一些移动应用程序可能会使用MySQL for Android.

使用现代C++ 11或更高版本的for循环迭代语法.

当前for循环语法非常不透明,可能有很多不足之处.C++ 11引入了一个更清晰的for循环语法来迭代标准库容器,如map或vector.使用:for(auto it : vector_name).如果需要修改每个,请使用it--the迭代器的引用限定符.

使用预增量语法可能实现最小的加速.

++i并i++略有不同.++i在继续评估表达式之前,只需直接修改它在表达式中出现的对象.i++创建对象的副本,返回它,并递增原始对象.创建值或对象的副本在C++中有成本,因此在某些情况下避免这种情况会有所帮助,无论如何这样做是一个很好的约定.

路过const &.不仅仅是定期参考.

函数参数默认在C++中按值传递.这意味着C++只是复制了该对象.但是,当对某个对象重复应用突变时,例如,使用函数来改变整数值随时间的变化,您可能希望通过引用传递.引用基本上传递"真实"对象,这意味着您对引用所做的任何更改都是在"真实"对象上完成的.

现在,为什么传递一个不可修改的对象？因为它可以带来更好的优化.通过常量引用传递允许编译器对您的代码做出更强的假设(例如,因为引用在程序的过程中不能改变,在函数中多次引用相同的引用不需要重新加载参数的值重复,因为它不应该在函数内部改变).

使用std::unique_ptr或std::shared_ptr.

智能指针也是C++ 11引入的一个很好的特性,它涉及通过将它们的生命周期附加到范围来自动解除分配的指针.换句话说,不需要使用new或delete--just创建指针,你不必跟踪何时释放内存.在某些情况下这可能会变得复杂,但一般来说,使用智能指针可以提高安全性并减少内存管理问题的变化,这就是为什么它们首先被引入标准库的原因.

---

4是一个有争议的问题.编译器将[优化](http://stackoverflow.com/questions/1116735/i-less-efficient-than-i-how-to-show-this)前后增加和减少`for`-环.

---

@GlennTeitelbaum是的,我刚刚删除了.这比没有意义的事情更无意义.

---

@erip我说,因为这是一个很好的经验法则.必须处理具有创建奇怪行为的"i ++"的表达式可能很难找到,因为你认为它只是"i + 1",当它真的只是"i"然后是"i + 1"时.我知道我之前已经绊过它所以我把它放在那里.

2> Andnp..：

---

我想在这里有几个问题要回答.第一个是:这个算法可以更有效吗？另一个是:我在c ++中实现算法能更有效吗？

对于第一个问题,我会回答否.基于这个问题,我觉得你没有更多的信息可以让你做得比O(n ^ 2)更好.

正如评论中所提到的,您可以迭代每个人并按截止日期对他们的书进行排序.在实践中,这可以节省一些时间,但理论上书籍查找仍然是线性时间,O(n).另外,您添加了排序的开销,使您的算法现在成为O(mnlog(n))其中m是顾客的数量,n是书籍的数量.如果你知道你的顾客很少,每本都有很多书,那么排序可能是有益的.如果你有很多书籍的顾客很少,那将是不太有益的.

至于第二个问题:有一些小的调整(和一些大的调整)可以使你的代码更有效,虽然我认为绝大多数时间他们是没有必要的.我注意到的一件主要事情是你在每次迭代时重新创建一个矢量对象for循环.通过这样做,您将产生不必要的开销.请尝试使用此伪代码:

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

另一个可能是大修的优化就是删除Vector库.c ++中的向量具有动态调整大小以及其他不必要的开销(用于您的任务)的能力.简单地使用数组可以提高内存效率,尽管它具有相当的时间效率.

你提到你在第一学期,所以你可能还没有被介绍过Big O符号.

3> Glenn Teitel..：

---

如果这是你正在优化的唯一操作,那么保持一个tuple 按照intevey 的代表截止日期排序的向量检出Book然后迭代直到截止日期大于当前日期应用程序罚款相关的Patron.