Очистка массива от заданного (ых) элементов - страница 30

[Nikolai Semko]

Stanislav Dray:

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

конечно

[nicholish en]

Я, наконец, нашел способ сделать быстрый хеш-набор.

#include <generic/hashmap.mqh>
template<typename T>
class HashSet : public CHashMap<T, bool>
{
 public:
   HashSet(const T &arr[]):CHashMap(10000) {
      for(int i=ArraySize(arr)-1; i>=0; --i)
         this.Add(arr[i], true);
   }
   bool operator[](const T key) { 
      return this.ContainsKey(key); 
   }
};

int array_filter(int &a[],const int &f[])
{
   int k = 0;
   int x=ArraySize(a);
   HashSet<int> d(f);
   for(int i=0; i<x; i++)
      if(!d[a[i]])
         a[k++]=a[i];
   return ArrayResize(a, k);
}

[fxsaber]

Еще одна задача для мозгового штурма.

[Jurii Kuvshinov]

nicholi shen:

Хорошо, двухмерный массив например [13][12]. Как удалить 7-ю строку, оставив остальные без изменений ?

[Vladimir Simakov]

template<typename T>
int EraseRate(T &tArray[],T tRate){
   int tCount=ArraySize(tArray),
       tRes=tCount;
   for (int i=0,ii=0;i+ii<tCount;i++){
      if (ii) tArray[i]=tArray[i+ii];
      while (tArray[i]==tRate&&i+ii<tCount){
         if (i+(++ii)<tCount) tArray[i]=tArray[i+ii];
         tRes--;}}
   return(ArrayResize(tArray,tRes));}

Как-то так

[Vladimir Simakov]

template<typename T>
int EraseRate(T &tArray[],T tRate){
   int tCount=ArraySize(tArray),
       tDelCount=0;
   for (int i=0,tNext=0;tNext<tCount;i++,tNext++){
      if (tDelCount) tArray[i]=tArray[tNext];
      while (tArray[i]==tRate&&tNext<tCount){
         if (++tNext<tCount) tArray[i]=tArray[tNext];
         tDelCount++;}}
   return(ArrayResize(tArray,tCount-tDelCount));}

После оптимизации.

[Stanislav Dray]

/*
//the original code of nicholi shen

int array_filter(int &a[],const int &b[]) 
{
   int e=ArraySize(a);
   bool c[];
   int d = ArrayResize(c, b[ArrayMaximum(b)] + 1);
   ArrayInitialize(c, 0);
   for(int i=ArraySize(b)-1; i>=0; --i)
      c[b[i]] = 1;
   int g=0, h=0, f=0;
   for(g=0; g<e; g++){
      f = a[g];
      if(f >= d || !c[f]){
         a[h]=f;
         h++;
      }
   }
   return ArrayResize(a, h);
}
*/

//by Stanislav_Dray, based on the code above
int ArrayDeleteVectorINT(int &A[],const int &F[])
{
   if(!ArrayIsDynamic(A))
   {
      Print(__FUNCTION__,": cannot be used for static allocated array");
      return(-1);
   }
   int Fp[];
   int A_size=ArraySize(A); 
   int F_size=ArraySize(F);
   int F_maxval=F[ArrayMaximum(F)];
   int F_minval=F[ArrayMinimum(F)];
   //extra memory needed : ExtraMemory*sizeof(int)
   int ExtraMemory=((MathMax(F_maxval,MathAbs(F_minval)))>>5) + 1;
   if(ArrayResize(Fp,ExtraMemory)==-1)
   {
      Print(__FUNCTION__,": cannot allocate memory");
      return(-1);   
   }
   
   int h;
   int i;
   int j;
   int A_value;
   int F_value;
   
   if(F_maxval>=0)
   {
      ArrayInitialize(Fp, 0);
      i=0;h=0;
      while(i<F_size)
      {
         F_value=F[i];
         if(F_value>-1)
         {     
            j=F_value>>5;
            Fp[j]|=(1<<(F_value-(j<<5)));
         }
         i++; 
      } 
      
      for(i=0; i<A_size; i++)
      {
         A_value = A[i];
         if(A_value>F_maxval || A_value<0)
         {
            A[h]=A_value;
            h++;
         }else
         {
            j=A_value>>5;
            if(Fp[j]==0 || !(Fp[j] & (1<<(A_value-(j<<5)))) )
            {
               A[h]=A_value;
               h++;
            }
         }
      }
      A_size=h;
   }
   if(F_minval<0)
   {
      ArrayInitialize(Fp, 0);
      i=0; h=0;
      while(i<F_size)
      {
         F_value=F[i];
         if(F_value<0)
         { 
            F_value=(~F_value)+1;    
            j=F_value>>5;
            Fp[j]|=(1<<(F_value-(j<<5)));
         }
         i++; 
      }

      for(i=0; i<A_size; i++)
      {        
         A_value = A[i];
         if(A_value<F_minval || A_value>-1)
         {
            A[h]=A_value;
            h++;
         }else
         {
            j=(~A_value+1)>>5;
            if(Fp[j]==0 || !(Fp[j] & (1<<((~A_value+1)-(j<<5)))) )
            {
               A[h]=A_value;
               h++;
            }
         }
      }
      A_size=h;   
   }
    
   return (ArraySize(A)!=A_size ? ArrayResize(A, A_size):A_size);
}

Поправил немножко код nicholi shen

теперь отвечает условиям задачи и работает для int массивов. Помоему это самый быстрый вариант с учётом того что размер фильтра F будет не меньше 6.