Std::unordered_map::emplace работает медленнее, чем оператор[] в LeetCode [закрыто] ⇐ C++

[Anonymous]

Я решал ежедневную задачу LeetCode: https://leetcode.com/problems/step-by-s ... o-another/
Мой ответ был следующим:

Код: Выделить всё

class Solution {
unordered_map parentMap;
TreeNode* startNode;
int startVal;
int destVal;
unordered_set visitedNodes;
string result;

void FindParent(TreeNode* root) {
if (root->val == startVal) {
startNode = root;
}

if (root->left) {
parentMap.emplace(root->left->val, root);
FindParent(root->left);
}

if (root->right) {
parentMap.emplace(root->right->val, root);
FindParent(root->right);
}
}

bool Solve(TreeNode* node) {
if (node->val == destVal) {
return true;
}

visitedNodes.emplace(node->val);

if (node->left && !visitedNodes.count(node->left->val)) {
result += 'L';

if (Solve(node->left)) {
return true;
}
}

if (node->right && !visitedNodes.count(node->right->val)) {
result += 'R';

if (Solve(node->right)) {
return true;
}
}

if (auto it = parentMap.find(node->val); it != parentMap.end() && !visitedNodes.count(it->second->val)) {
result += 'U';

if (Solve(it->second)) {
return true;
}
}

result.pop_back();
return false;
}

public:
string getDirections(TreeNode* root, int startValue, int destValue) {
startVal = startValue;
destVal = destValue;
FindParent(root);
Solve(startNode);
return result;
}
};

После отправки я получил время выполнения 2883 мс. Учитывая, что временная сложность моего ответа равна O(n), он был невероятно медленным. Я попытался изменить часть своего кода, сохранив ту же логику, например. используя BFS вместо DFS при поиске необходимого пути, но я не смог найти причину медленной работы моего кода.
Думаю, что это не проблема использования emplace , я попытался заменить все emplace на оператор[], чтобы выполнить вставку карты в функции FindParent(TreeNode* root), и время выполнения стало 397 мс. Я был шокирован и не могу придумать разумного объяснения происходящему. Это было не просто быстрее; это было более чем в 6 раз быстрее!
Я знаю, что при использовании emplace пара ключ-значение все равно может быть создана, даже если ключ уже существовал в карте. Но я обходил дерево, а это означает, что к каждому узлу обращались только один раз, и, следовательно, никакие две вставки не имели один и тот же ключ. Следовательно, это не должно быть причиной. Я также пытался использовать try_emplace, и время выполнения стало 1638 мс.
Я пытался отправить несколько раз с каждым методом вставки, но результат не изменился. слишком. Чтобы прояснить ситуацию, я суммирую время выполнения каждого метода вставки ниже:

Код: Выделить всё

emplace    : 2883 ms
try_emplace: 1638 ms
operator[] :  397 ms

Чтобы увидеть, действительно ли производительность каждого метода вставки соответствует результату, полученному LeetCode, я провел здесь быстрый тест C++: https://quick-bench.com/q/ KwjHYKLEVS__-tGzcbVHvDQUvvE.
Я не уверен, нужно ли это, но скопирую фрагмент и вставлю сюда:

Код: Выделить всё

#include 

constexpr int TREE_DEPTH = 16;

struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

void ConstructTree(TreeNode* root, int level) {
if (level > TREE_DEPTH) {
return;
}

int child = (root->val + 1) * 2 - 1;
root->left = new TreeNode(child);
ConstructTree(root->left, level + 1);
root->right = new TreeNode(child + 1);
ConstructTree(root->right, level + 1);
}

TreeNode* root = []() {
TreeNode* root = new TreeNode(0);
ConstructTree(root, 1);
return root;
}();

void FindParentByEmplace(TreeNode* root, std::unordered_map& parentMap) {
if (root->left) {
parentMap.emplace(root->left->val, root);
FindParentByEmplace(root->left, parentMap);
}

if (root->right) {
parentMap.emplace(root->right->val, root);
FindParentByEmplace(root->right, parentMap);
}
}

void FindParentByTryEmplace(TreeNode* root, std::unordered_map& parentMap) {
if (root->left) {
parentMap.try_emplace(root->left->val, root);
FindParentByTryEmplace(root->left, parentMap);
}

if (root->right) {
parentMap.try_emplace(root->right->val, root);
FindParentByTryEmplace(root->right, parentMap);
}
}

void FindParentByIndex(TreeNode* root, std::unordered_map& parentMap) {
if (root->left) {
parentMap[root->left->val] = root;
FindParentByIndex(root->left, parentMap);
}

if (root->right) {
parentMap[root->right->val] = root;
FindParentByIndex(root->right, parentMap);
}
}

static void TestEmplace(benchmark::State& state) {
for (auto _ : state) {
std::unordered_map parentMap;
FindParentByEmplace(root, parentMap);
benchmark::DoNotOptimize(parentMap);
}
}

BENCHMARK(TestEmplace);

static void TestTryEmplace(benchmark::State& state) {
for (auto _ : state) {
std::unordered_map parentMap;
FindParentByTryEmplace(root, parentMap);
benchmark::DoNotOptimize(parentMap);
}
}

BENCHMARK(TestTryEmplace);

static void TestIndex(benchmark::State& state) {
for (auto _ : state) {
std::unordered_map parentMap;
FindParentByIndex(root, parentMap);
benchmark::DoNotOptimize(parentMap);
}
}

BENCHMARK(TestIndex);

В тесте производительности я создал идеальное двоичное дерево и использовал ту же логику поиска родительских элементов для построения unordered_map, каждая из которых использует один из emplace, try_emplace и оператор[]. Кроме того, чтобы максимально точно имитировать среду C++, используемую LeetCode, я использую следующую настройку для запуска теста:

Код: Выделить всё

Compiler        : Clang 11.0
Standard Version: C++17
Optimization    : O2

Это изображение результата теста
Из изображения ясно видно, что производительность emplace не это плохо. Фактически, emplace является самым быстрым методом вставки среди всех трех методов, за ним следует оператор[], а самым медленным является try_emplace. Это означает, что результат LeetCode не отражает реальную производительность этих трех методов вставки (по крайней мере, по результатам быстрого теста).
Мой тест производительности может быть плохо спроектирован, но Я уже изо всех сил старался смоделировать вариант использования как можно ближе. Итак, мой вопрос:

• Действительно ли результат LeetCode неточный?
• Если он действительно неточный, то почему? Я знаю, что, вероятно, никто не может дать уверенный ответ, но мне просто любопытно.
• Если нет, то вы можете судить, насколько плохо был разработан мой тест производительности. Но вместо этого я хотел бы знать, почему emplace работает так медленно в этой ситуации?

Извините, что не могу дать вам < em>минимально воспроизводимый пример, поскольку его можно воспроизвести только на платформе LeetCode (насколько я могу), а это означает, что мой код должен пройти все тестовые примеры, предоставленные LeetCode, чтобы получить результат времени выполнения, что делает мой код код практически не минимизируется.

Подробнее здесь: https://stackoverflow.com/questions/787 ... n-leetcode