Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Ассоциативный контейнер


Автор: MastEdm 22.7.2008, 09:39
Добрый день.

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

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

Автор: vinter 22.7.2008, 10:04
Цитата(MastEdm @  22.7.2008,  10:39 Найти цитируемый пост)
но тогда для увеличения счетчика придется сначала каким-то образом находить нужную запись

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

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

Автор: vinter 22.7.2008, 11:23
Цитата(MastEdm @  22.7.2008,  12:05 Найти цитируемый пост)
Но ведь если у нас сортировка задана по счетчику, то это будет неэффективно, тем более для строк с большим значением счетчика. 

O(ln(n))
Цитата(MastEdm @  22.7.2008,  12:05 Найти цитируемый пост)
А как в таком случае искать нужную пару? С помощью пары ("строка", 1)?

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

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

Автор: xvr 22.7.2008, 11:40
Цитата(MastEdm @ 22.7.2008,  09:39)
Добрый день.

Задача такая. Построить рейтинг строк, подсчитать, сколько раз встречается каждая строка.

boost::multi_index_container

Автор: vinter 22.7.2008, 12:24
Цитата(MastEdm @  22.7.2008,  12:29 Найти цитируемый пост)
Ну вот когда добавляем очередную строку: если она есть (вот тут нужно найти пару ("строка", [число])), то её счетчик увеличивается на 1, в противном случае добавляем пару ("строка", 1).  

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

Автор: MastEdm 22.7.2008, 13:07
Ясно. Спасибо smile  

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

Автор: MastEdm 22.7.2008, 15:07
Цитата(xvr @ 22.7.2008,  11:40)
Цитата(MastEdm @ 22.7.2008,  09:39)
Добрый день.

Задача такая. Построить рейтинг строк, подсчитать, сколько раз встречается каждая строка.

boost::multi_index_container

А вы не могли бы набросать примерчик, а то я в boost не силен и первое знакомство (http://www.solarix.ru/for_developers/cpp/boost/multi_index/ru/an/multi_index.shtml) как-то не пошло

Автор: vinter 22.7.2008, 16:08
Цитата(MastEdm @  22.7.2008,  14:07 Найти цитируемый пост)
А что эффективнее: map с map["строка"] += 1 или set с find_if()? То есть использует ли find_if() информацию о последовательности или же тупо циклом просматривает все элементы?

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

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

Автор: Ulysses4j 22.7.2008, 19:41
Цитата(xvr @  22.7.2008,  12:40 Найти цитируемый пост)
boost::multi_index_container

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

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

Автор: xvr 23.7.2008, 10:53
Цитата(MastEdm @ 22.7.2008,  15:07)
Цитата(xvr @ 22.7.2008,  11:40)
Цитата(MastEdm @ 22.7.2008,  09:39)
Добрый день.

Задача такая. Построить рейтинг строк, подсчитать, сколько раз встречается каждая строка.

boost::multi_index_container

А вы не могли бы набросать примерчик, а то я в boost не силен и первое знакомство (http://www.solarix.ru/for_developers/cpp/boost/multi_index/ru/an/multi_index.shtml) как-то не пошло

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

Автор: MastEdm 5.8.2008, 22:03
И все-таки если вернуться к эффективности. Добавление в 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 работают быстрее. Если я неправ, переубедите меня smile 

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

Код

class top
{
    private:
        static const unsigned size = 1000;

        struct node
        {
            unsigned id;
            unsigned count;
            unsigned pos;
        };

        typedef std::map<unsigned, node*> top_t;

        top_t top_map;
        node* table[size];

        int end_pos;

    public:

        top()
        {
            end_pos = 0;
        }

        ~top() { ; }

        void add ( unsigned id )
        {
            top_t::iterator iter = top_map.find ( id );
            if ( iter != top_map.end() )
            {
                node* nd = ( *iter ).second;
                nd->count += 1;
                unsigned pos = nd->pos;
                // Пересчитываем топ, поднимая в нем нужную запись
                }
            }
            else
            {
                if ( end_pos < size )
                {
                    node* nd = new node();
                    nd->id = id;
                    nd->count = 1;
                    nd->pos = end_pos;
                    table[nd->pos] = nd;
                    end_pos += 1;
                    top_map[id] = nd;
                }
            }
        }

        unsigned get_pos_by_id ( unsigned id )
        {
            top_t::iterator iter = top_map.find ( id );
            if ( iter != top_map.end() )
            {
                return ( *iter ).second->pos;
            }
            else
            {
                return static_cast<unsigned> ( -1 );
            }
        }

        void print_table()
        {
            for ( int i = 0; i < end_pos; ++i )
            {
                std::cout << table[i]->pos << " " << table[i]->id << " "
                << table[i]->count << std::endl;
            }
        }
};


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

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

Автор: maxim1000 6.8.2008, 22:21
Цитата(MastEdm @  6.8.2008,  17:20 Найти цитируемый пост)
При таком раскладе добавление за log(n)

ох, не уверен
вот этот цикл:
Цитата(MastEdm @  6.8.2008,  17:20 Найти цитируемый пост)

                    while ( table[pos]->count > table[prev]->count )
                    {
                        if ( prev == 0 ) break;
                        prev -= 1;
                    }

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

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

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

Автор: MastEdm 7.8.2008, 22:00
Цитата(maxim1000 @ 6.8.2008,  22:21)

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

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

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

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

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

struct node {
    int id;        // Id строки
    int count; // Счетчик
    int pos;    // Позиция в рейтинге
};

node* table[SIZE];
node* top[SIZE];

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

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

Автор: maxim1000 8.8.2008, 15:22
Цитата(MastEdm @  7.8.2008,  22:00 Найти цитируемый пост)
И сортировать нужно не по строкам, а по счетчику. Мы ведь рейтинг строим. А если отсортировано по счетчику, то по строке искать за логарифм не получится.

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)