Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> STL list или vector 
:(
    Опции темы
azesmcar
Дата 7.1.2011, 21:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


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

Репутация: 81
Всего: 211
Цитата(lamber @  7.1.2011,  21:23 Найти цитируемый пост)
### я думал это казуальная задача а выходит на деле далеко не так.  

ну.. в принципе так оно и есть, просто когда размеры файла превышают всякие разумные пределы, то приходиться иметь дело с непростой оптимизацией. Если загрузишь второй файл в память то задача станет более чем казуальной.
PM   Вверх
lamber
Дата 7.1.2011, 21:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Думаю загрузить второй файл т.к. он в разы меньше первого, разбить его в алфавитное дерево map<char<vector<string>> и загружать первый файл кусками и обходить его в цикле.
PM MAIL   Вверх
azesmcar
Дата 7.1.2011, 21:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


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

Репутация: 81
Всего: 211
lamber

Зачем? Почему не просто
map<string, string> или hash_table? а первый файл естественно нужно кусками, его всего загружать и не нужно.
PM   Вверх
lamber
Дата 7.1.2011, 21:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Немного не улавливаю. с hash_table 

пробовал map<string,vector<string>> но начинает ругатся на следующую конструкцию
Код

string line="somedata";
map<string,vector<string>> table;
table[line[0]].push_back(line);


ругается на приведение из char в string 
PM MAIL   Вверх
azesmcar
Дата 7.1.2011, 21:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


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

Репутация: 81
Всего: 211
Цитата(lamber @  7.1.2011,  21:40 Найти цитируемый пост)
Немного не улавливаю. с hash_table 

его нет в стандарте, посмотри в boost.

Цитата(lamber @  7.1.2011,  21:40 Найти цитируемый пост)
пробовал map<string,vector<string>> 

а почему vector<string>?
я так понял соответствие идет одно к одному key=>value, почему не просто
map<string, string> ?

Цитата(lamber @  7.1.2011,  21:40 Найти цитируемый пост)
ругается на приведение из char в string  

ну да, line[0] это первый символ строки, т.е. char, а line - это string
PM   Вверх
lamber
Дата 7.1.2011, 22:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
Это я делаю для того что бы собрать алфавитное дерево т.е.

к примеру в первом файле находим первый ключ и начинается он на 'a' зачем просматривать весь массив во втором файле когда мне нужны ключи начинающиеся только с 'a' 

тогда я просто делаю следующим образом

Код

map<char,vector<string>> vtoroy_fayl;

for(size_t i=0;i<vtoroy_fayl['a'].size();i++)
{
if(compare(key,vtoroy_fayl['a'][i]))
{
//сохраняем т.к. нашли совпадения

}

}


Я вот так подошел к проблеме чтоб ускорить процесс, он подходит когда первый файл структурирован т.к. когда мы точно знаем где key в первом файле (ну он выделен как то там )

Это сообщение отредактировал(а) lamber - 7.1.2011, 22:10
PM MAIL   Вверх
azesmcar
Дата 8.1.2011, 07:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


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

Репутация: 81
Всего: 211
lamber

поиск в std::map имеет логарифмическую сложность и твое алфавитное дерево будет лишь тормозить. Большинство реализаций map и так хранят данные в виде бинарного дерева, хотя тебя должна интересовать только сложность поиска, остальное не важно.

Это сообщение отредактировал(а) azesmcar - 8.1.2011, 07:39
PM   Вверх
lamber
Дата 8.1.2011, 13:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
2azesmcar
Т.е. ты хочешь сказать что map<string,string> будет быстрее чем map<char<vector<string>> :?
Мне критическми является скорость, вчера всю ночь просидел, так и ничего путного не сделал, скорость поиска и замена ацкий ацтой.
PM MAIL   Вверх
azesmcar
Дата 8.1.2011, 13:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


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

Репутация: 81
Всего: 211
Цитата(lamber @  8.1.2011,  13:02 Найти цитируемый пост)
Т.е. ты хочешь сказать что map<string,string> будет быстрее чем map<char<vector<string>> :?

Да. Для того map и существует. 
map<string, string> найдет твой ключ за логарифмическое время, т.е. для миллиона записей там будет порядка 14 итераций (смотри бинарный поиск), а в твоем случае ты за 3-4 итерации найдешь несортированный список, который потом придется обходить линейно, т.е. количество итераций равно количеству записей в векторе.
хотя я не совсем понял что за
Цитата(lamber @  8.1.2011,  13:02 Найти цитируемый пост)
vector<string>

? это что? вектор ключей, значений или и того и другого?

Это сообщение отредактировал(а) azesmcar - 8.1.2011, 13:15
PM   Вверх
boostcoder
Дата 8.1.2011, 13:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


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

Репутация: 49
Всего: 110
а hash_map разве в стандарт не входит?
если ключ - строка, то имеет смысл воспользоваться именно hash_map`ом.


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
lamber
Дата 8.1.2011, 13:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

Репутация: нет
Всего: нет
я имел ввиду map<char<vector<key_value>> где key_value структура

string key;
string value;

Добавлено через 1 минуту и 19 секунд
2boostcoder
Не работал с boost'ом разве что с regex'ом если скинешь пример или ссылку на пример будет очень круто.
PM MAIL   Вверх
azesmcar
Дата 8.1.2011, 14:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


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

Репутация: 81
Всего: 211
Цитата(boostcoder @  8.1.2011,  13:43 Найти цитируемый пост)
а hash_map разве в стандарт не входит?

Нет, но много где реализован.

Цитата(lamber @  8.1.2011,  13:45 Найти цитируемый пост)
я имел ввиду map<char<vector<key_value>> где key_value структура

Я так и подумал.

Цитата(azesmcar @  8.1.2011,  13:13 Найти цитируемый пост)
map<string, string> найдет твой ключ за логарифмическое время, т.е. для миллиона записей там будет порядка 14 итераций (смотри бинарный поиск), а в твоем случае ты за 3-4 итерации найдешь несортированный список, который потом придется обходить линейно, т.е. количество итераций равно количеству записей в векторе.

 smile 
PM   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1052 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.