Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Нужен ли дженерик для бинарного дерева?  [new]
SOFT FOR YOU
Member [заблокирован]

Откуда:
Сообщений: 2761
Всем привет
Есть у меня библиотечка, которая полностью повторяет функционал стандартных дженериков: https://github.com/d-mozulyov/Rapid.Generics

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

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

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

В общем интересны ваши мнения.
12 мар 18, 17:02    [21250455]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3617
SOFT FOR YOU,

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

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

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

а что у тебя перечислители классами сделаны? не по православному ...
и LinkedHashMap вроде нет ещё
12 мар 18, 17:18    [21250512]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
SOFT FOR YOU
Member [заблокирован]

Откуда:
Сообщений: 2761
kealon(Ruslan),

Неплохое имя, кстати
Шо за LinkedHashMap?
Итераторы я копировал стандартные. Или что я сделал не так? Давай код :)
12 мар 18, 17:29    [21250545]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
defecator
Member

Откуда:
Сообщений: 38978
Каким бы ни был "дженерик для бинарного дерева", он должен быть самым быстрым в мире
12 мар 18, 17:32    [21250556]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
SOFT FOR YOU
Member [заблокирован]

Откуда:
Сообщений: 2761
defecator,

Обижаешь. Конечно должен
12 мар 18, 17:35    [21250577]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
Vlad F
Member

Откуда:
Сообщений: 353
SOFT FOR YOU,

И делай, пожалуйста, сразу так, чтобы (быстрый) доступ был мультипоточным.))
12 мар 18, 17:46    [21250641]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
YuRock
Member

Откуда: Донецк
Сообщений: 3631
Vlad F
SOFT FOR YOU,

И делай, пожалуйста, сразу так, чтобы (быстрый) доступ был мультипоточным.))

И при этом - неблокирующим!
12 мар 18, 18:09    [21250725]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
rgreat
Member

Откуда:
Сообщений: 4591
И лекарство от жадности.
12 мар 18, 18:22    [21250767]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
rgreat
Member

Откуда:
Сообщений: 4591
SOFT FOR YOU
Во-вторых, мне не хватает TSet<T>, который я сейчас эмулирую через TDictionary<T,Boolean>.
У меня для этого есть TArrayEx<T>.
12 мар 18, 18:23    [21250772]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
Vlad F
Member

Откуда:
Сообщений: 353
Не мешайте настраивать человека сразу на большие дела и великие свершения. )))
12 мар 18, 19:02    [21250860]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3617
SOFT FOR YOU
Шо за LinkedHashMap?

гуглится же легко
https://habrahabr.ru/post/129037/
12 мар 18, 19:20    [21250897]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
fd00ch
Member

Откуда: Нижний Новгород
Сообщений: 5913
SOFT FOR YOU
библиотечка, которая полностью повторяет функционал стандартных дженериков
а зачем?
12 мар 18, 19:36    [21250925]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
rgreat
Member

Откуда:
Сообщений: 4591
fd00ch,

Наверно она будет самой быстрой в мире. ;)
12 мар 18, 19:38    [21250926]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
fd00ch
Member

Откуда: Нижний Новгород
Сообщений: 5913
rgreat, пока не придет Шарахов и не набросит че-нить))
12 мар 18, 19:43    [21250937]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
SOFT FOR YOU
Member [заблокирован]

Откуда:
Сообщений: 2761
kealon(Ruslan),

Я ничерта не понял
Какие у него преимущества над хешем или деревом?
12 мар 18, 19:45    [21250942]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
SOFT FOR YOU
Member [заблокирован]

Откуда:
Сообщений: 2761
Vlad F,

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

В частности можно разграничить читающие потоки и модифицирующие. Читающие потоки могут сколько угодно заходить в контейнер, пока не появился модифицирующий.
12 мар 18, 19:52    [21250949]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
SOFT FOR YOU
Member [заблокирован]

Откуда:
Сообщений: 2761
fd00ch
SOFT FOR YOU
библиотечка, которая полностью повторяет функционал стандартных дженериков
а зачем?

Стандартные дженерики написаны по-дебильному, мне удалось реализовать дженерики, которые быстрее в разы. А Шарахов, да, может сделать ещё быстрее. Но у него не дженерики.
12 мар 18, 19:54    [21250953]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
fd00ch
Member

Откуда: Нижний Новгород
Сообщений: 5913
SOFT FOR YOU
которые быстрее в разы
при использовании одинаковой хеш-функции?)
12 мар 18, 19:57    [21250954]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3617
SOFT FOR YOU
kealon(Ruslan),

Я ничерта не понял
Какие у него преимущества над хешем или деревом?

если в TDictionary добавляешь элементы, пройдёшся по ним итератором; в каком порядке они будут?
12 мар 18, 19:57    [21250956]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
Vlad F
Member

Откуда:
Сообщений: 353
SOFT FOR YOU,

Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.))
12 мар 18, 20:01    [21250961]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
defecator
Member

Откуда:
Сообщений: 38978
Vlad F
SOFT FOR YOU,

Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.))

и без генериков
12 мар 18, 20:04    [21250965]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3617
SOFT FOR YOU
Итераторы я копировал стандартные. Или что я сделал не так? Давай код :)
первый плюс - итератор можно сделать Record и он не будет создаваться в куче.

второй плюс, фактически нужно всего 1 свойство и один метод - вызов по сравнению с перекрытием виртуальных методов будет чуток, но быстрее.
12 мар 18, 20:06    [21250967]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 3617
Vlad F
SOFT FOR YOU,

Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.))
даже если он его содаст, как его использовать будешь?
12 мар 18, 20:08    [21250971]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3125
SOFT FOR YOU
мне удалось реализовать дженерики, которые быстрее в разы.

На самом деле нет. Просто ты бенчи писать не умеешь. Дельфийский словарь нагибает твой влёгкую.
12 мар 18, 20:10    [21250974]     Ответить | Цитировать Сообщить модератору
 Re: Нужен ли дженерик для бинарного дерева?  [new]
SOFT FOR YOU
Member [заблокирован]

Откуда:
Сообщений: 2761
fd00ch
SOFT FOR YOU
которые быстрее в разы
при использовании одинаковой хеш-функции?)


В том числе.
Но дженерики это не только хеши. Это ещё списки, сортировки, очереди.
12 мар 18, 20:14    [21250986]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Delphi Ответить