Уничтожение значений-объектов массива TMap из FCL-STL

[zub]

>>И совсем уж чистейший эксперимент. Поскольку вы малость извратили вторым for'ом, подсчитывающим сумму, всю суть ассоциированных массивов, я тоже изменил второй цикл в декаловском примере:
Стоп. я 10000000 раз ищу элемент по его имени, и суммирую результат. Дайте эталонный код делающий также, а не тупо пробегающий все элементы по порядку.

[java73]

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

дал в конце же

[zub]

Скопипастите код целиком, зачем мне собирать из кусков - нето ченить соберу

[java73]

Код: Выделить всё

program hashmaptest;

uses
  decal,
  SysUtils;

const
  elemcount = 10000000;

type
  TMyMapElement = class
    Value: integer;
  end;

  function GetName(Value: integer): string;
  begin
    Result := format('MapElementKey %10d', [Value]);
  end;

  function TMapElement_Create(_value: integer): TMyMapElement;
  var
    me: TMyMapElement;
  begin
    me := TMyMapElement.Create;
    me.Value := _value;
    exit(me);
  end;

var
  m: DMap;
  ts: string;
  i: integer;
  sum: integer;
  myTime: TDateTime;

begin
  m := DMap.Create;

  myTime := now;
  for i := 1 to elemcount do
    m.PutPair([GetName(i), TMapElement_Create(i)]);
  str((now - myTime) * 10e4: 2: 3, ts);
  writeln('Insert    ' + ts + 'sec.');

  sum := 0;
  myTime := now;
  for i := 1 to elemcount do
    Sum := Sum + TMyMapElement(getObject(m.locate([GetName(i)]))).Value;
  str((now - myTime) * 10e4: 2: 3, ts);
  writeln('Calculate ' + ts + 'sec.');
  writeln('Sum=', sum);

  myTime := now;
  ObjFree(m);
  m.Free;
  str((now - myTime) * 10e4: 2: 3, ts);
  writeln('Destroy   ' + ts + 'sec.');
  readln;
end.\0

[zub]

10e6 элементов

E:\zcad\other\maptests>E:\zcad\other\maptests\dmaptest.exe
Insert 3.183sec.
Calculate 2.206sec.
Sum=1784293664
Destroy 0.138sec.


E:\zcad\other\maptests>E:\zcad\other\maptests\hashmaptest.exe
Insert 7.731sec.
Calculate 6.900sec.
Sum=1784293664
Destroy 0.141sec.


E:\zcad\other\maptests>E:\zcad\other\maptests\maptest.exe
Insert 6.793sec.
Calculate 4.484sec.
Sum=1784293664
Destroy 0.094sec.

10е7 элементов

E:\zcad\other\maptests>E:\zcad\other\maptests\dmaptest.exe
Insert 36.258sec.
Calculate 24.766sec.
Sum=-2004260032
Destroy 1.380sec.


E:\zcad\other\maptests>E:\zcad\other\maptests\hashmaptest.exe
Insert 51.589sec.
Calculate 23.117sec.
Sum=-2004260032
Destroy 1.918sec.


E:\zcad\other\maptests>E:\zcad\other\maptests\maptest.exe
Insert 78.976sec.
Calculate 51.696sec.
Sum=-2004260032
Destroy 0.937sec.

чета тут нетак

[java73]

НЛО не может объяснить, видимо в hasmap используется что-то, чего у меня в компьютере нет))) У меня hashmap медленнее всех исполняется

Добавлено спустя 1 минуту 5 секунд:
Но хотя бы с dmap всё правильно)))

Добавлено спустя 37 минут 54 секунды:
Кстати, у decal тоже есть хэшмапы, завтра надо затестить

[zub]

Пока склонен списать всё на какието чудеса с стрингами. если ключик поменять на интежер - все становится на свои места

Код: Выделить всё

E:\zcad\other\maptests>E:\zcad\other\maptests\maptest.exe
Insert    4.918sec.
Calculate 1.432sec.
Sum=-2004260032
Destroy   0.435sec.


E:\zcad\other\maptests>E:\zcad\other\maptests\dmaptest.exe
Insert    17.700sec.
Calculate 10.751sec.
Sum=-2004260032
Destroy   0.981sec.

Слив в разы - как оно и должно быть

[serbod]

Вот вам еще один вариант, совместимый со старыми дельфями.

Код: Выделить всё

program stringhashtest;
uses
  IniFiles, SysUtils;
const
  elemcount=10000000;
type
TMyMapElement = record
  Value:integer;
end;

function GetName(value:integer):string;
begin
  result:=format('MapElementKey %10d',[value]);
end;

var
  arr: array of TMyMapElement;
  m:TStringHash;
  s,ts:string;
  i, n:integer;
  sum:integer;
  myTime:TDateTime;
  mapelement:TMyMapElement;
begin
  SetLength(arr, elemcount);
  m:=TStringHash.Create(8192);

  myTime:=now;
  for i:=1 to elemcount do
  begin
    arr[i-1].Value:=i;
    m.Add(GetName(i), i-1);
  end;
  str((now-myTime)*10e4:2:3,ts);
  writeln('Insert    '+ts+'sec.');

  sum:=0;
  myTime:=now;
  for i:=1 to elemcount do
  begin
    n:=m.ValueOf(GetName(i));
    if n >= 0 then sum:=sum+arr[n].Value;
  end;
  str((now-myTime)*10e4:2:3,ts);
  writeln('Calculate '+ts+'sec.');
  writeln('Sum=',sum);

  myTime:=now;
  m.Free;
  str((now-myTime)*10e4:2:3,ts);
  writeln('Destroy   '+ts+'sec.');
  readln;
end.

Результаты такие:

Код: Выделить всё

>maptest.exe
Insert    322.383sec.
Calculate 212.369sec.
Sum=-2004260032
Destroy   4.352sec.


>hashmaptest.exe
Insert    66.409sec.
Calculate 63.898sec.
Sum=-2004260032
Destroy   6.229sec.


>stringhashtest.exe
Insert    68.647sec.
Calculate 64.910sec.
Sum=-2004260032
Destroy   6.464sec.

[zub]

и еще вариант, совместимый с новыми делфями.

Код: Выделить всё

program genericscollections;
{$IFDEF FPC}{$MODE DELPHI}{$ENDIF}
{$APPTYPE CONSOLE}
uses
  generics.collections,
  sysutils;

const
  elemcount=10000000;
type
TMyMapElement = record
  Value:integer;
end;
TMyMap = TDictionary<string, TMyMapElement>;


function GetName(value:integer):string;
begin
  result:=format('MapElementKey %10d',[value]);
end;

function TMapElement_Create(_value:integer):TMyMapElement;
begin
  result.Value:=_value;
end;
var
  m:TMyMap;
  s,ts:string;
  i:integer;
  sum:integer;
  myTime:TDateTime;
  mapelement:TMyMapElement;
begin
  m:=TMyMap.Create;

  myTime:=now;
  for i:=1 to elemcount do
  m.Add(GetName(i),TMapElement_Create(i));
  str((now-myTime)*10e4:2:3,ts);
  writeln('Insert    '+ts+'sec.');

  sum:=0;
  myTime:=now;
  for i:=1 to elemcount do
  sum:=sum+m.Items[GetName(i)].Value;
  str((now-myTime)*10e4:2:3,ts);
  writeln('Calculate '+ts+'sec.');
  writeln('Sum=',sum);

  myTime:=now;
  m.Destroy;
  str((now-myTime)*10e4:2:3,ts);
  writeln('Destroy   '+ts+'sec.');
  readln;
end.

результаты fpc

E:zcadothermaptests>E:zcadothermaptestsgenericscollections.exe
Insert 16.524sec.
Calculate 10.192sec.
Sum=-2004260032
Destroy 2.226sec.

результаты delphi xe

E:zcadothermaptestsdelphiDebugWin32>E:zcadothermaptestsdelphiDebugWin32genericscollections.exe
Insert 6.402sec.
Calculate 4.439sec.
Sum=-2004260032
Destroy 2.221sec.

Добавлено спустя 6 минут 9 секунд:
И вот настоящее чудо - победа над XE если уйти от стринга в качестве ключа в сторону интегер:

E:\zcad\other\maptests>E:\zcad\other\maptests\genericscollections.exe
Insert 1.892sec.
Calculate 1.148sec.
Sum=-2004260032
Destroy 0.160sec.


E:\zcad\other\maptests\delphi\Debug\Win32>E:\zcad\other\maptests\delphi\Debug\Win32\genericscollections.exe
Insert 2.326sec.
Calculate 1.563sec.
Sum=-2004260032
Destroy 0.164sec.

[java73]

Блин, в ассоциированных массивах в том и смысл, что ключ не целое число! Если есть целое число, зачем извращаться с другими структурами данных вместо стандартного массива?

[zub]

Ошибаешся. Стринги какраз очень частный случай - а ключики наподобии интегер обычное дело - например THandle

>>Если есть целое число, зачем извращаться с другими структурами данных вместо стандартного массива?
это только в моем тесте от нуля до elemcount подряд, в жизни совсем нетак

[java73]

Проектируя структуру программы, модуля, их логику, входные и выходные данные нужно учитывать не только один аспект, но и другие, и делать выбор в пользу того, преимущество которого в данных условиях важнее преимуществ других. В моем конкретном случае построчно прочитать любой html файл, в котором в самом диком, нереальном случае может быть максимум тысяча строк, считать все нужные тэги в массив, чтобы потом вернуть обратно в файл, заменив нужными значениями, выбор пал на то, что приятнее читается и легче кодится. Скорость работы мне в этих условиях совершенно не нужна.
Да и в любом случае, я остановился на варианте с Tmap из fcl, так что совершенно не понимаю, что тут вообще происходит)

Добавлено спустя 4 минуты 54 секунды:
Выбранный вами тест крайне непоказателен для алгоритмов записи и чтения из структур, работающих на r/b деревьях или хэш функциях. У вас значения и ключи генерятся по возрастающей, поэтому сымитировать реальные условия не получится, а в них массив наполняется никак не связанными друг с другом парами.

[zub]

Поздравляю, ты сделал правильный выбор! Сравнили разные реализации мапов. тебе от этого хуже?

Добавлено спустя 5 минут 39 секунд:
Я не претендую на суперпоказательность и время наполнения мапа - далеко не главный показатель, а вот поиск в мапе - очень важен и ему нет разницы в каком порядке искать. Такчто то что мне интересно - я посмотрел, увидел безполезность для меня thashmap (покрайней мере в реализации fcl-stl) и возможный повод для багрепорта про тормознутость tmap с ключем стрингом

[vitaly_l]

увидел безполезность для меня thashmap

Попробуй вот с таким MakeHash протестировать.

Код: Выделить всё

function MakeHash(const s:AnsiString):SizeUInt;  
var
  thehash,g,I : LongWord;
begin
   thehash:=0;
   for I:=1 to Length(S) do begin
     thehash:=thehash shl 4;
     inc(theHash,Ord(S[i]));
     g:=thehash and LongWord($f shl 28);
     if g<>0 then begin
       thehash:=thehash xor (g shr 24);
       thehash:=thehash xor g;
     end;
   end;
   if theHash=0
      then MakeHash:=$ffffffff
      else MakeHash:=TheHash;
end; 

Интересно что покажет тест?

.

[zub]

10e6

E:zcadothermaptests>E:zcadothermaptestshashmaptest.exe
Insert 2.023sec.
Calculate 1.407sec.
Sum=1784293664
Destroy 0.119sec.

10e7

E:zcadothermaptests>E:zcadothermaptestshashmaptest.exe
Insert 24.229sec.
Calculate 13.955sec.
Sum=-2004260032
Destroy 1.465sec.

Наши победили?

Плачевные результаты TMap судя по всему из-за особенностей его сравнения - он использует компоратор возвращающий boolean (т.е. либо больше либо меньше) dmap использует CompareStr и за одно сравнение понимает что больше-меньше-равно, TMap`у для этого приходится проводить 2 сравнения, цитата из fcl-stl про двоичный поиск:

Код: Выделить всё

function TSet.NFind(value:T):PNode;inline;
var x:PNode;
begin
  x:=FBase;
  while(x <> nil) do begin
    if(TCompare.c(value,x^.Data)) then x:=x^.Left
    else if(TCompare.c(x^.Data,value)) then x:=x^.Right
    else begin
      exit(x);
    end;
  end;
  exit(nil);
end;

такчто тмап не подойдет там где сравнение относительно дорого

Добавлено спустя 6 часов 12 минут 3 секунды:
Лучший результат для THashMap у меня получился используя DelphiHashLittle из Generics.Hashes
10e6

E:zcadothermaptests>E:zcadothermaptestshashmaptest.exe
Insert 1.671sec.
Calculate 1.150sec.
Sum=1784293664
Destroy 0.272sec.

10e7

E:zcadothermaptests>E:zcadothermaptestshashmaptest.exe
E:zcadothermaptests>E:zcadothermaptestshashmaptest.exe
Insert 20.184sec.
Calculate 11.944sec.
Sum=-2004260032
Destroy 3.925sec.

Добавлено спустя 10 минут 13 секунд:
Вариант от serbod хоть и имхо академической ценности не имеет - приведу его циферки на моем компе
10е6

E:zcadothermaptests>E:zcadothermaptestsstringhashtest.exe
Insert 1.207sec.
Calculate 1.111sec.
Sum=1784293664
Destroy 0.212sec.

10е7

E:zcadothermaptests>E:zcadothermaptestsstringhashtest.exe
Insert 34.054sec.
Calculate 33.617sec.
Sum=-2004260032
Destroy 2.141sec.

Добавлено спустя 16 минут 28 секунд:
java73
давай реализацию с хэшем, сделаю подробный тест для 10,100,1000,10000,100000,1000000,10000000 ключей