Algoritmaların optimizasyonu. - sayfa 4

Yeni yorum
 
MetaDriver :
Şimdi bir sorunum var. Kopyalama öğelerinin (yani öğeleri hacimli, "ağır" yapılar, sınıf nesneleri , uzun dizeler vb. olan) "maliyeti" olan dizilerin verimli bir şekilde sıralanması gerekir. Sağduyu, onları yerinde bırakmanız ve yerine bir tür işaretçi ile sıralamanız gerektiğini belirtir - orijinal konumlarının hücre dizinleri. Buradan daha fazla alıntı: https://www.mql5.com/en/forum/6476#comment_178318Şimdiye saygın terminal geliştiricilerini sayısız mevcut görevleriyle bırakalım ve mql5'te uygulayalım.

Her şey bizden önce çalındı bile :)

MQL5'te elektronik tablolar

girdi, sıralanan dizinin bir kopyası olmalı, yorumlar yorumlanmamalı, gereksiz yorumlar yapılmalıdır

 //+------------------------------------------------------------------+
//void QuickSort(double &A[],int &r[],int from,int to)
void QuickSort( double &A[], int from , int to)
  {
   int i,j; //,itemp;
   double x,temp;
   if ( from >=to) return ;
   i= from ;
   j=to;
   x=A[( from +to)>> 1 ];
   while (i<=j)
     {
       while (A[i]<x)i++; 
       while (A[j]>x)j--;
       if (i<=j)
        {
         temp=A[i]; A[i]=A[j]; A[j]=temp;
         //itemp=r[i]; r[i]=r[j]; r[j]=itemp;
         i++;
         j--;
        }
     }
   QuickSort(A, from ,j);
   //QuickSort(A,r,from,j);
   QuickSort(A,i,to);  
   //QuickSort(A,r,i,to);
  }
//+------------------------------------------------------------------+
 
Urain :

Her şey bizden önce çalındı bile :)

MQL5'te elektronik tablolar

girdi, sıralanan dizinin bir kopyası olmalı, yorumlar yorumlanmamalı, gereksiz yorumlar yapılmalıdır

Kötü seni! Şarkıyı mahvettim... Daha doğrusu denedim. :)

// İyi yaklaşımların olduğu açıktır. Aynı başarı ile standart kitaplıktan bir örnek çıkarabilirim. :)

Örnekler var. Ve hatta harikalar. Ama hala. Burada her şeyi kaydetmek ve ayrı bir kullanılabilir ürünün çalışma durumuna göre hata ayıklamak önemlidir. Üstelik (bunu neden buraya gönderiyorum) - olabildiğince hızlı. Onlar. Mümkün olan tüm performansı yüzde birin yüzde birine kadar sıkıştırmayı öneriyorum. :)

Bu ilk. İkinci olarak, nesneler için dizin dizilerinin sayısı, genel durumda birkaç tane olabilen sıralama ölçütlerinin sayısına eşit istenir, + (tercihen) çeşitli ölçütlere göre sıralanmış dizinlenmiş bir diziye ekleme işlevi.

 
MetaDriver :

Kötü seni! Şarkıyı mahvettim... Daha doğrusu denedim. :)

// İyi yaklaşımların olduğu açıktır. Aynı başarı ile standart kitaplıktan bir örnek çıkarabildim. :)

Örnekler var. Ve hatta harikalar. Ama hala. Burada her şeyi kaydetmek ve ayrı bir kullanılabilir ürünün çalışma durumuna göre hata ayıklamak önemlidir. Üstelik (bunu neden buraya gönderiyorum) - olabildiğince hızlı. Onlar. Mümkün olan tüm performansı yüzde birin yüzde birine kadar sıkıştırmayı öneriyorum. :)

Bu ilk. İkinci olarak, nesneler için dizin dizilerinin sayısı, genel durumda birkaç tane olabilen sıralama ölçütlerinin sayısına eşit istenir, + (tercihen) çeşitli ölçütlere göre sıralanmış dizinlenmiş bir diziye ekleme işlevi.

MQL5'te hala aynı cevap Elektronik Tablolar

hepsi orada. Masayı yan çevirin. Pekala, belirli bir görev için, onu sütunları değil, satırları manipüle etmek için yeniden yapabilirsiniz, sütunlar orada yapılır, böylece onları farklı türler ilan edebilirsiniz. Tablo türü bir ise, her şey yeniden oynatılabilir.

 

Temel türler için dizin sıralamalı bir içerme yapıldı.

 bool ArrayIndexSort( const void &source[], int &index[], bool byDescending= true );

Varsayılan sıralama "azalan" şeklindedir, artan düzende sıralamak için sıralama yönü bayrağını false olarak ayarlayın.

Test sonuçları: // dizi indeksleme double[], int[], string[]; Sıralı: ham dizi, azalan, artan

 2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     SArray[index[i]] = {MetaQuotes, Абырвалг, Газета, Колбаса, Компилятор, Молоко, Препроцессор, Яйцо}
2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     SArray[index[i]] = {Яйцо, Препроцессор, Молоко, Компилятор, Колбаса, Газета, Абырвалг, MetaQuotes}
2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     SArray[i]        = {Абырвалг, Газета, MetaQuotes, Колбаса, Молоко, Яйцо, Компилятор, Препроцессор}
2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     iarray[index[i]] = { 89 , 2393 , 3742 , 4772 , 5098 , 5364 , 5560 , 6226 , 6758 , 7029 , 7245 , 7540 , 8097 , 8195 , 8908 , 8945 }
2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     iarray[index[i]] = { 8945 , 8908 , 8195 , 8097 , 7540 , 7245 , 7029 , 6758 , 6226 , 5560 , 5364 , 5098 , 4772 , 3742 , 2393 , 89 }
2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     iarray[i]        = { 8945 , 7245 , 8195 , 5364 , 8097 , 5560 , 5098 , 3742 , 89 , 6758 , 6226 , 7029 , 4772 , 7540 , 8908 , 2393 }
2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     darray[index[i]] = { 0.29 , 13.40 , 16.11 , 28.86 , 31.05 , 35.63 , 38.71 , 39.65 , 47.79 , 50.33 , 50.40 , 59.39 , 63.31 , 65.35 , 70.65 , 78.98 }
2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     darray[index[i]] = { 78.98 , 70.65 , 65.35 , 63.31 , 59.39 , 50.40 , 50.33 , 47.79 , 39.65 , 38.71 , 35.63 , 31.05 , 28.86 , 16.11 , 13.40 , 0.29 }
2012.04 . 08 05 : 04 : 46      IndexSort_Test (USDJPY,M30)     darray[i]        = { 50.33 , 47.79 , 39.65 , 70.65 , 31.05 , 16.11 , 38.71 , 78.98 , 50.40 , 35.63 , 0.29 , 63.31 , 13.40 , 59.39 , 28.86 , 65.35 }

Fragmanda kitaplık ve test.

Dahil etmeyi "MQL5\Include\Indexs\" klasörüne koyun

Dosyalar:
IndexSort.mqh  14 kb
IndexSort_Test.mq5  4 kb
 

İşte OCL ile çalışmak için bir sınıf hazırlığı. Elbette bir şey tamamlanmamış ve hantal değildir, ancak birileri için faydalı olabilir.

 //——————————————————————————————————————————————————————————————————————————————
//|                                                            class   OCL.mqh |
//|                                                Copyright 2011, JQS aka Joo |
//|                                        https://www.mql5.com/ru/users/joo |
//——————————————————————————————————————————————————————————————————————————————
#property copyright "Copyright 2011, JQS aka Joo"
#property link       "https://www.mql5.com/ru/users/joo"
//——————————————————————————————————————————————————————————————————————————————
class OCL
{
public :
   bool               DeviceInfo( int DeviceID);
   bool               InitOCL   ( int DeviceID, uint &Offset[], uint &Work[], int BuffCount, int ArgCount, string Source);
   bool               BuffInit  ( int buffID, int size, int regime);
   bool               Execute   ( int work_dim);
   void               DeinitOCL ();
   //---
   int                BuffID[]; // идентификаторы буферов
   //----------------------------------------------------------------------------
private :
   int                cl_ctx;   // идентификатор контекста
   int                cl_prg;   // идентификатор программы
   int                cl_krn;   // идентификатор ядра
   //---
   int                ArguID[]; // идентификаторы аргументов
   uint               offset[]; 
   uint               work  [];
};
//——————————————————————————————————————————————————————————————————————————————
bool OCL::DeviceInfo( int DeviceID)
{
   long DeviceCount=CLGetInfoInteger( 0 ,CL_DEVICE_COUNT);
   if (DeviceCount< 1 )
     return ( false );
   else
  {
     string s= "Всего устройств OCL: " +( string )CLGetInfoInteger( 0 ,CL_DEVICE_COUNT)+ " - " ;
     long DeviceType=CLGetInfoInteger(DeviceID,CL_DEVICE_TYPE);

     switch (DeviceType)
    {
     case CL_DEVICE_ACCELERATOR:
      s=s+ "Используется спец.OpenCL ускоритель (например, IBM CELL Blade)" ;
       break ;
     case CL_DEVICE_CPU:
      s=s+ "Используется CPU" ;
       break ;
     case CL_DEVICE_GPU:
      s=s+ "Используется GPU" ;
       break ;
     case CL_DEVICE_DEFAULT:
      s=s+ "Устройство по умолчанию" ;
       break ;
     case CL_DEVICE_CUSTOM:
      s=s+ "Специализированный ускоритель, не поддерживает OpenCL" ;
       break ;
     default :
      s=s+ "Непонятное устройство, скорее всего это какое то устройство по умолчанию" ;
       break ;
    }
     Print (s);
     return ( true );
  }
}
//——————————————————————————————————————————————————————————————————————————————
bool OCL::InitOCL( int DeviceID, uint &Offset[], uint &Work[], int BuffCount, int ArgCount, string Source)
{
   ArrayResize (offset, ArraySize (Offset)); ArrayCopy (offset,Offset, 0 , 0 , WHOLE_ARRAY );
   ArrayResize (work,   ArraySize (Work));   ArrayCopy (work,  Work,   0 , 0 , WHOLE_ARRAY );

   if ((cl_ctx=CLContextCreate(DeviceID))==- 1 )
  {
     Print ( "OpenCL не найден: " , GetLastError ());
     return ( false );
  }
//----------------------------------------------------------------------------
// Создаем OpenCL программу из исходного кода
   if ((cl_prg=CLProgramCreate(cl_ctx,Source))==- 1 )
  {
    CLContextFree(cl_ctx);
     Print ( "Ошибка созания OpenCL-программы" );
     switch ( GetLastError ())
    {
     case ERR_OPENCL_INVALID_HANDLE:
       Print ( "Некоректный хендл на программу OpenCL" );
       break ;
     case ERR_INVALID_PARAMETER :
       Print ( "Некоректный строковой параметр" );
       break ;
     case ERR_OPENCL_TOO_LONG_KERNEL_NAME:
       Print ( "Имя кернела содержит более 127 символов" );
       break ;
     case ERR_OPENCL_KERNEL_CREATE:
       Print ( "Внутренняя ошибка при создании объекта OpenCL." );
       break ;
     default : Print ( "Неопознанная ошибка." );
    }
     return ( false );
  }
   //----------------------------------------------------------------------------
   //Создаем точку входа в программу OpenCL  
   if ((cl_krn=CLKernelCreate(cl_prg, "Work" ))==- 1 )
  {
    CLProgramFree(cl_prg);
    CLContextFree(cl_ctx);
     Print ( "Ошибка создания OpenCL-ядра" );
     return ( false );
  }
   //----------------------------------------------------------------------------
   ArrayResize (BuffID,BuffCount);
   ArrayResize (ArguID,ArgCount);
   return ( true );
}
//——————————————————————————————————————————————————————————————————————————————
void OCL::DeinitOCL()
{
   for ( int i= 0 ;i< ArraySize (BuffID);i++)
    CLBufferFree(BuffID[i]);

  CLKernelFree (cl_krn);
  CLProgramFree(cl_prg);
  CLContextFree(cl_ctx);
}
//——————————————————————————————————————————————————————————————————————————————
bool OCL::Execute( int work_dim)
{
   if (!CLExecute(cl_krn,work_dim,offset,work))
  {
     Print ( "Ошибка при расчете в OpenCL" );
     return ( false );
  }
   return ( true );
}
//——————————————————————————————————————————————————————————————————————————————
bool OCL::BuffInit( int buffID, int size, int regime)
{
   if (buffID>= ArraySize (BuffID))
     return ( false );

  BuffID[buffID]=CLBufferCreate(cl_ctx,size,regime);
   if (BuffID[buffID]==- 1 )
  {
     Print ( "OpenCL buffer create failed" );
     switch ( GetLastError ())
    {
     case ERR_OPENCL_INVALID_HANDLE:
       Print ( "Нкоректный хендл на контекст OpenCL" );
       break ;
     case ERR_NOT_ENOUGH_MEMORY :
       Print ( "Недостаточно памяти" );
       break ;
     case ERR_OPENCL_BUFFER_CREATE:
       Print ( "Внутренняя ошибка создания буфера" );
       break ;
     default : Print ( "Неопознанная ошибка." );
    }
     return ( false );
  }
   //Выставляем буфер OpenCL в качестве параметра функции OpenCL
   if (!CLSetKernelArgMem(cl_krn,buffID,BuffID[buffID]))
     return ( false );
   return ( true );
}
//——————————————————————————————————————————————————————————————————————————————


ZY Bitok başlatmayı değiştirdi, şimdi çok boyutlu hesaplamaları çalıştırabilirsiniz.

 
Güzel, beğendim. Belki de C benzeri kodunuzu yeniden yapın?
 

Harika konu!

Az önce fiyat ekstremum (minimum) arama algoritmasının bir optimizasyon problemiyle karşılaştım. Koşullar aşağıdaki gibidir, bir çubuk vardır, solunda ve sağında maksimum değerinden daha düşük (yüksek) olan n çubuk vardır:

n , isteğe bağlı olarak seçilen serbest bir değerdir. Sağdaki ve soldaki iki bölümün toplamı her zaman bir çift sayı olacağından, n periyodu her zaman tektir, buna aşırı fiili fiyatın merkez çubuğunun eklendiği.

Algoritmanın ilk versiyonu hakkında fazla düşünmedim ve en bariz kodu yazdım. Şimdi WealthLab platformu çerçevesinde C# ile yazıyorum ama problemli algoritmanın özünü kolaylıkla anlayabileceğinizi düşünüyorum, işte en problemli kısmı:

 //Перебираем все бары
for ( int bar = 0 ; bar < MyQuotes.Count; bar++)
{
    //Подготовка данных
   ...
   int pperiod = ( N - 1)/2;
   //Перебираем бары относительно потенциального экстремума
    for ( int i = 1 ; i <= pperiod; i++)
   {
      if (MyQuotes.High[bar - i] > MyQuotes.High[bar] ||
         MyQuotes.High[bar + i] > MyQuotes.High[bar])
         up = false ;
      if (MyQuotes.Low[bar - i] < MyQuotes.Low[bar] ||
         MyQuotes.Low[bar + i] < MyQuotes.Low[bar])
         down = false ;
   }
}

Bütün sorun ikinci döngüde. Potansiyel ekstremumdan sol ve sağ dalları eşzamanlı olarak işler ve bu nedenle yalnızca (N - 1)/2 çubuk üzerinde yinelenir, ancak bu yeterli değildir. Ölçümler, aritmetik bir ilerlemede bir ekstremum aramak için harcanan zamanın, çok, çok kötü olan N periyoduna bağlı olduğunu gösteriyor:

 N         Time
3        00 : 00 : 00.5460312
4        00 : 00 : 00.4720270
5        00 : 00 : 00.4820276
6        00 : 00 : 00.4250243
7        00 : 00 : 00.4410252
8        00 : 00 : 00.4350249
9        00 : 00 : 00.4300246
10        00 : 00 : 00.4380251
11        00 : 00 : 00.4520258
12        00 : 00 : 00.4420253
13        00 : 00 : 00.4500257
14        00 : 00 : 00.4640266
15        00 : 00 : 00.5100291
16        00 : 00 : 00.4950284
17        00 : 00 : 00.5200297
18        00 : 00 : 00.5110292
19        00 : 00 : 00.5090291
20        00 : 00 : 00.5690326
21        00 : 00 : 00.5320304
22        00 : 00 : 00.5560318
23        00 : 00 : 00.5750329
24        00 : 00 : 00.5850335
25        00 : 00 : 00.6140351
26        00 : 00 : 00.6120350
27        00 : 00 : 00.6160352
28        00 : 00 : 00.6510373
29        00 : 00 : 00.6510372
30        00 : 00 : 00.6770387
31        00 : 00 : 00.6900395
32        00 : 00 : 00.7040403
33        00 : 00 : 00.7000400
34        00 : 00 : 00.7190411
35        00 : 00 : 00.7320419
36        00 : 00 : 00.7510430
37        00 : 00 : 00.7510429
38        00 : 00 : 00.8290474
39        00 : 00 : 00.7760444
40        00 : 00 : 00.8080463
41        00 : 00 : 00.7990457
42        00 : 00 : 00.8240471
43        00 : 00 : 00.8460484
44        00 : 00 : 00.8690497
45        00 : 00 : 00.8680496
46        00 : 00 : 00.9120522
47        00 : 00 : 00.8870507
48        00 : 00 : 00.9520545
49        00 : 00 : 00.9230528
50        00 : 00 : 00.9430539
51        00 : 00 : 00.9460541
52        00 : 00 : 00.9590549
53        00 : 00 : 00.9750558
54        00 : 00 : 00.9920567
55        00 : 00 : 01.0010573
56        00 : 00 : 01.0440597
57        00 : 00 : 01.0400595
58        00 : 00 : 01.0610607
59        00 : 00 : 01.0610606
60        00 : 00 : 01.0860622
61        00 : 00 : 01.0730613
62        00 : 00 : 01.1170639
63        00 : 00 : 01.1400652
64        00 : 00 : 01.1370651
65        00 : 00 : 01.1190640
66        00 : 00 : 01.1960684
67        00 : 00 : 01.1740671
68        00 : 00 : 01.2110693
69        00 : 00 : 01.2490715
70        00 : 00 : 01.3010744
71        00 : 00 : 01.2750730
72        00 : 00 : 01.3090748
73        00 : 00 : 01.3000744
74        00 : 00 : 01.3060747
75        00 : 00 : 01.3610779
76        00 : 00 : 01.3740785
77        00 : 00 : 01.4190812
78        00 : 00 : 01.3500772
79        00 : 00 : 01.3350764
80        00 : 00 : 01.3530774
81        00 : 00 : 01.4690840
82        00 : 00 : 01.4270816
83        00 : 00 : 01.3870794
84        00 : 00 : 01.4250815
85        00 : 00 : 01.4250815
86        00 : 00 : 01.4500829
87        00 : 00 : 01.4600835
88        00 : 00 : 01.4630837
89        00 : 00 : 01.4500830
90        00 : 00 : 01.5060861
91        00 : 00 : 01.4930854
92        00 : 00 : 01.5340878
93        00 : 00 : 01.5620893
94        00 : 00 : 01.5470885
95        00 : 00 : 01.5450884
96        00 : 00 : 01.5730899
97        00 : 00 : 01.5640895
98        00 : 00 : 01.5840906
99        00 : 00 : 01.5970914

Periyotların sayımı, zaman içindeki aritmetik ilerlemenin toplamını alacaktır ve bu çok büyük bir değerdir.

Olası bir çözüm eklemektir değişken. Sonuçta, bir ekstremum bulunursa, (N - 1)/2 sırasında sağında tek bir çubuk olmaması garanti edilir, bu nedenle yeni bir ekstremum araması çubuktan başlatılabilir: current_bar + (N - 1)/2. Ancak aşırı uçlarla birlikte, düşükleri de bulmanız gerekir ve current_bar + (N - 1)/2 çubuğundan önce yeni bir düşük bulunabilir. Bu nedenle, aşırı uçlar ve minimumlar arayışını iki geçişe bölmek gerekecektir, bu da performans kazancını olumsuz etkileyecektir. C#'da, iki geçişi iki çekirdekte aynı anda işlenen iki iş parçacığına kolayca bölebilirsiniz, ancak önce en uygun algoritmayı bulmak ve zaten optimize etmek istiyorum. Uzmanların yardımını bekliyorum.

 
C-4 : Az önce fiyat ekstremum (minimum) arama algoritmasında bir optimizasyon problemiyle karşılaştım.

Eh, bu bir optimizasyon sorunu değil.

Periyotların sayımı, zaman içindeki aritmetik ilerlemenin toplamını alacaktır ve bu çok büyük bir değerdir.

Bir ekstremum araması, n'nin veri sayısı olduğu bir O(n) sıra problemidir. Bu asimptotik nasıl daha da kötüleştirilebilir, yani. O(n^2) - Hayal bile edemiyorum. Ya da kavramlarda kafanız karıştı.

En basit algoritma ArraySort() öğesini sıralamaktır, yerleşik oldukça hızlıdır, O(n * ln( n ) ) bölgesinde bir şeydir. Ama muhtemelen bu görev için fazladan.

Daha hızlı olacak özyinelemeli bir şey bulabilirsin.

Minimum ve kaç çubuk için ne kadar süreyle arama yapıyorsunuz? 100 barda en fazla bir buçuk saniye aradığınıza inanmıyorum.

 
Mathemat :

En basit algoritma ArraySort() sıralamadır, yerleşik oldukça hızlıdır. Ama muhtemelen bu görev için fazladan.

En iyi sıralama O(n*log(n)) şeklindedir. Kesinlikle gereksiz.

Daha hızlı olacak özyinelemeli bir şey bulabilirsin.

Yavaş. Özyineleme çoğu zaman kötüdür. tekrarlayan? İşte muhtemelen, nasıl yaparsanız yapın, hızın yaklaşık olarak aynı olacağı durumdur.

Kodla:

 //Перебираем все бары
for ( int bar = 0 ; bar < MyQuotes.Count; bar++)
{
   //Подготовка данных
   ...
   int pperiod = (N - 1 )/ 2 ;
   //Перебираем бары относительно потенциального экстремума
   for ( int i = 1 ; i <= pperiod; i++)
   {
       if (MyQuotes.High[bar - i] > MyQuotes.High[bar] ||
         MyQuotes.High[bar + i] > MyQuotes.High[bar])
         up = false ;
       if (MyQuotes.Low[bar - i] < MyQuotes.Low[bar] ||
         MyQuotes.Low[bar + i] < MyQuotes.Low[bar])
         down = false ;
   }
}

Min ve max döngüleri açık bir şekilde ayrılmalıdır. Ve başarısız olursa döngüden hemen çıkın.

 
TheXpert : Bu muhtemelen, nasıl yaparsanız yapın, hızın aşağı yukarı aynı olacağı durumdur.

Sanırım, evet. Ama yine de O(n)'den fazla değil.

OCL burada yardımcı olacaktır. Asimptotikler elbette aynı kalacaktır. Ancak hızı yüz kat artırmak oldukça mümkündür.

12345678910
Yeni yorum