Tìm kiếm chuỗi nhanh?

Question

Tôi có một chuỗi các chuỗi và phải kiểm tra xem mỗi phần tử trong vectơ có xuất hiện trong danh sách 5000 từ đã cho hay không. Bên cạnh phương pháp trần tục của hai vòng lồng nhau, có cách nào nhanh hơn để thực hiện điều này trong C++ không?

Answer 1

Bạn nên đặt danh sách các chuỗi vào một số std::set. Đó là cấu trúc dữ liệu được tối ưu hóa để tìm kiếm. Tìm kiếm nếu một phần tử đã cho trong tập hợp hay không là một hoạt động nhanh hơn nhiều so với việc lặp lại tất cả các mục nhập.

Khi bạn đã sử dụng C++ 11, bạn cũng có thể sử dụng số std::unordered_set thậm chí còn nhanh hơn để tra cứu, vì nó được triển khai dưới dạng bảng băm.

Đây có phải là trường học/đại học: Hãy chuẩn bị để giải thích cách các cấu trúc dữ liệu này quản lý nhanh hơn. Khi người hướng dẫn của bạn yêu cầu bạn giải thích lý do tại sao bạn sử dụng chúng, "một số người trên internet nói với tôi" không có khả năng kiếm cho bạn một nhãn dán trong cuốn sách lớp học.

Answer 2

Bạn có thể đặt danh sách các từ trong một số std::unordered_set. Sau đó, đối với mỗi phần tử trong vectơ, bạn chỉ cần kiểm tra nếu nó nằm trong unordered_set trong O (1). Bạn sẽ có một sự phức tạp kỳ vọng của O (n) (xem xét nhận xét để xem tại sao nó chỉ được mong đợi).

Answer 3

Bạn có thể sắp xếp véc tơ, sau đó bạn có thể giải quyết vấn đề này bằng một "vòng lặp" (nghĩa là từ điển của bạn cũng được sắp xếp) có nghĩa là O (n) không tính vào chi phí sắp xếp.

Answer 4

Vì vậy, bạn có vectơ chuỗi, với mỗi chuỗi có một hoặc nhiều từ và bạn có vectơ là từ điển và bạn phải xác định từ nào trong vectơ của chuỗi cũng có trong từ điển? Vector của chuỗi là một ít phiền toái, vì bạn cần phải nhìn vào từng từ. Tôi bắt đầu bằng cách tạo một vectơ mới, tách từng chuỗi thành các từ và đẩy mỗi từ vào vectơ mới. Sau đó, sắp xếp vectơ mới và chạy nó thông qua thuật toán std::unique để loại bỏ các bản sao. Sau đó, sắp xếp từ điển. Sau đó chạy cả hai phạm vi qua std::set_intersection để ghi kết quả.