информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыSpanning Tree Protocol: недокументированное применениеЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Phrack #70/0x46 
 Возможно, Facebook наступил на... 
 50 лет электронной почте 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
[C++] Да. Логарифмическое (для худшего случая) время... 25.05.07 05:16  Число просмотров: 2780
Автор: void <Grebnev Valery> Статус: Elderman
<"чистая" ссылка>
> RB-деревья. Соответственно std::map-ы практически
> всегда реализуются на них.

Спасибо. Хорошее замечния. Я думал, что используют B-деревья.

> Ну, вставка КАЖДОГО элемента в map - операция с логарифмической сложностью.
> А сортировка массива - однократная операция. Хотя согласен,
> они похожи в том смысле, что если дерево/вектор создается только один раз,
> а потом из него только выбираются элементы, то поиск и в том и в другом - логарифмический.

Да, но не всегда с логарифмической. Для поиска в сортированном в массиве (и в вецторе)
в принципе можно использовать алгоритмы быстре O(lоg n) взамен бинарного поиска
из стандартной библиотеки. В дереве этого не сделать.
Кстати, прямой просмотр может быть в ДЕСЯТКИ раз быстре О(n), O(lоg n),
если изестно распределение частот элементов массива.
У меня так работает примитивный адаптивный алгоритм (не в этих примерах)
с использованием эмпирических распределений.


> Есть целая пачка способов указать операцию сравнения для map-ы.
> Если не считать извращений с наследованием от std::string,
> то самыми логичными видятся два:
> 1. Специализация std::less<std::string>
> 2. Создание std::map<<Key, Type, case_insensitive_compare>

Наследовать от std::string нет необходимости.
Можно использовать чуть менее извращенное (хотя это вопрос ... изврат и есть изврат):
struct field {
std::string m_name;
field(const char* name ): m_name (name) {}
field(const std::string& name ): m_name (name) {}
bool operator < ( const field & f) const { return (stricmp(f.m_name.c_str() ,m_name.c_str()) < 0); }
};

std::map<const field, int, std::less<field>> m_field_map;


Но ведь в данной конкретной задаче это практически ничего не дает
в сравнении с куда более яснным
std::string str_toupper;
int (*fn_toupper)(int) = std::toupper;
m_field_map.clear();
for (unsigned int i = 0; i < m_field_count; i ++)
{
str_toupper = m_fields[i].name;
std::transform(str_toupper.begin(), str_toupper.end(), str_toupper.begin(), fn_toupper);
m_field_map[str_toupper] = i;
}

Сравни результаты, где в скобках даны результаты для мап с
bool operator < ( const field & f) const { return (stricmp(f.m_name.c_str() ,m_name.c_str()) < 0); }

========================
поиск:

vector - 30-40 ms (40 ms)
linear - (40-50 ms)
map - 60-70 ms (50-60 ms)

========================
создание вектора или мап и поиск:

vector - 110-150 ms (100-120 ms)
map - 170-210 ms (150-190 ms)

========================

Улучшение в пределах погрешности.

> Хэш функция не обязана использовать ВСЮ строку (данные в общем случае),
> которую ей передают. В частности алфавитный указатель в словарях - пример хэш
> таблицы. В этом случае хэшем является первая буква.

Пока не буду делать. Боюсь уволят. Наказали, чтобы просто и прозрачно было.

Спасибо.
<programming> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach