Najszybszy kontener C++: Unikalne wartości

Question

Piszę aplikację e-mail, która łączy się z bazą danych MySQL. Mam dwie tabele, które pobierają moje dane, z których jedna zawiera rezygnację z subskrypcji, a druga to standardowa tabela użytkowników. W tej chwili tworzę wektor wskaźników do obiektów e-mail i początkowo przechowuję w nim wszystkie niesubskrybowane e-maile. Mam wtedy standardową pętlę SQL, w której sprawdzam, czy e-mail nie znajduje się w wektorze anulowania, a następnie dodam go do globalnego wektora wysyłania wiadomości e-mail. Moje pytanie brzmi, czy istnieje skuteczniejszy sposób robienia tego? Muszę przeszukać wektor unsub dla każdego e-maila w moim systemie, do 50K różnych. Czy istnieje lepsza struktura do wyszukiwania? I lepszą strukturę do utrzymywania wyjątkowej kolekcji wartości? Być może taki, który po prostu odrzuciłby wartość, jeśli już to zawiera?

Answer 1

Jeśli implementacja biblioteki standardowej C++ ją obsługuje, należy rozważyć użycie std::unordered_set lub std::hash_set.

Można również użyć std::set, choć narzut ten może być wyższy (zależy to od kosztu wygenerowania skrótu dla obiektu w porównaniu z kosztem porównywania dwóch obiektów kilka razy).

Jeśli używasz pojemnika na bazie węzła jak set lub unordered_set, można również uzyskać tę zaletę, że usuwanie elementów jest stosunkowo tani w porównaniu do usuwania ze vector.

Answer 2

Zapisz swoje adresy e-mail w numerze std::set lub użyj std::set_difference().

Answer 3

1. Zadania tak (zestaw manipulacje) są lepiej pozostawić to, co ma na celu ich wykonania - baza danych!

   E.g. coś wzdłuż linii:

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

2. Jeśli chcesz algorytm, można to zrobić szybko, pobierając zarówno listę e-maile i listy unsubscriptions as ordered list. Następnie możesz przejrzeć listę e-mail (która jest zamówiona), a kiedy to zrobisz, przesuniesz się wzdłuż listy wypisania. Chodzi o to, że przesuwasz o 1 do przodu, w zależności od tego, który element ma "największy" bieżący element.To algo to O (M + N) zamiast O (M * N), takie jak bieżące:

3. Lub, możesz wykonaj mapowanie hash, które odwzorowuje z niesubskrybowanego adresu e-mail na 1. Następnie wykonujesz wywołania find() na tej mapie, dla poprawnych implementacji hash są O (1) dla każdego wyszukiwania Niestety, nie ma standardu Hash Map w C++ - zobacz this SO question for existing implementations (kilka pomysłów istnieją SGI STL hash_map i doładowania i/lub TR1 std::tr1::unordered_map)

   Jedna z uwag dotyczących tego stanowiska wskazuje, zostanie on dodany do normy. „Mając to na uwadze, standardowa biblioteka Raport techniczny C++ wprowadzony nieuporządkowanego asocjacyjne pojemniki, które są realizowane z wykorzystaniem tabel mieszania, a one zostały dodane do projektu Roboczej C++ standard.”

Answer 4

Najlepszym sposobem, aby to zrobić jest w MySQL, myślę. Możesz zmodyfikować schemat tabeli użytkowników za pomocą innej kolumny, kolumna BIT, ponieważ "nie jest subskrybowana". Co lepsze: dodaj kolumnę DATETIME dla "data usunięta" z domyślną wartością NULL.

Jeżeli stosując kolumnę BIT, zapytanie będzie coś takiego:

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

Jeżeli stosując kolumnę DATETIME, zapytanie będzie coś takiego:

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