一种基于滑动窗口的对齐排序算法

码农的修炼之道 2021-10-24

1364

在日常开发中会遇到一些大数据的排序对齐场景，当然了，常规的思路比较多，比如常见的排序算法（堆排序、快排等）都能获得不错的收益。本次的场景有些特别，我们需要考虑的是尽量不移动内存块，实现多内存块的数据有序对齐输出。

场景简化，假设我们有N个内存块，每个内存块包括了1-M个数据。如下图所示，假设我们拿到了N个存储集合，每一块存储集合内部元素已经有序了。那么现在的需求就是将这N个存储集中的数据进行对齐输出，也就是按照某一种规则排序依次输出。

这个需求有点类似于N个有序链表，合并成1个有序链表。类似这个题目，leetcode上面应该也有题解。

这里，我参考tcp协议里面的滑动窗口的思想，首先建立一个N个元素的数组作为滑动窗口，数组的下标与每一个存储集进行关联。首先把每个存储集的第一条记录存放到滑动窗口的数组里面，然后进行排序输出。

如果当前的记录是当前最小的记录，则将当前的存储集中的下一条记录拉取到滑动窗口中替换。如下图所示，假如第一轮中的存储集2中的记录1符合条件，最先进行输出，然后需要将存储集2中的下一条记录拉取到滑动窗口中进行下一轮输出，如果没有记录，则用NULL代替存储。

下面我们以C++为例，写一下记录和存储集的定义格式，如下。

class MenRecord{ //拉取的一条记录
    //省略定义......
  public:
    long long timestamp;
    char* pData;
};
class MemResult{ //定义结果集
      MenRecord* Read()
      {
          if(m_read_index < m_Record_Size)
             return pRecord[m_read_index++];
          return NULL;
      };
      //判断当前存储集中是否 还有未处理记录
      bool Readable() {return (m_read_index<m_Record_Size)};
private：
      int m_write_index;
      int m_read_index;
      int m_Record_Size; //记录的条数
      MenRecord* pRecord;//记录
};

接下来，我们重点实现MemDataOrderImpl类的Read方法即可。

class MemDataOrderImpl{
public:
    void Read(buffer* buff);
private:
    std::vector<MemResult*>  myMemResultVec; //所有存储集的对象
};

实现如下：

void MemDataOrderImpl::Read(buffer* buff)
{
     std::vector<MenRecord*> MemRcdVec;
     //先从每一个存储集中获得第一轮的记录数
     for(int i=0;i<myMemResultVec.size();i++)
     {
          MemRcdVec.push_back(myMemResultVec[i].Read());
     }
     //开始处理
     while(true)
     {
         //计算得到当前滑动窗口中的 最小记录
         long long ll_time_stamp = MAX_LONG;
         int m_index_for_current_round = 0; //当前轮的最小记录
         //针对当前 滑动窗口中记录 进行处理，得到最小记录
         for(int i=0;i<MemRcdVec.size();i++)
         {
              if(MemRcdVec[i])
              {
                    if(MemRcdVec[i]->timestamp < ll_time_stamp )
                    {
                        ll_time_stamp = MemRcdVec[i]->timestamp;
                        m_index_for_current_round = i;
                    }
              }
         }
         //输出当前记录，更新滑动窗口
         MemRcdVec[m_index_for_current_round] = 
          myMemResultVec[m_index_for_current_round].Read();
         //当每个存储集合中数据处理完成，跳出循环
         bool b_exit_flag = true;
         for(int i=0;i<myMemResultVec.size();i++)
         {
              if(myMemResultVec[i].Readable()) 
              {
                   b_exit_flag = false;//如果还有未处理数据
                   break;
              }
         }
         if(b_exit_flag )
              break;
     }
}

当然了，这里的代码还有很多细节可以优化的，这里就不讨论优化的细节了。现在假设，我们这里的记录很多，需要分批或者每秒钟输出N条记录，这样前端有处理和反映的时间。那么我们可以增加一个新的读取接口函数签名如下：

void Read(buffer* buff, int max_record_cnt);

我们只要在每一轮的处理后，判断是否满足max_record_cnt，如果达到该记录的数量，则break出循环，等到下一次业务层调用并读取下一批max_record_cnt记录。

最后，我们说一下，很多时候，我们内存装不下这么多数据，那么我们也可以把Read接口当成从文件中读取的接口。最终只要应用层抽象出一层接口，包括Write和Read的接口即可。

class IDataInterface{
//读取全部记录，写入缓冲区buff中
virtual void Read(buffer* buff) = 0; 
//读取最多max_record_size记录数，并写入buff中
virtual void Read(buffer* buff, int max_record_size) =0; 
//写入内存块，包括size记录数
virtual void Write(MemResult*,int size) = 0 ;
};

总结：如果记录是链表存储的，则滑动窗口可以采用最小堆的方式，每次取出堆顶记录，同时获得下一条记录。但是目前每一个记录都是数组存储的连续内存块，则只能用这种对齐方式进行处理。

数据库

文章转载自码农的修炼之道，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

一种基于滑动窗口的对齐排序算法

评论