Admin: 1 revision imported

2021-02-07T06:56:29Z

1 revision imported

Admin at 11:42, 8 August 2019

2019-08-08T11:42:06Z

New page

Данный пример сравнивает скорость работы функции Find для сортированного и не сортированного списков. Внутри цикла поиска также происходит увеличение массива с помощью функции Add для проверки корректности ее работы.
<pre>
ProfilerClear();
ProfilerStart();

randomize(1);
aList:=List.Create();
For i:=1 To 100000 Do
aList.Add(Random(10000));
EndDo;

aList.Sort();
For i:=1 To 10000 Do
j:=Random(aList.Size())+1;
aNum:=aList.Get(j);
While _And(j>1,aList.Get(j-1)=aNum) Do
j:=j-1;
EndDo;
j2:=aList.Find(aNum,,1);
If j<>j2 Then
Message("Проблема при поиске значения!","!");
EndIf;
//Добавление случайного значения внутри цикла поиска
aList.Add(Random(10000),,,1);
EndDo;

randomize(1);
aList:=List.Create();
For i:=1 To 100000 Do
aList.Add(Random(10000));
EndDo;

aList.Sort();
For i:=1 To 10000 Do
j:=Random(aList.Size())+1;
aNum:=aList.Get(j);
While _And(j>1,aList.Get(j-1)=aNum) Do
j:=j-1;
EndDo;
j2:=aList.Find(aNum);
If j<>j2 Then
Message("Проблема при поиске значения (2)!","!");
EndIf;
//Добавление случайного значения внутри цикла поиска, в данном примере нас интересует сравнительная скорость работы функции Add с сортировкой, поэтому
// этот блок не имеет большого значения, кроме как поддержание соответствия может циклами
//Дополнение: j2 не будет возвращать 0 для последовательности, инициированной randomize(1), в ином случае, возможно, потребуется дополнительная проверка
j:=Random(10000);
j2:=aList.Find(j,,1);
aList.Insert(j2,j);
EndDo;

ProfilerStop();
debugbreak;

Message("Done!");
//Для i5, конечные результаты для среднего времени исполнения каждой операции:
//aList.Sort(); -- 3 сек./1
//j2:=aList.Find(aNum,,1); -- 30.5 мс./10000
//aList.Add(Random(10000),,,1); -- 640 мс./10000
//j2:=aList.Find(aNum); -- 31733 мс./10000
//aList.Insert(j2,j); -- 690 мс./10000
//
//Как показывает эксперимент, для больших массивов поиск в сортированном массиве имеет очень большое преимущество перед поиском без учета сортировки (1000 раз в нашем случае),
// преимущество будет только расти при увеличении количества элементов в массиве
//Сортировка больших массивов работает достаточно медленно, поэтому, в циклах, где происходит одновременное добавление и поиск элементов списка, гораздо выгоднее использовать
// функцию добавления с сортировкой, нежели множественные вызовы сортировки перед поиском.
</pre>

← Older revision	Revision as of 06:56, 7 February 2021
(No difference)

Template:Пример поиск в сортированных списках - Revision history

Admin: 1 revision imported

Admin at 11:42, 8 August 2019