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

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

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 раз в нашем случае), 
//  преимущество будет только расти при увеличении количества элементов в массиве
//Сортировка больших массивов работает достаточно медленно, поэтому, в циклах, где происходит одновременное добавление и поиск элементов списка, гораздо выгоднее использовать
//  функцию добавления с сортировкой, нежели множественные вызовы сортировки перед поиском.