powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Нужен ли дженерик для бинарного дерева?
41 сообщений из 41, показаны все 2 страниц
Нужен ли дженерик для бинарного дерева?
    #39613635
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Всем привет
Есть у меня библиотечка, которая полностью повторяет функционал стандартных дженериков: https://github.com/d-mozulyov/Rapid.Generics

В последнее время стал замечать, что мне не хватает некоторого функционала. Во-первых, мне не хватает, чтобы классы поддерживали интерфейсы. Во-вторых, мне не хватает TSet<T>, который я сейчас эмулирую через TDictionary<T,Boolean>.

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

Все мы знаем сишный контейнер map<>, который долгое время был единственным способом быстрого поиска. На уровне алгоритма используется красно-чёрное дерево и как следствие - упорядоченная по возрастанию структура. Вопрос: нужен ли такой контейнер в Delphi? И если да, то как его назвать? Какие методы нужны? Нужно ли что-то типа... обойти элементы, начиная с ...? Нужно ли пройтись в обратном порядке?

В общем интересны ваши мнения.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613645
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

слишком редко они бывают нужны

TOrderedDictionary если уж безобразить, хотя мне и жутко не нравятся префиксы T перед генериками

>>Нужно ли что-то типа... обойти элементы, начиная с ...? Нужно ли пройтись в обратном порядке?
"в интервале" забыл
куда ж без них

а что у тебя перечислители классами сделаны? не по православному ...
и LinkedHashMap вроде нет ещё
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613658
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Неплохое имя, кстати
Шо за LinkedHashMap?
Итераторы я копировал стандартные. Или что я сделал не так? Давай код :)
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613662
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
Каким бы ни был "дженерик для бинарного дерева", он должен быть самым быстрым в мире
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613666
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
defecator,

Обижаешь. Конечно должен
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613684
Vlad F
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

И делай, пожалуйста, сразу так, чтобы (быстрый) доступ был мультипоточным.))
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613697
YuRock
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vlad FSOFT FOR YOU,

И делай, пожалуйста, сразу так, чтобы (быстрый) доступ был мультипоточным.))
И при этом - неблокирующим!
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613709
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И лекарство от жадности.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613710
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUВо-вторых, мне не хватает TSet<T>, который я сейчас эмулирую через TDictionary<T,Boolean>.У меня для этого есть TArrayEx<T>.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613732
Vlad F
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не мешайте настраивать человека сразу на большие дела и великие свершения. )))
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613739
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUШо за LinkedHashMap?
гуглится же легко
https://habrahabr.ru/post/129037/
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613742
fd00ch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUбиблиотечка, которая полностью повторяет функционал стандартных дженерикова зачем?
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613743
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fd00ch,

Наверно она будет самой быстрой в мире. ;)
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613744
fd00ch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreat, пока не придет Шарахов и не набросит че-нить))
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613745
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan),

Я ничерта не понял
Какие у него преимущества над хешем или деревом?
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613749
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vlad F,

Может ты конечно и подколол, но на самом деле не очень далеко ушёл от истины :)
Я стартовал отдельный репозиторий шаблонов lock-free, но пока остановился на очереди. Делать лок фри хеш или дерево - жестко. Но оптимизировать для мультипоточного доступа можно.

В частности можно разграничить читающие потоки и модифицирующие. Читающие потоки могут сколько угодно заходить в контейнер, пока не появился модифицирующий.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613750
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fd00chSOFT FOR YOUбиблиотечка, которая полностью повторяет функционал стандартных дженерикова зачем?
Стандартные дженерики написаны по-дебильному, мне удалось реализовать дженерики, которые быстрее в разы. А Шарахов, да, может сделать ещё быстрее. Но у него не дженерики.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613751
fd00ch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUкоторые быстрее в разыпри использовании одинаковой хеш-функции?)
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613752
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUkealon(Ruslan),

Я ничерта не понял
Какие у него преимущества над хешем или деревом?
если в TDictionary добавляешь элементы, пройдёшся по ним итератором; в каком порядке они будут?
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613754
Vlad F
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU,

Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.))
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613755
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
Vlad FSOFT FOR YOU,

Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.))
и без генериков
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613756
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUИтераторы я копировал стандартные. Или что я сделал не так? Давай код :)первый плюс - итератор можно сделать Record и он не будет создаваться в куче.

второй плюс, фактически нужно всего 1 свойство и один метод - вызов по сравнению с перекрытием виртуальных методов будет чуток, но быстрее.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613758
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vlad FSOFT FOR YOU,

Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.))даже если он его содаст, как его использовать будешь?
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613759
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUмне удалось реализовать дженерики, которые быстрее в разы.
На самом деле нет. Просто ты бенчи писать не умеешь. Дельфийский словарь нагибает твой влёгкую.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613762
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fd00chSOFT FOR YOUкоторые быстрее в разыпри использовании одинаковой хеш-функции?)

В том числе.
Но дженерики это не только хеши. Это ещё списки, сортировки, очереди.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613763
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Vlad F,

Тогда ответь на первый вопрос. Как назвать класс и методы. И что они должны делать ))
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613771
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)SOFT FOR YOUИтераторы я копировал стандартные. Или что я сделал не так? Давай код :)первый плюс - итератор можно сделать Record и он не будет создаваться в куче.

второй плюс, фактически нужно всего 1 свойство и один метод - вызов по сравнению с перекрытием виртуальных методов будет чуток, но быстрее.
Закинь пример. В коде.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613772
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev AlexeySOFT FOR YOUмне удалось реализовать дженерики, которые быстрее в разы.
На самом деле нет. Просто ты бенчи писать не умеешь. Дельфийский словарь нагибает твой влёгкую.
Сильное заявление :)
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613773
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)SOFT FOR YOUkealon(Ruslan),

Я ничерта не понял
Какие у него преимущества над хешем или деревом?
если в TDictionary добавляешь элементы, пройдёшся по ним итератором; в каком порядке они будут?
Вообще говоря, сейчас - в порядке добавления. Если без удаления.
А что, часто нужно проходиться итератором в порядке добавления?
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613784
Vlad F
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUТогда ответь на первый вопрос. Как назвать класс и методы. И что они должны делать ))
Ок, но тогда беру паузу до завтра. Надо свериться с кое-какими записями на работе..
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613793
чччД
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOU...Как назвать класс и методы. И что они должны делать ))
Имя класса: TB023. B023 - аббревиатура от "Brilliantly Optimized Binary Tree".
Методы: конструктор, деструктор.

И еще два метода:
- SetExpectedPerformance(UInt64) - назначением понятно.
- GetRealPerformance() : UInt64 - должен возвращать значение, установленное в предыдущем методе с небольшим случайным отклонением. Метод должен возвращать управление с небольшой, еле заметной задержкой.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613795
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUСильное заявление :)
Сам проверь. Используй одинаковый компарер и при поиске ключи выбирай рандомно, а не в порядке занесения в словарь.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613800
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev Alexey,

Я проверил. У меня всё норм.
Можешь зафигачить свой тест - посмотрим.

А зачем кстати стандартный компаратор использовать вместо быстрого?
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613809
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
чччД> Имя класса: TB023. B023 - аббревиатура от "Brilliantly Optimized Binary Tree".

Классно. Предлагаю запатентовать.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613811
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
чччДSOFT FOR YOU...Как назвать класс и методы. И что они должны делать ))
Имя класса: TB023. B023 - аббревиатура от "Brilliantly Optimized Binary Tree".
Методы: конструктор, деструктор.

И еще два метода:
- SetExpectedPerformance(UInt64) - назначением понятно.
- GetRealPerformance() : UInt64 - должен возвращать значение, установленное в предыдущем методе с небольшим случайным отклонением. Метод должен возвращать управление с небольшой, еле заметной задержкой.
если внутри не будет нечитаемой ассемблерной мегапортянки, то не считается
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613812
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUЯ проверил. У меня всё норм.
Покажи, как проверял.

SOFT FOR YOUА зачем кстати стандартный компаратор использовать вместо быстрого?
Используй какой хочешь, лишь бы они были одинаковы у обоих словарей.
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613968
mumbo jumbo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
SOFT FOR YOUКак назвать классв дотнете которые на деревьях называются SortedSet и SortedDictionary
(которые на хэштаблицах - HashSet и Dictionary)

SOFT FOR YOU, а вам случайно не попадался где-нибудь алгоритм подбора совершенной хэш-функции (т.е. подбора параметров для некоей параметризованной хэш-функции, делающих её совершенной) для заданного набора ключей?
если нет (ну то есть вообще "в природе" не встречается) - возможно, вам было бы интересно такое написать
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39613978
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mumbo jumbo,

Не, писать идеальную хеш я не буду. Да и смысла в этом особо не вижу. Тяжёлая хеш-функция сведёт на нет профит от обхода коллизий.

А если нужно идентифицировать изначально известный набор строк - то есть чудеснейшее средство CachedSerializer. Если длина изначально не известна - нужен Ахо-Корасик
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39614030
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUkealon(Ruslan)пропущено...
первый плюс - итератор можно сделать Record и он не будет создаваться в куче.

второй плюс, фактически нужно всего 1 свойство и один метод - вызов по сравнению с перекрытием виртуальных методов будет чуток, но быстрее.
Закинь пример. В коде.
что закидывать то, минимальный итератор

Код: pascal
1.
2.
3.
4.
5.
6.
7.
    TSipleEnum = record
    private
      FCurrent: T;
    public
      function MoveNext: Boolean;
      property Current: T read FCurrent;
    end;
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39614109
mumbo jumbo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
SOFT FOR YOUТяжёлая хеш-функцияда почему тяжелая-то? простейший хэш - накопленную сумму (изначально 0) умножаем на константу (обычно простое число) и прибавляем очередной байт/символ/четырехбайтное целое, ну можно еще затем другую константу прибавить - это в цикле по всем байтам/символам/..., а в конце цикла берем остаток от деления суммы на то, что называлось "число корзин" в обычных хэш-таблицах (еще 1 константа)
вот эти 2-3 константы и нужно подобрать (в самом внутреннем цикле подбираем число корзин, наращивая от N до приемлемого максимума)

А если нужнода мне-то не нужно, просто идея такая перфекционистская возникла - решил с вами поделиться
типа а вдруг у кого-то есть шанс стать автором первой в мире публичной либы/функции подбора perfect hash?
...
Рейтинг: 0 / 0
Нужен ли дженерик для бинарного дерева?
    #39614124
mumbo jumbo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
P.S. туплю, для обычных применений будет лишним и делить на это "число корзин", и подбирать его - просто результаты (32/64-битные) хэш-функции по ключам не должны совпадать, и в любом случае эту проверку отсутствия совпадений нужно делать раньше подбора "числа корзин"
...
Рейтинг: 0 / 0
41 сообщений из 41, показаны все 2 страниц
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Нужен ли дженерик для бинарного дерева?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]