|
|
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Всем привет Есть у меня библиотечка, которая полностью повторяет функционал стандартных дженериков: https://github.com/d-mozulyov/Rapid.Generics В последнее время стал замечать, что мне не хватает некоторого функционала. Во-первых, мне не хватает, чтобы классы поддерживали интерфейсы. Во-вторых, мне не хватает TSet<T>, который я сейчас эмулирую через TDictionary<T,Boolean>. В связи с этим выберу как-нибудь выходные, засяду за доработку, внесу изменения. Но возник вопрос, который самостоятельно не могу решить, решил посоветоваться. Все мы знаем сишный контейнер map<>, который долгое время был единственным способом быстрого поиска. На уровне алгоритма используется красно-чёрное дерево и как следствие - упорядоченная по возрастанию структура. Вопрос: нужен ли такой контейнер в Delphi? И если да, то как его назвать? Какие методы нужны? Нужно ли что-то типа... обойти элементы, начиная с ...? Нужно ли пройтись в обратном порядке? В общем интересны ваши мнения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 17:02 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, слишком редко они бывают нужны TOrderedDictionary если уж безобразить, хотя мне и жутко не нравятся префиксы T перед генериками >>Нужно ли что-то типа... обойти элементы, начиная с ...? Нужно ли пройтись в обратном порядке? "в интервале" забыл куда ж без них а что у тебя перечислители классами сделаны? не по православному ... и LinkedHashMap вроде нет ещё ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 17:18 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), Неплохое имя, кстати Шо за LinkedHashMap? Итераторы я копировал стандартные. Или что я сделал не так? Давай код :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 17:29 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Каким бы ни был "дженерик для бинарного дерева", он должен быть самым быстрым в мире ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 17:32 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
defecator, Обижаешь. Конечно должен ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 17:35 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, И делай, пожалуйста, сразу так, чтобы (быстрый) доступ был мультипоточным.)) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 17:46 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Vlad FSOFT FOR YOU, И делай, пожалуйста, сразу так, чтобы (быстрый) доступ был мультипоточным.)) И при этом - неблокирующим! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 18:09 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
И лекарство от жадности. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 18:22 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUВо-вторых, мне не хватает TSet<T>, который я сейчас эмулирую через TDictionary<T,Boolean>.У меня для этого есть TArrayEx<T>. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 18:23 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Не мешайте настраивать человека сразу на большие дела и великие свершения. ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:02 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:20 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUбиблиотечка, которая полностью повторяет функционал стандартных дженерикова зачем? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:36 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
fd00ch, Наверно она будет самой быстрой в мире. ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:38 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
rgreat, пока не придет Шарахов и не набросит че-нить)) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:43 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), Я ничерта не понял Какие у него преимущества над хешем или деревом? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:45 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Vlad F, Может ты конечно и подколол, но на самом деле не очень далеко ушёл от истины :) Я стартовал отдельный репозиторий шаблонов lock-free, но пока остановился на очереди. Делать лок фри хеш или дерево - жестко. Но оптимизировать для мультипоточного доступа можно. В частности можно разграничить читающие потоки и модифицирующие. Читающие потоки могут сколько угодно заходить в контейнер, пока не появился модифицирующий. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:52 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
fd00chSOFT FOR YOUбиблиотечка, которая полностью повторяет функционал стандартных дженерикова зачем? Стандартные дженерики написаны по-дебильному, мне удалось реализовать дженерики, которые быстрее в разы. А Шарахов, да, может сделать ещё быстрее. Но у него не дженерики. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:54 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUкоторые быстрее в разыпри использовании одинаковой хеш-функции?) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:57 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUkealon(Ruslan), Я ничерта не понял Какие у него преимущества над хешем или деревом? если в TDictionary добавляешь элементы, пройдёшся по ним итератором; в каком порядке они будут? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 19:57 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.)) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:01 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Vlad FSOFT FOR YOU, Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.)) и без генериков ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:04 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUИтераторы я копировал стандартные. Или что я сделал не так? Давай код :)первый плюс - итератор можно сделать Record и он не будет создаваться в куче. второй плюс, фактически нужно всего 1 свойство и один метод - вызов по сравнению с перекрытием виртуальных методов будет чуток, но быстрее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:06 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Vlad FSOFT FOR YOU, Какой там подколол, - сделай, пожалуйста, сбалансированное бинарное дерево, по возможности наиболее быстрое, с многопоточных доступом на вставку/поиск, очень надо. Понятно, что совсем без блокировок в нем таки не обойдёшься, но и блокировки блокировкам рознь. Верю в тебя.))даже если он его содаст, как его использовать будешь? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:08 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUмне удалось реализовать дженерики, которые быстрее в разы. На самом деле нет. Просто ты бенчи писать не умеешь. Дельфийский словарь нагибает твой влёгкую. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:10 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
fd00chSOFT FOR YOUкоторые быстрее в разыпри использовании одинаковой хеш-функции?) В том числе. Но дженерики это не только хеши. Это ещё списки, сортировки, очереди. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:14 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Vlad F, Тогда ответь на первый вопрос. Как назвать класс и методы. И что они должны делать )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:16 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)SOFT FOR YOUИтераторы я копировал стандартные. Или что я сделал не так? Давай код :)первый плюс - итератор можно сделать Record и он не будет создаваться в куче. второй плюс, фактически нужно всего 1 свойство и один метод - вызов по сравнению с перекрытием виртуальных методов будет чуток, но быстрее. Закинь пример. В коде. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:38 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Kazantsev AlexeySOFT FOR YOUмне удалось реализовать дженерики, которые быстрее в разы. На самом деле нет. Просто ты бенчи писать не умеешь. Дельфийский словарь нагибает твой влёгкую. Сильное заявление :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:39 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan)SOFT FOR YOUkealon(Ruslan), Я ничерта не понял Какие у него преимущества над хешем или деревом? если в TDictionary добавляешь элементы, пройдёшся по ним итератором; в каком порядке они будут? Вообще говоря, сейчас - в порядке добавления. Если без удаления. А что, часто нужно проходиться итератором в порядке добавления? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 20:40 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUТогда ответь на первый вопрос. Как назвать класс и методы. И что они должны делать )) Ок, но тогда беру паузу до завтра. Надо свериться с кое-какими записями на работе.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 21:11 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU...Как назвать класс и методы. И что они должны делать )) Имя класса: TB023. B023 - аббревиатура от "Brilliantly Optimized Binary Tree". Методы: конструктор, деструктор. И еще два метода: - SetExpectedPerformance(UInt64) - назначением понятно. - GetRealPerformance() : UInt64 - должен возвращать значение, установленное в предыдущем методе с небольшим случайным отклонением. Метод должен возвращать управление с небольшой, еле заметной задержкой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 21:48 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUСильное заявление :) Сам проверь. Используй одинаковый компарер и при поиске ключи выбирай рандомно, а не в порядке занесения в словарь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 21:51 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, Я проверил. У меня всё норм. Можешь зафигачить свой тест - посмотрим. А зачем кстати стандартный компаратор использовать вместо быстрого? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 21:57 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
чччД> Имя класса: TB023. B023 - аббревиатура от "Brilliantly Optimized Binary Tree". Классно. Предлагаю запатентовать. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 22:14 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
чччДSOFT FOR YOU...Как назвать класс и методы. И что они должны делать )) Имя класса: TB023. B023 - аббревиатура от "Brilliantly Optimized Binary Tree". Методы: конструктор, деструктор. И еще два метода: - SetExpectedPerformance(UInt64) - назначением понятно. - GetRealPerformance() : UInt64 - должен возвращать значение, установленное в предыдущем методе с небольшим случайным отклонением. Метод должен возвращать управление с небольшой, еле заметной задержкой. если внутри не будет нечитаемой ассемблерной мегапортянки, то не считается ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 22:26 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUЯ проверил. У меня всё норм. Покажи, как проверял. SOFT FOR YOUА зачем кстати стандартный компаратор использовать вместо быстрого? Используй какой хочешь, лишь бы они были одинаковы у обоих словарей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.03.2018, 22:27 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUКак назвать классв дотнете которые на деревьях называются SortedSet и SortedDictionary (которые на хэштаблицах - HashSet и Dictionary) SOFT FOR YOU, а вам случайно не попадался где-нибудь алгоритм подбора совершенной хэш-функции (т.е. подбора параметров для некоей параметризованной хэш-функции, делающих её совершенной) для заданного набора ключей? если нет (ну то есть вообще "в природе" не встречается) - возможно, вам было бы интересно такое написать ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.03.2018, 10:48 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
mumbo jumbo, Не, писать идеальную хеш я не буду. Да и смысла в этом особо не вижу. Тяжёлая хеш-функция сведёт на нет профит от обхода коллизий. А если нужно идентифицировать изначально известный набор строк - то есть чудеснейшее средство CachedSerializer. Если длина изначально не известна - нужен Ахо-Корасик ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.03.2018, 10:57 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUkealon(Ruslan)пропущено... первый плюс - итератор можно сделать Record и он не будет создаваться в куче. второй плюс, фактически нужно всего 1 свойство и один метод - вызов по сравнению с перекрытием виртуальных методов будет чуток, но быстрее. Закинь пример. В коде. что закидывать то, минимальный итератор Код: pascal 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.03.2018, 11:57 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUТяжёлая хеш-функцияда почему тяжелая-то? простейший хэш - накопленную сумму (изначально 0) умножаем на константу (обычно простое число) и прибавляем очередной байт/символ/четырехбайтное целое, ну можно еще затем другую константу прибавить - это в цикле по всем байтам/символам/..., а в конце цикла берем остаток от деления суммы на то, что называлось "число корзин" в обычных хэш-таблицах (еще 1 константа) вот эти 2-3 константы и нужно подобрать (в самом внутреннем цикле подбираем число корзин, наращивая от N до приемлемого максимума) А если нужнода мне-то не нужно, просто идея такая перфекционистская возникла - решил с вами поделиться типа а вдруг у кого-то есть шанс стать автором первой в мире публичной либы/функции подбора perfect hash? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.03.2018, 13:56 |
|
||
|
Нужен ли дженерик для бинарного дерева?
|
|||
|---|---|---|---|
|
#18+
P.S. туплю, для обычных применений будет лишним и делить на это "число корзин", и подбирать его - просто результаты (32/64-битные) хэш-функции по ключам не должны совпадать, и в любом случае эту проверку отсутствия совпадений нужно делать раньше подбора "числа корзин" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.03.2018, 14:11 |
|
||
|
|

start [/forum/topic.php?all=1&fid=58&tid=2041157]: |
0ms |
get settings: |
5ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
147ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
57ms |
get tp. blocked users: |
1ms |
| others: | 197ms |
| total: | 438ms |

| 0 / 0 |
