Реализация медианного фильтра на QLUA

Введение

Мне всегда не нравился QUIK тем, что в нем нельзя было писать собственные индикаторы, если быть точнее, можно, но результаты реализация индикатора вряд ли бы отвечала заявленным требованиям, так как скрипты на qpile запускаются по таймеру, а не по событию. Я не считаю язык qpile ущербным или не пригодным для реализации, по мнению некоторых робостроителей, сложных алгоритмов. Всякий алгоритм можно реализовать на любом языке программирования, вопрос только в уровне затрат на реализацию, наличие или отсутствие нужных функций и процедур.
С появлением в QUIK QLUA все заиграло для меня яркими красками.
В заметке хочу рассмотреть вопросы реализации медианного фильтра на QLUA.

Постановка задачи

Медианный фильтр используются для уменьшения уровня шума. Алгоритм рассчета фильтра достаточно прост и доступен широким массам. Одним из пунктов рассчета медианы — является сортировка подмассива. Вот на этом и остановимся подробнее.

 Сортировка массива

Что такого сложного в сортировке на первый взгляд? Алгоритмов сортировки великое множество, их эффективность оценивается по быстродействию. Рассмотрим несколько алгоритмов сортировки и попытаемся их сравнить. Здесь не будем рассматривать вопросы создания индикаторов на qlua, только сортировка и больше ничего.

  Встроенный алгоритм сортировки

Рассмотрим первый вариант расчета медианного фильтра:
Settings=
{
  Name = "_Median",
  period = 12,
  line =
  { {
   Name = «Median»,
   Color = RGB(255, 0, 0),
   Type = TYPE_LINE, Width = 2 } } }
function Init()
 return 1
end
function OnCalculate(index)
  if index < Settings.period then
    return nil
  else
    local ind = 1
    local cash = {}
    for i = index-Settings.period+1, index do
         cash[ind] = C(i)
         ind = ind + 1
   end
   table.sort(cash)
   return cash[math.floor(Settings.period/2)]
 end
end

 Здесь сортировка выполняется стандартной процедурой table.sort , один из её недостатков — не устойчивая сортировка (меняет местами элементы массива с одинаковыми значениями)

Сортировка «пузырьком»

Изменим предыдущий пример, заменив table.sort(cash) на следующий набор команд:
local tmp = 0
for i = 1, Settings.period-1 do
  for j = 1, Settings.period-1 do
    if cash[j] > cash[j+1] then
        tmp = cash[j]
        cash[j] = cash[j+1]
        cash[j+1] = tmp
     end
 end
end
 
Данный метод не особо «шустрый», но ничего страшного, нам он нужен для сравнения

Быстрая сортировка

Один из популярных алгоритмов сортировки массивов, приведем весь код индикатора:
Settings=
{
   Name = "_Median2",
   period = 12,
   line =
      { {
      Name = «Median2»,
      Color = RGB(255, 0, 0),
      Type = TYPE_LINE, Width = 2 } } }
function Init()
   return 1
end
function asort(ar1, low, high)
   local wsp = 0
   local i=low
   local j=high
   local m=ar1[math.floor((i+j) / 2)] — Взятие среднего опорного элемента
   repeat
      while ar1[i]<m do
         i = i + 1 — изменить порядок сортировки можно
      end
      while ar1[j]>m do
         j = j — 1 — поменяв >< в этих двух строках
      end
      if i<=j then
         wsp=ar1[i]
         ar1[i]=ar1[j]
         ar1[j]=wsp
         i = i + 1
         j = j — 1
      end;
   until i>j
   if low<j then
      ar1 = asort(ar1, low, j)
   end
   if i<high then
      ar1 = asort(ar1, i, high)
   end
   return ar1
end

function qSort(ar)
   return asort(ar, 1, Settings.period)
end
function OnCalculate(index)
   if index < Settings.period then
      return nil
   else
      local ind = 1
      local cash = {}
      for i = index-Settings.period+1, index do
      cash[ind] = C(i)
      ind = ind + 1
   end
   cash = qSort(cash)
  return cash[math.floor(Settings.period/2)]
end
end
 Здесь метод быстрой сортировки реализован на основе рекурсии

Авторский метод сортировки

Не скромно, но похожей реализации медианного фильтра не встречал. У всех рассмотренных методов сортировки один общий недостаток: при появлении нового значения цены все алгоритмы берут последние N отсчетов цены (N — параметр фильтрации) и сортируют их, то есть на каждом шаге выполняется сортировка массива данных, при этом на предыдущем отсчете N-1 значений уже были отсортированы.
Суть предлагаемого метода:
1) при появлении нового тика сразу сортируем массив и запоминаем его
2) при появлении следующего тика
  2.1) удалим N+1 отсчет (считая новый тик отсчетом номер один) в отсортированном массиве
  2.2) добавим к отсортированному массиву новый тик
  2.3) сортируем получившийся массив, для сортировки достаточно осуществить один проход, например, {1, 2, 5, 6, 4}, здесь {1, 2, 5, 6} часть массива, которая была отсортирована на предыдущем тике, добавили новый элемент {6} — нужен один проход, чтобы отсортировать исходный массив.
Код:

Settings=
{
    Name = "_Median3",
    period = 12,
    line =
        { {
        Name = «Median3»,
        Color = RGB(255, 0, 0),
        Type = TYPE_LINE, Width = 2 } } }
function Init()
    m_cach = {}
    m_index = {}
    last_ind = 0
    return 1
end
function qSort1(arr,arr_ind)
    if #arr > 1 then
        local ind = #arr
        local tmp = 0
        local tmp_i = 0
        local cycle = false
        repeat
        if (ind > 1) then
            if (arr[ind] < arr[ind-1]) then
                tmp = arr[ind-1]
                tmp_i = arr_ind[ind-1]
                arr[ind-1] = arr[ind]
                arr_ind[ind-1] = arr_ind[ind]
                arr[ind] = tmp
                arr_ind[ind] = tmp_i
                ind = ind — 1
            else
                cycle = true
            end
        else
            cycle = true
        end
    until cycle
    end
    return arr, arr_ind
end
function min_arr (_arr)
    local min_index = _arr[1]
    local min_i = 1
    for i = 2,#_arr do
        if min_index > _arr[i] then
            min_index = _arr[i]
            min_i = i
        end
    end
    return min_i
end
function find_index (_arr,index1)
    local ind = 1
    while _arr[ind]~=index1 do
        ind = ind +1
    end
    return ind
end
function OnCalculate(index)
    if index <= Settings.period then
        if index == 1 then
            m_cach = {}
            m_index = {}
            last_ind = 0
        end
        table.insert(m_cach,C(index))
        table.insert(m_index,index)
        m_cach, m_index = qSort1(m_cach,m_index)
        last_ind = index
        return nil
    else
        if (last_ind == index) then
            local ind = find_index(m_index,index)
            table.remove(m_cach,ind)
            table.remove(m_index,ind)
        else
            local min_index = min_arr(m_index)
            table.remove(m_cach,min_index)
            table.remove(m_index,min_index)
        end
        table.insert(m_cach,C(index))
        table.insert(m_index,index)
        m_cach,m_index = qSort1(m_cach,m_index)
        last_ind = index
        return m_cach[math.floor(Settings.period/2)]
    end
end

Результаты

 Для сравнения медианных фильтров, использующих разные алгоритмы сортировки используем тиковый график цен на акции Сбербанка на 04.03.2014  с окном фильтрации в 200 тиков:

• встроенный алгоритм сортировки — 35 сек
• сортировка пузырьком — 485 сек
• быстрая сортировка — 39 сек
• авторская сортировка — 7 сек

 
Медиана с сортировкой пузырьком показала худшее время — все очевидно, время сортировки пропорционально квадрату n (n — размерность массива), быстрая сортировка — хорошо, но реализован на рекурсии, что кушает ресурсы + многократное копирование массива в памяти… Преимущество авторской сортировки очевидны — сортировка заточена под предметную область.

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