Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 7 8 9 10 11 12 13 [14] 15 16   вперед  Ctrl
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Саша, пройдись по коду, везде ли я поставил инициализацию/финализацию?

По идее нужны нотификаторы как в стандартном TDictionary. Хотя бы на удаление и замену (в оригинале удаление+добавление)

Модератор: Вложение удалено.
12 янв 17, 02:26    [20096480]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

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

Кончилось тем, что люди как юзали Lua на старых Delphi, так и юзают
А на новых - сильно расстраиваются, что нет

https://github.com/felipedaragon/pLua-XE
12 янв 17, 03:14    [20096488]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1029
SOFT FOR YOU
Саша, пройдись по коду, везде ли я поставил инициализацию/финализацию?
По идее нужны нотификаторы как в стандартном TDictionary. Хотя бы на удаление и замену (в оригинале удаление+добавление)


Похоже надо кое-что прояснить.

Идея описать другие хеш-функции сообществу родилась по трем причинам:
1. Мне показалось, что в ходе обсуждения начала формироваться мысль, что каноническая реализация Седжвика - наше все. На самом деле Седжвик - это целое семейство функций, которое можно подстроить под язык и множество слов. Я порулил только одним параметром, но идея должна быть понятна.
2. Мне показалось, что идея простоты хеш-функции некоторыми участниками дискуссии возводится в абсолют и они несколько хаотично ей следуют. Хотя в целом верно, но давайте использовать хотя бы школьные знания, если не хотим читать теорию. Отсюда берется вторая хеш-функция.
3. Хеш-функции имеют 2 главных применения - сравнение данных и поиск данных. Наиболее просто продемонстрировать достоинства и недостатки хеш-функций можно на хеш-таблицах. Отсюда вытекает вторая часть статьи.

На самом деле в своей работе я никогда не использовал хеш-таблиц в том виде, как там описано. Иногда надо было надо хранить только строки или только числа (без объектов). Иногда именованные объекты (имя не снаружи а внутри объекта) иногда объекты с идентификаторами. Так что класс TShaStringDictionary реализован только для демонстрации идеи, и я серьезно подумываю, чтобы его заменить, скажем, классом TShaNamedObjectDictionary. Так что все мои применения самописных подобий словарей чаще всего сводились к следующему
1. Создать контейнер заданной емкости.
2. Наполнить (возможно с переаллокациями).
3. Что-то много искать.
4. Очистить (обычно с сохранением размера).
5. Если надо, повторить с п.2
6. Пробежаться и собрать статистику.
Никакие удаления и нотификации мне ни разу не требовались. Свойство Owned - да, часто может упростить код. Но нотификации, на мой взгляд, все равно проще самому ручками.

Теперь относительно кода. Там же написано "берите, кто хотите, и делайте, что хотите".
Можете даже сослаться на оригинальный код автора, если хотите.
Но только большая просьба:

НЕ ПИШИТЕ НА СВОЕМ КОДЕ, ЧТО ЭТО МОЙ КОД.

P.S. У меня в Delphi7 твой даже не компилируется.
12 янв 17, 11:10    [20097290]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Aleksandr Sharahov,

Ну с дженериками то ты знаком?
Меня удивляет распространённая тут позиция "функция наше всё", ровно как тебя удивила аналогичная фраза с Седжвиком. Очевидно, кроме функции, есть существенный ряд других особенностей, внутри таблицы. На мой взгляд твоя реализация достаточно слаба.

Я поправил твой класс на дженерик, где в качестве Value может быть произвольный тип. И попросил тебя проверить. Надеюсь, господин Казанцев тоже выложит свою реализацию. Насколько я помню, его реализация подразумевала произвольный тип в качестве Value

А по поводу нотификаторов - всё просто. У тебя есть возможность высвобождать экземпляры класса, то же самое делается в дженериках по нотификатору
12 янв 17, 11:49    [20097621]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Aleksandr Sharahov,

А ты видел структуру его таблицы?
Я что-то пропустил )

Эмбы очень обидятся, узнав, что их ты тоже считаешь идиотами
Главное, чтобы об этом не узнали Майкрософт, Oracle и другие разного калибра IT-компании, использующие контейнеры на основе хеша )
12 янв 17, 14:25    [20098501]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1029
Выше писал уже: элемент правильной хеш-таблицы состоит ровно из двух полей хеш-код и объект (или индекс объекта в другом хранилище).
Если другого хранилища нет, то возможны различные варианты эмуляции правильной таблицы в зависимости от размера значения: короткое - вместо объекта, среднее и длинное - в доп. массиве. При этом для средних и длинных возможны свои варианты организации.
12 янв 17, 15:19    [20098816]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Aleksandr Sharahov,

Ну и в чем тогда проблема, что я Obj заменил на Value?
Я у тебя спросил, правильно ли расставлены инициализаторы/финализаторы. Чтобы потом замерить производительность твоего решения

И ещё. Не хочешь видеть чужой код - пиши свой. Не хочешь свой - не кричи тогда по поводу копирайтов. Чья ещё эта таблица если не твоя? Устроил тут )
12 янв 17, 15:28    [20098896]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1029
SOFT FOR YOU
Ну и в чем тогда проблема, что я Obj заменил на Value?


Проблема в том, что SizeOf(Value)<>4

SOFT FOR YOU
Не хочешь видеть чужой код - пиши свой. Не хочешь свой - не кричи тогда по поводу копирайтов. Чья ещё эта таблица если не твоя? Устроил тут )


Ты правда идиот?
Напиши, что это твой код.
Если хочешь, напиши что взял за образец код с моего сайта.
И нет проблем.
12 янв 17, 15:46    [20098999]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Aleksandr Sharahov,

Для твоего алгоритма нет разница, равен размер Value 4 или нет
Нет, я буду распространять этот модуль с твоими копирайтами и пусть люди подумают, что ты умеешь делать дженерики
12 янв 17, 16:02    [20099070]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
defecator
Member

Откуда: arm-pascal.ru
Сообщений: 31528
SOFT FOR YOU
пусть люди подумают, что ты умеешь делать дженерики


Да ! Пихайте ! пихайте это дженериковое говно везде !
12 янв 17, 16:06    [20099090]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

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

Спасибо, что одобряешь :)
12 янв 17, 16:10    [20099108]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1029
SOFT FOR YOU
Aleksandr Sharahov,

Для твоего алгоритма нет разница, равен размер Value 4 или нет
Нет, я буду распространять этот модуль с твоими копирайтами и пусть люди подумают, что ты умеешь делать дженерики


Но есть разница в скорости.
Так что пусть лучше люди думают, что ты можешь писать только тормознутый код.
12 янв 17, 16:13    [20099119]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Aleksandr Sharahov,

Саня, чё ты взьелся?
Дженерики есть с 2009 года, всю черновую работу я тебе уже прописал. На тот случай если ты сам не умеешь, или времени нет, или оба варианта. У Казанцева таблица универсальная, у Эмбы (да и вообще у всех) универсальная, у тебя только TObject-ы. Надо же сравнивать твою таблицу на универсальном Value, а ты вместо благодарности слюной брызжешь.

По поводу скорости... а ты думаешь другим авторам таблиц легко?
12 янв 17, 16:30    [20099230]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1029
SOFT FOR YOU
Дженерики есть с 2009 года, всю черновую работу я тебе уже прописал. На тот случай если ты сам не умеешь, или времени нет, или оба варианта. У Казанцева таблица универсальная, у Эмбы (да и вообще у всех) универсальная, у тебя только TObject-ы.

У нас разные представления об универсальности. Как сделать универсально на TObject, я уже писал не раз.
А реализация на Value в твоем исполнении - это полный бред и я так никогда бы не сделал.

SOFT FOR YOU
Надо же сравнивать твою таблицу на универсальном Value, а ты вместо благодарности слюной брызжешь.

Если хочешь сравнить свою реализацию с моей - бери код с сайта без всяких изменений.
А в своем коде поменяй Value на TObject.

SOFT FOR YOU
По поводу скорости... а ты думаешь другим авторам таблиц легко?

Вот соревнуйтесь между собой.
Нефиг ломать чужой код, а потом выезжать на белом коне.
12 янв 17, 17:07    [20099425]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 1823
SOFT FOR YOU
У Казанцева таблица универсальная

В который раз убеждаюсь, что ты, либо не читаешь, либо не понимаешь написанного. На счёт универсальности перечитай ещё раз. Речи о данных не было вообще.
12 янв 17, 17:22    [20099489]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Aleksandr Sharahov,

TObject плох тем, что для каждого экземпляра дёргается менеджер памяти, куча обвязок типа Before/After, Init/Cleanup. В случае менеджмента структурами менеджер задействуется при реаллоке, а поля могут вообще никак не модифицироваться если нет сложных типов из строк/интерфейсов/дин.массивов

Поэтому если ты думаешь, что сделать TObject это большое достижение - то ты сильно заблуждаешься. Нет ни гибкости, ни выигрыша по скорости. Почему ты подумал, что при переходе с Obj на дженерик в рамках текущей архитектуры будет проседание по производительности - я не понял. Но если они есть - Эмба, boost и C# как-то решают их. В моей реализации разницы нет

Ты сегодня успел назвать меня идиотом только потому, что "ты бы так не сделал". Аргумент конечно... но слабый. И в целом показывает уровень культуры, я думал, он выше. Нет силы соревноваться - я могу это понять. Если великая ценность твоей статьи в том, что ты немного дополнил Седжвика - я тоже это приму. Но раньше я думал, что уровень твоего профессионализма выше.
12 янв 17, 17:51    [20099595]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Kazantsev Alexey,

Понятно. Я думал твоя таблица представляет какую-то ценность
12 янв 17, 17:55    [20099608]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1029
SOFT FOR YOU,

культура общения в первую очередь состоит в умении
слушать, что говорит собеседник, и не навязывать ему свою точку зрения,

а как профессионал замени TObject на Pointer
12 янв 17, 17:58    [20099632]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Aleksandr Sharahov,

Профессиональные авторы контейнеров делают Value универсальным
Глупо нам всем подстраиваться под твой TObject/Pointer только потому, что ты не умеешь дженерики
12 янв 17, 18:04    [20099656]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1029
SOFT FOR YOU,

Глупо не понимать, то что разжевано вдоль и поперек.
Как правило, TObject уже существует где-то в момент добавления ссылки на него в таблицу.
А профессиональные авторы контейнеров пишут их для тех, кто не может/не хочет написать контейнер для себя.
12 янв 17, 18:09    [20099680]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Владимир2012
Member

Откуда:
Сообщений: 1424
SOFT FOR YOU
Я думал, потенциал больше, но окончилось чем окончилось
Вопросы связанные с разработкой hash очень важны и интересны.
И действительно использование hash в многих алгоритмах целесообразно.

Понятно, что скорее всего нет и быть не может "универсального" hash.
Нет ли у вас tools, который позволял анализировать входной поток данных и предоставлять рекомендации
по использованию того или иного подхода.
Или к примеру имеет смысл подумать над вопросом "адаптивного" hash.

О чем речь?

Программа в процессе работы в течении некоторого времени ее эксплуатации пытается использовать
тот или иной подход связанный с hash, tree, ... и пытается адаптироваться /то бишь использовать/ самый лучший из ей известный подход.

Понятно, что при таком подходе должны быть использованы интерфейсы, которые бы скрывали native структуры
используемые при обработке данных.
Приблизительно как при разработки interafaces скажем для ActiveX.
В этом случае программа будет как-бы "самоулучшаемая".

Экспромтом.

На счет collision.
Может быть при их возникновении такие данные следует помещать во вторичную hash таблицу /для которой используется иной алгоритм расчета hash/?
13 янв 17, 01:25    [20100823]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1029
Владимир2012,

Относительно хешей очень много теории и разработок.
В частности, ваш экспромт называется FKS Hashing. У него рассматриваются статический и динамический варианты.
Есть его же развитие на случай вторичного хеширования. В частности доказывается, что для вторичного хеширования можно из очень простого семейства линейных хешей выбрать такие, что там не будет коллизий, а суммарный размер таблиц будет при этом расти линейно.
13 янв 17, 09:44    [20101299]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

Откуда:
Сообщений: 3023
Пошарился тут по коду TDictionary в Seattle.

Заменил хеш-функции для Integer и String ключей на свои.

Результаты:
+ с родным System.Generics.Defaults.pas
1. Benchmark TDictionary<Integer,Integer>
Add 10.000.000 integers. 1734 msec.
Add 10.000 integers in 10.000.000 iterations. 484 msec.
Locate 10.000 integers in 10.000.000 iterations. 422 msec.

2. Benchmark TDictionary<string,Integer>
Add 1.000.000 GUIDs. 469 msec.
Add 150844 strings in 10.000.000 iterations. 1844 msec.
Locate 150844 strings in 10.000.000 iterations. 1593 msec.
+ с кастомным System.Generics.Defaults.pas
1. Benchmark TDictionary<Integer,Integer>
Add 10.000.000 integers. 390 msec.
Add 10.000 integers in 10.000.000 iterations. 156 msec.
Locate 10.000 integers in 10.000.000 iterations. 94 msec.

2. Benchmark TDictionary<string,Integer>
Add 1.000.000 GUIDs. 328 msec.
Add 150844 strings in 10.000.000 iterations. 1282 msec.
Locate 150844 strings in 10.000.000 iterations. 1203 msec.

Для Integer словаря выигрыш по скорости оказался в 2-3 раза!
Эти дятлы расчитывали(!) бобом дженкинсом(!) хэши для 1-4 байтных целых.

Для строк переход на Роберта Седжевика дал ускорение поскромней.
Но все равно процентов 30 я выиграл.

Как-то так.
15 янв 17, 00:46    [20106851]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

Откуда:
Сообщений: 3023
Ой, ошибся.

Для Integer словаря выигрыш по скорости оказался не в 2-3 раза, а в 3-4+.
15 янв 17, 00:49    [20106857]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

Откуда:
Сообщений: 3023
У кого берлин стоит, гляньте, там таже фигня?
15 янв 17, 00:50    [20106859]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 7 8 9 10 11 12 13 [14] 15 16   вперед  Ctrl
Все форумы / Delphi Ответить