博客网 >

用双队列实现高效插入和删除
作者:分类:默认分类标签:
用双队列实现高效插入和删除
By David.Zhu 2006/12/18
1.1 问题描述
  现在需要实现一个元素插入和删除的机制,元素为指针类型,插入时对顺序不做要求,要求在高密度和高强度的插入和删除操作里时,该机制能够保持较高的性能。

1.2 list实现
typedef struct 
{
	....
   DWORD   dwQueueIndex;			
}ENTRY,*LPENTRY;

deque  m_SingleQueue;

void Direct_AddEntry(LPENTRY pEntry)
{
   m_SingleQueue.push_back(pEntry);
}

void Direct_RemoveEntry(LPENTRY pEntry)
{
   deque::iterator Iter;
   for(Iter=m_SingleQueue.begin();Iter!=m_SingleQueue.end();Iter++)
   {
     if(*Iter==pEntry)
     {
        m_SingleQueue.erase(Iter);
        break;
     }
   }
}


1.3 map/set实现
set    m_Set;

void Set_AddEntry(LPENTRY pEntry)
{
   m_Set.insert(pEntry);
}
void CTest::Set_RemoveEntry(LPENTRY pEntry)
{
    set::iterator Iter=m_Set.find(pEntry);
    if(Iter!=m_Set.end())
    {
       m_Set.erase(Iter);
    }
}


1.4 双队列实现
deque		 m_Queue;
deque		m_CacheQueue;

void DQueue_AddAsyncIo(LPENTRY pEntry)
{
   if(m_CacheQueue.empty())
   {
       pEntry>dwQueueIndex =m_Queue.size();
       m_Queue.push_back(pEntry);
   }
   else
  {
       pEntry>dwQueueIndex=m_CacheQueue.front();
       m_CacheQueue.pop_front();
			
       m_Queue[pEntry>dwQueueIndex]=pEntry;
   }	
}


void  DQueue_RemoveAsyncIo(LPENTRY pEntry)
{
   m_Queue[pEntry>dwQueueIndex]=0;
   m_CacheQueue.push_back(pEntry>dwQueueIndex);
}
1.5 性能比较
int main(int argc, char* argv[])
{
   int n,i,j;

   #define  COUNT   400
   ENTRY  Entry[COUNT]={0};
   BYTE   index[COUNT];

   for(n=0;n<COUNT;n++)
   {
      index[n]=n;
   }

   srand(GetTickCount());
   for(n=0;n<100;n++)
   {
      i=rand()%COUNT;
      j=rand()%COUNT;

      int temp=index[i];
      index[i]=index[j];
      index[j]=temp;
   }

   DWORD dwStartTimer=GetTickCount();
   for(n=0;n<1000;n++)
   {		
       for(i=0;i<COUNT;i++)
         DQueue_AddAsyncIo(&(Entry[i])); 		
		
       for(j=0;j<COUNT;j++)
       {
         DQueue_RemoveAsyncIo(&(Entry[index[j]]));
       }
    }
    printf("DQueue_AddAsyncIo Use %d ms\n",GetTickCount()-dwStartTimer);


    dwStartTimer=GetTickCount();
    for(n=0;n<1000;n++)
    {		
	   for(i=0;i<COUNT;i++)
           Set_AddAsyncIo(&(Entry[i])); 		
		
       for(j=0;j<COUNT;j++)
       {
          Set_RemoveAsyncIo(&(Entry[index[j]]));
       }
    }
    printf("Set_AddAsyncIo Use %d ms\n",GetTickCount()-dwStartTimer);
	
    dwStartTimer=GetTickCount();
    for(n=0;n<1000;n++)
    {		
        for(i=0;i<COUNT;i++)
          Direct_AddAsyncIo(&(Entry[i])); 		
		
        for(j=0;j<COUNT;j++)
        {
           Direct_RemoveAsyncIo(&(Entry[index[j]]));
        }
     }
     printf("Direct_AddAsyncIo Use %d ms\n",GetTickCount()-dwStartTimer);
     return 0;

测试结果:
DQueue_AddAsyncIo Use 31 ms
Set_AddAsyncIo Use 219 ms
Direct_AddAsyncIo Use 153844 ms
分析: list,单Queue在插入时效率较高O(1),但删除时需要一个遍历操作,时间复杂度为O(N)
set/map由于采用了树结构,在插入和删除时需要对树进行旋转和调整,降低了其效率
双Queue实质上是一个缓冲池的概念,由于索引的使用,插入和删除时间复杂度均为O(1),并且 由于引入了缓冲池,避免了频繁的内存申请和释放,进一步增加了该机制的运行效率。
<< 这半年干嘛去了 / 一个程序员如何月进万金的 >>

专题推荐

不平凡的水果世界

不平凡的水果世界

平凡的水果世界,平凡中的不平凡。 今朝看水果是水果 ,看水果还是水果 ,看水果已不是水果。这境界,谁人可比?在不平凡的水果世界里,仁者见仁,智者见智。

中国春节的那些习俗

中国春节的那些习俗

正月是农历新年的开始,人们往往将它看作是新的一年年运好坏的兆示期。所以,过年的时候“禁忌”特别多。当然,各个地方的风俗习惯不一样,过年的禁忌也是不一样的。

评论
0/200
表情 验证码:

David.Zhu

  • 文章总数0
  • 画报总数0
  • 画报点击数0
  • 文章点击数0
个人排行
        博文分类
        日期归档