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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В том числе.
Но дженерики это не только хеши. Это ещё списки, сортировки, очереди.
...
Рейтинг: 0 / 0
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Нужен ли дженерик для бинарного дерева? / 25 сообщений из 41, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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