Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: хэши
Форум на CrossPlatform.RU > Разработка > С\С++
B_u_R_n
Проблема такая, что при очень большом массиве строк, для которых нужно составить таблицу хэшей , происходит очень долго соответственно нет смысла делать поиск зжшированием, ибо больше часа занимает времени что бы пройти по всем записям файла и захэшировать каждое слово, слов 5+лямов. Что посоветуете... Нужно именно поиск хэшированием , мб есть какой нибудь метод хэширования который дает наименьшее число коллизий и наибольшую скорость...
Алексей1153
к примеру, пусть хеш будет первые три буквы + длина слова

например вот такой ключ (сейчас под ascii, но легко можно переделать под юникодные литеры - место оставлено)

struct s_my_hash_key
{
    typedef UINT64 td_base;

    td_base m_key;

    bool operator==(s_my_hash_key o2)const
    {
        return m_key==o2.m_key;
    }

    bool operator<(s_my_hash_key o2)const
    {
        return m_key<o2.m_key;
    }

    void operator=(s_my_hash_key o2)
    {
        m_key=o2.m_key;
    }

    struct s_parser
    {
        td_base letter0:16;
        td_base letter1:16;
        td_base letter2:16;
        td_base length_:16;
    };


    s_my_hash_key():m_key(0)
    {
    }

    s_my_hash_key(UINT16 letter0, UINT16 letter1, UINT16 letter2, UINT16 length_):m_key(0)
    {
        s_parser& p=(s_parser&)m_key;

        if(sizeof(p)!=sizeof(m_key))throw 0;//чисто для самоконтроля в дебаге

        p.letter0=letter0;
        p.letter1=letter1;
        p.letter2=letter2;
        p.length_=length_;
    }

    s_my_hash_key(const char* pWord):m_key(0)
    {
        s_parser& p=(s_parser&)m_key;

        if(sizeof(p)!=sizeof(m_key))throw 0;//чисто для самоконтроля в дебаге

        if(!pWord)return;

        p.length_=strlen(pWord);

        if(p.length_>0)p.letter0=pWord[0];
        if(p.length_>1)p.letter1=pWord[1];
        if(p.length_>2)p.letter2=pWord[2];

    }
};

//

s_my_hash_key h1;
s_my_hash_key h2;

if(h1==h2)
{
}

if(h1<h2)
{
}

h1=h2;

s_my_hash_key h3('a','b','c',10);
s_my_hash_key h4("abcdefghij");
B_u_R_n
Цитата(Алексей1153 @ 14.12.2011, 7:42) *
к примеру, пусть хеш будет первые три буквы + длина слова

например вот такой ключ (сейчас под ascii, но легко можно переделать под юникодные литеры - место оставлено)

struct s_my_hash_key
{
    typedef UINT64 td_base;

    td_base m_key;

    bool operator==(s_my_hash_key o2)const
    {
        return m_key==o2.m_key;
    }

    bool operator<(s_my_hash_key o2)const
    {
        return m_key<o2.m_key;
    }

    void operator=(s_my_hash_key o2)
    {
        m_key=o2.m_key;
    }

    struct s_parser
    {
        td_base letter0:16;
        td_base letter1:16;
        td_base letter2:16;
        td_base length_:16;
    };


    s_my_hash_key():m_key(0)
    {
    }

    s_my_hash_key(UINT16 letter0, UINT16 letter1, UINT16 letter2, UINT16 length_):m_key(0)
    {
        s_parser& p=(s_parser&)m_key;

        if(sizeof(p)!=sizeof(m_key))throw 0;//чисто для самоконтроля в дебаге

        p.letter0=letter0;
        p.letter1=letter1;
        p.letter2=letter2;
        p.length_=length_;
    }

    s_my_hash_key(const char* pWord):m_key(0)
    {
        s_parser& p=(s_parser&)m_key;

        if(sizeof(p)!=sizeof(m_key))throw 0;//чисто для самоконтроля в дебаге

        if(!pWord)return;

        p.length_=strlen(pWord);

        if(p.length_>0)p.letter0=pWord[0];
        if(p.length_>1)p.letter1=pWord[1];
        if(p.length_>2)p.letter2=pWord[2];

    }
};

//

s_my_hash_key h1;
s_my_hash_key h2;

if(h1==h2)
{
}

if(h1<h2)
{
}

h1=h2;

s_my_hash_key h3('a','b','c',10);
s_my_hash_key h4("abcdefghij");

не понял, пример использовния можно ?


все, не заметил. не подходит, нужно генерить инт значения что бы вставить по индексу в струткруту запись
Алексей1153
без проблем
typedef int td_base;

struct s_parser
{
td_base letter0:8;
td_base letter1:8;
td_base letter2:8;
td_base length_:8;
};

ну и символы - только ascii, а длина будет не больше 255 (вернее - будет обрезаться по модулю 256)
Влад
Хм, здесь, насколько я понимаю, будут неслабые такие коллизии... это ТС устраивает?
B_u_R_n
Цитата(Алексей1153 @ 14.12.2011, 14:21) *
без проблем
typedef int td_base;

struct s_parser
{
td_base letter0:8;
td_base letter1:8;
td_base letter2:8;
td_base length_:8;
};

ну и символы - только ascii, а длина будет не больше 255 (вернее - будет обрезаться по модулю 256)

ммм не понял о длинне, если слов 50+ лямов то и индексов должно быть столько же
Влад
А какой метод хеширования используется сейчас?
Попробуй использовать CRC32 - он довольно быстрый, и возможных хешей 2^32.
B_u_R_n
Цитата(Влад @ 14.12.2011, 17:05) *
А какой метод хеширования используется сейчас?
Попробуй использовать CRC32 - он довольно быстрый, и возможных хешей 2^32.

дело все в том что в текущем методе очень много коллизий получается
Алексей1153
Цитата(Влад @ 14.12.2011, 16:41) *
Хм, здесь, насколько я понимаю, будут неслабые такие коллизии... это ТС устраивает?


зато считаться будет мгновенно, а коллизии - "недлинные", так как вряд ли будет много таких совпадений - три первых символа и длина слова (хотя, я по словарю не сравнивал) . Тут тонок баланс между скоростью хеширования и скоростью поиска - можно регулировать этот баланс размером td_base

CRC32 всяко дольше будет считаться.

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

Цитата(B_u_R_n @ 14.12.2011, 18:08) *
ммм не понял о длинне, если слов 50+ лямов то и индексов должно быть столько же

при чём тут количество слов, я про длину слов )
B_u_R_n
Цитата(Алексей1153 @ 14.12.2011, 18:46) *
Цитата(Влад @ 14.12.2011, 16:41) *
Хм, здесь, насколько я понимаю, будут неслабые такие коллизии... это ТС устраивает?


зато считаться будет мгновенно, а коллизии - "недлинные", так как вряд ли будет много таких совпадений - три первых символа и длина слова (хотя, я по словарю не сравнивал) . Тут тонок баланс между скоростью хеширования и скоростью поиска - можно регулировать этот баланс размером td_base

CRC32 всяко дольше будет считаться.

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

Цитата(B_u_R_n @ 14.12.2011, 18:08) *
ммм не понял о длинне, если слов 50+ лямов то и индексов должно быть столько же

при чём тут количество слов, я про длину слов )

генерируются 9-и значные индексы начиная от 100000000 а как же <100000000
Алексей1153
B_u_R_n, у тебя какое-то неверное представление о хеш-функции. Почитай http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%...%B8%D1%86%D0%B0

и где какие 9-значные ? Ничо не понимаю ))
B_u_R_n
Цитата(Алексей1153 @ 14.12.2011, 21:51) *
B_u_R_n, у тебя какое-то неверное представление о хеш-функции. Почитай http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%...%B8%D1%86%D0%B0

и где какие 9-значные ? Ничо не понимаю ))

спасибо, все, разобрался, но решил все же использовать мд5
Алексей1153
скорость помахает ручкой )

ну возьми ты не 3 первые буквы, а 4, 5, 6
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2024 IPS, Inc.