最快的C++容器：唯一值

Question

我正在编写一个与MySQL数据库交互的电子邮件应用程序。我有两个表来获取我的数据，其中一个包含取消订阅的内容，另一个是标准用户表。目前，我正在创建指向电子邮件对象的指针向量，并最初将所有取消订阅的电子邮件存储在其中。然后，我使用标准的SQL循环来检查电子邮件是否不在取消订阅向量中，然后将其添加到全局发送电子邮件向量中。我的问题是，是否有更有效的方法来做到这一点？我必须为系统中的每个电子邮件搜索取消订阅向量，高达50K个不同的电子邮件。是否有更好的结构来搜索？以及，维护唯一值的更好结构？也许可以简单地丢弃已经包含它的值？

- Josh

---

DVK和Daniel Trebbien是正确的：最好在数据库中实现这个功能。当你说这是不可能的时候，我并不相信你 - 请发布模式的相关部分。 - j_random_hacker

为什么在检查用户是否希望接收邮件之前生成邮件？这里你做了额外的工作... - Matthieu M.

@Matthieu：我不是生成电子邮件内容，而是收集电子邮件地址进行交叉引用。 - Josh

Answer 1

如果您使用的C ++标准库支持，可以考虑使用 std::unordered_set 或 std::hash_set。

您也可以使用std::set，但它的开销可能会更高（这取决于生成对象哈希的成本与多次比较两个对象的成本之间的差异）。

如果您使用像set或unordered_set这样的基于节点的容器，则还可以获得元素删除相对便宜的优势，而不是从vector中进行删除。

- James McNellis

---

我认为你指的是 std::unordered_set 或者 std::tr1::unordered_set。 - Evan Teran

另外，std::hash_set 不是标准的一部分，如果你没有 TR1 或 c++0x，最好使用 boost::unordered_set。 - Evan Teran

@Evan：你说得对，我是指std::unordered_set。今天早上我还没喝咖啡。大多数标准库实现都以某种形式提供了hash_set。 - James McNellis

Answer 2

1. Tasks like this (set manipulations) are better left to what is MEANT to execute them - the database!

   E.g. something along the lines of:

    SELECT email FROM all_emails_table e WHERE NOT EXISTS (
        SELECT 1 FROM unsubscribed u where e.email=u.email
    )
   

2. If you want an ALGORITHM, you can do this fast by retrieving both the list of emails AND a list of unsubscriptions as ORDERED lists. Then you can go through the e-mail list (which is ordered), and as you do it you glide along the unsubscribe list. The idea is that you move 1 forward in whichever list has the "biggest" current" element. This algo is O(M+N) instead of O(M*N) like your current one

3. Or, you can do a hash map which maps from unsubscribed e-mail address to 1. Then you do find() calls on that map whcih for correct hash implementations are O(1) for each lookup. Unfortunately, there's no Hash Map standard in C++ - please see this SO question for existing implementations (couple of ideas there are SGI's STL hash_map and Boost and/or TR1 std::tr1::unordered_map).

   One of the comments on that post indicates it will be added to the standard: "With this in mind, the C++ Standard Library Technical Report introduced the unordered associative containers, which are implemented using hash tables, and they have now been added to the Working Draft of the C++ Standard."

- DVK

---

很遗憾，由于其中一个表格之前的布局方式，我无法为我的应用程序的某个部分完成这项任务。 - Josh

@Josh：你能发布一下你模式的相关部分吗？你是否有一个单独的表格来存储取消订阅的电子邮件？ - Daniel Trebbien

为什么不使用 LEFT OUTER JOIN？ SELECT \email` FROM `all_emails_table` AS `e` LEFT OUTER JOIN `unsubscribed` AS `u` ON `e`.`email` = `u`.`email` WHERE `u`.`email` IS NULL;` - Daniel Trebbien

@Daniel - 我来自TSQL背景，因此通过NOT EXISTS编写反连接对我来说比ANSI SQL的等效LEFT OUTER JOIN更自然。但两者基本相同（尽管从性能角度来看并非总是如此-谷歌搜索“anti-join performance outer exists”或类似内容以获取各种数据库服务器的几篇优秀文章-我知道有一些适用于MySQL和MS SQL）。 - DVK

Answer 3

将您的电子邮件地址存储在std::set中或使用std::set_difference()。

- Sven Marnach

---

+1 给 set_difference（因为它已经内置了），但我建议使用 3 个（排序后的）向量而不是集合，因为遍历它们应该会更快（更好的内存局部性）。或者，如果大小较大，并且您没有使用 Dirkumware（及其小桶），也可以考虑使用 deque。 - Matthieu M.

@Matthieu：当使用set_difference时，当然你会使用排序后的向量。还有什么？ - Sven Marnach

只是确认一下 :) 基于节点的容器可能非常慢。 - Matthieu M.

Answer 4

我认为最好的方法是在MySQL中完成。您可以使用另一列，即“取消订阅”BIT列，修改用户表模式。更好的做法是：添加一个“删除日期”DATETIME列，并将默认值设置为NULL。

如果使用BIT列，则查询变成了：

SELECT * FROM `users` WHERE `unsubscribed` <> 0b1;

如果使用 DATETIME 列，您的查询将变成以下形式：

SELECT * FROM `users` WHERE `date_unsubscribed` IS NULL;

- Daniel Trebbien

---

现在，您正在取消订阅用户。当前模式是取消订阅电子邮件地址，这并不完全相同。如果用户将其电子邮件地址更改为已取消订阅的地址，则应该停止接收消息吗？OP的方法是“是”，而这种方法是“否”，我猜更可能是正确答案。 - Steve Jessop