Две хеш-таблицы с одинаковым ключом против комбинированного хеша

Question

Мне интересно, какие реализации (ниже) дадут мне лучшую производительность во времени и пространстве.Допустим, у меня есть следующая структура каталогов.

/dir1
    OWN={root,usr}
/dir2
    DEP={dir1}
    OWN={usr}

Я однократно прошёл все директории из "./", где у каждого каталога есть файл владельца и может быть файл зависимости.Я читаю их содержание и создаю хеш-таблицы.

#include <iostream>
#include <unordered_map>

using namespace std;

int main(int argc, char** argv){

    unordered_map<string, vector<string>> dir_ownerss;
    // /dir1 --> [root, usr]
    // /dir2 --> [usr]
    unordered_map<string, vector<string>> dir_dependenciess;
    // /dir1 --> [dir2]

    unordered_map<string, vector<vector<string>>> dir_owners_and_dependenciess;
    // /dir1 --> [ [/dir1, root, usr] [/dir2, usr] ]
    // /dir2 --> [ [/dir2, usr] ]

    return 0;
}   

Позже в этой программе я выполню некоторые операции поиска или поиска () для проверки принадлежности и зависимостей.Поскольку операции хеширования в среднем равны O (1), то в порядке порядка я не вижу разницы.Один требует двух вызовов find (), другой - одного вызова, но, возможно, не предпочтителен из-за хеширования, пробела, ... Кроме того, в плане дизайна нет предела.

Answer 1

Чтобы ответить на ваши вопросы:

1. Множественный поиск O (1) будет дороже, чем один поиск O (1).Обновление нескольких карт также занимает больше времени при добавлении или удалении элемента.
2. Существует определенное количество накладных расходов на хранение ключей и тому подобное для карты.С одной картой вы платите эти накладные расходы один раз.С несколькими картами вы платите несколько раз.

Конечно, это все O (1) для поиска и O (n) для памяти, но две карты занимают вдвое больше памяти.В два раза больше поисков занимает вдвое больше времени.

Я думаю, вам будет лучше, если использовать одну карту, в которой в качестве значения используется класс.(Прошу прощения за синтаксис; C ++ - это не то, с чем я работаю каждый день.)

class directory {
    vector<string> owners;
    vector<string> dependencies;
}

И тогда ваша карта станет такой:

unordered_map<string, directory> directories;

Так что, если вы хотите что-то узнать оконкретный каталог, вы посмотрите этот каталог на карте.Вы имеете непосредственный доступ к владельцам и зависимостям.Нет причин иметь отдельную карту для каждого отдельного атрибута.

Еще одно преимущество использования одной карты, в которой хранится класс: это упрощает ваш код.И это всегда хорошо.