> 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::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)
========================
Улучшение в пределах погрешности.
> Хэш функция не обязана использовать ВСЮ строку (данные в общем случае), > которую ей передают. В частности алфавитный указатель в словарях - пример хэш > таблицы. В этом случае хэшем является первая буква.
Пока не буду делать. Боюсь уволят. Наказали, чтобы просто и прозрачно было.
Похожих стандартных задач поиска уйма. Например, MySQL C API позволяет получить значение поля "рекордсет"-а по индексу (что в 90% практических задач достаточно), типа:
std::string val = get_StringField(size_t_field_index);
Иногда, правда, софтверные архитекторы просят, чтобы можно было получать полe "рекордсет"-а по его имени, типа:
std::string val = get_StringField("some_field_name");
При этом, конечно, интересует лексикографическое сравнение "some_field_name", и число полей, как правило, не велико, до 20.
Нехитрое применение google машины показывает предложения использовать от std::map или бинарного поиска по сорированному std::vector до хеширования.
Кстати, использование хеш таблиц есть в весима профессиональном коде, см., например, C# исходники MySQL .NET Connector 1.0.
Другое нехитрое сопоставление скорости получения индесов 15 полей рекордсета со случаиными именами по "значениям" этих полей с использованием прямого просмотра, бинарного поиска по сортированному std::vector, поиска елемента по ключу std::map
показывает, что:
vector - 30-40 ms
linear - 40-50 ms
map - 60-70 ms
Т.е при небольшом числе элементов ("полей") прямой просмотр - не хуже, а лучше c практической точки зрения с учётом накладных расходов.
Те результаты что выше не учитывают время, необходимое для создания std::vector, std::map, а в случае std::vector ещё и его сортировку. Т.е. это только затраты собственно на поиск. Поскольку в реальной программе это надо делать (создать std::vector или std::map, а в случае std::vector ещё сортировать его) , то результаты будут:
linear - 40-50 ms
vector - 110-150 ms
map - 170-210 ms
Может, я чего-то упускаю? Меня интересует мнение практиков. В схожих задачах вы делаете прямой просмотр? Похоже прямой просмотр - вне конкуренции.
[C++] У Кнута есть довольно подробное разжевывание преимуществ и недостатков алгоритмов.22.05.07 11:19 Автор: amirul <Serge> Статус: The Elderman
> Нехитрое применение google машины показывает предложения > использовать от std::map или бинарного поиска по > сорированному std::vector до хеширования.
Если бы набор данных был большим, то я бы их хранил в векторе, а к нему прицепил бы std::map или std::hash_map из boost::shared_ptr-ов (или boost::intrusive_ptr-ов) на элементы этого вектора.
> Кстати, использование хеш таблиц есть в весима > профессиональном коде, см., например, C# исходники MySQL > .NET Connector 1.0.
Ну к примеру майкрософтовский tcpip.sys использует хэш таблицы для связывания пар ip:port со внутренними структурами. Тоже далеко не новички писали :-)
Вообще хэш-таблицы - очень удобная штука. В своем классе задач, разумеется :-)
> Т.е при небольшом числе элементов ("полей") прямой просмотр > - не хуже, а лучше c практической точки зрения с учётом > накладных расходов.
Ага. Именно такой вывод сделан у Кнута.
> Те результаты что выше не учитывают время, необходимое для > создания std::vector, std::map, а в случае std::vector ещё > и его сортировку. Т.е. это только затраты собственно на > поиск. Поскольку в реальной программе это надо делать > (создать std::vector или std::map, а в случае std::vector > ещё сортировать его) , то результаты будут:
А это смотря сколько запросов будет на один вектор. Если одна сортировка - один запрос, то сортировать каждый раз - очень дорого. Если же на одну сортировку будет произовдиться много поисков, то лучше выполнить предвычисления.
> linear - 40-50 ms > vector - 110-150 ms > map - 170-210 ms
> Может, я чего-то упускаю? Меня интересует мнение практиков. > В схожих задачах вы делаете прямой просмотр? Похоже прямой > просмотр - вне конкуренции.
На малых размерах данных линейный поиск действительно заслуживает внимания. В данной конкретной задаче на мой взгляд все зависит от того, можно ли отнести сортировку вектора к предвычислениям (то есть является ли тип доступа write once read many) или нет. Если нужна еще бОльшая скорость, то на таких объемах данных очень неплохо должна проявить себя хэш-таблица.
Сортировка вектора всегда гарантирована в данной задаче.23.05.07 05:17 Автор: void <Grebnev Valery> Статус: Elderman
> Если бы набор данных был большим, то я бы их хранил в векторе, а к нему > прицепил бы std::map или std::hash_map из boost::shared_ptr-ов (или > boost::intrusive_ptr-ов) на элементы этого вектора.
Сортировка вектора всегда гарантирована в данной задаче.
Кстати вопрос - а гарантируется ли построение сбалансированного дерева std::map или 3party::map?
> А это смотря сколько запросов будет на один вектор. Если одна сортировка - > один запрос, то сортировать каждый раз - очень дорого.
То же относится и к map.
Только std::map хуже. В перед включением ключа std::string (по условию задачи) в map, его надо будет "привести" к верхнему/нижнему регистру.
Это потому, что сравнение должно быть лексикографическое (без учета регистра).
А перед поиском в map, соответственно привести к тому же регистру ключ.
Это очень затратная операция для std::string.
В практических задачах с вектором этого можно не делать, выполняя сортировку "как есть"; а бинарном поиске использовать _stricmp(str1.c_str(), str2.c_str()).
> Если нужна еще бОльшая скорость, то на таких объемах данных очень неплохо > должна проявить себя хэш-таблица.
Для хэш-таблицы перед вычислением хеша потребуется преобразование строки std::string к верхнему/нижнему регистру как при постоении таблицы, так и при определении индекса ("поиске").
Да. Логарифмическое (для худшего случая) время...23.05.07 11:21 Автор: amirul <Serge> Статус: The Elderman
> Сортировка вектора всегда гарантирована в данной задаче. > Кстати вопрос - а гарантируется ли построение > сбалансированного дерева std::map или 3party::map?
Да. Логарифмическое (для худшего случая) время поиска/вставки/удаления элемента в std::map - это требование стандарта. На данный момент я знаю только одну структуру данных, которая отвечает данным требованиям: RB-деревья. Соответственно std::map-ы практически всегда реализуются на них.
> > А это смотря сколько запросов будет на один вектор. > Если одна сортировка - > > один запрос, то сортировать каждый раз - очень дорого. > > То же относится и к map.
Ну, вставка КАЖДОГО элемента в map - операция с логарифмической сложностью. А сортировка массива - однократная операция. Хотя согласен, они похожи в том смысле, что если дерево/вектор создается только один раз, а потом из него только выбираются элементы, то поиск и в том и в другом - логарифмический.
> Только std::map хуже. В перед включением ключа std::string > (по условию задачи) в map, его надо будет "привести" к > верхнему/нижнему регистру.
> Это потому, что сравнение должно быть лексикографическое > (без учета регистра). > А перед поиском в map, соответственно привести к тому же > регистру ключ.
template <
class Key,
class Type,
class Traits = less<Key>,
class Allocator=allocator<pair <const Key, Type> >
>
class map
---
Есть целая пачка способов указать операцию сравнения для map-ы. Если не считать извращений с наследованием от std::string, то самыми логичными видятся два:
1. Специализация std::less<std::string>
2. Создание std::map<<Key, Type, case_insensitive_compare>
> Это очень затратная операция для std::string. > В практических задачах с вектором этого можно не делать, > выполняя сортировку "как есть"; а бинарном поиске > использовать _stricmp(str1.c_str(), str2.c_str()).
"Как есть" в данном случае это посимвольное преобразование регистра и первой и второй строки непосредственно в момент сравнения. Для худшего случая такой вариант будет в 2 раза медленнее, чем вариант с однократным преобразованием первой строки.
Да и в случае std::map этого тоже можно не делать, если есть увернность в том, что худшего случая не будет.
> Для хэш-таблицы перед вычислением хеша потребуется > преобразование строки std::string к верхнему/нижнему > регистру как при постоении таблицы, так и при определении > индекса ("поиске"). Хэш функция не обязана использовать ВСЮ строку (данные в общем случае), которую ей передают. В частности алфавитный указатель в словарях - пример хэш таблицы. В этом случае хэшем является первая буква.
[C++] Да. Логарифмическое (для худшего случая) время...25.05.07 05:16 Автор: 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::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)
========================
Улучшение в пределах погрешности.
> Хэш функция не обязана использовать ВСЮ строку (данные в общем случае), > которую ей передают. В частности алфавитный указатель в словарях - пример хэш > таблицы. В этом случае хэшем является первая буква.
Пока не буду делать. Боюсь уволят. Наказали, чтобы просто и прозрачно было.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
