Глобальные массивы: технология поиска

Прежде всего код функции SearchItem() начинается с того, что мы локируем критическую секцию, чтобы обеспечить монопольный доступ к данным массива:

   // Залокировать критическую секцию
   string critical_section = array+"Lock";
   if (Lock(critical_section)!=0) return(-1);  

Для осуществления поиска мы должны знать количество элементов в массиве:

    // Количество элементов массива хранится в переменной с именем, 
    // равным имя массива + "Count"
    string gv_count;
    gv_count = array+"Count";
    
    int count, err;
    
    // Если глобальная переменная не существует, то элементов нет
    if (!GlobalVariableCheck(gv_count))
      {
       err = GetLastError();
       if (err!=0) 
        {
         // Разлокировать критическую секцию
         Unlock(critical_section);
         
         // Вывести сообщение об ошибке и выйти
         Print("SearchItem()->GlobalVariableCheck(): ошибка ", err);
         return(-1);
        }
       else 
         count = 0;
      }
    else
       // переменная существует, получим количество элементов
       count = GlobalVariableGet(gv_count);

После этого мы смотрим, отсортирован ли массив:

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

Технология поиска простым перебором:

      int i;
      for (i=1; i<=count; i++)
        if (item==GlobalVariableGet(array+DoubleToStr(i, 0)))
         {
          // Разлокировать критическую секцию
          Unlock(critical_section);

          return(i);
         }

Технология двоичного поиска:

1. Левая граница поиска - первый элемент, правая граница поиска - последний эелемент.
2. Берем элемент, который находится посередине между левой и правой границами.
3. Если этот элемент меньше того, который мы ищем, то сдвигаем левую границу поиска к середине нашего диапазона (т.к. однозначно, что искомый элемент находится выше серединного). В противном случае - сдвигаем правую границу поиска к середине диапазона. Каждый раз диапазон поиска уменьшается в два раза.
4. Повторяем шаги 2 и 3, пока диапазон больше 2 элементов

Такая технология поиска гарантирует быстрое нахождение элемента в отсортированном массиве. Например, в массиве из 1,000 элементов мы найдем элемент за 10 итераций, а в массиве из 1,000,000,000 элементов - за 30 итераций. В то время как поиск путем простого перебора даст тот же результат в среднем за 500 и 500,000,000 итераций соответственно. Выигрыш в скорости очень ощутим.

Напомню кусок кода, который осуществляет двоичный поиск в отсортированном массиве:

      int pos1, pos2, mid;
      pos1 = 1;
      pos2 = count;
      
      while (pos1+1<pos2)
        {         
         mid = (pos1+pos2)/2;
         
         if (item>GlobalVariableGet(array+DoubleToStr(mid, 0))) 
           pos1 = mid;
         else
           pos2 = mid;
        }
        
      if (GlobalVariableGet(array+DoubleToStr(pos1, 0))==item)
        {
         // Разлокировать критическую секцию
         Unlock(critical_section);
    
         return(pos1);
        } 
      if (GlobalVariableGet(array+DoubleToStr(pos2, 0))==item)
        {
         // Разлокировать критическую секцию
         Unlock(critical_section);
    
         return(pos2);
        } 
     }    

В следующем выпуске я расскажу о том, как с помощьюе функции GetItem() получить значение элемента в определенной позиции массиве.

Все статьи по теме "Пишем советников для MetaTrader 4".

• Механическая торговая система - миф или реальность?
• С чего начать при написании советника:
  

  	-	Создаем нового советника
  	-	Настраиваем параметры.

• Язык MetaQuotes Language 4:
  

  	-	Структура советника.
  	-	Создаем собственные функции. Функции init(), start() и deinit().
  	-	Исходный код нашего первого советника.
  	-	Использование констант в эксперте.
  	-	Хранение данных в переменных: локальные, статические, внешние и глобальные переменные. Параметры функций.
  	-	Операторы: Составной оператор. Оператор присваивания (арифметические операции, операции отношения, логические операции НЕ, ИЛИ и И, побитовые операции). Условный оператор. Цикл while. Цикл for. Break. Сontinue. Переключатель Switch.
  	-	Получение информации об ордере: OrderSelect(). OrdersTotal(). HistoryTotal(). OrderClosePrice(). OrderStopLoss(). OrderType(). OrderCloseTime(). OrderTakeProfit(). OrderSymbol(). OrderComment(). OrderSwap(). OrderCommission(). OrderOpenPrice(). OrderTicket(). OrderProfit(). OrderOpenTime(). OrderExpiration(). OrderMagicNumber().
  	-	Управление ордерами и открытие/закрытие позиций: OrderSend(). OrderModify(). OrderDelete(). OrderClose(). OrderClosyBy().
  	-	Ошибки: GetLastError(). Коды ошибок.
  	-	Секреты правильной торговли: IsExpertEnabled(). IsTradeContextBusy(). IsTradeAllowed(). Как бороться с ошибкой ERR_TRADE_CONTEXT_BUSY (146). IsStopped(). RefreshRates(). Выдерживаем паузу между сделками. IsTesting().
  	-	Глобальные переменные: GlobalVariableCheck(). GlobalVariableSet(). GlobalVariableSetOnCondition(). Как дождаться освобождения торгового потока. GlobalVariableGet(). GlobalVariableDel(). "Критическая секция": разграничение доступа к ресурсу. GlobalVariablesTotal(). GlobalVariableName(). GlobalVariablesDeleteAll().
  	-	Глобальные массивы: Count(). AddItem(). SearchItem(). GetItem().