Pagina 2 di 6 primaprima 1 2 3 4 ... ultimoultimo
Visualizzazione dei risultati da 11 a 20 su 55
  1. #11
    Ok, ho fatto qualche prova io in C++ con un programma di test di questo tipo:
    codice:
    #include <vector>
    #include <algorithm>
    #include <stdlib.h>
    #include <iostream>
    #include <unordered_map>
    #include <map>
    
    const int comb_n = 233;
    const int tot_count = 172400;
    
    int main() {
        std::string sz = "abcdefghijklm";
        std::vector<std::string> combs;
        for(int i=0; i<comb_n; ++i) {
            std::random_shuffle(sz.begin(), sz.end());
            combs.push_back(sz);
        }
    
        {
            std::cout<<"Lineare\n";
            std::vector<std::pair<std::string, unsigned>> count_v;
            for(auto &sz: combs) {
                count_v.push_back(std::make_pair(sz, 0U));
            }
            for(int i=0; i<tot_count*comb_n; ++i) {
                const std::string &key = combs[rand()%comb_n];
                for(auto &it: count_v) {
                    if(it.first == key) {
                        it.second++;
                        break;
                    }
                }
            }
            std::cout<<"Fine lineare!\n";
    
            std::cout<<"Dicotomica\n";
            std::sort(count_v.begin(), count_v.end());
            for(int i=0; i<tot_count*comb_n; ++i) {
                const std::string &key = combs[rand()%comb_n];
                auto it = std::lower_bound(count_v.begin(), count_v.end(), key,
                        [](const std::pair<std::string, int> &a, const std::string &b) {
                            return a.first < b;
                        });
                it->second++;
            }
            std::cout<<"Fine dicotomica\n";
        }
    
        {
            std::cout<<"Hashtable\n";
            std::unordered_map<std::string, unsigned> count_h;
            for(int i=0; i<tot_count*comb_n; ++i) {
                const std::string &key = combs[rand()%comb_n];
                count_h[key]++;
            }
            std::cout<<"Fine hashtable\n";
        }
    
        {
            std::cout<<"Map\n";
            std::map<std::string, unsigned> count_h;
            for(int i=0; i<tot_count*comb_n; ++i) {
                const std::string &key = combs[rand()%comb_n];
                count_h[key]++;
            }
            std::cout<<"Fine map\n";
        }
        return 0;
    }
    I risultati:
    codice:
    [mitalia@mitalia ~/scratch/lookup]$ stdbuf -o0 ./lookup.x | ts -i '%.s'
    0.000017 Lineare
    34.237293 Fine lineare!
    0.000084 Dicotomica
    6.239760 Fine dicotomica
    0.000086 Hashtable
    1.640778 Fine hashtable
    0.000086 Map
    3.793371 Fine map
    (i valori che contano sono quelli delle righe "Fine xxx", e si riferiscono a 233*172400 lookup fatti in ordine casuale)

    Vince la hashtable di default fornita con libstdc++, che sembra usare murmurhash2 come funzione di hashing.
    Amaro C++, il gusto pieno dell'undefined behavior.

  2. #12
    Niente male anche le trie; con un'implementazione abbastanza povera (senza check che l'elemento sia un terminale e con payload su ogni nodo) ma con interi piccoli come indici e "frozen trie" con un vector come backend (dopo aver costruito il tutto con la deque per evitare riallocazioni del vettore durante il lookup) per guadagnare un 30% in prestazioni, il risultato è competitivo con la hashtable.

    Trie:
    codice:
    template<typename T>
    struct trie_node {
        uint16_t next[26] = {0};
        T payload = T();
    
        template<typename TCont>
        trie_node *lookup(const char *sz, bool add, TCont &alloc) {
            if(*sz==0) return this;
            uint16_t &n = next[*sz-'a'];
            if(n==0) {
                if(add) {
                    n = alloc.size();
                    alloc.push_back(trie_node());
                } else {
                    return nullptr;
                }
            }
            return alloc[n].lookup(sz+1, add, alloc);
        }
    };
    
    template<typename T>
    struct trie {
        std::deque<trie_node<T>> nodes;
        trie_node<T> *lookup(const char *sz, bool add) {
            return nodes[0].lookup(sz, add, nodes);
        }
    
        trie() {
            nodes.resize(1);
        }
    };
    
    template<typename T>
    struct frozen_trie {
        std::vector<trie_node<T>> nodes;
        trie_node<T> *lookup(const char *sz) {
            return nodes[0].lookup(sz, false, nodes);
        }
    
        frozen_trie(trie<T> &orig) : nodes(orig.nodes.begin(), orig.nodes.end()) {}
    };
    Codice in coda al main:
    codice:
        {
            std::cout<<"Trie\n";
            trie<unsigned> count_t;
            for(auto &sz: combs) {
                count_t.lookup(sz.c_str(), true);
            }
            frozen_trie<unsigned> count_t_frozen(count_t);
            for(int i=0; i<tot_count*comb_n; ++i) {
                const std::string &key = combs[rand()%comb_n];
                count_t_frozen.lookup(key.c_str())->payload++;
            }
            std::cout<<"Fine trie\n";
        }
    Risultati:
    codice:
    [mitalia@mitalia ~/scratch/lookup]$ stdbuf -o0 ./lookup.x | ts -i '%.s'
    0.000019 Lineare
    33.315037 Fine lineare!
    0.000230 Dicotomica
    6.158021 Fine dicotomica
    0.000079 Hashtable
    1.610438 Fine hashtable
    0.000084 Map
    3.777893 Fine map
    0.000089 Trie
    2.120793 Fine trie
    Amaro C++, il gusto pieno dell'undefined behavior.

  3. #13
    Sistemando un po' il codice della trie (per cui neanche serve più il pasticcio della frozen_trie) direi che siamo quasi a pari con l'hashtable:
    codice:
    template<typename T>
    struct trie {
        struct trie_node {
            uint16_t next[26] = {0};
            T payload = T();
        };
    
        std::vector<trie_node> nodes;
    
        trie_node *lookup(const char *sz, bool add, uint16_t cur = 0) {
            trie_node *it = &nodes[cur];
            if(*sz==0) return it;
            uint16_t *n = &it->next[*sz-'a'];
            if(n==0) {
                if(add) {
                    *n = nodes.size();
                    nodes.push_back(trie_node());
                    // possibile riallocazione, ricalcola tutto
                    it = &nodes[cur];
                    n = &it->next[*sz-'a'];
                } else {
                    return nullptr;
                }
            }
            return lookup(sz+1, add, *n);
        }
    
        trie() {
            nodes.resize(1);
        }
    };
    codice:
        {
            std::cout<<"Trie\n";
            trie<unsigned> count_t;
            for(int i=0; i<tot_count*comb_n; ++i) {
                const std::string &key = combs[rand()%comb_n];
                count_t.lookup(key.c_str(), true)->payload++;
            }
            std::cout<<"Fine trie\n";
        }
    codice:
    [mitalia@mitalia ~/scratch/lookup]$ stdbuf -o0 ./lookup.x | ts -i '%.s'
    0.000014 Lineare
    32.403874 Fine lineare!
    0.000093 Dicotomica
    6.345617 Fine dicotomica
    0.000073 Hashtable
    1.579729 Fine hashtable
    0.000076 Map
    3.749461 Fine map
    0.000074 Trie
    1.736539 Fine trie
    Tutto questo con il caveat che le chiavi sono solo alfabetici minuscoli; se però d'altro canto si sa che in tutto possono essere al più 13 caratteri diversi, si può diminuire il numero di nodi della trie aggiungendo una tabella di lookup per convertire i caratteri della chiave nel corrispondente indice 0-13.
    Amaro C++, il gusto pieno dell'undefined behavior.

  4. #14
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Dillo, avevi solo voglia di sperimentare ed eri annoiato!
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  5. #15
    Naturale, qualunque cosa è meglio del refactoring che sto affrontando al lavoro.

    (eppoi le trie sono una delle mie strutture dati preferita da quando le ho scoperte qualche anno fa per scrivere il solutore di Ruzzle )
    Ultima modifica di MItaly; 30-08-2017 a 15:16
    Amaro C++, il gusto pieno dell'undefined behavior.

  6. #16
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Quote Originariamente inviata da MItaly Visualizza il messaggio
    Naturale, qualunque cosa è meglio del refactoring che sto affrontando al lavoro.

    (eppoi le trie sono una delle mie strutture dati preferita da quando le ho scoperte qualche anno fa per scrivere il solutore di Ruzzle )
    Ah, quindi ti ho fatto venire voglia di testare parlandone?
    Comunque, a parte gli scherzi, sappiamo ben poco sulla natura di queste fantomatiche distribuzioni di 13 caratteri, sulla loro lunghezza e sulla loro distribuzione. Quindi è difficile fare una comparazione abbastanza fedele all'uso. Per esempio il tuo codice di test utilizza delle permutazioni, ma avendo @zacca94 parlato solamente di distribuzioni non sappiamo nulla sulla possibile lunghezza e sulla forma effettiva di queste distribuzioni. Potrebbero essere stringhe di 200 caratteri o di 3. La lunghezza effettiva della stringa potrebbe incidere notevolmente sulle performance relative.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  7. #17
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,316
    Oh grazie, a breve provo e ti do i risultati

  8. #18
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Any news? La cosa mi interessava
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  9. #19
    Mi associo, tutte queste prove e neanche la soddisfazione di sapere com'è andata a finire la cosa?
    Amaro C++, il gusto pieno dell'undefined behavior.

  10. #20
    Utente di HTML.it
    Registrato dal
    Jun 2008
    Messaggi
    1,316
    pazientate ancora un pò per favore

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.