Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | |
Да. Логарифмическое (для худшего случая) время... 23.05.07 11:21 Число просмотров: 3489
Автор: 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 к верхнему/нижнему
> регистру как при постоении таблицы, так и при определении
> индекса ("поиске").
Хэш функция не обязана использовать ВСЮ строку (данные в общем случае), которую ей передают. В частности алфавитный указатель в словарях - пример хэш таблицы. В этом случае хэшем является первая буква.
|
|
<programming>
|
[C++] Найти индекс "поля" рекордсет-а по имени (анти-оптимизация). 22.05.07 06:20
Автор: void <Grebnev Valery> Статус: Elderman
|
Похожих стандартных задач поиска уйма. Например, 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::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)
========================
Улучшение в пределах погрешности.
> Хэш функция не обязана использовать ВСЮ строку (данные в общем случае),
> которую ей передают. В частности алфавитный указатель в словарях - пример хэш
> таблицы. В этом случае хэшем является первая буква.
Пока не буду делать. Боюсь уволят. Наказали, чтобы просто и прозрачно было.
Спасибо.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
