ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Delphi [игнор отключен] [закрыт для гостей] / TDictionary или TList<>.BinarySearch с позиции поиска
25 сообщений из 479, страница 18 из 20
  18  все
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422509
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Значит я посмотрю
Возможно под x86 имеет смысл использовать стандартный ассемблерный компаратор строк, а не мой самописный
...
Рейтинг: 0 / 0
19.03.2017, 15:13:50
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422510
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
SOFT FOR YOUЕсли бы сравнивались только указатели, то в данном случае был бы Exception
А посмотреть - только трейсить
У тебя сохранены строки в Items. Cтроки у нас рефкаунтед, а потому там сохранены только указатели. Когда ты вставляешь данные в словарь, то словарь сохраняет строковый ключ и тоже как указатель. Когда ты в поиске даёшь словарю сохранённую в Items строку, то фактически ты передаёшь уже сохранённый адрес. Компарер видя что адреса сравниваемых строк совпадают дальнейшее сравнение не делает. Так понятно?
...
Рейтинг: 0 / 0
19.03.2017, 15:14:55
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422511
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Kazantsev Alexey,

В Items есть Key: TKey
Он конечно указатель, но обычный string в соответствующем случае
Если указатели string совпадают - то строки равны. А ты как хотел?
...
Рейтинг: 0 / 0
19.03.2017, 15:18:55
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422513
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
SOFT FOR YOUЕсли указатели string совпадают - то строки равны. А ты как хотел?
Для корректности поиск нужно делать по копиям ключей, чтобы дать возможность отрабатывать компареру, как это происходило бы в реальных сценариях.
...
Рейтинг: 0 / 0
19.03.2017, 15:23:12
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422519
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Kazantsev AlexeySOFT FOR YOUЕсли указатели string совпадают - то строки равны. А ты как хотел?
Для корректности поиск нужно делать по копиям ключей, чтобы дать возможность отрабатывать компареру, как это происходило бы в реальных сценариях.

Очень интересная мысль
Наверное, действительно нужно предусмотреть отдельный вариант теста с уникальными строками

Но:
1) Стандартный компаратор тоже сравнивает указатели
2) Значит дело не в компараторе x86, а в чём-то другом. Не может у Шарахова поиск по хешу работать быстрее моего :)
Но может быть действительно дело в архитектуре, том факте, что память расходуется больше
...
Рейтинг: 0 / 0
19.03.2017, 15:40:59
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422521
Фотография defecator
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
defecatorПривилегированный пользователь
Модератор форума
SOFT FOR YOUНе может у Шарахова поиск по хешу работать быстрее моего
Самоуверенность просто прёт !
Когда библиотеки Шарахова использовались, ты ещё сиську сосал, и к его коду доверия гораздо больше, чем к коду всемирного оптимизатора.
...
Рейтинг: 0 / 0
19.03.2017, 15:44:32
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422548
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Добавил в свой тест ShaDictionary

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
1. Benchmark TArrayEx<Integer>
Add 10.000.000 integers. 594 msec. 32 msec (optimised).
Add 10.000 integers in 10.000.000 iterations. 718 msec.
Locate 10.000 integers in 10.000.000 iterations. 719 msec.

2. Benchmark THashTable<Integer,Integer>
Add 10.000.000 integers. 1860 msec. 672 msec (optimised).
Add 10.000 integers in 10.000.000 iterations. 281 msec.
Locate 10.000 integers in 10.000.000 iterations. 266 msec.

3. Benchmark TDictionary<Integer,Integer>
Add 10.000.000 integers. 2109 msec.
Add 10.000 integers in 10.000.000 iterations. 656 msec.
Locate 10.000 integers in 10.000.000 iterations. 531 msec.

4. Benchmark TRapidDictionary<Integer,Integer>
Add 10.000.000 integers. 453 msec.
Add 10.000 integers in 10.000.000 iterations. 172 msec.
Locate 10.000 integers in 10.000.000 iterations. 140 msec.

5. Benchmark TShaObjectDictionary
Add 10.000.000 integers. 1375 msec.
Add 10.000 integers in 10.000.000 iterations. 282 msec.
Locate 10.000 integers in 10.000.000 iterations. 250 msec.
...
Рейтинг: 0 / 0
19.03.2017, 16:57:47
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422561
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
rgreat,

а где можно скачать исходники?
...
Рейтинг: 0 / 0
19.03.2017, 17:11:33
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422565
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Aleksandr Sharahov,

http://www.rgreat.ru/tmp/Delphi/Test.zip
...
Рейтинг: 0 / 0
19.03.2017, 17:15:50
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422585
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
А я в свой тест добавил TShaNamedObjectDictionary

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
RawByteString
TRunner<System.RawByteString>.Sha Add... 686ms
TRunner<System.RawByteString>.Sha Add+Capacity... 577ms
TRunner<System.RawByteString>.Sha Items... 468ms
TRunner<System.RawByteString>.RapidRapid Add... 764ms
TRunner<System.RawByteString>.RapidRapid Add+Capacity... 639ms
TRunner<System.RawByteString>.RapidRapid Items... 515ms
TRunner<System.RawByteString>.RapidDictionary Add... 748ms
TRunner<System.RawByteString>.RapidDictionary Add+Capacity... 577ms
TRunner<System.RawByteString>.RapidDictionary Items... 453ms



rgreat,

Кстати я нашёл баг конструктора, про который ты говорил
Фиг знает, почему в одних случай конструктор класса происходит, а в других нет
В общем исправил, обновил файл в репозитории
...
Рейтинг: 0 / 0
19.03.2017, 17:50:06
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422588
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Я так и не понял, у тебя в хеш-таблице есть возможность создать <RawByteString,Integer>, например?
Или для хранения Integer должен быть какой-то отдельный массив?
...
Рейтинг: 0 / 0
19.03.2017, 17:54:06
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422640
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
rgreatAleksandr Sharahov,

http://www.rgreat.ru/tmp/Delphi/Test.zip

Посмотрел, есть несколько предложений:

1. Тесты с целочисленными ключами работают с неодинаковыми случайными данными
из-за того, что в начале каждого теста RandSeed имеет разные значения. Исправление:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
    Randomize; Seed:=RandSeed;
    if TestIntegers then begin
      RandSeed:=Seed; TArrayExTestInteger;
      RandSeed:=Seed; THashTableTestInteger;
      RandSeed:=Seed; TDictionaryTestInteger;
      RandSeed:=Seed; TRapidDictionaryTestInteger;
      RandSeed:=Seed; TShaDictionaryTestInteger;
      RandSeed:=Seed; TShaBoxTestInteger;
    end;



2. Мои словари используют взбалтывание идентификаторов, из-за чего работают в неравных условиях с другими.
Переделал, теперь это опция, по умолчанию отключенная. Для сравнимости результатов лучше использовать
обновленные исходники к статье http://guildalfa.ru/alsha/node/32

3. По аналогии добавил замеры скорости для TShaIntegerBox:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
procedure TShaBoxTestInteger;
type
  TDict = ShaDictionaries.TShaIntegerBox;
var
  A : TDict;
  i : Integer;
  T : Cardinal;
const
  SearchVal = 5;
begin
  WriteHeader('Benchmark '+PTypeInfo(TypeInfo(TDict)).Name);

  A:=TDict.Create;
  try
    Write('Add 10.000.000 integers. ');
    T:=GetTickCount;
    for i:=0 to 9999999 do begin
      A.Add(i);
    end;
    T:=GetTickCount-T;
    WriteLn(IntToStr(T)+' msec.');

    A.Clear;
    Write('Add 10.000 integers in 10.000.000 iterations. ');
    T:=GetTickCount;
    for i:=0 to 9999999 do begin
      A.Add(Random(10000));
    end;
    T:=GetTickCount-T;
    WriteLn(IntToStr(T)+' msec.');

    Write('Locate 10.000 integers in 10.000.000 iterations. ');
    T:=GetTickCount;
    for i:=0 to 9999999 do begin
      A.Find(Random(10000));
    end;
    T:=GetTickCount-T;
    WriteLn(IntToStr(T)+' msec.');

  finally
    A.Free;
  end;
end;




После этих изменений на E6850 получил:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
Add 10.000.000 integers. 952 msec. 46 msec (optimised).
Add 10.000 integers in 10.000.000 iterations. 1154 msec.
Locate 10.000 integers in 10.000.000 iterations. 1155 msec.

2. Benchmark THashTable<Integer,Integer>
Add 10.000.000 integers. 3042 msec. 1123 msec (optimised).
Add 10.000 integers in 10.000.000 iterations. 484 msec.
Locate 10.000 integers in 10.000.000 iterations. 452 msec.

3. Benchmark TDictionary<Integer,Integer>
Add 10.000.000 integers. 3089 msec.
Add 10.000 integers in 10.000.000 iterations. 1014 msec.
Locate 10.000 integers in 10.000.000 iterations. 811 msec.

4. Benchmark TRapidDictionary<Integer,Integer>
Add 10.000.000 integers. 936 msec.
Add 10.000 integers in 10.000.000 iterations. 327 msec.
Locate 10.000 integers in 10.000.000 iterations. 250 msec.

5. Benchmark TShaObjectDictionary
Add 10.000.000 integers. 655 msec.
Add 10.000 integers in 10.000.000 iterations. 203 msec.
Locate 10.000 integers in 10.000.000 iterations. 140 msec.

6. Benchmark TShaIntegerBox
Add 10.000.000 integers. 562 msec.
Add 10.000 integers in 10.000.000 iterations. 187 msec.
Locate 10.000 integers in 10.000.000 iterations. 141 msec.
...
Рейтинг: 0 / 0
19.03.2017, 19:31:15
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422642
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUА я в свой тест добавил TShaNamedObjectDictionary

Мои словари используют взбалтывание идентификаторов, из-за чего работают в неравных условиях с другими.
Переделал, теперь это опция, по умолчанию отключенная. Для сравнимости результатов лучше использовать
обновленные исходники к статье http://guildalfa.ru/alsha/node/32


SOFT FOR YOUAleksandr Sharahov,
Я так и не понял, у тебя в хеш-таблице есть возможность создать <RawByteString,Integer>, например?
Или для хранения Integer должен быть какой-то отдельный массив?

У меня элементы хеш-таблицы содержат только два поля: хеш-код и адрес данных.

Если ты хочешь хранить в хеш-таблице адреса объектов или записей,
которые имеют поля RawByteString, Integer и/или любые другие,
то, разумеется, они должны находиться где-то в памяти вне таблицы.
...
Рейтинг: 0 / 0
19.03.2017, 19:42:28
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422659
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Сурово
У тебя вызываются калбеки на хеш и компаратор строки. У меня они инлайнятся, кроме того хеш сначала считается четверками байт.
Как ты думаешь, почему производительность может уступать?
...
Рейтинг: 0 / 0
19.03.2017, 20:18:59
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422672
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr Sharahov,

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

При случайном доступе к элементам хеш-таблицы производительность определяется, в первую очередь, количеством элементов таблицы, которое помещается в кеш-линии.
...
Рейтинг: 0 / 0
19.03.2017, 20:37:47
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422677
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Т.е. если количество элементов будет таким, что все они поместятся в L1, у меня станет быстрее?
...
Рейтинг: 0 / 0
19.03.2017, 20:49:11
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422686
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUТ.е. если количество элементов будет таким, что все они поместятся в L1, у меня станет быстрее?

Не в этом дело.
Искомый элемент хеш-таблицы может иметь индекс, отличающийся от предсказанного.
В этом случае придется последовательно прочитать данные из нескольких кеш-линий.
...
Рейтинг: 0 / 0
19.03.2017, 21:17:20
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422694
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Надо конечно проанализировать коллизии, но, насколько я помню, их было не много
...
Рейтинг: 0 / 0
19.03.2017, 21:36:47
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422717
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

А есть у твоей реализации ещё какие-то преимущества над стандартным TDictionary? Кроме урезания данных
...
Рейтинг: 0 / 0
19.03.2017, 23:19:58
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422724
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr Sharahov,

А есть у твоей реализации ещё какие-то преимущества над стандартным TDictionary? Кроме урезания данных

Разумеется, вот те, что мне нравятся:
- скорость,
- удобство,
- единообразное использование,
- размер и понятность кода,
- отсутствие ненужных мне функций,
- простота изменения под себя.
...
Рейтинг: 0 / 0
19.03.2017, 23:35:41
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422729
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Мягко говоря аргументы спорные
Но меня интересует именно производительность
Есть ли особенности, кроме урезания размера рабочих структур, которые позволяют увеличить производительность относительно стандартной TDictionary?
...
Рейтинг: 0 / 0
19.03.2017, 23:58:30
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422732
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUНо меня интересует именно производительность
Есть ли особенности, кроме урезания размера рабочих структур, которые позволяют увеличить производительность относительно стандартной TDictionary?

Разумеется, есть неиспользованные возможности.
Например, производительность можно дополнительно увеличить инлайнами и всякой другой хренью, ну, ты понял )
...
Рейтинг: 0 / 0
20.03.2017, 00:08:55
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422736
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr Sharahov,

Ясно :)
...
Рейтинг: 0 / 0
20.03.2017, 00:24:34
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422749
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Aleksandr Sharahovпонятность кода,
Смотрю я на твою функцию ShiftItems и понятность от меня уплывает. :)
...
Рейтинг: 0 / 0
20.03.2017, 01:01:30
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422774
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
rgreatAleksandr Sharahovпонятность кода,
Смотрю я на твою функцию ShiftItems и понятность от меня уплывает. :)

Если не читал статью, то да, может быть непонятно.

Там всего 3 идеи при сдвиге:
1. не делать лишнего,
2. не нарушить упорядоченность,
3. учесть заворот данных при выходе за границу массива.
...
Рейтинг: 0 / 0
20.03.2017, 07:16:55
| Ответить | Цитировать | Написать  
25 сообщений из 479, страница 18 из 20
  18  все
Форумы / Delphi [игнор отключен] [закрыт для гостей] / TDictionary или TList<>.BinarySearch с позиции поиска
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=58&msg=39422521&tid=2041988]:
 0ms
get settings:
 8ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 185ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 38ms
get tp. blocked users:
 1ms
others: 227ms
total:  488ms
созд. / загр.: 488ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]