ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Delphi [игнор отключен] [закрыт для гостей] / TDictionary или TList<>.BinarySearch с позиции поиска
25 сообщений из 479, страница 17 из 20
  17  все
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422370
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
rgreatAleksandr SharahovМы боремся не с атакой на хеш. Это бред.
Мы боремся с регулярностью ключа. А это реальность.Надежней через Capacity это решить.
При условии что положение в листе ищется через n:=Value mod Capacity.

И коллизий не будет и в скорости не потеряешь.

Пример.

Capacity=256*1024
Заполняем на 3/4, N=3*64*1024 элементов.
Ключи вида K=I*256, I=0..N-1.
Имеем K mod Capacity = I*256 mod (256*1024),
итого 1024 разных значения модуля,
т.е. в каждый из 1024 кластеров попадет N/1024=3*64=192 ключа
...
Рейтинг: 0 / 0
19.03.2017, 01:49:32
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422372
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
SOFT FOR YOUЗавершил бенчмарки для проекта Rapid.Generics
Ни в одной из этих версий не компилируется: XE2, XE3, XE6, XE7, 10.1 Berlin. (commit: aadf2824eb9003154f5ab048092df53c4fc12c38)
...
Рейтинг: 0 / 0
19.03.2017, 02:29:23
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422373
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
SOFT FOR YOUrgreatПроверь разницу.
Лень
Там исходники бенчмарка открыты, посмотри, если хочешь
Вангую, что скорость будет как у TRapidGenerics
Но я считаю, предложенный тобой способ не надёжен для универсального использования. Хотя в частных случаях годится - вполне
Не угадал.

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
1. Benchmark TDictionary<Integer,Integer>
Add 10.000.000 integers. 2000 msec.
Add 10.000 integers in 10.000.000 iterations. 641 msec.
Locate 10.000 integers in 10.000.000 iterations. 500 msec.

2. Benchmark TRapidDictionary<Integer,Integer>
Add 10.000.000 integers. 422 msec.
Add 10.000 integers in 10.000.000 iterations. 172 msec.
Locate 10.000 integers in 10.000.000 iterations. 125 msec.

3. Benchmark TRapidDictionary<Integer,Integer> Modified.
Add 10.000.000 integers. 359 msec.
Add 10.000 integers in 10.000.000 iterations. 140 msec.
Locate 10.000 integers in 10.000.000 iterations. 94 msec.
...
Рейтинг: 0 / 0
19.03.2017, 02:33:45
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422375
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Aleksandr SharahovПример.

Capacity=256*1024
Заполняем на 3/4, N=3*64*1024 элементов.
Ключи вида K=I*256, I=0..N-1.
Имеем K mod Capacity = I*256 mod (256*1024),
итого 1024 разных значения модуля,
т.е. в каждый из 1024 кластеров попадет N/1024=3*64=192 ключаОпять частный случай.
Сделай ключ I*255 или I*257 и проблема исчезает.

Как я уже сказал подобрать правило можно под любой хэш в таблице с открытой адресацией.
Перебор разных хешей это не более чем игры в угадайку.
...
Рейтинг: 0 / 0
19.03.2017, 02:50:27
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422376
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Хотя про "коллизий не будет" это я глупость сказал, конечно. Не подумавши.
...
Рейтинг: 0 / 0
19.03.2017, 02:51:42
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422381
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
rgreatНе угадал.

Не :)
Я имел ввиду, если ты InterfaceDefaults.GetHashCode_N4 подменишь

А вообще буст виден, согласен. Только я на такое в универсальной либе так и не решусь :)
...
Рейтинг: 0 / 0
19.03.2017, 04:48:13
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422382
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Kazantsev AlexeySOFT FOR YOUЗавершил бенчмарки для проекта Rapid.Generics
Ни в одной из этих версий не компилируется: XE2, XE3, XE6, XE7, 10.1 Berlin. (commit: aadf2824eb9003154f5ab048092df53c4fc12c38)

У меня как раз XE8 :)
А что ругается? Internal error?
...
Рейтинг: 0 / 0
19.03.2017, 04:49:29
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422459
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUБлин, хотел модуль Шарахова добавить, а UnicodeString нет, RawByteString-таблица основана на поле в обжекте
Нет, хватит париться )

Жаль, что твоя гнедая сломала ногу )

Во-первых, заметил небольшую неточность.
Тест на время заполнения учитывает время создания словаря и время заполнения, но не учитывает время освобождения.
Учел.

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

В-третьих, чтобы использовать "поле в обжекте" достаточно умения работать с указателями.

В общем добавил немного отсебятины в твой код:
Код: 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.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
uses
  ShaDictionaries;

...

var
  arr: array of RawByteString;

procedure ShaPrepare;
var
  Len, i, j, Seed: Integer;
begin;
  SetLength(arr, ITEMS_COUNT);
  Randomize; Seed:=RandSeed;
  for i := 0 to ITEMS_COUNT-1 do begin;
    Len := 5 + Random(8);
    SetLength(arr[i], Len);
    for j := 1 to Len do arr[i][j] := AnsiChar(Ord('A') + Random(Ord('Z') - Ord('A') + 1));
    end;
  RandSeed:=Seed;
  end;

procedure ShaRun;
const
  ITERATIONS_COUNT = 10;
  MODES: array[0..2] of string = ('Add', 'Add+Capacity', 'Items');
  CAPACITIES: array[0..2] of Integer = (0, ITEMS_COUNT, ITEMS_COUNT);
var
  i, cnt, Mode: integer;
  Time: cardinal;
  d: TShaNamedObjectDictionary;
  p: pointer;
begin;
  for Mode := Low(MODES) to High(MODES) do begin;
    Write('TShaNamedObjectDictionary ', MODES[Mode], '... ');
    if Mode<>2 then begin;
      Time:=GetTickCount;
      for cnt:=1 to ITERATIONS_COUNT do begin;
        d:=TShaNamedObjectDictionary.Create(CAPACITIES[Mode], false, 0);
        for i:=0 to Length(arr)-1 do d.Add(arr[i], @arr[i]);
        d.Free;
        end;
      Time := GetTickCount - Time;
      end
    else begin;
      d:=TShaNamedObjectDictionary.Create(CAPACITIES[Mode], false, 0);
      for i:=0 to Length(arr)-1 do d.Add(arr[i], @arr[i]);
      Time:=GetTickCount;
      for cnt:=1 to ITERATIONS_COUNT do for i:=0 to Length(arr)-1 do p:=d.Objects[arr[i]];
      Time := GetTickCount - Time;
      d.Free;
      if p<>@arr[Length(arr)-1] then Write(' *not found* ');
      end;
    Writeln(Time, 'ms');
    end;
  end;

begin
  try
    ShaPrepare;
    ShaRun;
...



скомпилировал на XE8 и прогнал на E6850, результаты ниже:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
TShaNamedObjectDictionary Add... 1357ms
TShaNamedObjectDictionary Add+Capacity... 1123ms
TShaNamedObjectDictionary Items... 982ms

string
TRunner<System.string>.SystemSystem Add... 4976ms
TRunner<System.string>.SystemSystem Add+Capacity... 3042ms
TRunner<System.string>.SystemSystem Items... 1513ms
TRunner<System.string>.SystemRapid Add... 4664ms
TRunner<System.string>.SystemRapid Add+Capacity... 2699ms
TRunner<System.string>.SystemRapid Items... 1185ms
TRunner<System.string>.RapidRapid Add... 1904ms
TRunner<System.string>.RapidRapid Add+Capacity... 1591ms
TRunner<System.string>.RapidRapid Items... 1030ms
TRunner<System.string>.RapidDictionary Add... 2028ms
TRunner<System.string>.RapidDictionary Add+Capacity... 1716ms
TRunner<System.string>.RapidDictionary Items... 1155ms



женерики наше все.
...
Рейтинг: 0 / 0
19.03.2017, 13:21:59
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422471
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr SharahovВо-первых, заметил небольшую неточность.
Тест на время заполнения учитывает время создания словаря и время заполнения, но не учитывает время освобождения.
Учел.
Не совсем понял, что ты имеешь ввиду
Операцию Delete или Clear?
Delete показала бы превосходство моего кода, но Delete происходит редко, поэтому я решил не добавлять в тест
Clear тоже не медленнее... на Integer разницы быть не должно, для string разница незначительна. Хотя... в оригинале вроде виртуальные калбеки дёргаются, я уже не помню

Aleksandr SharahovВо-вторых, ты ж понимаешь, что разницы между UnicodeString и RawByteString в данном нашем случае нет никакой,
все особенности легко учитываются внутри хеш-функции.
Не понятно, это ты к чему?
Я не против RawByteString :)

Aleksandr SharahovВ-третьих, чтобы использовать "поле в обжекте" достаточно умения работать с указателями.
Что-то я не понял. А к чему тогда поле Offset?

Aleksandr SharahovВ общем добавил немного отсебятины в твой код:
скомпилировал на XE8 и прогнал на E6850, результаты ниже:
женерики наше все.
Так ты RawByteString и UnicodeString похоже сравниваешь. Во втором в 2 раза больше байт
...
Рейтинг: 0 / 0
19.03.2017, 14:05:45
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422475
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr SharahovRandomize; Seed:=RandSeed;
Сначала надо Seed сохранять, потом рандомайзить )
Ну и потом здесь специально нет рандомайза, чтобы сохранить одинаковость данных
...
Рейтинг: 0 / 0
19.03.2017, 14:08:41
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422482
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr SharahovВо-первых, заметил небольшую неточность.
Тест на время заполнения учитывает время создания словаря и время заполнения, но не учитывает время освобождения.
Учел.
Не совсем понял, что ты имеешь ввиду

Я Instance.Free имею в виду
У тебя так:
Код: pascal
1.
2.
3.
4.
        Time := GetTickCount;
        Instance := TestClass.Create(Items, CAPACITIES[Mode]);
        Time := GetTickCount - Time;
        Instance.Free;



логичее было бы так
Код: pascal
1.
2.
3.
4.
        Time := GetTickCount;
        Instance := TestClass.Create(Items, CAPACITIES[Mode]);
        Instance.Free;
        Time := GetTickCount - Time;



SOFT FOR YOUAleksandr SharahovВ-третьих, чтобы использовать "поле в обжекте" достаточно умения работать с указателями.
Что-то я не понял. А к чему тогда поле Offset?


Offset - это смещение поля внутри объекта или записи. В нашем тесте запись состоит из одного единственного строкового поля. Offset=0.

SOFT FOR YOUТак ты RawByteString и UnicodeString похоже сравниваешь. Во втором в 2 раза больше байт
Разумеется, но у нас с тобой хеш-функции не блобы обрабатывают, а строки посимвольно, т.е. на них это не влияет, т.к. количество операций одинаково.
...
Рейтинг: 0 / 0
19.03.2017, 14:21:27
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422483
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr SharahovRandomize; Seed:=RandSeed;
Сначала надо Seed сохранять, потом рандомайзить )
Ну и потом здесь специально нет рандомайза, чтобы сохранить одинаковость данных

Ты бы разобрался сначала.

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

Ну, все в твоих руках, напиши женерик для Raw )

Я не забываю, я на этом как раз играю в своем словаре.
...
Рейтинг: 0 / 0
19.03.2017, 14:39:33
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422490
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
[quot Aleksandr Sharahov]SOFT FOR YOUНу, все в твоих руках, напиши женерик для Raw )
Я не забываю, я на этом как раз играю в своем словаре.
Так у меня есть и RawByteString, и DynamicArray, и структуры, и всё что хочешь :)
...
Рейтинг: 0 / 0
19.03.2017, 14:41:19
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422492
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
SOFT FOR YOUИ потом ты забываешь про компаратор и кеш-мисс
В твоих тестах строковый компарер не отрабатывает по данным.
...
Рейтинг: 0 / 0
19.03.2017, 14:44:28
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422493
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Kazantsev Alexey,

Отрабатывает
...
Рейтинг: 0 / 0
19.03.2017, 14:46:09
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422494
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
SOFT FOR YOU,

У тебя же там один массив под ключи. И когда ты ищешь все ключи, то фактически, у одинаковых строк сравниваются только адреса.
...
Рейтинг: 0 / 0
19.03.2017, 14:49:01
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422496
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Kazantsev AlexeySOFT FOR YOU,

У тебя же там один массив под ключи. И когда ты ищешь все ключи, то фактически, у одинаковых строк сравниваются только адреса.
Обижаешь :)
...
Рейтинг: 0 / 0
19.03.2017, 14:50:22
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422499
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
SOFT FOR YOUОбижаешь :)
Где я могу увидеть создание копий ключей?
...
Рейтинг: 0 / 0
19.03.2017, 14:54:01
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422500
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOU,

Замена string на RawByteString не добавила скорости твоему словарю:

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
TShaNamedObjectDictionary Add... 1342ms
TShaNamedObjectDictionary Add+Capacity... 1123ms
TShaNamedObjectDictionary Items... 983ms

RawByteString
TRunner<System.RawByteString>.SystemSystem Add... 4617ms
TRunner<System.RawByteString>.SystemSystem Add+Capacity... 2824ms
TRunner<System.RawByteString>.SystemSystem Items... 1326ms
TRunner<System.RawByteString>.SystemRapid Add... 4430ms
TRunner<System.RawByteString>.SystemRapid Add+Capacity... 2606ms
TRunner<System.RawByteString>.SystemRapid Items... 1107ms
TRunner<System.RawByteString>.RapidRapid Add... 1810ms
TRunner<System.RawByteString>.RapidRapid Add+Capacity... 1529ms
TRunner<System.RawByteString>.RapidRapid Items... 983ms
TRunner<System.RawByteString>.RapidDictionary Add... 1918ms
TRunner<System.RawByteString>.RapidDictionary Add+Capacity... 1607ms
TRunner<System.RawByteString>.RapidDictionary Items... 1060ms
...
Рейтинг: 0 / 0
19.03.2017, 14:56:55
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422502
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Виноват, *почти* не добавила
...
Рейтинг: 0 / 0
19.03.2017, 15:00:46
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422505
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Kazantsev AlexeySOFT FOR YOUОбижаешь :)
Где я могу увидеть создание копий ключей?
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function Test: Integer;
var
  Dictionary: TRapidDictionary<string,Integer>;
begin
  Dictionary := TRapidDictionary<string,Integer>.Create;
  try
    Dictionary.Add('1', 1);
    Result := Dictionary[IntToStr(1)];
  finally
    Dictionary.Free;
  end;
end;



Если бы сравнивались только указатели, то в данном случае был бы Exception
А посмотреть - только трейсить
...
Рейтинг: 0 / 0
19.03.2017, 15:06:48
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422506
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Aleksandr SharahovЗамена string на RawByteString не добавила скорости твоему словарю:
Любопытно, я посмотрю
А ты точно в Release сравниваешь?
...
Рейтинг: 0 / 0
19.03.2017, 15:07:44
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422508
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
SOFT FOR YOUAleksandr SharahovЗамена string на RawByteString не добавила скорости твоему словарю:
Любопытно, я посмотрю
А ты точно в Release сравниваешь?

На самом деле небольшое ускорение есть, но все равно моя чуточку быстрее, т.к. не хранит "лишних" данных.

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


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