VPF::Ассоциативный контейнер - Форум программистов

MastEdm

Дата 6.8.2008, 17:20 (ссылка)

(нет голосов)

Загрузка ...

Master

Профиль
Группа: Участник
Сообщений: 178
Регистрация: 3.12.2005
Где: Москва, МГИУ

Репутация: 1
Всего: 2

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

Код


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...

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

maxim1000

Дата 6.8.2008, 22:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 17
Всего: 110

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

--------------------

qqq

MastEdm

Дата 6.8.2008, 22:28 (ссылка)

(нет голосов)

Загрузка ...

Master

Профиль
Группа: Участник
Сообщений: 178
Регистрация: 3.12.2005
Где: Москва, МГИУ

Репутация: 1
Всего: 2

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

MastEdm

Дата 7.8.2008, 22:00 (ссылка)

(нет голосов)

Загрузка ...

Master

Профиль
Группа: Участник
Сообщений: 178
Регистрация: 3.12.2005
Где: Москва, МГИУ

Репутация: 1
Всего: 2

Цитата(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

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

maxim1000

Дата 8.8.2008, 15:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 17
Всего: 110

Цитата(MastEdm @ 7.8.2008, 22:00

)

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

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

--------------------

qqq

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »