Vùng chứa C++ nhanh nhất: Giá trị duy nhất

Question

Tôi đang viết một ứng dụng email có giao diện với cơ sở dữ liệu MySQL. Tôi có hai bảng được tìm nguồn cung ứng dữ liệu của tôi, một trong số đó có chứa unsubscriptions, một trong số đó là một bảng người dùng chuẩn. Hiện tại, tôi đang tạo một vectơ con trỏ để gửi các đối tượng email và lưu trữ tất cả các email chưa đăng ký trong đó, ban đầu. Sau đó tôi có một vòng lặp SQL chuẩn, trong đó tôi đang kiểm tra xem email có nằm trong vector hủy đăng ký hay không, sau đó thêm nó vào vectơ gửi email chung. Câu hỏi của tôi là, có cách nào hiệu quả hơn để làm việc này không? Tôi phải tìm kiếm các vector unsub cho mỗi email duy nhất trong hệ thống của tôi, lên đến 50K khác nhau. Có cấu trúc tốt hơn để tìm kiếm không? Và, một cấu trúc tốt hơn để duy trì một tập hợp các giá trị duy nhất? Có lẽ một trong đó chỉ đơn giản là sẽ loại bỏ giá trị nếu nó đã có nó?

Answer 1

Nếu triển khai Thư viện chuẩn C++ của bạn hỗ trợ, hãy xem xét sử dụng std::unordered_set hoặc std::hash_set.

Bạn cũng có thể sử dụng std::set, mặc dù chi phí của nó có thể cao hơn (phụ thuộc vào chi phí tạo băm cho đối tượng so với chi phí so sánh hai đối tượng nhiều lần).

Nếu bạn sử dụng vùng chứa dựa trên nút như set hoặc unordered_set, bạn cũng có được lợi thế là việc loại bỏ các phần tử tương đối rẻ so với việc xóa khỏi một số vector.

Answer 2

Lưu trữ địa chỉ email của bạn trong một số std::set hoặc sử dụng std::set_difference().

Answer 3

1. Nhiệm vụ như thế này (đặt thao tác) là tốt hơn để MEANT thực hiện chúng - cơ sở dữ liệu!

   Ví dụ: cái gì đó dọc theo dòng:

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

2. Nếu bạn muốn một thuật toán, bạn có thể làm điều này nhanh chóng bằng cách lấy cả hai danh sách các thư và danh sách hủy đăng ký như danh sách đặt hàng. Sau đó, bạn có thể đi qua danh sách e-mail (được đặt hàng), và khi bạn làm điều đó bạn lướt dọc theo danh sách hủy đăng ký. Ý tưởng này là bạn di chuyển 1 về phía trước trong danh sách nào có phần tử "lớn nhất" hiện tại. Bản ngã này là O (M + N) thay vì O (M * N) như hiện tại của bạn

3. Hoặc bạn có thể làm một bản đồ băm mà bản đồ từ địa chỉ e-mail chưa đăng ký để 1. Sau đó, bạn làm find() các cuộc gọi trên bản đồ đó để thực hiện băm chính xác là O (1) cho mỗi tra cứu Thật không may, không có tiêu chuẩn Hash Map trong C++ - vui lòng xem this SO question for existing implementations (một số ý tưởng có số STL hash_map của SGI và Tăng và/hoặc TR1 std::tr1::unordered_map).

   Một trong những nhận xét về bài đăng đó cho biết nó sẽ được thêm vào tiêu chuẩn: "Với điều này, trong báo cáo kỹ thuật thư viện chuẩn C++ giới thiệu các container kết hợp có thứ tự, được triển khai sử dụng bảng băm, và họ hiện nay đã được bổ sung vào Dự thảo làm việc của ++ Chuẩn C."

Answer 4

Cách tốt nhất để làm điều này là trong MySQL, tôi nghĩ vậy. Bạn có thể sửa đổi giản đồ bảng người dùng của mình với một cột khác, một cột BIT, cho "bị hủy đăng ký". Tốt hơn: thêm một cột DATETIME cho "ngày bị xóa" với giá trị mặc định là NULL.

Nếu sử dụng một cột BIT, truy vấn của bạn trở nên một cái gì đó như:

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

Nếu sử dụng một cột DATETIME, truy vấn của bạn trở nên một cái gì đó như:

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