Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Текстовый файл и ХЕШ таблица ???

Автор: Syberex 22.9.2006, 08:57

Трабла такая, есть текстовый файл 1,6 мегабайта, там 170 000 слов, в конце слов энтеры, необходимо убрать и создать хеш таблицу.
Требования: поиск, запись, чтение.И самое главное чтоб быстро работало .Как сделать??? Поиск в масиве таким способом идёт 200 раз в секунду проход 1,6 мегобайта, но я хочу хеш, чтоб можно было слова и во внутрь добовлять. Что такое хеш я знаю, но вот как это слепить воедино так и не нашёл. Кто подскажет?
     int handle=open("D:\\slovar11.txt",O_CREAT);  //0x0100
     long LenFile=filelength(handle);
     close (handle);
     fstream in("D:\\slovar11.txt");
     char *ch=new char[LenFile];
     in.read(ch,LenFile);
     in.close();
     ........
     ........
     delete ch;

Автор: _hunter 22.9.2006, 11:07

а почему бы std::map не юзать?

Автор: Syberex 22.9.2006, 12:23

вот чёто я не долюбливаю эту стд, органически у меня к ней не сварение. А примерчик есть?

Автор: _hunter 22.9.2006, 12:41

std::map<std::string, int> someMap;
...
someMap[word] = id++;

Автор: Syberex 22.9.2006, 13:58

мне это не очём не говорит smile

Автор: kondr 22.9.2006, 14:41

Цитата

std::map<std::string, int> someMap;
...
someMap[word] = id++;

А зачем в качестве ключа строку использовать? Если хэш будет расчитываться, то ключом должно быть некоторое числовое значение. А вообще я не понимаю зачем тут хэш. Просто использовать set<string> и все. Слова будут лексикографически упорядочены и поиск бинарный. Ну вставка (в смысле начальное считывание слов в set) конечно будет немного медленновата, но это ж только один раз...

Хотя поиск по строкам наверное дорого стоит... Может действительно хэш лучше...

Автор: kondr 22.9.2006, 16:03

Короче вот так я бы сделал:

Код



#include <iostream>
#include <fstream>
#include <string>
#include <map>

using namespace std;

int hash(string s)
{
    //Считаем хэш для строки
}

class Dictionary
{
public:
    Dictionary(char* dictfile)
    {
        dictFileName = dictfile;
    };
    
    int readDictFile()
    {
        ifstream dictFile;
        string word;

        dictFile.open(dictFileName.c_str());
        
                if (dictFile)
        {
            dictMap.clear();

            while (!dictFile.eof())
            {
                 getline(dictFile,word);
                 dictMap.insert(make_pair(hash(word),word)); //make_pair - создает пару ключ-значение
            }

            dictFile.close();
            return 0;
        }

        return -1;
    }

    string* Search(string & word)
    {
        map <int,string>::iterator it = dictMap.find(hash(word));
        if (it == dictMap.end()) return NULL;
        return &it->second;  //Возвращаем укащатель на значение, ассоциированное с хэшем или нул                        
    }

    ~Dictionary(){};

private:
    string dictFileName;
    map <int,string> dictMap;
};

убого, но смысл понятен smile

Автор: _hunter 22.9.2006, 16:14

Цитата(kondr @ 22.9.2006, 14:41

)

А зачем в качестве ключа строку использовать?

а что еще ключем может быть???

Автор: Syberex 25.9.2006, 07:49

Ребят всё конечно круто, но мне одного не понятно, хеш должен возвращать указатель на значение в файле, токо одна МАЛЕНЬКАЯ проблемка, как она его вернёт правильно, если если слова там разной длины, и при всавке и удалении слов, даже 10-ка, уже идёт сильное смещение указателей, и всё становиться крайне не эффективно, я так подозреваю, что хешь функция должна как-то модифицироваться после каждого слова, а это уже полный бред. smile

Автор: Earnest 25.9.2006, 07:56

170000 слов - это не так уж много: загрузи в память и не парься. Если все же хочешь работать с файлом, то сделай map строка->позиция в файле. Новые слова добавляй взад. Если нужно удалять - введи дополнительный флаг.
Лучше, конечно, использовать hash_map, а не map, если твоя stl поддерживает.