[ViKo 1]

В таблице не хватает процентного отношения (пре + пост) к сорт. Также время сортировки может зависеть от того, какие данные в массиве. Желательно усреднить множество сортировок.

"Кто-то" сравнивает линейный пробег по массиву с одним из проходов функции сортировки. Вот что соизмеримо. Понятно, сортировка 1000-элементного массива будет выполняться проходов за 10 (по фрагментам массива). Здесь вклад дополнительных внешних проходов будет невелик. А вот 10-элементный массив наглядно демонстрирует неоптимальность такого подхода.

[Gruffly 0]

1. По приведенной выше таблице - можно прикинуть проценты, если кто-то учился в детстве считать в уме.

2. Как я вижу, из постановки задачи, массив формируется из random-чисел и это есть наиболее общая постановка задачи.

Рассматривать особые частные случаи - интересно, но в оговоренных случаях.

3. При рандом-массиве, размерностью свыше нескольких десятков, тем более сотен - QuickSort отработает предсказуемо.

4. При размерности 4..10 - есс-но могут быть реализованы крайне эффективные варианты решения Задачи, да хоть на тех же if..else.

 

[@Ark 3]

Делаем точные замеры ( на PC, Win7, Delphi 7, размерность времени в мкс)...

Объясните, пожалуйста, как сочетаются понятия WIN7 (явно, не real-time) и "точные замеры времени в мкс"?

 

 

 

[Gruffly 0]

Объясните, пожалуйста, как сочетаются понятия WIN7 (явно, не real-time) и "точные замеры времени в мкс"?

 

Учить, до посинения, такие вещи, как:

 

GetThreadPriority(GetCurrentThread );
GetSystemTimeAdjustment(Ad, Int, Q);
QueryPerformanceCounter( i1 );
QueryPerformanceFrequency( i1 );


// System slice, [100*ns]
// 156001 == 15.6001 ms
function GetAccuracy_: Cardinal;
var  Ad, Int: Cardinal;
     Q: LongBool;
begin
  GetSystemTimeAdjustment(Ad, Int, Q);
  Result:= Int;
end;

// CPU frequency, [MHz]
function GetCPUFreq_: extended;
var
    i1,i2,t:int64;
    pr:dword;
begin
    pr := GetThreadPriority(GetCurrentThread );
    SetThreadPriority(GetCurrentThread,THREAD_PRIORITY_TIME_CRITICAL);
    QueryPerformanceCounter( i1 );
    t := GetCPUTicks_;
    Sleep(SleepTime);
    asm
      dw 310Fh // rdtsc
      sub eax, dword[t]
      sbb edx, dword[t+4]
      mov dword[t], eax
      mov dword[t+4], edx
    end;
    QueryPerformanceCounter( i2 );
    i2 := i2-i1;
    QueryPerformanceFrequency( i1 );
    Result := i2*1000000 div i1;
    Result := t/(Result);
    CPUFreq := Result;
    SetThreadPriority(GetCurrentThread,pr);
end;

procedure SetRealTime_;
var
   ProcessID : DWORD;
   ProcessHandle : THandle;
   ThreadHandle : THandle;
begin
  ProcessID := GetCurrentProcessID;
  ProcessHandle := OpenProcess(PROCESS_SET_INFORMATION,
        false,ProcessID);
  SetPriorityClass(ProcessHandle, REALTIME_PRIORITY_CLASS);
  ThreadHandle := GetCurrentThread;
  SetThreadPriority(ThreadHandle, THREAD_PRIORITY_TIME_CRITICAL);
end;

procedure SetNormalTime_;
var
   ProcessID : DWORD;
   ProcessHandle : THandle;
   ThreadHandle : THandle;
begin
  ProcessID := GetCurrentProcessID;
  ProcessHandle := OpenProcess(PROCESS_SET_INFORMATION,
        false,ProcessID);
  SetPriorityClass(ProcessHandle, NORMAL_PRIORITY_CLASS);
  ThreadHandle := GetCurrentThread;
  SetThreadPriority(ThreadHandle, THREAD_PRIORITY_NORMAL);
end;

[@Ark 3]

Учить, до посинения ...

Спасибо. А Вы не могли бы, кратко, своими словами, объяснить суть? :)

 

 

[Gruffly 0]

Спасибо. А Вы не могли бы, кратко, своими словами, объяснить суть? :)

Что, именно?

 

Win-система позволяет управлять собой вплоть до кольца 0 (ring 0).

Любой поток(и) можно возвысить до статуса реал-тайм для выполнения некоторых time-замеров и вернуть его обратно, в normal-time.

Есть очень много тонкостей по замеру времени исполнения той или иной программы, того или иного участка ее.

Объяснить двумя словами - нереально.

Однако, начиная с WinNT - Windows может считаться реал-тайм системой, более того, есть специальные релизы ее.

Важно другое - что мы понимаем под реал-тайм?

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

Где-то ранее, я приводил реализацию большого проекта на WinNT - супервизорное управление технологическим оборудованием + управление электро-приводом.

Реализовано, более того - продано китайцам :)

Изменено 7 апреля, 2017 пользователем Gruffly

[Eddy_Em 2]

Какой поток бреда!..

[blackfin 32]

Какой поток бреда!..

Обычная в наших краях дуэль джентльменов на пенисах!

[Gruffly 0]

Какой поток бреда!..

Не спеши причислять себя к горным баранам, в горах их и без тебя хватает :)

Using Windows NT for Real-Time Applications (Mitsubishi Electric Research Labs)

TR98_02.pdf

 

 

[@Ark 3]

Using Windows NT for Real-Time Applications (Mitsubishi Electric Research Labs)

TR98_02.pdf

Почитал. Может, что-то не так понял, но там говорится о временах порядка миллисекунд.

Вы выложили измерения в микросекундах... :rolleyes:

 

[Eddy_Em 2]

Даже из линукса при помощи rt- патча полноценной ртоси не получится! Что уж о пускалке игр говорить?

[Gruffly 0]

Почитал. Может, что-то не так понял, но там говорится о временах порядка миллисекунд.

Вы выложили измерения в микросекундах... :rolleyes:

 

Теперь по порядку:

 

Методы измерения времени на платформе Windows имеют свою историческую подоплеку:

 

1. timeGetTime() - возвращает время в ms, прошедшее с момента старта OS. Работает от мультимедийного таймера. Точность 1..5 ms.

2. GetTickCount() - возвращает время в ms, прошедшее с момента старта OS. Работает от того же таймера, но точность ниже (10..55 ms), т.к. срабатывает по прерываниям часов реального времени.

3. RDTS - чи­та­ет из про­цес­сор­но­го счёт­чи­ка чис­ло так­тов, про­шед­шее с мо­мен­та за­пус­ка про­цес­со­ра. Са­мый точ­ный счёт­чик из до­ступ­ных.

При частоте CPU = 3 GHz длительность тика составляет 1/3 = 0.33 нс.

Есть проблемы на современных платформах, связанные с изменением частоты процессора, переключением задачи между CPU в многопроцессорных и многоядерных случаях.

Проблемы не принципиальные, просто надо учитывать особенности применения rdts.

4. QueryPerformance­Counter() - «тай­мер вы­со­ко­го раз­ре­ше­ния».

Вве­дён фир­мой Microsoft, что­бы раз и на­все­гда по­ста­вить точ­ку в про­бле­мах из­ме­ре­ния вре­ме­ни.

Ча­сто­та это­го тай­ме­ра ( ~ 3 МГц и вы­ше) и не ме­ня­ет­ся во вре­мя ра­бо­ты си­сте­мы. Запрос частоты QueryPerfomanceFrequency().

Очевидно, что длительность тика составляет 1/3 = 0.33 мкс.

 

Методы превращения платформы Windows в реал-тайм OS (того или иного типа) тоже имеют свою историческую подоплеку:

1. Впервые это стало возможным после появления WinNT 3.1

2. Win2000 Advanced Server вполне претендовал на эту роль и использовался ( в т.ч. мной) для создания "мягких" реал-тайм приложений.

3. Были выпущены расширения для WinNT платформ.

Их много, наиболее известная - RTX от фирмы VenturCom (затем Ardence, затем куплена Citrix), сейчас подразделение Citrix выделилось в отдельную фирму IntervalZero Inc.

4. Microsoft всегда следила на требованиями embebbed-рынка.

Список специальных релизов реал-тайм Windows достаточно большой:

 

Windows 7 Professional for Embedded Systems and Windows 7 Ultimate for Embedded Systems

Windows Embedded POSReady 7

Windows Server 2008 R2 for Embedded Systems

Windows Embedded POSReady 2009

Windows Server 2012 R2 for Embedded Systems

System Center 2012 SP1

Windows Embedded Compact 2013

Windows Embedded 8.1 Industry

и более ранние + для мобильных девайсов.

 

Есть такое понятие, как время System-slice (SST). Это время переключения задач на той или иной платформе в многозадачных OS.

Для обычных реализаций Windows, значение SST составляет от 10 до 20 ms, для embedded - 1 ms, для расширений - менее 1 ms.

Именно это, в первую очередь, ограничивает диапазон применения любой многозадачной OS.

К измерениям времени на платформе имеет опосредованное отношение.

 

P.S.

Надеюсь, что ответил на вопросы.

Изменено 8 апреля, 2017 пользователем Gruffly

[@Ark 3]

Надеюсь, что ответил на вопросы.

Да. Спасибо за информацию.

 

[Eddy_Em 2]

Как вообще можно говно мастдайное как операционную систему рассматривать? Она же только для игрулек годится! И создавалась изначально как пускалка игр!!!

[Gruffly 0]

Как вообще можно говно мастдайное как операционную систему рассматривать? Она же только для игрулек годится! И создавалась изначально как пускалка игр!!!

В горы вернись - там телескопы, звезды, инопланетяне и незамутненное сознание.