주어진 요소의 배열 지우기 - 페이지 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]와 같은 2차원 배열입니다. 나머지는 변경하지 않고 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이 될 것이라는 사실을 고려하면 이것이 가장 빠른 옵션입니다.