Tôi có một yêu cầu đơn giản, tôi cần bản đồ loại. tuy nhiên tôi cần thời gian truy xuất nhanh nhất về mặt lý thuyết.Sự khác biệt về hiệu suất giữa bản đồ và unordered_map trong C++
tôi đã sử dụng cả bản đồ và đề xuất unordered_map mới từ tr1 tôi thấy rằng ít nhất là khi phân tích cú pháp tệp và tạo bản đồ, bằng cách chèn phần tử vào thời điểm đó.
bản đồ chỉ mất 2 phút trong khi unordered_map mất 5 phút.
Vì tôi sẽ là một phần của mã được thực hiện trên cụm Hadoop và sẽ chứa ~ 100 triệu mục nhập, tôi cần thời gian truy xuất nhỏ nhất có thể.
Cũng có một thông tin hữu ích khác: hiện dữ liệu (khóa) đang được chèn vào là phạm vi số nguyên từ 1,2, ... đến ~ 10 triệu.
Tôi cũng có thể áp đặt người dùng để chỉ định giá trị tối đa và sử dụng thứ tự như trên, điều đó có ảnh hưởng đáng kể đến việc triển khai của tôi không? (I nghe bản đồ dựa trên cây rb và chèn thứ tự tăng dần dẫn đến hiệu suất tốt hơn (hoặc tồi tệ nhất)?)
đây là mã
map<int,int> Label // this is being changed to unordered_map
fstream LabelFile("Labels.txt");
// Creating the map from the Label.txt
if (LabelFile.is_open())
{
while (! LabelFile.eof())
{
getline (LabelFile,inputLine);
try
{
curnode=inputLine.substr(0,inputLine.find_first_of("\t"));
nodelabel=inputLine.substr(inputLine.find_first_of("\t")+1,inputLine.size()-1);
Label[atoi(curnode.c_str())]=atoi(nodelabel.c_str());
}
catch(char* strerr)
{
failed=true;
break;
}
}
LabelFile.close();
}
Giải pháp dự kiến: Sau khi xem xét ý kiến và câu trả lời, tôi tin rằng mảng Dynamic C++ sẽ là lựa chọn tốt nhất, vì việc triển khai sẽ sử dụng các khóa dày đặc. Cảm ơn
có từ kinh nghiệm dict của tôi trong python một bảng băm nên được nhanh hơn so với một bản đồ dựa trên cây nhị phân, nhưng ít nhất là để chèn i am tìm bản đồ để được nhanh hơn unordered_map. –
ya của nó có thể là rehashing sẽ dẫn đến tăng đáng kể trong thời gian cho insertions, kể từ khi tôi không cung cấp bất kỳ gợi ý về số lượng có thể của các yếu tố. –
vì vậy nó được bảo đảm để được O (1) trên chèn hay không tôi không thể nói? Anh ta đã làm gì sai? – jokoon