Добрый день.

Задача такая. Построить рейтинг строк, подсчитать, сколько раз встречается каждая строка. Если использовать std::map<std::string, int>, то можно нормально увеличивать счетчик, но тогда сортировка производится по строкам, хотя нужно по значению счетчика. Если использовать std::set<std::pair<std::string, int> >, то можно задать свою функцию сортировки, но тогда для увеличения счетчика придется сначала каким-то образом находить нужную запись. К слову сказать, добавление строк производится гораздо чаще, чем построение самого отчета. Как я понял, для map нельзя написать функцию сравнения для значения (только для ключа). Может можно еще придумать какую-нибудь структуру данных? 

Да, еще нужно уметь по строке определить ее позицию в рейтинге. Это уже, конечно, дополнительный функционал, но все-таки.

делаешь функтор\функцию сравнения для second из pair, потом lower_bound\find для поиска. Только изменяй по следующей схеме, удаляешь элемеент и записываешь уже новый, измененный. Если бы не частое добавление, то можно было бы юзать сортированный вектор

А как в таком случае искать нужную пару? С помощью пары ("строка", 1)? Но ведь если у нас сортировка задана по счетчику, то это будет неэффективно, тем более для строк с большим значением счетчика.

O(ln(n))

так искать надо по паре? или только по счетчику?

Ну вот когда добавляем очередную строку: если она есть (вот тут нужно найти пару ("строка", [число])), то её счетчик увеличивается на 1, в противном случае добавляем пару ("строка", 1). 

boost::multi_index_container

ну так в чем прроблема? пишешь две функции сравнения, одна по счетчика(ее передаем в контейнер при создании), вторая по строке(ее передаем в ф-ию поиска) ф-ия поиска возвращает итератор, по которому мы удаляем 'элемент и записываем новый с обновленным счетчиком

Ясно. Спасибо   

А что эффективнее: map с map["строка"] += 1 или set с find_if()? То есть использует ли find_if() информацию о последовательности или же тупо циклом просматривает все элементы?

Это сообщение отредактировал(а) MastEdm - 22.7.2008, 13:26

А вы не могли бы набросать примерчик, а то я в boost не силен и первое знакомство (тут) как-то не пошло

Это сообщение отредактировал(а) MastEdm - 22.7.2008, 15:38

если find_if это алгоритм контейнера, то эффективность равнозначна.

MastEdm, 
тебе нужен контейнер с возможностью независимого поиска как по ключу, так и по значению.
либо сооруди такой сам из двух std::map, либо поищи в сети готовые варианты. В boost тоже есть, и не в одном варианте.

Кажется, скореее boost::bimap — более специализировано для данной задачи.

Интересно, а за какое время производится добавление и поиск в boost::multi_index_container? Ведь где-то мы должны проиграть  

Это сообщение отредактировал(а) MastEdm - 23.7.2008, 09:39

boost::bimap (действительно более подходящий) - http://www.boost.org/doc/libs/1_35_0/libs/...html/index.html
boost::multi_index_container - http://www.boost.org/doc/libs/1_35_0/libs/.../doc/index.html

И все-таки если вернуться к эффективности. Добавление в map происходит за логарифмическое время. То есть при добавлении строки в рейтинг мы можем найти ее за log(n) и прибавить к ее счетчику 1, а если ее нет, то добавить как новую пару <строка, 1> за тоже время. Когда же нам нужно построить сам рейтинг, то есть отсортировать строки по счетчику, то придется перебрать все элементы и добавить, к примеру, в multimap с сортировкой по счетчику. Получаем время n*log(n).  Теперь если нам нужно определить положение конкретной строки в рейтинге, то осуществляем полный перебор сформированного ранее multimap. Подитожу выше сказанное по операциям:

add(string)         C*log(n)
get_rating()        C*n*log(n)
get_pos(string)  C*n*log(n)

Результаты неутешительные (если, конечно, я нигде не наврал).

Не уверен, что предложенные контейнеры из boost работают быстрее. Если я неправ, переубедите меня  

После некоторых размышлений родился такой вариант (строки заменил на идентификаторы):



При таком раскладе добавление за log(n), построение таблицы константное время занимает (я не учитываю печать), определение позиции по id за log(n). Может что-то можно эффективнее сделать?

PS Прошу не пинать за форматирование кода: пришлось применить автоматическое форматирование из kdevelop, поскольку сам пишу в emacs...

Это сообщение отредактировал(а) MastEdm - 8.8.2008, 14:59

ох, не уверен
вот этот цикл:

,как мне кажется, может сделать из логирифма линейное время
предположим, что у нас получилось куча слов с одинаковым количеством экземляров (что, в общем-то, для обычного текста не так уж странно), тогда при увеличении одного из таких слов придётся его протащить наверх, срелняя длина будет пропорицональна длине такого отрезка

Добавлено через 3 минуты и 17 секунд
можно тупо построить мапу <строка, количество экземпляров>, потом перегнать её в вектор пар, отсортировать его по строкам и искать там нужную строку за логарифм (т.к. отсортированный), а индекс - как раз нужная позиция

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

Можно, только сортировка в любом случае займет n*log(n). И сортировать нужно не по строкам, а по счетчику. Мы ведь рейтинг строим. А если отсортировано по счетчику, то по строке искать за логарифм не получится.

Итого, по двум вариантам алгоритма:

• Добавление: log(n), Определение позиции: n*log(n)
• Добавление: n*log(n), Определение позиции: log(n)

 

У меня складывается дурное предчувствие, что ничего лучше придумать не получится   

Есть такая мысля. Заводим два массива указателей на структуру:

Индексация в массиве table по id строки, а в top записи отсортированы по счетчику. Таким образом добавление займет время C*n в худшем случае, определение позиции - константное время. 

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




Это сообщение отредактировал(а) MastEdm - 8.8.2008, 14:04

да, это я что-то ступил маленько...
можно сначала отсортировать по счётчику, пробежаться, подобавлять в каждую запись позицию (т.е. индекс), а потом - по строкам, чтобы искать легко было
но быстрее n*log n вряд ли что-то получится...