从队列创建双向链表查找中位数与使用数组的效率
Efficiency of creating a doubly linked list from a queue for finding median vs using an array
我正在为学校做一项作业，模拟学生排队和多个 windows 在注册办公室开放。我们必须计算平均值、中位数、最长等待时间等统计数据，以便在模拟结束时显示。
有人建议我创建另一个双向链表，将 "done" 在 window 的学生放入，以便计算这些统计数据。
当 loop/program 是 运行 时，只跟踪那些东西（中位数除外）不是更有效吗？然后对于中位数，我可以创建一个学生等待时间的数组，并在学生队列通过后对整个数组进行排序。
或者是否更多 efficient/better 练习在 window 完成后为学生做另一个双向链表，然后只用它来计算最后的统计数据？
这里有两个性能方面的考虑；
最适合您情况的容器类型是什么？
我将把你选择的链表与向量进行比较，这是我对该场景的建议；
你说的是存储多个条目，然后在某个时间点对它们进行迭代以计算一些统计数据，在考虑迭代时，使用任何类型的链表都会立即成为一个问题。链表的问题在于内存是不连续的，因此当您迭代项目时，缓存未命中率要高得多，请参阅 what every programmer should know about memory 以获得非常详细的解释，但简而言之；如果内存尚未加载到缓存中，那么您将不得不等待它加载，这会花费大量时间，并且对于算法级优化来说是一个轻松的胜利。另一方面，向量是连续的，因此迭代它们可以保证产生尽可能低的缓存未命中率，但这当然是以插入为代价的。
对于您希望在数据集之间进行大量插入、删除或移动条目的场景，链表要好得多，因为它们只是交换一些指针并继续，例如AAA CCC BBB 的字母顺序列表，先添加 AAA，然后添加 CCC，需要插入 BBB，它应该在 CCC 之前。向量处理插入特别糟糕，通常必须将插入点和末尾之间的所有数据移动一个位置，如果你总是在向量的开头插入，那么你每次都必须移动元素！ None越少;您没有声明需要排序数据，所以我假设这不会成为问题。
除了移动数据之外，由于矢量 guaranteeing contiguous memory, when they reach the end of their current allocation they must reallocate and copy the entire contents to the new allocation. If you know in advance how many entries there will be then you can avoid this issue by using reserve(n) which will allocate enough memory to store n entries, failing this the vector will reallocate each time you pass the current n, however assuming your implementation uses a smarter reallocation strategy 不仅仅是将当前大小加倍，对于更大的重新分配，此成本会降低。
懒惰或急于评估
你问的问题是你是否应该在每次进入时评估你的统计数据，或者在最后，或者第三个值得考虑的选项；只有当它被要求时！这是evaluation strategies的考虑。在您的情况下，我绝对会推荐真正或部分惰性评估，除非您需要 运行 总计 mean/median 值，否则没有必要为每个新条目计算它们，只有在您计算时才计算它需要。每当计算平均数据时，只需将 bool 存储为 true，并在每次插入或从数据集中删除时设置为 false。
我正在为学校做一项作业，模拟学生排队和多个 windows 在注册办公室开放。我们必须计算平均值、中位数、最长等待时间等统计数据，以便在模拟结束时显示。
有人建议我创建另一个双向链表，将 "done" 在 window 的学生放入，以便计算这些统计数据。
当 loop/program 是 运行 时，只跟踪那些东西（中位数除外）不是更有效吗？然后对于中位数，我可以创建一个学生等待时间的数组，并在学生队列通过后对整个数组进行排序。
或者是否更多 efficient/better 练习在 window 完成后为学生做另一个双向链表，然后只用它来计算最后的统计数据？
这里有两个性能方面的考虑；
最适合您情况的容器类型是什么？
我将把你选择的链表与向量进行比较，这是我对该场景的建议；
你说的是存储多个条目，然后在某个时间点对它们进行迭代以计算一些统计数据，在考虑迭代时，使用任何类型的链表都会立即成为一个问题。链表的问题在于内存是不连续的，因此当您迭代项目时，缓存未命中率要高得多，请参阅 what every programmer should know about memory 以获得非常详细的解释，但简而言之；如果内存尚未加载到缓存中，那么您将不得不等待它加载，这会花费大量时间，并且对于算法级优化来说是一个轻松的胜利。另一方面，向量是连续的，因此迭代它们可以保证产生尽可能低的缓存未命中率，但这当然是以插入为代价的。
对于您希望在数据集之间进行大量插入、删除或移动条目的场景，链表要好得多，因为它们只是交换一些指针并继续，例如AAA CCC BBB 的字母顺序列表，先添加 AAA，然后添加 CCC，需要插入 BBB，它应该在 CCC 之前。向量处理插入特别糟糕，通常必须将插入点和末尾之间的所有数据移动一个位置，如果你总是在向量的开头插入，那么你每次都必须移动元素！ None越少;您没有声明需要排序数据，所以我假设这不会成为问题。
除了移动数据之外，由于矢量 guaranteeing contiguous memory, when they reach the end of their current allocation they must reallocate and copy the entire contents to the new allocation. If you know in advance how many entries there will be then you can avoid this issue by using reserve(n) which will allocate enough memory to store n entries, failing this the vector will reallocate each time you pass the current n, however assuming your implementation uses a smarter reallocation strategy 不仅仅是将当前大小加倍，对于更大的重新分配，此成本会降低。
懒惰或急于评估
你问的问题是你是否应该在每次进入时评估你的统计数据，或者在最后，或者第三个值得考虑的选项；只有当它被要求时！这是evaluation strategies的考虑。在您的情况下，我绝对会推荐真正或部分惰性评估，除非您需要 运行 总计 mean/median 值，否则没有必要为每个新条目计算它们，只有在您计算时才计算它需要。每当计算平均数据时，只需将 bool 存储为 true，并在每次插入或从数据集中删除时设置为 false。