Wydajność złożonej struktury

0

W aplikacji mam dane w postaci:

struct Data
{
    QString scope;
    QString name;
    QVariant value;
};

typedef QString Scope;
QHash<Scope, QList<Data>> data;

Możemy do struktury dodawać nowe przestrzenie nazw a do nich zmienne z wartościami lub dodawać nowe zmienne do już istniejących przestrzeni nazw o ile nie występuje konflikt nazw.

Problem w tym że do jednoznacznego zdefiniowania zmiennej potrzebujemy zmiennych scope i name a więc w tym wypadku wyszukiwanie mogłoby wyglądać tak :

 
Data value(const QString &scope, const QString &name)
{
    if( data.contains(scope) ) {
        QList<Data> list = data.value(scope);
        auto it = std::find_if(list.begin(), list.end(),
                  [&](const Data & d)->bool{ return d.name == name; });
        return *it;
    }
}

a gdyby strukture zdefiniować tak

typedef QString Name;
QHash<Scope, QHash<Name, Data>> data;

i wyszukiwanie wygląda już lepiej

Data value(const QString &scope, const QString &name)
{
    if( data.contains(scope) ) {
        if( data.value(scope).contains(name) )
            return data.value(scope).value(name);
    }
}

czy druga opcja jest najlepszą w tym wypadku? dublujemy trochę danych bo dla każdej struktury mamy dodatkowe 2 zmienne QString które są w QHash w celu identyfikacji.

0

Niech n będzie liczbą itemów typu Data w całym kontenerze data. W kontekście złożoności obliczeniowej pierwsza wersja funkcji 'value' wykonuje jeden lookup w tablicy haszującej + iterację po liście co kosztuje średnio O(1) * O(n) = O(n). Druga wersja jest lepsza bo mamy dwa lookup-y po hasz tablicy co daje średnio O(1) + O(1) czyli tylko O(1).
Jeszcze więcej wyciśniesz jeśli zmienisz typ Data na coś a'la

 
struct Data
{
    QString scopeAndName;
    QVariant value;
};

gdzie scopeAndName jest skonkatenowanym string-em oraz typ kontenera na

 
QHash<Scope, Data> data;

Nie musisz wtedy rozdrabniać się na 2 lookup-y/contains, wystarczy tylko jeden contains. Złożoność (zamortyzowana/średnia) się nie zmieni, ale layout w pamięci stanie się znacznie bardziej cache-friendly (jedna tablica haszująca w jednym zwartym obszarze pamięci) przez co "value" powinna przyspieszyć.
Oczywiście takie rozwiązanie ma też wadę - scope i name są trzymane w jednym string-u więc od tej pory wyłuskanie Name-a będzie nieco bardziej kłopotliwe.
Chętnie zobaczyłbym jakiś benchmark dla wszystkich 3 wersji 'value'.

Ref: http://doc.qt.io/qt-5/containers.html#algorithmic-complexity

1

To nie będzie odpowiedź, ale na etapie projektowania nie zastanawiaj się nad takimi optymalizacjami. Napisz prościej, czytelniej i wygodniej w użyciu, a potem odpal profiler i dopiero jak on Ci pokaże, że wyszukiwanie zżera za dużo czasu to nad Tym przysiądź.

Oczywiście fajnie jest pisać jak najoptymalniejszy kod. Zależy jakie masz priorytety

0

Niestety w niektórych przypadkach "potem" może być już za późno i trzeba takie rzeczy projektowe przemyśleć jeszcze przed napisaniem 1 linijki kodu.

Doszedłem do tego że jeśli konkretną wartość definiuje przestrzeń tej wartości( scope ) i jej nazwa( name ) to dobrym rozwiązaniem może być taka struktura:

QHash<QPair<Scope, Name>, Data> data;

oszczędzi to wielu dodatkowych wyszukiwań jak find_if a jedynym minusem będzie tworzenie lokalnych par podczas wyszukiwania wartości np

if( !data.contains(qMakePair(scope, name)) )
        return data.value(qMakePair(scope, name));

1 użytkowników online, w tym zalogowanych: 0, gości: 1