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

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

G>>Коллеги, создал голосование о необходимости выбора между binary tree и хэш таблицей. Если вы такой выбор осуществляли не могли бы вы описать код и ситуацию где это возникло.
C>Постоянно нужно. Для нескольких целей:
C>1) Запросы по диапазону ключей.
C>2) Упорядоченный перебор.
C>3) Подмножество пункта 2 — полностью воспроизводимые результаты. Т.е. чтобы два запуска с одними и теми же данными выдавали одинаковый результат.
Может лучше бы это делала база данных? Все равно вы до ее реализации не дотянете и будет хуже по производительности.

C>Язык — Java.

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

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

scf>>А вообще equals/hashCode на каждом объекте — великое изобретение Java, значительно увеличивающее её быстродействие.

vsb>Можно раскрыть мысль? equals и hashCode из Object бесполезны чуть менее чем полностью. Мне никогда не нравилась эта куча мусора в Object.

А как хэш-таблица (Dictionary в .net) по умолчанию работает? Через hashcode.

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

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

scf>>А вообще equals/hashCode на каждом объекте — великое изобретение Java, значительно увеличивающее её быстродействие.

vsb>Можно раскрыть мысль? equals и hashCode из Object бесполезны чуть менее чем полностью. Мне никогда не нравилась эта куча мусора в Object.

Это вопрос дизайна языка. equals/hashСode в Object подталкивают программистов к их переопределению в собственных объектах, тем более, что equals почти всегда нужен, а правила соответствия equals/hashСode вдалбливаются начинающим программистам с самого начала изучения языка.

В итоге — любой объект можно использовать в качестве ключа HashMap и у большинства классов equals/hashСode определены верно. Поэтому java программисты везде используют хеш таблицу вместо менее эффективного двоичного дерева.

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

_>>С учётом того, что сам Node.JS написан на C++, а его встроенный сервер работает через известную библиотеку, написанную вообще на C, это высказывание выглядит особо комично.
N>Оно неуместно (никак не связано с моей репликой), но не комично. Нода выступила профильной библиотекой.

В том то и дело, что нет. Ну т.е. если бы там http сервер был стандартной библиотечкой написаной на js, то твоё утверждение было бы верным. Однако там вся основная работа делается известной библиотечкой на C, которая и является тут "профильной". Причём её спокойно используют из множества других языков/платформ для буквально тех же целей.

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

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

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

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

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

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

  public
      enum NavigateFlag : byte
{ 
  Eqality,           // ==
  LessThan,          // <
  GreaterThan,       // >
  LessThanOrEqval,   // <=
  GreaterThanOrEqval // >=
}

Создание эффективной реализации сортированного списка с использованием generics

Автор(ы): Сергей Смирнов (Serginio1)
Дата: 14.08.2004
Пример реализации двухуровневого массива с помощью нового средства С# — generics. Сравнение производительности различных реализаций сортированных списков.

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

S>А как хэш-таблица (Dictionary в .net) по умолчанию работает? Через hashcode.

Да никак она по умолчанию не работает. Не перегрузишь hashCode и не будет работать. Точнее будет, как ссылочный объект, но толку от такой структуры немного, в 99% случаев не нужно. Было бы в виде интерфейса — можно было бы на этапе компиляции отлавливать ошибки, если не реализовал hashCode.

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

scf>>>А вообще equals/hashCode на каждом объекте — великое изобретение Java, значительно увеличивающее её быстродействие.

vsb>>Можно раскрыть мысль? equals и hashCode из Object бесполезны чуть менее чем полностью. Мне никогда не нравилась эта куча мусора в Object.

scf>Это вопрос дизайна языка. equals/hashСode в Object подталкивают программистов к их переопределению в собственных объектах, тем более, что equals почти всегда нужен, а правила соответствия equals/hashСode вдалбливаются начинающим программистам с самого начала изучения языка.

Не знаю, я вроде не начинающий программист, но меня это никуда не подталкивало никогда. Если реально нужен equals — переопределяю. Если объект в виде ключа в хеш-таблице используется — переопределяю hashCode. Просто так — зачем, это же мёртвый код, а к нему по-хорошему и тесты писать надо и в будущем поддерживать. А вот забыть и использовать вполне можно. Было бы по уму сделано, такой код не скомпилировался бы. По-хорошему должны быть интерфейсы Equatable, Hashable, так же как Comparable и если нужны соотв. методы, реализуешь интерфейс. Либо, что ещё правильней, определять отдельные объекты вроде Equator, Hasher по аналогии с Comparator и передавать их в соотв. структуры данных.

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

scf>>Это вопрос дизайна языка. equals/hashСode в Object подталкивают программистов к их переопределению в собственных объектах, тем более, что equals почти всегда нужен, а правила соответствия equals/hashСode вдалбливаются начинающим программистам с самого начала изучения языка.

vsb>Не знаю, я вроде не начинающий программист, но меня это никуда не подталкивало никогда. Если реально нужен equals — переопределяю. Если объект в виде ключа в хеш-таблице используется — переопределяю hashCode.

Правила таки о том, что это надо делать одновременно. Если ты переопределил hashCode() => переопредели и equals(), и наоборот.
Иначе с хэш-таблицами таки будут проблемы — например, оно найдёт позицию, куда записать ключ, но не сможет заменить его предыдущую версию.

vsb> Просто так — зачем, это же мёртвый код, а к нему по-хорошему и тесты писать надо и в будущем поддерживать. А вот забыть и использовать вполне можно. Было бы по уму сделано, такой код не скомпилировался бы.

Ну, это всё-таки ещё не для мэйнстрим-языка образца 95-го года.

vsb> По-хорошему должны быть интерфейсы Equatable, Hashable, так же как Comparable и если нужны соотв. методы, реализуешь интерфейс. Либо, что ещё правильней, определять отдельные объекты вроде Equator, Hasher по аналогии с Comparator и передавать их в соотв. структуры данных.

Ну в плюсах есть такая возможность, но по умолчанию они используют таки стандартные сравнения.

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

C>>3) Подмножество пункта 2 — полностью воспроизводимые результаты. Т.е. чтобы два запуска с одними и теми же данными выдавали одинаковый результат.
G>Может лучше бы это делала база данных? Все равно вы до ее реализации не дотянете и будет хуже по производительности.
Ну почему у этих формочкопрограммистов всё всегда к БД сводится? Я пишу код, в котором работы с БД часто нет вообще.

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

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

Это потому, что за вас уже сделали всю работу в самом Node.js — весь парсинг, обработка ошибок, асинхронщина и тд и тд. Все что надо — связать вместе.

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

scf>>>Это вопрос дизайна языка. equals/hashСode в Object подталкивают программистов к их переопределению в собственных объектах, тем более, что equals почти всегда нужен, а правила соответствия equals/hashСode вдалбливаются начинающим программистам с самого начала изучения языка.

vsb>>Не знаю, я вроде не начинающий программист, но меня это никуда не подталкивало никогда. Если реально нужен equals — переопределяю. Если объект в виде ключа в хеш-таблице используется — переопределяю hashCode.

N>Правила таки о том, что это надо делать одновременно. Если ты переопределил hashCode() => переопредели и equals(), и наоборот.

Ну дык Hashable extends Equatable или Hasher extends Equator и опять же имеем типизированную проверку этого факта.

vsb>> По-хорошему должны быть интерфейсы Equatable, Hashable, так же как Comparable и если нужны соотв. методы, реализуешь интерфейс. Либо, что ещё правильней, определять отдельные объекты вроде Equator, Hasher по аналогии с Comparator и передавать их в соотв. структуры данных.

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

А что такое стандартное сравнение для MyClass? operator== вроде не генерится автоматом, т.е. для обычного класса не определены ни сравнение ни хеширование.

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

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

C>>>3) Подмножество пункта 2 — полностью воспроизводимые результаты. Т.е. чтобы два запуска с одними и теми же данными выдавали одинаковый результат.
G>>Может лучше бы это делала база данных? Все равно вы до ее реализации не дотянете и будет хуже по производительности.
C>Ну почему у этих формочкопрограммистов всё всегда к БД сводится? Я пишу код, в котором работы с БД часто нет вообще.
А я вам контраргумент. Почему у этих знатоков алгоритмов все сводится к написанию своей СУБД, фаловой системы, nginx и пр. Зачем пользоваться уже готовым функционалом, когда можно гораздо дольше и некачественнее написать свое?

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

G>>>Может лучше бы это делала база данных? Все равно вы до ее реализации не дотянете и будет хуже по производительности.
C>>Ну почему у этих формочкопрограммистов всё всегда к БД сводится? Я пишу код, в котором работы с БД часто нет вообще.
G>А я вам контраргумент. Почему у этих знатоков алгоритмов все сводится к написанию своей СУБД, фаловой системы, nginx и пр. Зачем пользоваться уже готовым функционалом, когда можно гораздо дольше и некачественнее написать свое?
Потому, что есть проекты, которые вообще не занимаются предоставлением сетевых сервисов или рисованием сайтов? Это так сложно представить?

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

N>>Ч.Т.Д.
N>>Спасибо за откровенность.
G>Ни одного реального примера в ветке так и не смогли привести. Это показатель.
Примеры из недавнего у меня:
1) Сервис для временных рядов, отрабатывающий более 10000 запросов в секунду на 3 серверах. Классическое использование дерева для запросов по диапазонам.
2) Специализированный build tool. Деревья используются везде для обеспечения детерминированного исполнения.
3) Инструмент для иерархических метрик и тревожных сигналов. Всё аналогично — обеспечение детерминированности и куча алгоритмов на DAG'ах.

Ну и по мелочи вообще в куче мест — при чтении JSON-конфигов для сохранения порядка элементов в картах.

Из всего этого БД могла бы быть использована разве что для 1).

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

N>>Правила таки о том, что это надо делать одновременно. Если ты переопределил hashCode() => переопредели и equals(), и наоборот.

vsb>Ну дык Hashable extends Equatable или Hasher extends Equator и опять же имеем типизированную проверку этого факта.

Боюсь, в таком варианте надо для надёжности вводить один класс с двумя функциональностями. Если не побьют за нарушение SRP.

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

vsb>А что такое стандартное сравнение для MyClass? operator== вроде не генерится автоматом, т.е. для обычного класса не определены ни сравнение ни хеширование.

Тогда не скомпилируется. Стандартное — это то, что находится "естественным" поиском для a==b

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

В Sciter binary tree не используется вообще. Т.е. ни в имплементации DOM ни в CSS ни в script (compiler & VM).

Но используются hash map, sort на vector в паре мест, ternary trie (для dynamic string to uint map), gperf (для static string to uint map).

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

G>>А я вам контраргумент. Почему у этих знатоков алгоритмов все сводится к написанию своей СУБД, фаловой системы, nginx и пр. Зачем пользоваться уже готовым функционалом, когда можно гораздо дольше и некачественнее написать свое?
C>Потому, что есть проекты, которые вообще не занимаются предоставлением сетевых сервисов или рисованием сайтов? Это так сложно представить?
Сколько таких проектов? Как правило это обычный сайтик в рамках которого программист изобретает революционный алгоритм сортировки. Потом с этим кодом невозможно работать, а гордости и пафоса у того праграммиста хоть другим раздавай

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

C>>Потому, что есть проекты, которые вообще не занимаются предоставлением сетевых сервисов или рисованием сайтов? Это так сложно представить?
G>Сколько таких проектов?
Мне хватает.

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

Кстати, даже с сайтиком (простая внутренняя консолька для мониторинга) у меня потребовалось дерево. В одном месте там можно импортировать JSON и потом его экспортировать с изменениями. Чтобы порядок узлов не перекорёживался каждый экспорт — для карт используются бинарные деревья.

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

G>>Как правило это обычный сайтик в рамках которого программист изобретает революционный алгоритм сортировки. Потом с этим кодом невозможно работать, а гордости и пафоса у того праграммиста хоть другим раздавай
C>Если хочется рисовать сайты и дальше — то и продолжай постить такие темы.
Делать сайтики тоже уметь надо. Особенно тяжело сделать код простым и удержаться от соблазна впихнуть туда ненужную реализацию ненужного алгоритма.

C>Кстати, даже с сайтиком (простая внутренняя консолька для мониторинга) у меня потребовалось дерево. В одном месте там можно импортировать JSON и потом его экспортировать с изменениями. Чтобы порядок узлов не перекорёживался каждый экспорт — для карт используются бинарные деревья.
Так он и так перекореживаться не будет. Вы посто добавляете новый узел в середку и все. Но это то о чем я говорил. Не нужное усложнение кода ради экономии не нужных трех тактов процессора и стремления хоть где-то применить знание алгоритмов.

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

C>>Если хочется рисовать сайты и дальше — то и продолжай постить такие темы.
G>Делать сайтики тоже уметь надо. Особенно тяжело сделать код простым и удержаться от соблазна впихнуть туда ненужную реализацию ненужного алгоритма.
Так не спорю. Только вот те сайтики, которые надо уметь делать, обычно делаются теми, кто не задаёт вопросов про нужность деревьев.

C>>Кстати, даже с сайтиком (простая внутренняя консолька для мониторинга) у меня потребовалось дерево. В одном месте там можно импортировать JSON и потом его экспортировать с изменениями. Чтобы порядок узлов не перекорёживался каждый экспорт — для карт используются бинарные деревья.
G>Так он и так перекореживаться не будет. Вы посто добавляете новый узел в середку и все. Но это то о чем я говорил.
Так ещё и ликбез по хеш-картам надо проводить? Вау.

Подумай, что станет с порядком элементов в хэш-карте, если вставка элемента вызовет перебалансировку.