Строки лежат в vector.



Сортировка по алфавиту осуществляется так:



Ф-ия вызывается около 1000 раз за 1-2 сек, строк много.  Важно сэкономить даже мс, как можно гораздо быстрее отсортировать по алфавиту? Какие ещё способы, более скоростные?

Или, может лучше из STL что-нибудь другое, чтобы сразу при добавлении строки сортировалось по алфавиту? Как быстрее?

Строки добавляются так: 

Это сообщение отредактировал(а) Riddik - 30.6.2009, 17:18

std::set

Вопрос: а зачем сортировать 1000 раз в секкунду? 
Если вставка относительно редка - std::set подойдет, но нет доступа по индексу.

Спасибо. 
Всё равно не укладывается в 2 секунды, где ж узкое место...

Добавлено @ 17:29
Задача это. Time limit 2 секунды.

Вставка частая. 

Вот блин... народ за 0.02 сек решает, а я в 2-е не могу уложиться.

Это сообщение отредактировал(а) Riddik - 30.6.2009, 17:30

Riddik

а что надо сделать то?  

Пример:
исходные данные    
6
whale: big black water animal
penguin: black white ice beak
piano: keyboard black white wire
jackboot: leather heel black
train: rail wheel black
rose: red green thorn
3
whale penguin piano jackboot train
penguin piano
jackboot rose

Результат
black
black white
No solution.

Вот скажите мне честно, эта ж очень лёгкая задача?

Я с 8 утра над ней сижу и выдавить ничего путного не могу. Мой мусорный код не может уложиться в 2 секунды, и не факт, что правильно всё делает.

Вот так поздно чем-то начинать заниматься... 

Надо было в школе или в универе хотя бы учиться программированию... 

Такие моменты крылья напрочь отрезают и жутко в себе разочаровывают.

критический момент называется. если продержитесь - умней станете. нет - не умней 


ваши исходные данные очень смахивают на данные из базы данных. нельзя их положить в БД и одним запросом за 1 миллиардную секунды получить нужный ответ!?

вам нужно результат выборки вывести в отсортированном виде. строки до выборки сортировать не нужно.

Это сообщение отредактировал(а) zim22 - 30.6.2009, 19:45

так он только результат и сортирует :



покажите для начала как храните исходные данные.

А можно еще входной файл увидеть, на котором так долго работает? 

если кому-то интересно, вот задача
Пробуждение(XIII чемпионат Урала по спортивному программированию)
Отправка решения на проверку

Спасибо, что-то я не догадался сразу поискать эту задачку в гугле.
На Java решение в лоб сразу же прошло (0.718 / 15 998 KB):

вы уверены, что вам нужен именно скоростной метод сортировки, а не алгоритм нахождения пересечений слов?
***
предлагаю свой медленный  алгоритм:
считать первую часть исходных данных в map<string / * название объекта */ , set<string> /* набор ассоциаций */ > object_map;


Для каждой строки создавать set<string>, содержащий все значения для выбранных ключей
Например для первой строки:
set<string> union_phrases = object_map[whale] + object_map[penguin] + ... + object_map[train]
В цикле проверять наличие слова из union_phrases одновременно во всех ключах из object_map


Это сообщение отредактировал(а) zim22 - 30.6.2009, 21:13

Я  очень и очень криво всё реализовал. Думаю, для вас далее последует анекдот и попадёт в перлы.

Создал структуру, у которой есть string для имени объекта, указатель на string для его ассоциаций и unsigned short для числа ассоциаций. Т.е. структура описывает один объект:


Далее считывается первое число из входного потока  - количество всех объектов. И столько создаётся Mind объектов:



Далее считывает имя объекта в mind[i].name, считываются его ассоциации, всё после двоеточия и пробела считывается в строку, затем эта строка по словам заносится в mind[i].assot[cwi], по количеству ассоциаций для текущего объекта создаётся столько же "стрингов": 


Всё это в цикле, число итераций которого равно первому считанному числу из входного потока.

Таким образом есть база объектов mind, каждый объект "знает" своё имя, свои ассоциации и количество своих ассоциаций. 
Далее считывается следующее целое из входного потока - число наборов объектов, для которых надо искать ассоциации. Это число итераций для следующего блока. 
Считывается строка - набор объектов. Далее по порядку, каждое слово сравнивается со всеми mind[i].name, когда совпадение найдено, в vectot помещается номер (unsigned short) нужного mind. И параллелльно ищется объект с самым маленьким количеством ассоциаций - по нему и надо искать совпадение ассоциааций. 
Таким образом, мы имеем vector, хранящий номера нужных mind-ов для текущий выборки и номер mind'а с самым маленьким набором ассоциаций.  

где mind[minim].cw - это число ассоциаций, которое самое маленькое из всех mind'ов/ попавших в текущий набор. Чтобы делать наименьшее число итераций.

Далее вложенный цикл, проходит по всем mind'aм, номера которых в vector'е., и соответсвенно ещё вложенный цикл по ассоциациям текущего mind, как только встречается mind, у которого нет текущей ассоциации - эта ассоциация отбрасывается (break) и проверяется следующая. Если текущая ассоциация встретилась у всех объектов из текущего набора - она ложиться в rezalt. Сначала rezalt был vector'ом и пополнялся так: rezalt.push_back(assot);
Потом сортировал  sort(rezalt.begin(), rezalt.end(), less<string>());

Потом посоветовали set, его заполнял rezalt.insert(mind[minim].assot[per]).
После выводил резал через пробел или No solution., если ни одной ассоциации не было. 
И всё по-новой, пока не обойдёт все наборы. vector с номерами и rezalt очищались после каждой проверки очередного набора.
Вот так всё ужасно. Кирпичом мне по голове.

имхо узкое место в поиске объекта.  Поэтому объекты лучше хранить в отсортированном векторе и применять соотвествующий поиск,
либо чтоб не изобретать велосипед использовать map (multimap)