Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
[C++] Да. Логарифмическое (для худшего случая) время... 25.05.07 05:16 Число просмотров: 3098
Автор: 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)
========================
Улучшение в пределах погрешности.
> Хэш функция не обязана использовать ВСЮ строку (данные в общем случае),
> которую ей передают. В частности алфавитный указатель в словарях - пример хэш
> таблицы. В этом случае хэшем является первая буква.
Пока не буду делать. Боюсь уволят. Наказали, чтобы просто и прозрачно было.
Спасибо.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
[C++] Да. Логарифмическое (для худшего случая) время... - void