trieツリーとhashテーブルの検索速度の比較

#include 

#include 

#include 

#include 

#include "trie_tree.h"

using namespace std;

int trie_null(void * v, int f)

{

         return 0;

}

class StrHash

{

public:

         size_t operator()(const std::string &s) const

         {

                   unsigned int hash = 1315423911;

                   const char *str = s.c_str();

                   while (*str)

                   {

                            if (*str >= 'A' && *str <= 'Z')

                                     hash ^= ((hash << 5) + (*str++ + ('a' - 'A')) + (hash >> 2));

                            else

                                     hash ^= ((hash << 5) + (*str++) + (hash >> 2));

                   }

                   return (hash & 0x7FFFFFFF);

         }



};

class IgnoreCaseComparator

{

public:

         bool operator()(const std::string &s1, const std::string &s2) const

         {

                   return (strcasecmp(s1.c_str(), s2.c_str()) == 0);

         }

};

typedef std::tr1::unordered_map<const std::string, unsigned long, StrHash,

                   IgnoreCaseComparator> NameTblmetaMap;

int main()

{

         trie_tree m_table;

         NameTblmetaMap m_tables;

         init_trie_tree(&m_table, 100000, trie_null, 0);

         for (long i = 11100000; i < 11110000; i++)

         {

                   char buf[20] =

                   { 0 };

                   sprintf(buf, "%ld", i);

                   m_tables[string(buf)] = i;

                   insert_trie_tree(&m_table, (unsigned char*) buf, (void*) i);

         }

         string *slist = new string[1000];

         char ** plist = new char*[1000];

         for (int i = 0; i < 1000; i++)

         {

                   plist[i] = new char[20];

                   sprintf(plist[i], "%ld", i + 11100000);

                   slist[i] = string(plist[i]);

         }

         struct timespec s, e;

         clock_gettime(CLOCK_REALTIME, &s);

         for (int i = 0; i < 100000; i++)

         {

                   for (int j = 0; j < 1000; j++)

                   {

                            get_trie_tree_value(&m_table, (unsigned char*) plist[j]);

                   }

         }

         clock_gettime(CLOCK_REALTIME, &e);

         printf("trie %lu
",

                            (e.tv_sec - s.tv_sec) * 1000000000 + e.tv_nsec - s.tv_nsec);

         clock_gettime(CLOCK_REALTIME, &s);



         for (int i = 0; i < 100000; i++)

         {

                   for (int j = 0; j < 1000; j++)

                   {

                            m_tables.find(slist[j]);

                   }

         }

         clock_gettime(CLOCK_REALTIME, &e);

         printf("unordered_map  %lu
",

                            (e.tv_sec - s.tv_sec) * 1000000000 + e.tv_nsec - s.tv_nsec);

}

10000個のレコードを挿入し、そのうち1000個のレコードを検索し、100000輪を作ります.
Trieツリーの消費時間は3251830320 ns
Stl unordered_map消費時間は7080112117 ns
複数回の実行時間の変動が小さく、trieツリーの速度がunordered_を上回ることがわかります.map 2倍
挿入したレコード数を1000まで小さくする場合
Trieツリーの消費時間は3195810157です
Stl unordered_map消費時間は7020927158
あまり変わっていない
trieツリーとunorderedを別々に注釈します.mapの挿入は、検索せずに11100000-1170000の計7万本を挿入した後、pmapを使用してメモリの占有量を表示します.
mapped: 19676K writeable/private: 3968K trie
mapped: 22480K writeable/private: 6776K unordered_mapの両方の実際のメモリ消費量は4-6 MBで、いずれも少なく、trieツリーは比較的低いが、このシーンはtrieツリーのメモリ消費量に有利である.