2

想象一下，你是一个批发商，你的客户有客户。交易是由您客户的客户完成的，但是当您看到每笔交易时，您只需要向您的客户收费，并且只需要担心您的客户的存款被用完。这是一项预付费服务。

交易是针对服务的，其价值是服务持续时间 * 费率的函数。

我需要一种方法，通过汇总客户累积的费用来观察我的 000 万客户账户的存款用尽情况。我与客户的客户没有任何财务安排。

当一个给定的服务实例启动时，我的客户的 BurnRate 会随着任何给定服务的收费率被添加到我代表我的客户提供的所有正在进行的服务的累积费率中而增加。当服务终止时，BurnRate 也会降低。

一个好的候选似乎是min heap或priority queue，但在我看来，传统的树/映射也可以工作，因为最左边的节点，即从迭代器读取的第一个节点，会产生相同的信息。

至少有可能 N 个客户可能有完全相同的存款耗尽时刻，AKA 生存时间 (TTL) 计算为“现在”+ (CurrentBalance/BurnRate)，因此多图可能比堆更合适。同样，任何基于经验的见解都会非常有帮助。

我的主要问题是哪个性能更好，堆还是映射/多映射？其次，堆会优雅地处理重复值吗？

TVMIA 可提供任何性能洞察力，尤其是来自经验或基准。

PS：回顾文献，我省略了一个重要的要求。当新服务启动或进程内服务结束时，我必须通过删除客户的旧 TTL 节点来更新数据结构，并用新的 TTL 插入一个新节点。看来 priority_queue 不支持这些操作。

此外，在The C++ Programming Language, 4th Edition 的第 924 页第 31 章中，Stroustrup 强烈暗示使用树来实现 priority_queue 是首选方法。由于我上面的“oops”要求只能通过树来满足，我的选择很明确，因此不会进行基准测试来比较两种方法——至少在这个项目完成之前不会。

感谢所有出席（或潜伏）并分享他们的知识和经验的人。

4

1 回答 1

0

由于没有提供实际的数据/架构，因此只能讨论理论

让我们首先定义正在使用的 3 个选项：

堆这个，根据您提供的链接似乎是排序的vector

树this，通过在 OP 中的使用是std::map，它可以被认为是一棵红黑树

通常散列，这称为散列映射，并已合并到 STL 中std::unordered_map

我们将忽略一个，多个有效载荷（map vs multimap），因为性能应该差别不大

由于我们正在谈论许多数据点，我们可以查看预期的最大时间。我们还可以查看摊销平均时间，因为您没有提到响应时间限制，而是更多的吞吐量限制。

必须看的3个操作是，insert，delete，find先（其实已经没有提到随机访问的要求了）

对于每个集合/操作：将列出平均复杂度/最大复杂度

collection   insert       delete     first
heap         N/N^2        N/N        1/1
tree         log N/log N  1/1        log N/log N
hash         1/N^2        1/N        1/N

注意 has 有两个问题

  • 如果冲突太多，所有操作都可以变成线性的

  • insert 可能需要存储数组增长

堆有两个问题

  • 插入和删除可能会导致大多数数据元素移动

  • 插入可能需要向量增长

在这些数据结构中，散列似乎具有最佳性能，但偶尔会出现非常糟糕的性能损失。如果这可以摊销（平均而不是最差的性能是至关重要的）然后使用hash，否则在最好的最坏情况下，性能图确实最接近满足要求。如果插入/删除时间不重要并且可以与影响首次查找的影响隔离开来，那么堆将是最快的并且可能提供最佳位置。

而且，如前所述，您确实应该对所有正在考虑的解决方案进行分析/压力测试

于 2015-08-10T16:43:45.113 回答