Голосование

Автор: Gattaka
Дата: 18.06.17
Вопрос: Как часто в реальных, рабочих проектах вы говорили: "Неее... здесь лучше использовать не хэш таблицу, а двоичное дерево". И это было действительно необходимо.

Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.

Здравствуйте, Gattaka, Вы писали:

G>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.

Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы.

Здравствуйте, Gattaka, Вы писали:

G>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.

Ну, например, когда надо искать не среди конкретных значений, а среди диапазонов значений, хеш-таблица не слишком-то подойдет.

Здравствуйте, Nuzhny, Вы писали:

N>Здравствуйте, Gattaka, Вы писали:

G>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.

N>Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы.

Ну это в вашем С++ мире. В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)

Здравствуйте, Gattaka, Вы писали:

G>>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.

N>>Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы.

G>Ну это в вашем С++ мире.

Задача от языка тут не зависит. Или нужен поиск по неточному равенству по ключу, или нет — это свойство задачи.
Очень много задач такого не требуют. Но много есть таких, что требуют.

G> В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)

([UPDATE: перепутал с прямым углом, отменено])

Для дотнета есть, например, такая реализация полноценного дерева с поиском по неточному равенству. Наверняка же не просто так придумали

Здравствуйте, netch80, Вы писали:

N>Задача от языка тут не зависит. Или нужен поиск по неточному равенству по ключу, или нет — это свойство задачи.
N>Очень много задач такого не требуют. Но много есть таких, что требуют.
И вот как раз эти задачи решают на С++.

G>> В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)

N>O(1) — это что-то фантастическое. У хэша амортизированная O(log n) на все операции. Если Вы вспомнили, что в MSDN упомянуто O(1) для чтения значения, то это именно для чтения, когда оно уже уложено в память в нужных местах.

N>Для дотнета есть, например, такая реализация полноценного дерева с поиском по неточному равенству.

Здравствуйте, netch80, Вы писали:

N>Здравствуйте, Gattaka, Вы писали:

G>> В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)

N>O(1) — это что-то фантастическое. У хэша амортизированная O(log n) на все операции. Если Вы вспомнили, что в MSDN упомянуто O(1) для чтения значения, то это именно для чтения, когда оно уже уложено в память в нужных местах.

У хэш-таблицы амортизированное время (aka среднее) для поиска, вставки и удаления O(1). Худшее — линейное.
O(n) при вставке для худшего случая возникает при рехэшинге. Который происходит примерно раз на n вставок, а n/n = 1, отсюда имеем среднее время O(1). На пальцах как-то так.
Можно в википедии посмотреть https://en.wikipedia.org/wiki/Hash_table .

Здравствуйте, anton_t, Вы писали:

G>>> В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)
N>>O(1) — это что-то фантастическое. У хэша амортизированная O(log n) на все операции. Если Вы вспомнили, что в MSDN упомянуто O(1) для чтения значения, то это именно для чтения, когда оно уже уложено в память в нужных местах.
_>У хэш-таблицы амортизированное время (aka среднее) для поиска, вставки и удаления O(1). Худшее — линейное.
_>O(n) при вставке для худшего случая возникает при рехэшинге. Который происходит примерно раз на n вставок, а n/n = 1, отсюда имеем среднее время O(1). На пальцах как-то так.

Угу. Что-то я не проснулся. ;(

Здравствуйте, Gattaka, Вы писали:

N>>Задача от языка тут не зависит. Или нужен поиск по неточному равенству по ключу, или нет — это свойство задачи.
N>>Очень много задач такого не требуют. Но много есть таких, что требуют.
G>И вот как раз эти задачи решают на С++.

Почему сразу на C++? Есть куча других вариантов. Java, например

Здравствуйте, netch80, Вы писали:

N>Почему сразу на C++? Есть куча других вариантов. Java, например

Нет. Такие низкоуровневые вещи делают на С++. В более высокоуровневых языках используют это как внешние библиотеки, СУБД и т.п.

Здравствуйте, Gattaka, Вы писали:

G>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.

Бывали случаи, когда использовал boost::flat_map (обёртку над отсортированным массивом) для производительности (на небольших объёмах это оказывается эффективнее хеш-таблицы std::unordered_map)

Бывали случаи, когда требуется работа с диапазонами или отсортированность по другим причинам. Тут и binary tree (std::map) приходилось применять.

Здравствуйте, Gattaka, Вы писали:

N>>Почему сразу на C++? Есть куча других вариантов. Java, например

G>Нет. Такие низкоуровневые вещи делают на С++. В более высокоуровневых языках используют это как внешние библиотеки, СУБД и т.п.

"Отучаемся говорить за всех" (tm)
Я с ходу нашёл в нашем коде несколько использований явовского TreeMap.
И теор. обоснований Вашему тезису что-то не видно даже на горизонте.

Здравствуйте, netch80, Вы писали:

N>"Отучаемся говорить за всех" (tm)
N>Я с ходу нашёл в нашем коде несколько использований явовского TreeMap.
"Отучаемся считать свой код эталоном красоты"
Я имею наглость спросить может это косяк? Просто предположение. Было у нас как-то соревнование между программистами нужно сделать было сервер по ТЗ. Так вот на NodeJS сделали его за час. C++ программиста за день не справились, т.к. надо ведь строчки парсить, кодировки мучать и пр. Начали писать свой nginx, в общем симптомы С++ налицо.

Здравствуйте, Pzz, Вы писали:

Pzz>Ну, например, когда надо искать не среди конкретных значений, а среди диапазонов значений, хеш-таблица не слишком-то подойдет.
Погоди ка а диапозоны как?

Здравствуйте, Gattaka, Вы писали:

G>Так вот на NodeJS сделали его за час.
G> C++ программиста за день не справились
Вот это ты щас на полном серьёзе сравниваешь языки по скорости написания веб сервера когда для одного языка есть либы, которые как раз под написание серваков и заточены, а для второго таких либ под рукой не было.

G>в общем симптомы С++ налицо.
Ну ну.

Здравствуйте, Gattaka, Вы писали:

Pzz>>Ну, например, когда надо искать не среди конкретных значений, а среди диапазонов значений, хеш-таблица не слишком-то подойдет.
G>Погоди ка а диапозоны как?

Уууу, алгоритмы то знать таки надо.

Здравствуйте, Gattaka, Вы писали:

G>Здравствуйте, netch80, Вы писали:

N>>"Отучаемся говорить за всех" (tm)
N>>Я с ходу нашёл в нашем коде несколько использований явовского TreeMap.
G>"Отучаемся считать свой код эталоном красоты"

Странные у тебя фантазии.

G>Я имею наглость спросить может это косяк? Просто предположение.

Нет, не косяк.

G> Было у нас как-то соревнование между программистами нужно сделать было сервер по ТЗ. Так вот на NodeJS сделали его за час. C++ программиста за день не справились, т.к. надо ведь строчки парсить, кодировки мучать и пр. Начали писать свой nginx, в общем симптомы С++ налицо.

К чему всё это в данной теме?

Здравствуйте, Gattaka, Вы писали:

G>Здравствуйте, Pzz, Вы писали:

Pzz>>Ну, например, когда надо искать не среди конкретных значений, а среди диапазонов значений, хеш-таблица не слишком-то подойдет.
G>Погоди ка а диапозоны как?

Ну, допустим, у нас есть набор непересекающихся диапазонов (к примеру, адреса в памяти), и нам надо по заданному адресу уметь определять, в какой диапазон он попадает.

Строим дерево поиска, в каждом узле которого хранится диапазон, а функция сравнения смотрит, какой диапазон левее, тот и "меньше". Поскольку диапазоны у нас не пересекаются, это несложно.

Теперь поиск. Идем, как обычно, от корня. Если искомый адрес левее начала диапазона, идем налево, если правее конца — направо. Иначе нашли. Если идти больше некуда, а все еще не нашли, значит уже совсем не нашли.

Как-то вот так.

Здравствуйте, Gattaka, Вы писали:

N>>Почему сразу на C++? Есть куча других вариантов. Java, например

G>Нет. Такие низкоуровневые вещи делают на С++. В более высокоуровневых языках используют это как внешние библиотеки, СУБД и т.п.

Звучит, как религиозная догма. А если так не делать, отлучат от Святой Церкви Явы, и больше нигде чашку кофе не подадут?

Здравствуйте, netch80, Вы писали:

N>Для дотнета есть, например, такая реализация полноценного дерева с поиском по неточному равенству. Наверняка же не просто так придумали

Для дотнета есть даже штатная реализация R/B tree, называется SortedDictionary. Название это как бы намекаэ, в каких случаях обычный Dictionary не катит.