VPF::sizeof(std::string) == 32, Почему ??? - Форум программистов

W4FhLF

Дата 3.8.2008, 13:11 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

phprus, в общем видимо я где-то протормозил, но под хеш-таблицей я не имел ввиду структуру данных "hash table". Всё что я говорил про время и память касалось только лишь расчёта хешей для слов, а не их отображения в какую-либо структуру. И когда ты говорил коллизия я это понимал как hash(s1) == hash(s2). Теперь всё ясно.

Цитата(phprus @ 3.8.2008, 11:33

)

Либо все слова держать в памяти, либо в хэш-таблице придется хранить смещения в файлах данных, но это приведет к огромным дисковым тормозам.

Да какие дисковые тормоза? В качестве value харнить позиции слов в файле. Файл читать целиком придётся в любом случае(кусками или ещё как-нибудь). А про запись автор ничего не говорил. Он сказал, что надо проанализировать на предмет наличия дубликатов.

Цитата(phprus @ 3.8.2008, 11:33

)

А про алгоритмы внешней сортировки вы не слышали?

А это не дисковые тормоза?

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

phprus

Дата 3.8.2008, 14:50 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 22.8.2006

Репутация: 1
Всего: 3

Цитата(W4FhLF @ 3.8.2008, 13:11

)

Да какие дисковые тормоза? В качестве value харнить позиции слов в файле.

Вот здесь и всплывут тормоза. Даже для фрагментированного файла последовательное чтение будет быстрее, чем чтение маленьких кусочков из разных участков файла. (Тут так-же не надо забывать про то, что ОС кеширует данные с диска в оперативке, и этот кэш будет эффективнее при последовательном чтении, чем при постоянных перескоках в разные концы файла).

В случае сортировки количество чтений из произвольных участков файла будет минимальным, а в случае работы с отсортированными последовательностями будет вообще только последовательное чтение.

W4FhLF

Дата 3.8.2008, 15:11 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

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

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

phprus

Дата 3.8.2008, 16:24 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 22.8.2006

Репутация: 1
Всего: 3

Цитата(W4FhLF @ 3.8.2008, 15:11

)

Я не понимаю зачем нам читать из разных концов файла?

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

W4FhLF

Дата 3.8.2008, 16:43 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

phprus, всё понял, я действительно гоню smile

Спасибо, что проявил терпение.

Добавлено через 6 минут и 44 секунды
А что если в качестве значения использовать pair<hash, position>? Hash в любом случае вычисляется один раз, позиция известна при первом проходе. Тогда для разрешения коллизий не придётся читать с диска.

Это сообщение отредактировал(а) W4FhLF - 3.8.2008, 16:44

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

phprus

Дата 3.8.2008, 19:09 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 129
Регистрация: 22.8.2006

Репутация: 1
Всего: 3

Цитата(W4FhLF @ 3.8.2008, 16:43

)

А что если в качестве значения использовать pair<hash, position>? Hash в любом случае вычисляется один раз, позиция известна при первом проходе. Тогда для разрешения коллизий не придётся читать с диска.

Не получится.
На входе функции поиска у нас строка, а в хэш-таблице смещение в файле. И эти 2 сущности надо как-то сравнивать. Как следствие надо читать строку из файла.

Mayk

Дата 4.8.2008, 07:34 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Вопрос,задаваемый (n+1)-ый раз:
А кто нибудь может доступным языком объяснить почему БД нельзя использовать?

Это сообщение отредактировал(а) Mayk - 4.8.2008, 07:35

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Lazin

Дата 4.8.2008, 09:14 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3820
Регистрация: 11.12.2006
Где: paranoid oil empi re

Репутация: 41
Всего: 154

Цитата(Mayk @ 4.8.2008, 07:34

)

А кто нибудь может доступным языком объяснить почему БД нельзя использовать?

топикстартер желает написать свою БД, имхо.

--------------------

C++ is the steampunk of programming languages: modern ideas realized with victorian technology.

andrew_121

Дата 4.8.2008, 09:33 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 6
Всего: 33

Цитата(Lazin @ 1.8.2008, 12:17

)

блин, так и не понял, нафига тебе хранить кучу строк в памяти?

Уже не надо в памяти хранить. Это так для развития, понимания...

--------------------

Удалил аккаунт. Прощайте!

W4FhLF

Дата 6.8.2008, 15:46 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 20
Всего: 121

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

Перестраховался и в качестве хеша вычисляется md5 и берутся его 1 и 4 блоки. Хеш хранится в __int64. Для вычисления хеша подключил свою когда-то написанную на ассемблере оптимизированную либу для вычисления md5. Поэтому процедура string_hash слегка уродлива smile

Для сортировки массива используется алгоритм HeapSort.

В конце программы в консоль выводятся слова, которые имеют дубликаты в словаре.

Словари для тестов брал отсюда: http://www.insidepro.com/eng/download.shtml

На моём процессоре AMD 2.2 гц на построение таблицы и её сортировку для словаря 2.5 млн. слов уходит ~5 секунд. Меня такой результат вполне удовлетворил так, что решил оставить реализацию как есть.

Проект для VS 2008 в аттаче.

Код


// words_unify.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>

#pragma comment (lib, "md5.lib") 

extern "C" { 
    void _stdcall procMD5hash(char* in_buffer, 
        unsigned int size, 
        void* out_buffer); 
} 

unsigned __int64 string_hash(const char* str, unsigned len)
{
    unsigned int md5[4];
    char tmp_str[256] = {0};

    strcpy((char*)&tmp_str, str);
    procMD5hash((char*)&tmp_str, len, &md5);

    md5[1] = md5[3];
    return *((unsigned __int64*)(&md5[0]));
}

typedef std::pair<unsigned __int64, unsigned> PairItem;
typedef std::vector< PairItem > HashTable;

void compute_hash_array(const std::string& filepath, HashTable& hash_table )
{
    #define CRLF_LEN 2        // для файлов, где перенос строки == \r\n

    std::ifstream ifs(filepath.c_str());

    if(ifs.fail())
        throw std::ios::failure("File not found.");

    std::string word;
    unsigned current_pos = 0;

    while(!ifs.eof())
    {
        ifs >> word;

        hash_table.push_back(std::make_pair(string_hash(word.c_str(), word.length()), current_pos));

        current_pos += word.length() + CRLF_LEN;
        word.clear();
    }
}

void print_duplicates(const std::string& filepath, const HashTable& hash_table)
{
    std::ifstream ifs(filepath.c_str());

    if(ifs.fail())
        throw std::ios::failure("Cannot open the file.");

    size_t size = hash_table.size();
    std::string word;

    for(size_t i = 0; i < (size - 1); ++i)
    {
        if(hash_table[i].first == hash_table[i+1].first)
        {
            ifs.seekg(hash_table[i].second);
            ifs >> word;

            std::cout << word << std::endl;
            while(hash_table[i].first == hash_table[i+1].first)
                ++i;
        }
    }
}


void downHeap(HashTable& a, long k, long n) 
{
    PairItem new_elem = a[k];
    long child;

    while(k <= n/2) 
    {
        child = 2*k;
        
        if( child < n && (a[child].first < a[child+1].first) )
            child++;

        if( new_elem.first >= a[child].first ) 
            break; 

        a[k] = a[child];
        k = child;
    }
    a[k] = new_elem;
}

void heapSort(HashTable& a) {
    long i, size = a.size();
    PairItem temp;

    for(i = size / 2 - 1; i >= 0; --i) 
        downHeap(a, i, size - 1);

    for(i = size - 1; i > 0; --i) 
    {
        temp = a[i]; 
        a[i] = a[0]; 
        a[0] = temp;
        downHeap(a, 0, i - 1); 
    }
}

int main(int argc, char* argv[])
{
    HashTable hash_table;
    std::string s = "E:\\dictionary_huge_c.txt";
    
    try 
    {

        compute_hash_array(s, hash_table); 
        heapSort(hash_table);
        print_duplicates(s, hash_table);

    } catch(...) {}

    return 0;
}

Присоединённый файл ( Кол-во скачиваний: 2 )

words_unify.rar 5,21 Kb

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »