|
|
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Саша, пройдись по коду, везде ли я поставил инициализацию/финализацию? По идее нужны нотификаторы как в стандартном TDictionary. Хотя бы на удаление и замену (в оригинале удаление+добавление) Модератор: Вложение удалено. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 02:26:30 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUТоварищ старший сержант, Кончилось тем, что люди как юзали Lua на старых Delphi, так и юзают А на новых - сильно расстраиваются, что нет https://github.com/felipedaragon/pLua-XE ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 03:14:01 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUСаша, пройдись по коду, везде ли я поставил инициализацию/финализацию? По идее нужны нотификаторы как в стандартном TDictionary. Хотя бы на удаление и замену (в оригинале удаление+добавление) Похоже надо кое-что прояснить. Идея описать другие хеш-функции сообществу родилась по трем причинам: 1. Мне показалось, что в ходе обсуждения начала формироваться мысль, что каноническая реализация Седжвика - наше все. На самом деле Седжвик - это целое семейство функций, которое можно подстроить под язык и множество слов. Я порулил только одним параметром, но идея должна быть понятна. 2. Мне показалось, что идея простоты хеш-функции некоторыми участниками дискуссии возводится в абсолют и они несколько хаотично ей следуют. Хотя в целом верно, но давайте использовать хотя бы школьные знания, если не хотим читать теорию. Отсюда берется вторая хеш-функция. 3. Хеш-функции имеют 2 главных применения - сравнение данных и поиск данных. Наиболее просто продемонстрировать достоинства и недостатки хеш-функций можно на хеш-таблицах. Отсюда вытекает вторая часть статьи. На самом деле в своей работе я никогда не использовал хеш-таблиц в том виде, как там описано. Иногда надо было надо хранить только строки или только числа (без объектов). Иногда именованные объекты (имя не снаружи а внутри объекта) иногда объекты с идентификаторами. Так что класс TShaStringDictionary реализован только для демонстрации идеи, и я серьезно подумываю, чтобы его заменить, скажем, классом TShaNamedObjectDictionary. Так что все мои применения самописных подобий словарей чаще всего сводились к следующему 1. Создать контейнер заданной емкости. 2. Наполнить (возможно с переаллокациями). 3. Что-то много искать. 4. Очистить (обычно с сохранением размера). 5. Если надо, повторить с п.2 6. Пробежаться и собрать статистику. Никакие удаления и нотификации мне ни разу не требовались. Свойство Owned - да, часто может упростить код. Но нотификации, на мой взгляд, все равно проще самому ручками. Теперь относительно кода. Там же написано "берите, кто хотите, и делайте, что хотите". Можете даже сослаться на оригинальный код автора, если хотите. Но только большая просьба: НЕ ПИШИТЕ НА СВОЕМ КОДЕ, ЧТО ЭТО МОЙ КОД. P.S. У меня в Delphi7 твой даже не компилируется. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 11:10:30 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Ну с дженериками то ты знаком? Меня удивляет распространённая тут позиция "функция наше всё", ровно как тебя удивила аналогичная фраза с Седжвиком. Очевидно, кроме функции, есть существенный ряд других особенностей, внутри таблицы. На мой взгляд твоя реализация достаточно слаба. Я поправил твой класс на дженерик, где в качестве Value может быть произвольный тип. И попросил тебя проверить. Надеюсь, господин Казанцев тоже выложит свою реализацию. Насколько я помню, его реализация подразумевала произвольный тип в качестве Value А по поводу нотификаторов - всё просто. У тебя есть возможность высвобождать экземпляры класса, то же самое делается в дженериках по нотификатору ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 11:49:20 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, А ты видел структуру его таблицы? Я что-то пропустил ) Эмбы очень обидятся, узнав, что их ты тоже считаешь идиотами Главное, чтобы об этом не узнали Майкрософт, Oracle и другие разного калибра IT-компании, использующие контейнеры на основе хеша ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 14:25:09 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Выше писал уже: элемент правильной хеш-таблицы состоит ровно из двух полей хеш-код и объект (или индекс объекта в другом хранилище). Если другого хранилища нет, то возможны различные варианты эмуляции правильной таблицы в зависимости от размера значения: короткое - вместо объекта, среднее и длинное - в доп. массиве. При этом для средних и длинных возможны свои варианты организации. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 15:19:29 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Ну и в чем тогда проблема, что я Obj заменил на Value? Я у тебя спросил, правильно ли расставлены инициализаторы/финализаторы. Чтобы потом замерить производительность твоего решения И ещё. Не хочешь видеть чужой код - пиши свой. Не хочешь свой - не кричи тогда по поводу копирайтов. Чья ещё эта таблица если не твоя? Устроил тут ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 15:28:49 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUНу и в чем тогда проблема, что я Obj заменил на Value? Проблема в том, что SizeOf(Value)<>4 SOFT FOR YOUНе хочешь видеть чужой код - пиши свой. Не хочешь свой - не кричи тогда по поводу копирайтов. Чья ещё эта таблица если не твоя? Устроил тут ) Ты правда идиот? Напиши, что это твой код. Если хочешь, напиши что взял за образец код с моего сайта. И нет проблем. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 15:46:37 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Для твоего алгоритма нет разница, равен размер Value 4 или нет Нет, я буду распространять этот модуль с твоими копирайтами и пусть люди подумают, что ты умеешь делать дженерики ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 16:02:33 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUпусть люди подумают, что ты умеешь делать дженерики Да ! Пихайте ! пихайте это дженериковое говно везде ! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 16:06:43 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
defecator, Спасибо, что одобряешь :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 16:10:47 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUAleksandr Sharahov, Для твоего алгоритма нет разница, равен размер Value 4 или нет Нет, я буду распространять этот модуль с твоими копирайтами и пусть люди подумают, что ты умеешь делать дженерики Но есть разница в скорости. Так что пусть лучше люди думают, что ты можешь писать только тормознутый код. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 16:13:32 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Саня, чё ты взьелся? Дженерики есть с 2009 года, всю черновую работу я тебе уже прописал. На тот случай если ты сам не умеешь, или времени нет, или оба варианта. У Казанцева таблица универсальная, у Эмбы (да и вообще у всех) универсальная, у тебя только TObject-ы. Надо же сравнивать твою таблицу на универсальном Value, а ты вместо благодарности слюной брызжешь. По поводу скорости... а ты думаешь другим авторам таблиц легко? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 16:30:55 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUДженерики есть с 2009 года, всю черновую работу я тебе уже прописал. На тот случай если ты сам не умеешь, или времени нет, или оба варианта. У Казанцева таблица универсальная, у Эмбы (да и вообще у всех) универсальная, у тебя только TObject-ы. У нас разные представления об универсальности. Как сделать универсально на TObject, я уже писал не раз. А реализация на Value в твоем исполнении - это полный бред и я так никогда бы не сделал. SOFT FOR YOUНадо же сравнивать твою таблицу на универсальном Value, а ты вместо благодарности слюной брызжешь. Если хочешь сравнить свою реализацию с моей - бери код с сайта без всяких изменений. А в своем коде поменяй Value на TObject. SOFT FOR YOUПо поводу скорости... а ты думаешь другим авторам таблиц легко? Вот соревнуйтесь между собой. Нефиг ломать чужой код, а потом выезжать на белом коне. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 17:07:19 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUУ Казанцева таблица универсальная В который раз убеждаюсь, что ты, либо не читаешь, либо не понимаешь написанного. На счёт универсальности перечитай ещё раз . Речи о данных не было вообще. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 17:22:00 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, TObject плох тем, что для каждого экземпляра дёргается менеджер памяти, куча обвязок типа Before/After, Init/Cleanup. В случае менеджмента структурами менеджер задействуется при реаллоке, а поля могут вообще никак не модифицироваться если нет сложных типов из строк/интерфейсов/дин.массивов Поэтому если ты думаешь, что сделать TObject это большое достижение - то ты сильно заблуждаешься. Нет ни гибкости, ни выигрыша по скорости. Почему ты подумал, что при переходе с Obj на дженерик в рамках текущей архитектуры будет проседание по производительности - я не понял. Но если они есть - Эмба, boost и C# как-то решают их. В моей реализации разницы нет Ты сегодня успел назвать меня идиотом только потому, что "ты бы так не сделал". Аргумент конечно... но слабый. И в целом показывает уровень культуры, я думал, он выше. Нет силы соревноваться - я могу это понять. Если великая ценность твоей статьи в том, что ты немного дополнил Седжвика - я тоже это приму. Но раньше я думал, что уровень твоего профессионализма выше. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 17:51:53 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, Понятно. Я думал твоя таблица представляет какую-то ценность ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 17:55:03 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, культура общения в первую очередь состоит в умении слушать, что говорит собеседник, и не навязывать ему свою точку зрения, а как профессионал замени TObject на Pointer ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 17:58:58 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Профессиональные авторы контейнеров делают Value универсальным Глупо нам всем подстраиваться под твой TObject/Pointer только потому, что ты не умеешь дженерики ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 18:04:13 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Глупо не понимать, то что разжевано вдоль и поперек. Как правило, TObject уже существует где-то в момент добавления ссылки на него в таблицу. А профессиональные авторы контейнеров пишут их для тех, кто не может/не хочет написать контейнер для себя. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.01.2017, 18:09:22 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUЯ думал, потенциал больше, но окончилось чем окончилосьВопросы связанные с разработкой hash очень важны и интересны. И действительно использование hash в многих алгоритмах целесообразно. Понятно, что скорее всего нет и быть не может "универсального" hash. Нет ли у вас tools, который позволял анализировать входной поток данных и предоставлять рекомендации по использованию того или иного подхода. Или к примеру имеет смысл подумать над вопросом "адаптивного" hash. О чем речь? Программа в процессе работы в течении некоторого времени ее эксплуатации пытается использовать тот или иной подход связанный с hash, tree, ... и пытается адаптироваться /то бишь использовать/ самый лучший из ей известный подход. Понятно, что при таком подходе должны быть использованы интерфейсы, которые бы скрывали native структуры используемые при обработке данных. Приблизительно как при разработки interafaces скажем для ActiveX. В этом случае программа будет как-бы "самоулучшаемая". Экспромтом. На счет collision. Может быть при их возникновении такие данные следует помещать во вторичную hash таблицу /для которой используется иной алгоритм расчета hash/? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.01.2017, 01:25:40 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Владимир2012, Относительно хешей очень много теории и разработок. В частности, ваш экспромт называется FKS Hashing. У него рассматриваются статический и динамический варианты. Есть его же развитие на случай вторичного хеширования. В частности доказывается, что для вторичного хеширования можно из очень простого семейства линейных хешей выбрать такие, что там не будет коллизий, а суммарный размер таблиц будет при этом расти линейно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.01.2017, 09:44:02 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Пошарился тут по коду TDictionary в Seattle. Заменил хеш-функции для Integer и String ключей на свои. Результаты: с родным System.Generics.Defaults.pas Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. с кастомным System.Generics.Defaults.pas Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. Для Integer словаря выигрыш по скорости оказался в 2-3 раза! Эти дятлы расчитывали(!) бобом дженкинсом(!) хэши для 1-4 байтных целых. Для строк переход на Роберта Седжевика дал ускорение поскромней. Но все равно процентов 30 я выиграл. Как-то так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.01.2017, 00:46:10 |
|
||
|
TDictionary или TList<>.BinarySearch с позиции поиска
|
|||
|---|---|---|---|
|
#18+
Ой, ошибся. Для Integer словаря выигрыш по скорости оказался не в 2-3 раза, а в 3-4+. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.01.2017, 00:49:29 |
|
||
|
|

start [/forum/topic.php?fid=58&startmsg=39382822&tid=2041988]: |
0ms |
get settings: |
6ms |
get forum list: |
11ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
151ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
64ms |
get tp. blocked users: |
1ms |
| others: | 189ms |
| total: | 438ms |

| 0 / 0 |
