информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медГде водятся OGRыSpanning Tree Protocol: недокументированное применение
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Ростелеком заподозрили в попытке... 
 Линуксовый ботнет, распространяющийся... 
 Конец поддержки Internet Explorer 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
[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)

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

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

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

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

Спасибо.
1




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


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