Làm thế nào là std :: thiết lập chậm hơn std :: bản đồ?

Question

Tôi đã cố gắng giải quyết this problem from acm.timus.ru mà về cơ bản muốn tôi xuất số lượng các đoạn khác nhau của một chuỗi đã cho (độ dài tối đa 5000).

Các giải pháp mà tôi sắp trình bày tuyệt đối không hiệu quả và phải chịu số phận hạn chế thời gian vượt quá giới hạn cho các ràng buộc. Tuy nhiên, cách duy nhất trong đó hai giải pháp này khác nhau (ít nhất là tôi có thể thấy/hiểu) là sử dụng std::map<long long, bool>, còn cách khác sử dụng std::set <long long> (xem phần đầu của vòng lặp cuối cùng. có thể kiểm tra bằng bất kỳ công cụ tìm khác biệt nào). Giải pháp bản đồ kết quả trong "Giới hạn thời gian vượt quá thử nghiệm 3", trong khi giải pháp thiết lập kết quả trong "Giới hạn thời gian vượt quá thử nghiệm 2", có nghĩa là Phép thử 2 là giải pháp bản đồ hoạt động nhanh hơn so với giải pháp đã đặt. Đây là trường hợp nếu tôi chọn trình biên dịch Microsoft Visual Studio 2010. Nếu tôi chọn GCC, thì cả hai giải pháp dẫn đến TLE khi thử nghiệm 3.

Tôi không yêu cầu cách giải quyết vấn đề hiệu quả. Những gì tôi yêu cầu là làm thế nào người ta có thể giải thích rằng việc sử dụng std::map rõ ràng có thể hiệu quả hơn việc sử dụng std::set. Tôi chỉ không nhìn thấy cơ chế của hiện tượng này và hy vọng rằng ai đó có thể có bất kỳ thông tin chi tiết nào.

Code1 (sử dụng bản đồ, TLE 3):

#include <iostream> 
#include <map> 
#include <string> 
#include <vector> 

using namespace std; 

int main() 
{ 
    string s; 
    cin >> s; 
    vector <long long> p; 
    p.push_back(1); 
    for (int i = 1; i < s.size(); i++) 
     p.push_back(31 * p[i - 1]); 
    vector <long long> hash_temp; 
    hash_temp.push_back((s[0] - 'a' + 1) * p[0]); 
    for (int i = 1; i < s.size(); i++) 
     hash_temp.push_back((s[i] - 'a' + 1) * p[i] + hash_temp[i - 1]); 
    int n = s.size(); 
    int answer = 0; 
    for (int i = 1; i <= n; i++) 
    { 
     map <long long, bool> hash_ans; 
     for (int j = 0; j < n - i + 1; j++) 
     { 
     if (j == 0) 
      hash_ans[hash_temp[j + i - 1] * p[n - j - 1]] = true; 
     else 
      hash_ans[(hash_temp[j + i - 1] - hash_temp[j - 1]) * p[n - j - 1]] = true; 
     } 
     answer += hash_ans.size(); 
    } 
    cout << answer; 
} 

code2 (sử dụng bộ, TLE 2):

#include <iostream> 
#include <string> 
#include <vector> 
#include <set> 

using namespace std; 

int main() 
{ 
    string s; 
    cin >> s; 
    vector <long long> p; 
    p.push_back(1); 
    for (int i = 1; i < s.size(); i++) 
     p.push_back(31 * p[i - 1]); 
    vector <long long> hash_temp; 
    hash_temp.push_back((s[0] - 'a' + 1) * p[0]); 
    for (int i = 1; i < s.size(); i++) 
     hash_temp.push_back((s[i] - 'a' + 1) * p[i] + hash_temp[i - 1]); 
    int n = s.size(); 
    int answer = 0; 
    for (int i = 1; i <= n; i++) 
    { 
     set <long long> hash_ans; 
     for (int j = 0; j < n - i + 1; j++) 
     { 
     if (j == 0) 
      hash_ans.insert(hash_temp[j + i - 1] * p[n - j - 1]); 
     else 
      hash_ans.insert((hash_temp[j + i - 1] - hash_temp[j - 1]) * p[n - j - 1]); 
     } 
     answer += hash_ans.size(); 
    } 
    cout << answer; 
} 

Answer 1

Sự khác biệt thực tế tôi thấy (cho tôi biết nếu tôi bỏ lỡ bất cứ điều gì) là rằng trong trường hợp bản đồ bạn làm

hash_ans[key] = true; 

trong khi trong trường hợp bộ bạn làm

hash_ans.insert(key); 

Trong cả hai trường hợp, một phần tử được chèn vào, trừ khi nó đã tồn tại, trong đó nó không làm gì cả. Trong cả hai trường hợp, tra cứu cần tìm phần tử theo và chèn nó vào lỗi. Trong mỗi lần thực hiện hiệu quả ở đó, các thùng chứa sẽ sử dụng một cái cây, làm cho việc tra cứu không kém phần đắt đỏ. Thậm chí nhiều hơn, tiêu chuẩn C++ thực sự yêu cầu set::insert() và map::operator[]() là O (log n) phức tạp, do đó sự phức tạp của cả hai triển khai phải giống nhau.

Bây giờ, lý do nào khiến một hoạt động tốt hơn? Một điểm khác biệt là trong một trường hợp, một nút của cây nằm bên dưới chứa một số string, trong khi nút kia là số pair<string const, bool>. Vì cặp có chứa một chuỗi, nó phải lớn hơn và đặt thêm áp lực lên giao diện RAM của máy, vì vậy điều này không giải thích được sự tăng tốc. Những gì nó có thể làm là phóng to kích thước nút để các nút khác được đẩy ra khỏi dòng bộ nhớ cache, có thể là xấu cho hiệu suất trong hệ thống đa lõi.

Nói tóm lại, có một số điều tôi muốn thử:

1. sử dụng cùng một dữ liệu trong tập
   Tôi muốn làm điều này với struct data: string {bool b}; tức là bó chuỗi trong một cấu trúc mà cần phải có một tương tự bố cục nhị phân làm phần tử của bản đồ. Khi so sánh, hãy sử dụng less<string> để chỉ chuỗi thực sự tham gia vào so sánh.

2. sử dụng insert() trên bản đồ
   Tôi không nghĩ đây là vấn đề, nhưng chèn có thể xuất hiện một bản sao của đối số, ngay cả khi không có chèn diễn ra vào cuối. Tôi hy vọng rằng nó không mặc dù, vì vậy tôi không quá tự tin điều này sẽ thay đổi bất cứ điều gì.

3. tắt gỡ lỗi
   Hầu hết các triển khai đều có chế độ chẩn đoán, nơi các trình vòng lặp được xác thực. Bạn có thể sử dụng điều này để bắt lỗi mà C++ chỉ nói "hành vi không xác định", nhún vai và va chạm vào bạn. Chế độ này thường không đáp ứng được sự đảm bảo phức tạp và nó luôn có một số chi phí.

4. đọc mã
   Nếu triển khai tập hợp và bản đồ có các mức chất lượng và tối ưu hóa khác nhau, điều này có thể giải thích sự khác biệt. Dưới mui xe, tôi mong đợi cả hai bản đồ và thiết lập được xây dựng trên cùng một loại cây mặc dù, do đó, không có nhiều hy vọng ở đây cả.

Answer 2

Một tập hợp duy nhất là nhanh hơn một chút so với bản đồ trong trường hợp này Tôi đoán. Tuy nhiên tôi không nghĩ rằng bạn nên trường hợp nhiều như TLE 2 hoặc TLE 3 không thực sự là một việc lớn. Nó có thể xảy ra nếu bạn là clsoe đến giới hạn thời gian mà cùng một thời gian giải pháp giới hạn trên thử nghiệm 2 trên một gửi nhất định và thời gian tới nó giới hạn thời gian thử nghiệm 3. Tôi có một số giải pháp vượt qua các bài kiểm tra chỉ trên thời gian giới hạn và tôi đặt cược nếu Tôi gửi lại cho họ họ sẽ thất bại.

Vấn đề cụ thể này tôi đã giải quyết bằng cách sử dụng cây Ukonen Sufix.

Answer 3

Phụ thuộc vào thuật toán triển khai được sử dụng. Thông thường, các bộ được triển khai bằng bản đồ chỉ sử dụng trường khóa. Trong trường hợp như vậy sẽ có một chi phí rất nhỏ cho việc sử dụng một bộ như trái ngược với một bản đồ.