Самый быстрый C ++ контейнер: уникальные значения

Question

Я пишу почтовое приложение, которое взаимодействует с базой данных MySQL. У меня есть две таблицы, которые получают мои данные, одна из которых содержит отписки, а другая - стандартная таблица пользователей. На данный момент я создаю вектор указателей на объекты электронной почты и вначале сохраняю в нем все отписанные электронные письма. Затем у меня есть стандартный цикл SQL, в котором я проверяю, находится ли электронная почта в векторе отказа от подписки, а затем добавляю его в глобальный вектор отправки электронной почты. Мой вопрос: есть ли более эффективный способ сделать это? Я должен искать вектор неподписки для каждого отдельного письма в моей системе, вплоть до 50К разных. Есть ли лучшая структура для поиска? И лучшая структура для поддержания уникальной коллекции ценностей? Возможно, тот, который просто отбросит значение, если он уже содержит его?

Answer 1

Если ваша реализация Стандартной библиотеки C ++ поддерживает это, рассмотрите возможность использования std::unordered_set или std::hash_set.

Вы также можете использовать std::set, хотя его издержки могут быть выше (это зависит от стоимости создания хеш-функции для объекта по сравнению со стоимостью сравнения двух объектов несколько раз).

Если вы используете контейнер на основе узлов, такой как set или unordered_set, вы также получаете преимущество, заключающееся в том, что удаление элементов является относительно дешевым по сравнению с удалением из vector.

Answer 2

1. Задачи, подобные этой (манипуляции множеством), лучше оставить для того, что СЛЕДУЕТ выполнять их - базу данных!

   Например, что-то вроде:

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

2. Если вы хотите АЛГОРИТМ, вы можете сделать это быстро, получив как список электронных писем, так и список отписок в виде ЗАКАЗАННЫХ списков.Затем вы можете просмотреть список адресов электронной почты (который заказан), и, как только вы это сделаете, вы скользите по списку отписки.Идея состоит в том, что вы перемещаетесь на 1 вперед в том списке, который имеет «самый большой» текущий элемент. Этот алгоритм - O (M + N) вместо O (M * N), как ваш текущий

3. Или вы можете создать хеш-карту, которая сопоставляется с неподписанным адресом электронной почты в 1. Затем вы делаете find() вызовы на этой карте, для правильных реализаций хеш-функции - O (1) для каждого поиска. К сожалению, нетСтандарт Hash Map в C ++ - см. этот вопрос SO для существующих реализаций (есть пара идей: SGI STL hash_map и Boost и / или TR1 std::tr1::unordered_map).

   В одном из комментариев к этому сообщению указывается, что он будет добавлен в стандарт: «Имея это в виду, в Техническом отчете стандартной библиотеки C ++ представлены неупорядоченные ассоциативные контейнеры, которые реализованы с использованием хеш-таблиц, и теперь они добавлены вРабочий проект стандарта C ++. "

Answer 3

Храните адреса электронной почты в std::set или используйте std::set_difference().

Answer 4

Лучший способ сделать это, я думаю, в MySQL. Вы можете изменить схему таблицы пользователей с другим столбцом, столбцом BIT, для «отписался». Еще лучше: добавьте столбец DATETIME для «даты удаления» со значением по умолчанию NULL.

Если используется столбец BIT, ваш запрос будет выглядеть примерно так:

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

Если используется столбец DATETIME, ваш запрос будет выглядеть примерно так:

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