Сообщение Re[3]: [Голосование] Нужен ли binary tree если есть hash таб от 19.06.2017 9:49
Изменено 19.06.2017 12:34 netch80
Re[3]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, Gattaka, Вы писали:
G>>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.
N>>Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы.
G>Ну это в вашем С++ мире.
Задача от языка тут не зависит. Или нужен поиск по неточному равенству по ключу, или нет — это свойство задачи.
Очень много задач такого не требуют. Но много есть таких, что требуют.
G> В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)
O(1) — это что-то фантастическое. У хэша амортизированная O(log n) на все операции. Если Вы вспомнили, что в MSDN упомянуто O(1) для чтения значения, то это именно для чтения, когда оно уже уложено в память в нужных местах.
Для дотнета есть, например, такая реализация полноценного дерева с поиском по неточному равенству.
G>>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.
N>>Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы.
G>Ну это в вашем С++ мире.
Задача от языка тут не зависит. Или нужен поиск по неточному равенству по ключу, или нет — это свойство задачи.
Очень много задач такого не требуют. Но много есть таких, что требуют.
G> В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)
O(1) — это что-то фантастическое. У хэша амортизированная O(log n) на все операции. Если Вы вспомнили, что в MSDN упомянуто O(1) для чтения значения, то это именно для чтения, когда оно уже уложено в память в нужных местах.
Для дотнета есть, например, такая реализация полноценного дерева с поиском по неточному равенству.
Re[3]: [Голосование] Нужен ли binary tree если есть hash таб
Здравствуйте, Gattaka, Вы писали:
G>>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.
N>>Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы.
G>Ну это в вашем С++ мире.
Задача от языка тут не зависит. Или нужен поиск по неточному равенству по ключу, или нет — это свойство задачи.
Очень много задач такого не требуют. Но много есть таких, что требуют.
G> В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)
([UPDATE: перепутал с прямым углом, отменено])
Для дотнета есть, например, такая реализация полноценного дерева с поиском по неточному равенству. Наверняка же не просто так придумали
G>>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.
N>>Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы.
G>Ну это в вашем С++ мире.
Задача от языка тут не зависит. Или нужен поиск по неточному равенству по ключу, или нет — это свойство задачи.
Очень много задач такого не требуют. Но много есть таких, что требуют.
G> В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)
([UPDATE: перепутал с прямым углом, отменено])
Для дотнета есть, например, такая реализация полноценного дерева с поиском по неточному равенству. Наверняка же не просто так придумали