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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
[C++] У Кнута есть довольно подробное разжевывание преимуществ и недостатков алгоритмов. 22.05.07 11:19  Число просмотров: 3010
Автор: 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) или нет. Если нужна еще бОльшая скорость, то на таких объемах данных очень неплохо должна проявить себя хэш-таблица.
<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)

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

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

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

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

Спасибо.
1




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


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