Здравствуйте. В программе есть две структуры данных, которые вызывают вопросы: 1) Массив Temp, где каждый элемент типа Код (Text): struct subseq { string str; char checked; }; На каждой итерации цикла, он обрабатывается по следующей схеме: DO <условие> - создание заново путем добавления элементов в конец - последовательный просмотр с изменением поля checked - удаление всех элементов OD Суммарно на всех итерациях требуется вставка порядка 2*10^6 элементов. Соотвественно столько же удалений. 2) Массив Base. Представляет собой справочную таблицу, где каждый элемент типа: Код (Text): struct adrbas { string str; vector<int> address; char exs; short int cnt; }; Обрабатывается на каждой итерации данная таблица аналогичным образом: - создается путем добавления элементов в конец. При этом поле str здесь является ключом, на основе которого решается добавить ли новый элемент или, если элемент с таким ключом str существует, то в найденную строку просто вносятся необходимые изменения - последовательно просматривается - часть записей таблицы удаляются Суммарно на всех итерациях количество вставок/удалений тоже достаточно большое. Помогите, пожалуйста, советом по выбору стандартного класса для реализации задачи. Что лучше выбрать: vector, list или м.б. multimap. Объемы вычислений большие и время работы очень критично. Спасибо.
если есть ключ, то надо либо map, либо multimap. можно еще использовать set, но тогда надо будет писать процедуру сравнения элементов (сравнение будет только по полю str). я считаю, что в твоем случае лучше всего будет использовать map<string,adrbas>, где из adrbas следует убрать поле str. правда, при последовательном просмотре контейнера элементы будут отсортированы по ключу. если тебе важен ПОРЯДОК, в котором элементы были добавлены, то я не знаю пока что посоветовать. не знаю, с чего ты вдруг решил использовать multimap. это тот же map, только допускает наличие элементов с одинаковыми ключами. P.S. хочется высказаться еще насчет vector и list (касаемо не этой задачи, а вообще). vector хорош лишь тем, что обеспечивает быстрый произвольный доступ к элементу типа vec[0] или vec[5]. но вставка в середину очевидно медленная, да и после такой операции все итераторы становятся непригодными поэтому я для себя давно заметил, что в большинстве задач лучше списки, чем динамические массивы.
2luckysundog Спасибо за мысли. Задача если упрощенно, то такая: есть входная строчка из символов какого-то конечного алфавита. Необходимо всю ее разобрать и составить что-то вроде словаря со след. инфой: все строчки длины 1 и сколько раз встречается каждая, все строчки длины 2 и сколько раз встречается каждая и т.д. Например: Исходная: 12120, должно получится: substr len cnt "1" 1 2 "2" 1 2 "0" 1 1 "12" 2 2 "21" 2 1 "20" 2 1 ... и т.д. Плюс еще какая-нибудь доп. инфа - например позиции символов в строке, с которых начинается данная подстрока. Вот и получается, что если строка длины 2000 хотя-бы, то всего так или иначе нужно рассмотреть и вставить. 2000+...+1 подстрок. (я считал худший случай - когда они все неповторяющиеся) Соответсвенно нужен постоянный поиск по уже внесенным и корректировка значений - если рассматриваемая подстрока уже внесена в базу. Скажите, теперь с этой информацией, совет - что лучше использовать map - остался таким же? Если я правильно понял - то map - это НЕ списочная структура. Почему здесь использовать list не лучше? ведь необходимо большое количество вставок и удалений, которое с list-ом работает быстрее. P.S. Первоначально я все уже реализовал с vector-ом - но работает ооочень медленно. Поэтому, оптимизируя алгоритм, я решил более тщательно отнестись к выбору используемого класса.
причем в дальнейшем при работе со справочной таблицей, мне нужно будет извлекать строки только определенной длины, допустим длины 4. Насколько я понимаю - при использовании map -это будет не совсем удобно.
Pahan вставки и удаление - да, в list быстрее. но поиск, я так понимаю, у тебя сейчас линейный, а это жуть для таких объемов данных. в map поиск элемента с нужным ключом работает куда быстрее - это функция find(). не нужно обходить весь контейнер от начала до конца. такой полный обход нужен только когда нужно вывести все содержимое контейнера, например. для вставки - insert(). причем, если при вставке правильно использовать параметр position, то можно добиться довольно-таки быстрой вставки.
можно задать свою функцию сравнения двух ключей. т.е. чтобы они располагались не просто в лексикографическом порядке, но и в порядке возрастания длин строк. тогда можно будет очень быстро найти в контейнере первую строку с длиной N и дальше извлечь все остальные строки (lower_bound() / upper_bound())
т.е. например для длины N=4 выполняем lower_bound с ключом "aaaa" (если 'a' - самый первый символ алфавита)
Кое-что ясно. Да, поиск сейчас линейный, но моя база "перестраивется" на ходу и в конкретный момент времени там находятся только подстроки необходимые для вычислений и определенной длины (m и m-1, m увеличивается), а остальная (предыдущая) часть уже не нужна "отсекается". Т.е максимально там единовременно находится 2000+1999 подстрок длины 1 и 2. Соответственно "дороже" всего стоят операции вставок и удалений - а значит похоже лучше списки. Так? Хотя, конечно же можно и подумать о том, чтобы не "усекать" базу, а просто всегда пользоваться find-ом в этом огромном скоплении данных. Но наверное неизвестно окупится ли=) Я подумаю над этим. Подскажите, еще плиз - как мне прикрутить эту функцию сравнения less , чтобы компилятор использовал ее для сравнения. Просто написать: Код (Text): map(string, adrbas, less<string>) и ниже описать bool-евскую функцию less, которая вернет 0 или 1 (если первый параметр должен идти раньше второго)?? Я вопросы жирным выделил, а то все вперемешку идет.
Код (Text): #include <cstdio> #include <map> #include <string> #include <vector> using namespace std; typedef struct { vector<int> address; char exs; short int cnt; } t_adrbas; struct cmycomp { bool operator() (const string& L, const string& R) const { if(L.length() == R.length()) return (L < R); else return (L.length() < R.length()); } }; typedef map<string,t_adrbas,cmycomp> t_dic; typedef t_dic::iterator it_dic; typedef t_dic::value_type vt_dic; int main() { t_dic dic; it_dic idic; string sample = "12120"; int i,n,ns = sample.length(); for(n=1;n<=ns;n++) { for(i=0;i<ns-n+1;i++) { string subs = sample.substr(i,n); idic = dic.find(subs); if(idic != dic.end()) { idic->second.address.push_back(i); idic->second.cnt ++; } else { t_adrbas el; el.address.push_back(i); el.cnt = 1; dic.insert(vt_dic(subs,el)); } } } for(idic=dic.begin();idic!=dic.end();idic++) { printf("\"%s\" len=%d cnt=%d\n", idic->first.c_str(), idic->first.length(), idic->second.cnt); } return 0; }
если что, я не знаю как быстро работает функция length(), т.е. не знаю считает ли она каждый раз заново strlen() в этом случае лучше делать свой класс для строки или наследовать от string.
За код спасибо большое. Пока искал описание map - понятнее примера не видел=) Если честно то не совсем понял про length(). А разве можно иначе? Помоему она всякий раз когда при сравнении будет вычислять заново. Если можно, то напишите подробнее про тот как сделать иначе.
Pahan иначе, например, в Delphi. там строке сопутствует поле c длиной, которое обновляется после каких-либо операций со строкой. если добавляем N символов, то к длине прибавляется N и т.д. и функция Length() просто возвращает значение этого поля в данной задаче, если наследовать от класса string, можно перегрузить всего лишь operator=() (3 его варианта для string, char* и char), потому что никаких действий над строками не происходит кроме присваивания. ну и еще перегрузить саму функцию length().
вообще, предложенный мной словарь далек от идеала советую посмотреть (причем внимательно) на алгоритм Ахо-Корасик для построения словаря. и на суффиксные деревья. к сожалению, сейчас не могу сказать насколько они уместны в этой задаче, но если выбирать из vector, list и map, то лучше на мой взгляд map
