Библиотеки: Быстрая сортировка. - страница 2

Новый комментарий
 
Источник несортированных тиков?
 
fxsaber #:
Источник несортированных тиков?

 "Открытие", фортс, склейка сишки. Счёт реальный, не демо.

Хотел сюда же скинуть файл с тиками, но он 1.2 гига весит.


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

 
amrali #:

Hello,

The ticks array is already sorted. So, using either insertion sort, bubble sort or gnome sort (actually, a variation of insertion sort) will be the fastest.

But, for example if 10 ticks are out of order, they will take ages because these algorithms has O(n^2) running time. So, they have limited practical use, except for sorting small arrays < 10-20 elements.

I prefer to randomize (shuffle) the ticks array before sorting, then sort using QuickSort, Introspective sort, modified RadixSort.

The adaptive property (being fast with nearly sorted arrays) of these sort algorithms depends on the position of the out-of-order items. 

If you put at the end of array, speed is ok. Try to put them at the beginning, then check the difference.

Replace this old code:

      Print("Shuffling ticks array before sorting..");
      ArrayShuffle(ticksArr);
      Write(ticksArr, "Shuffled");

With this newer code:

      Print("swapping 10 ticks before sorting..");
      for(int i = 0; i < 10; i++)
         Swap(ticksArr[i], ticksArr[result-10+i]);
      Write(ticksArr, "Shuffled");

//...
//...

//+------------------------------------------------------------------+
template<typename T>
void Swap(T& a, T& b)
  {
   T temp = a;
   a = b;
   b = temp;
  }
 
Aleksandr Slavskii #:

 "Открытие", фортс, склейка сишки. Счёт реальный, не демо.

Хотел сюда же скинуть файл с тиками, но он 1.2 гига весит.


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

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

 
amrali #:

The adaptive property (being fast with nearly sorted arrays) of these sort algorithms depends on the position of the out-of-order items. 

If you put at the end of array, speed is ok. Try to put them at the beginning, then check the difference.

Replace this old code:

With this newer code:

swapping 10 ticks before sorting..
Sorting 27226171 integers: 
QuickSort() -> 2656 millisec
Introsort() -> 1813 millisec
RadixSort() -> 3546 millisec
GnomeSort() -> 7297 millisec
End of testing

Ну если поменять условие задачи, то да, RadixSort быстрее GnomeSort. Остальных я не рассматриваю, так как они опять всё напутали.

Но вы уходите от практики в теорию.

Я тестировал задачу, которую видел, а вы предлагаете изменить условие задачи на гипотетическое.



 
fxsaber #:

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

Берём обычные тики и делаем их не сортированными.  Просто часть сдвигаем ниже по времени.

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

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

Начал разбираться, выяснилось, что тики должны быть сортированы по времени, скачал тики CopyTicksRange() за последний день, распечатал , а у них в начале всё ок, потом с десяток тиков передвинуты на несколько миллисекунд ниже. Поставил сортировщик, всё заработало.

К вечеру вся эта история тиков скачивалась уже нормально, видимо на сервере их исправили и отсортировали.

 
Aleksandr Slavskii #:

Берём обычные тики и делаем их не сортированными.

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

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

Начал разбираться, выяснилось, что тики должны быть сортированы по времени, скачал тики CopyTicksRange() за последний день, а у них в начале всё ок, потом с десяток тиков передвинуты на несколько миллисекунд ниже. Поставил сортировщик, всё заработало.

К вечеру вся эта история тиков скачивалась уже нормально, видимо на сервере их исправили и отсортировали.

тут всех может уделать обычный "пузырёк", если добавить критерий "массив отсортирован".  Когда исходных нарушений порядка - иногда несколько тиков меняются местами, тогда можно придумать и добавить условие завершения сортировки и его O(N^2) превратится в O(N).

 
Maxim Kuznetsov #:

тут всех может уделать обычный "пузырёк", если добавить критерий "массив отсортирован".  Когда исходных нарушений порядка - иногда несколько тиков меняются местами, тогда можно придумать и добавить условие завершения сортировки и его O(N^2) превратится в O(N).

Совершенно верно!!! 

Ситуация которую предложил рассмотреть  amrali  https://www.mql5.com/ru/forum/383413/page2#comment_44818051  маловероятна, практически не возможна.

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

 

Ok, I understood your problem, you have a problem with stability of the sort.

A Stable Sort is one which preserves the original order of input set, where the comparison algorithm does not distinguish between two or more items. A Stable Sort will guarantee that the original order of data having the same rank is preserved in the output.  Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort and Radix Sort. And some sorting algorithms are not, like Heap Sort, Quick Sort, Introspective Sort, etc.


I suggest you sort the ticks using Merge Sort. I have uploaded a high-optimized hybrid Merge sort with Insertion sort.

Note: even for an almost sorted array, you cannot be 100% sure where the location of the out-of-order ticks will be, and this will harm the insertion, gnome and bubble sort. They will be O(N) if the out-of-order ticks are at the end of array. They become O(N^2) if out-of-order ticks are at the front of array (i.e., a high number of inversions). So, Merge sort in your case will be a more reliable sort (predicted worst running time), that is stable (preserves the original order) also adaptive (more speed for nearly sorted arrays).

swapping 10 ticks before sorting..
Sorting 8645149 ticks: 
QuickSort() -> 468 millisec
Introsort() -> 282 millisec
RadixSort() -> 625 millisec
MergeSort() -> 703 millisec

Edit:

theoretically speaking, the running time for insertion, gnome and bubble is O(N + I) for nearly sorted arrays. Where I, is the count of inversions (how far the ranks of items are away from their sorted order). If I as in your case is supposed to be low (i.e., the ticks are slightly shifted), then these simple sorts are the fastest.

Файлы:
sort_ticks_array_v2.mq5  12 kb
MergeSort.mqh  4 kb
 
Aleksandr Slavskii #:

Совершенно верно!!! 

Ситуация которую предложил рассмотреть  amrali  https://www.mql5.com/ru/forum/383413/page2#comment_44818051  маловероятна, практически не возможна.

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

физика образования подобных коллизий (тики поменялись местами) - тики собираются параллельными процессами и выкладываются в общий вывод. Иногда  отдельный процесс может поотстать, или какие-нибудь программные кеши запутались. То есть массив "почти" сортирован - каждый тик недалеко от того места где он должен быть, на пару тройку позиций обогнал или поотстал.

можно решить не универсальной сортировкой всего массива (а-ля qsort) - а фиксированная очередь с приоритетами. глубина очереди = максимальная дистанция перепутывания. Сначала ты заполняешь очередь, как заполнилась - очередной тик в неё помещаешь, а наименьший забираешь. В конце выводишь очередь

За один проход ты приведёшь весь массив в порядок 

123
Новый комментарий
Причина обращения: