Здравствуйте, Gattaka, Вы писали:
G>Просто предположение. Было у нас как-то соревнование между программистами нужно сделать было сервер по ТЗ. Так вот на NodeJS сделали его за час. C++ программиста за день не справились, т.к. надо ведь строчки парсить, кодировки мучать и пр. Начали писать свой nginx, в общем симптомы С++ налицо.
С учётом того, что сам Node.JS написан на C++, а его встроенный сервер работает через известную библиотеку, написанную вообще на C, это высказывание выглядит особо комично.
Re[5]: [Голосование] Нужен ли binary tree если есть hash таб
Здравствуйте, Ночной Смотрящий, Вы писали:
N>>Для дотнета есть, например, такая реализация полноценного дерева с поиском по неточному равенству. Наверняка же не просто так придумали
НС>Для дотнета есть даже штатная реализация R/B tree, называется SortedDictionary.
Я в курсе, но её способности ниже плинтуса — именно поисковые операции не включены.
Здравствуйте, alex_public, Вы писали:
G>>Просто предположение. Было у нас как-то соревнование между программистами нужно сделать было сервер по ТЗ. Так вот на NodeJS сделали его за час. C++ программиста за день не справились, т.к. надо ведь строчки парсить, кодировки мучать и пр. Начали писать свой nginx, в общем симптомы С++ налицо.
_>С учётом того, что сам Node.JS написан на C++, а его встроенный сервер работает через известную библиотеку, написанную вообще на C, это высказывание выглядит особо комично.
Оно неуместно (никак не связано с моей репликой), но не комично. Нода выступила профильной библиотекой.
The God is real, unless declared integer.
Re[10]: [Голосование] Нужен ли binary tree если есть hash таблица
Дерево даёт упорядоченность. Это и плюс (если она нужна) и минус (элементам нужен компаратор). Обе структуры нужны.
Вот вопрос — зачем нужен связный список, если есть массив, интересней. Теоретически на очень больших размерах связный список выиграет на O(1) операциях, но практически я до таких размеров не доходил. Массив практически всегда лучше.
Re[11]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, Gattaka, Вы писали:
G>>>Я имею наглость спросить может это косяк? Просто предположение.
N>>Нет, не косяк.
G>Остается лишь только поверить. Но я не буду.
Ну, теперь Вам осталось отменить результаты голосования. Под предлогом явной фальсификации.
The God is real, unless declared integer.
Re[3]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, Gattaka, Вы писали:
G>>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.
N>>Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы.
G>Ну это в вашем С++ мире. В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n)
На всякий случай напомню, что в реальном мире n вряд ли будет даже сравнима с 2^64. Обычно на много порядков меньше. Т.е. O(log N) можно ограничить O(1) для реальных задач и константа будет совсем не велика. А вот тот факт, что хеш-таблица может при вставке начать всё копировать в новую структуру, если старая забита, вносит определённую непредсказуемость.
Re[2]: [Голосование] Нужен ли binary tree если есть hash таб
Здравствуйте, vsb, Вы писали:
vsb>Дерево даёт упорядоченность. Это и плюс (если она нужна) и минус (элементам нужен компаратор). Обе структуры нужны.
[UPD] А для хэша нужен собственно hash code. Иногда получается, что сравнить элементы можно, а вот получить от элемента что-то, достойное для использования как хэш-код — дзуськи.
vsb>Вот вопрос — зачем нужен связный список, если есть массив, интересней. Теоретически на очень больших размерах связный список выиграет на O(1) операциях, но практически я до таких размеров не доходил. Массив практически всегда лучше.
Так надо померять доли операций (добавление/удаление в конец/в начало/в середину, etc.)
Тогда можно будет оценить влияние.
А ещё есть вариант массива массивов. А ещё его можно дорастить до дерева массивов
G>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.
Двоичное дерево нужно, если:
— функции хеширования нет, а компаратор есть (к примеру, для сложных объектов)
— множество на двоичном дереве уже отсортировано (а мапа отсортирована по ключу)
А вообще equals/hashCode на каждом объекте — великое изобретение Java, значительно увеличивающее её быстродействие.
Re[4]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, vsb, Вы писали:
G>>>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло. N>>>Скорее наоборот: сразу используется дерево (std::map). Если что-то не устраивает, то уже хэш таблица. У дерева есть очевидные преимущества: всегда доступен максимальный и минимальный элементы. G>>Ну это в вашем С++ мире. В дотнет я сколько не общался с коллегами все используют Dictionary. А это ведь скорость доступа в том числе. O(1) против O(log n) vsb>На всякий случай напомню, что в реальном мире n вряд ли будет даже сравнима с 2^64. Обычно на много порядков меньше. Т.е. O(log N) можно ограничить O(1) для реальных задач и константа будет совсем не велика.
При необходимости неточного поиска — да. Иначе же оказывается, что хэш-таблицы дешевле. А где-то даже 5% может значить победу над конкурентами.
vsb> А вот тот факт, что хеш-таблица может при вставке начать всё копировать в новую структуру, если старая забита, вносит определённую непредсказуемость.
Incremental resizing не так редко — например, AFAIR, в MSVC STL оно вместе с двоичным размером таблицы.
The God is real, unless declared integer.
Re[12]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, netch80, Вы писали:
N>Ну, теперь Вам осталось отменить результаты голосования. Под предлогом явной фальсификации.
Да ну что вы, я охотно допускаю наличие не только людей которые занимаются разработкой действительно критичных ко времени выполнения приложений. Но и большого числа говнокодеров, которые прочитали книгу по алгоритмам и теперь пытаются сверкать своими знаниями.
Re[13]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, Gattaka, Вы писали:
N>>Ну, теперь Вам осталось отменить результаты голосования. Под предлогом явной фальсификации.
G>Да ну что вы, я охотно допускаю наличие не только людей которые занимаются разработкой действительно критичных ко времени выполнения приложений. Но и большого числа говнокодеров, которые прочитали книгу по алгоритмам и теперь пытаются сверкать своими знаниями.
Ч.Т.Д.
Спасибо за откровенность.
The God is real, unless declared integer.
Re[14]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, Gattaka, Вы писали:
G>Здравствуйте, netch80, Вы писали:
N>>Ч.Т.Д. N>>Спасибо за откровенность.
G>Ни одного реального примера в ветке так и не смогли привести. Это показатель.
Я бы мог покопать, самому немного интересно, и время есть. Но после того, как ты вначале открыл голосование, а потом фактически обвинил в профессиональной некомпетентности (дословно: "большого числа говнокодеров, которые прочитали книгу по алгоритмам и теперь пытаются сверкать своими знаниями") проголосовавших против твоей позиции (на сейчас минимум 7+32+9 == 48%) — я сильно сомневаюсь, что стоит тебе отвечать конструктивно — это будет метание бисера перед сам знаешь кем.
Поэтому я лично приведу пример не раньше, чем ты в этой теме публично принесёшь извинения за фразу про "говнокодеров" и "пытаются сверкать".
The God is real, unless declared integer.
Re[16]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, netch80, Вы писали:
N>Поэтому я лично приведу пример не раньше, чем ты в этой теме публично принесёшь извинения за фразу про "говнокодеров" и "пытаются сверкать".
До чего у вас на Украине менталитет конфликтный. Казалось бы безобидный вопрос заданный еще в самом начале разговора остался не только без ответа, но еще подтянули минометы, танки, батальен Азов и понеслось. Прям ты приведешь пример, щаз.
Re: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, Gattaka, Вы писали:
G>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.
Постоянно нужно. Для нескольких целей:
1) Запросы по диапазону ключей.
2) Упорядоченный перебор.
3) Подмножество пункта 2 — полностью воспроизводимые результаты. Т.е. чтобы два запуска с одними и теми же данными выдавали одинаковый результат.
Язык — Java.
Sapienti sat!
Re[3]: [Голосование] Нужен ли binary tree если есть hash таб
Здравствуйте, netch80, Вы писали:
vsb>>Дерево даёт упорядоченность. Это и плюс (если она нужна) и минус (элементам нужен компаратор). Обе структуры нужны.
N>[UPD] А для хэша нужен собственно hash code. Иногда получается, что сравнить элементы можно, а вот получить от элемента что-то, достойное для использования как хэш-код — дзуськи.
Ну получить хэш код можно всегда, я по крайней мере не представляю, когда нельзя, разве что элемент это какой-то очень чёрный ящик, но это уже проблема архитектуры.
Re[2]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, netch80, Вы писали:
vsb>> А вот тот факт, что хеш-таблица может при вставке начать всё копировать в новую структуру, если старая забита, вносит определённую непредсказуемость.
N>Incremental resizing не так редко — например, AFAIR, в MSVC STL оно вместе с двоичным размером таблицы.
А как это работает? Индексы же меняются при изменении размера таблицы, даже если в 2 раза увеличивать, половину элементов нужно переставлять.
Re[6]: [Голосование] Нужен ли binary tree если есть hash таблица
Здравствуйте, vsb, Вы писали:
vsb>>> А вот тот факт, что хеш-таблица может при вставке начать всё копировать в новую структуру, если старая забита, вносит определённую непредсказуемость.
N>>Incremental resizing не так редко — например, AFAIR, в MSVC STL оно вместе с двоичным размером таблицы.
vsb>А как это работает? Индексы же меняются при изменении размера таблицы, даже если в 2 раза увеличивать, половину элементов нужно переставлять.
Ну да, так оно и работает. На каждую изменяющую операцию с таблицей — берётся 1-2 элемента из старой таблицы, пересчитывается хэш и вставляется в новую в нужное место.
При этом по старой таблице ползёт такой себе чистильщик, убирающий из неё элементы из последовательных позиций массива.
В случае двоичных таблиц там эта передвижка в новую таблицу упрощается (если упрощается). Смутно помнится, что её могут так ресайзить на месте, тогда после одного собственно realloc на массив (дорогой) уже примерно половину элементов не надо переставлять в новую верхнюю половину таблицы, а другую примерно половину таки переносят. Что-то не могу нагуглить детали, так что всё по памяти.
