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

Откуда: Москва
Сообщений: 1074
Kazantsev Alexey
У меня лучший результат на поиске по причине другой организации данных в таблице (для снижения расхода памяти, из-за размера хранимых значений + индексного доступа). В общем, если привести структуру ко классической таблице, то и по поиску будет паритет.


Насчет снижения расхода памяти не понял. Нам пофиг где там данные, в таблице или снаружи. Мы тестируем только таблицу, к данным не обращаемся, потому как это все всегда можно сделать как угодно.

И еще, ты заметил, что у меня кроме
function FindName(const Name: RawByteString): integer;
есть
function GetItemByName(const Name: RawByteString): PShaStringDictionaryItem;
?

Это аналог "найти+доступ по индексу", а после этого можно править на месте и все такое. Хотя я не понимаю причем тут вообще это, если тестируем голую таблицу?

Может перетестить надо? )

До кучи там еще есть энумератор для прохода по непустым.
10 янв 17, 23:33    [20091699]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 2041
white_nigger
а ты индексный доступ специально делал? Просто для перебора ключей?

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

Откуда:
Сообщений: 2041
Распределение для ELFHash. Словарь Лопатина:

К сообщению приложен файл. Размер - 32Kb
10 янв 17, 23:40    [20091732]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 2041
Распределение для ELFHash. Словарь Российских фамилий:

К сообщению приложен файл. Размер - 64Kb
10 янв 17, 23:41    [20091737]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 2041
Распределение для ELFHash. Строковые GUIDS:

К сообщению приложен файл. Размер - 64Kb
10 янв 17, 23:41    [20091742]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
__Avenger__
Member

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

Спасибо. И как Вам распределение данной функции?
10 янв 17, 23:48    [20091764]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 2041
Aleksandr Sharahov
Насчет снижения расхода памяти не понял. Нам пофиг где там данные, в таблице или снаружи. Мы тестируем только таблицу, к данным не обращаемся, потому как это все всегда можно сделать как угодно.

Ну вот у тебя элемент таблицы состоит из Hash, Key, Value. Value у тебя объект, 4 байта, у меня Value 16 байт. У таблицы нехилая избыточность, соответственно за счёт неиспользуемых Value набегает хороший оверхед по памяти. Поэтому у меня Value отделены от самой таблицы, за счёт этого экономится память.

Что я сделал с твоей таблицей. Поменял твой 4-байтный Value, на свой 16-байтный Value, дабы корректно оценить скорость вставки. Но из-за этого при поиске твоя таблица стала менее cache friendly, отсюда и отставание. Поэтому я и сказал, что если мне свою таблицу привести ко классической структуре, то она не будет показывать лучший результат на поиске.

Aleksandr Sharahov
Это аналог "найти+доступ по индексу", а после этого можно править на месте и все такое. Хотя я не понимаю причем тут вообще это, если тестируем голую таблицу?

Может перетестить надо? )

Не надо. Там всё честно протестировано (на поиске тестировался только поиск, данные по ключам не вычитывались). Я индексный доступ упомянул, просто для того чтобы стало понятнее о другой внутренней структуре моей таблицы.
10 янв 17, 23:58    [20091804]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1074
Kazantsev Alexey
Что я сделал с твоей таблицей. Поменял твой 4-байтный Value, на свой 16-байтный Value.


Не понял. Зачем? Правильнее было наоборот сделать. Поменять твой 16 на 4. Данные на вставляем же.
11 янв 17, 00:06    [20091820]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 2041
__Avenger__
Спасибо. И как Вам распределение данной функции?

Чем более схожи ключи, тем хуже распределение.

Вот распределение ELFHash для последовательных ключей index1 .. index262144:

К сообщению приложен файл. Размер - 64Kb
11 янв 17, 00:13    [20091837]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 2041
Aleksandr Sharahov
Не понял. Зачем? Правильнее было наоборот сделать. Поменять твой 16 на 4. Данные на вставляем же.

Мне бы пришлось полностью изменять структуру своей таблицы, просто по времени было бы более затратно.
11 янв 17, 00:19    [20091853]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1074
Kazantsev Alexey
Aleksandr Sharahov
Не понял. Зачем? Правильнее было наоборот сделать. Поменять твой 16 на 4. Данные на вставляем же.

Мне бы пришлось полностью изменять структуру своей таблицы, просто по времени было бы более затратно.


Ну тогда вообще ничего не менять.
Главное, чтобы при тестировании размер элемента в обеих таблицах точно совпадал. Иначе всегда проиграет тот, у кого в таблице размер элемента больше, т.к. там и вставка и поиск обращаются практически по случайным адресам в пределах таблицы. Получается тестируем кеш.
11 янв 17, 00:27    [20091870]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 2041
Aleksandr Sharahov
Главное, чтобы при тестировании размер элемента в обеих таблицах точно совпадал.

С этим-то как раз и проблема. Без переделки структуры моей таблицы этого не сделать.

Aleksandr Sharahov
Иначе всегда проиграет тот, у кого в таблице размер элемента больше, т.к. там и вставка и поиск обращаются практически по случайным адресам в пределах таблицы. Получается тестируем кеш.

Я же говорил, что напрямую сравнить не получится. Вот сейчас без переделки структуры "просто" заменил свой value на объект, в твоей тоже вернул объект и проверил на реальном железе: по вставке паритет 26/29, на поиске (1 тыс. итераций) 17700/19193. Теперь твоя таблица оказалась в более выгодном положении и на поиске появилось опережение.
11 янв 17, 00:59    [20091902]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1074
Kazantsev Alexey,

Вот это как раз и интересно.
Для корректного сравнения твой элемент таблицы должен полностью совпадать с моим (добавь TObject).
Работу со своим Value на время закомментируй, а добавленному полю присваивай адрес передаваемых данных.
Разница в скорости как раз и покажет разницу в алгоритмах вставки и поиска.
По идее, если ты упорядочиваешь данные при вставке, все должно совпасть,
если нет, то на вставке ты должен выиграть, на поиске проиграть.
Очень интересно на сколько.
11 янв 17, 07:56    [20092105]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1074
Kazantsev Alexey,

Или еще вариант.
Для закомментировать TObject в моей структуре (и всю работу с ним).
И убрать работу с Value у тебя.
11 янв 17, 09:12    [20092239]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

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

Сделал одинаковым размер элементов таблиц. Пришлось изменить структуру у своей таблицы. В результате вставка/поиск: моя - 25/16761, твоя - 26/16237. У меня переупорядочивание не выполняется.
11 янв 17, 11:09    [20092623]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1074
Kazantsev Alexey,

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

Не помню, результаты поиска в TDictionary ты приводил?
11 янв 17, 11:57    [20092928]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 2041
Aleksandr Sharahov
совсем почти вровень,
посмотрю еще, может получится побыстрее вставку сделать.

Я ещё не убрал дополнительный вызов на вычислении хеша, не стал совсем-то уж маньячить :)

Aleksandr Sharahov
Не помню, результаты поиска в TDictionary ты приводил?

Приводил, но там было с моим Value. Вот TDictionary<UnicodeString, TObject>: 81/32369
11 янв 17, 12:12    [20093006]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1986
Давайте таблицами мериться
Выложите 1 проект с 2 вариантами таблиц и возможностью добавить третью
11 янв 17, 14:13    [20093745]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1986
Можно даже дженерик заколбасить
Когда Key string, а Value - произвольный тип
11 янв 17, 14:19    [20093783]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1986
И пусть этот Value будет размером, например, 23 байта, и содержать будет хотя бы один из сложных типов: string/interface/дин.массив
11 янв 17, 14:22    [20093811]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Barmaley57
Member

Откуда: Москва
Сообщений: 5633
Да вы маньячки, товарищи!
11 янв 17, 17:35    [20094924]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

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

Маньяк здесь только один человек - я )
11 янв 17, 17:42    [20094960]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1621
SOFT FOR YOU
Давайте таблицами мериться
Выложите 1 проект с 2 вариантами таблиц и возможностью добавить третью

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

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

Так то деревья
А это хеши
11 янв 17, 18:41    [20095195]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 1621
SOFT FOR YOU,
там всё вместе
11 янв 17, 19:07    [20095281]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 7 8 9 10 11 [12] 13 14 15 16 .. 19   вперед  Ctrl
Все форумы / Delphi Ответить