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

Откуда:
Сообщений: 1672
SOFT FOR YOU
Ты на виртуалке тестировал?

Нет. Хоть это и не имеет значения.

SOFT FOR YOU
Может быть и теги тоже медленнее работают?

Нет. С тегами результат воспроизводим, но цифры разумеется другие.

SOFT FOR YOU
По поводу фамилий. Бери реальную выборку ФИО на 2000 человек - и будем смотреть

Почему только 2 тысячи, мне 248 больше нравятся.
10 янв 17, 14:11    [20089065]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

И да, смоделируй, пожалуйста, ситуацию, близкую к реальной, где понадобится хеш по Фамилиям?
Поисковые системы типа регистратуры выдают результаты после 3 введённых букв. И хеш по фамилиям тут не катит. Разве что по первым трём буквам )
10 янв 17, 14:12    [20089072]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

На свою подколку, я тебе сказал, что это реально
Остальное - не более чем твои влажные фантазии
10 янв 17, 14:13    [20089083]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
defecator
Member

Откуда: arm-pascal.ru
Сообщений: 31050
SOFT FOR YOU
defecator,

На свою подколку, я тебе сказал, что это реально
Остальное - не более чем твои влажные фантазии

ты мне начал втирать про то, чтобы я взял и сделал то, что мне не надо.
так что фантазии у тебя
10 янв 17, 14:15    [20089099]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

Ты начал втирать, что я грозился. Хотя было ясно, чётко, понятно, что это не так :)
Причём, что забавно, это было даже в тех цитатах, которые ты приводил в качестве аргумента )))
10 янв 17, 14:17    [20089119]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
defecator
Member

Откуда: arm-pascal.ru
Сообщений: 31050
SOFT FOR YOU
defecator,

Ты начал втирать, что я грозился. Хотя было ясно, чётко, понятно, что это не так :)
Причём, что забавно, это было даже в тех цитатах, которые ты приводил в качестве аргумента )))

о боже Картинка с другого сайта. Картинка с другого сайта. Картинка с другого сайта.
10 янв 17, 14:18    [20089126]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 1672
SOFT FOR YOU
И да, смоделируй, пожалуйста, ситуацию, близкую к реальной, где понадобится хеш по Фамилиям?
Поисковые системы типа регистратуры выдают результаты после 3 введённых букв. И хеш по фамилиям тут не катит. Разве что по первым трём буквам )

Я понять не могу, ты всё еще пытаешься написать хеш "подходящий вообще для всего", или ищешь возможность оправдаться?
10 янв 17, 14:19    [20089128]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

Для всего хорош Дженкинс. Может быть Сейджвик, его тоже надо проверять, интересно, почему его Эмба не взяла
Но хеш-таблицы не используются для всего. Каждый случай уникальный
10 янв 17, 14:29    [20089231]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

Если ты приколебался про пост, где после "для всего" поставил смайл - так это ежу должно быть понятно, что для множества похожих слов он не годится. Тем более, я потом правил функцию. Или к чему все твои наезду?
10 янв 17, 14:35    [20089283]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 1672
SOFT FOR YOU
Но хеш-таблицы не используются для всего. Каждый случай уникальный

Конечно используются. Моя таблица используется в условиях, когда я понятия не имею, что в неё будет загружено. TDictionary вообще универсал.

SOFT FOR YOU
Если ты приколебался про пост, где после "для всего" поставил смайл - так это ежу должно быть понятно, что для множества похожих слов он не годится.

Ежу-то может оно и понятно, а кто по русски читает, тот понимает только то о чём прямо написано. Перестань уже изворачиваться. Облажался, так признай это.

SOFT FOR YOU
Тем более, я потом правил функцию.

Ну так я и проверял её до самой последней мутации, чуда не случилось.

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

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

Тогда может ответишь, почему Седжвик, а не Дженкинс? Почему хеш не побайтовый? Зачем, наконец, сторона степени двойки, а не простое число?

Или что, коллизии уже не так важны?
Определись уже, я чушь порю, или ты лажаешь с реализацией?

P.S. нахрена опять ты говоришь про свою таблицу или про дженерик? Почему просто нельзя согласиться с тем, что юзание хеш-таблиц узко специализировано и уникально? Нафига эти детские перипетии?
10 янв 17, 15:08    [20089558]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 1672
SOFT FOR YOU
Тогда может ответишь, почему Седжвик, а не Дженкинс? Почему хеш не побайтовый? Зачем, наконец, сторона степени двойки, а не простое число?

Седжвик, потому что он лучше подходит для моих условий - каких угдно строковых ключей в UTF-16. По той же причине он символьный, а не байтовый. Ну а к размеру вообще привязки нет, поддерживаются оба варианта.

SOFT FOR YOU
Или что, коллизии уже не так важны?

Коллизии хеша это однозначный удар по производительности, как бы ни была реализована таблица, пойми это наконец.

SOFT FOR YOU
Определись уже, я чушь порю, или ты лажаешь с реализацией?

Ты порешь чушь. Если ты внимательно читал, то должен был видеть, что я приводил замеры производительности и своей таблицы, и TDictionary, и таблицы Шарахова.

SOFT FOR YOU
Почему просто нельзя согласиться с тем, что юзание хеш-таблиц узко специализировано и уникально?

Потому что это не так. Потому что использование универсальной таблицы является более частым вариантом, чем использование узкоспециализированной. Это должно быть понятно тем, кто знаком с понятием достаточной производительности.
10 янв 17, 15:30    [20089752]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

Ты уникальный человек
В одном и том же сообщении умудряешься говорить об универсальности, хвастаешься подобранным хешем под частный случай, подчеркиваешь особую важность коллизий для производительности, и берёшь не самую распределяющую функцию. Ах да, ещё и размер таблицы делаешь не по канонам.

Это пять!
10 янв 17, 15:42    [20089870]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

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

Используемый мною символный Седжвик, на строковых ключах в UTF-16, даёт хорошее распределение даже будучи адаптированым под байтовые строки, или просто байтовые последовательности. Изменения алгоритма не требуется. Это универсальный хеш. Используется потому, что работает быстрее Дженкинса.

Теперь о моей таблице. Моя таблица использует только строковые ключи в UTF-16, и поэтому, по дефолту, использует символьный хеш Седжвика. Алгоритм работы таблицы не завязан именно на строковые ключи в UTF-16. Адаптировать таблицу можно на любые типы ключей, алгоритм работы от этого не изменится. Это универсальная таблица. Собственно говоря, любая таблица реализующая классический алгоритм ни коим образом не зависит от используемых ключей, только от используемого хеша.
10 янв 17, 16:12    [20090059]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

Это что же получается...
Не я ерунду говорю, указывая на быстрый хеш ценой дополнительных коллизий, а ты устраиваешь шоу, руководствуясь озвученными мной принципами?
10 янв 17, 16:24    [20090144]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 1672
SOFT FOR YOU
Это что же получается...
Не я ерунду говорю, указывая на быстрый хеш ценой дополнительных коллизий, а ты устраиваешь шоу, руководствуясь озвученными мной принципами?

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

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

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

Опять не можешь признать собственный косяк?
Ты используешь модификацию Седжвика, а не универсальный байтовых оригинал. Потому, что он в 2 раза быстрее.
Ты используешь не Дженкинса потому, что Дженкинс медленнее. Хоть и меньше коллизий даёт.
И размер таблицы не простое число только потому, что mod во много раз медленнее and
Кстати ты ни разу не говорил про "коллизии пачками". Ты говорил о коллизиях и только о них.

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

Ну и какие ко мне претензии? Что он ищет Лопатина медленнее?
Да кому к черту сдался этот Лопатин в реалиях? Только тебе.
А теги ищет каждый автор парсера.
10 янв 17, 16:51    [20090291]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 1672
SOFT FOR YOU
Опять не можешь признать собственный косяк?

Не вали-ка ты с больной головы на здоровую.

SOFT FOR YOU
Ты используешь модификацию Седжвика, а не универсальный байтовых оригинал. Потому, что он в 2 раза быстрее.

Что логично. Только не модификацию, а адаптацию. Там алгоритм не тронут вообще.

SOFT FOR YOU
Ты используешь не Дженкинса потому, что Дженкинс медленнее. Хоть и меньше коллизий даёт.

Снова ты несёшь чушь. На русских словарях Дженкинс хуже Седжвика, хоть и совсем незначительно, но при этом медленне.

SOFT FOR YOU
И размер таблицы не простое число только потому, что mod во много раз медленнее and

Нет, просто у Шарахова была такая таблица, поэтому и замеры сделаны на идентичном варианте. Но вот прямо сейчас заменил And на Mod - разница на наборе в 1млн. ключей всего несколько миллисекунд, в конечном итоге. А если не просто поменять And на Mod, а изменить режим работы таблицы, чтобы её внутренний размер перестал быть кратен степени двойки, то разница на наборе в 1млн. составила всего 26 msec. (7%) на вставке, и 14 msec. (6%) на поиске. Зато потребление памяти снизилось на 4.5Mb (15%).

SOFT FOR YOU
Кстати ты ни разу не говорил про "коллизии пачками". Ты говорил о коллизиях и только о них.

Пачками - фигуральное выражение. Ну, если на наборе 248 тыс. фамилий хеш даёт 52 тыс. коллизий, как это ещё назвать? А когда на наборе в 1млн. никому не нужных ключей хеш чуть не весь миллион, а конкретно 900 тыс., обращает в коллизии, то что это? Но, это никому не нужные ключи виноваты, я в курсе.

SOFT FOR YOU
Я говорил о реальных ситуациях. Сериализация, поиск токенов.

Да ты говорил о столь же синтетической задаче, сколь и никому не нужные, по твоему, мнению ключи. В задаче Свириденкова набор был динамическим, с неизвестным содержим, а у тебя четыре десятка статических тегов.

SOFT FOR YOU
Других реальных задач я не знаю.

Отлично. Давай на этом и закончим.

SOFT FOR YOU
Ты же говоришь о синтетических ситуациях. Множество коротких похожих слов.

Да у тебя всё что тебе не нравится, всё сиснтетическая ситуация. Ну извините, других русских фамилий у меня для вас нет.

SOFT FOR YOU
Ну и какие ко мне претензии? Что он ищет Лопатина медленнее?
Да кому к черту сдался этот Лопатин в реалиях? Только тебе.

К тебе нет никаких претензий. Но вот твой хеш, который "быстр и удобен вообще для всего )" - полный шлак.
10 янв 17, 17:52    [20090579]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

Этот шлак обогнал твои хеши на реальной задаче. Получается, не такой уж и шлак?
Ты почему-то думаешь, что при увеличении количества тегов, ситуация изменится кардинально

Ты запарен на теории, коллизиях и всё такое.
Я об этом и писал, что есть 4 параметра, которые нужно учитывать в сумме. А не 1 как у тебя

Для Лопатина имеет смысл написать другой хеш
Или вообще для строк - более быстрый хеш
Но ты ведь дальше Byte-->Word не продвинулся, правда? )
И как свою таблицу сделать быстрее - ты видимо тоже не сильно думаешь
10 янв 17, 18:02    [20090631]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

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

Ты мне надоел, совершенно не хочешь понимать о чём тебе пишут. Я больше не стану тратить на тебя своё время. Удачи.
10 янв 17, 18:14    [20090677]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member [заблокирован]

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

Наконец-то
А то я думал и дальше будешь морочить мне голову своими частными, но универсальными хешами
10 янв 17, 18:22    [20090700]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1315
кое как дочитал
не спорьте, есть задачи где хеш-таблицами категорически нельзя пользоваться по требованиям безопасности
10 янв 17, 18:43    [20090764]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
white_nigger
Member

Откуда: Тула
Сообщений: 1269
Kazantsev Alexey, а ты индексный доступ специально делал? Просто для перебора ключей? Просто думаю насколько велика вероятность, что появится нужда в этом
10 янв 17, 22:37    [20091505]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
__Avenger__
Member

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

А на такой функции графическое распределение можете показать:
function ELFHash(const Value: String): Integer;
var
  i, x: Integer;
begin
  Result := 0;
  for i := 1 to Length(Value) do
  begin
    Result := (Result shl 4) + Ord(Value[i]);
    x := Result and $F0000000;
    if (x <> 0) then
      Result := Result xor (x shr 24);
    Result := Result and (not x);
  end;
end;

?
10 янв 17, 23:08    [20091605]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

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

Я заметил что отлаживаться при работе через индекс гораздо удобней, чем при работе по энумератору.
10 янв 17, 23:08    [20091606]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 6 7 8 9 10 [11] 12 13 14 15   вперед  Ctrl
Все форумы / Delphi Ответить