如何有效地对C++中输入的数十万个数据进行排序？

Question

假设我有一个10000+ of Epoch时间戳，跨越一个月，需要排序。

在程序中，我必须将这些纪元时间戳(包含13位数的long long int，就像1359997200000表示2013年2月4日下午5:00)排序为16个不同的日期，从上午8点到下午5点，时间间隔为10、120和300秒。

可以使用ctime将每个纪元时间戳转换为实时时间

也就是说，如果纪元时间戳是1359964803000 ( 2013年2月4日8:00:03)，它将被分组为时间间隔1359964800000( 2013年2月4日8:00:00)和1359964809000 ( 2013年2月4日8:00:09)

有没有一种在C++中不用手动定义成千上万的数组就能做到这一点的有效方法？我知道这样的应用程序可以更好地应用于数据处理语言，如Matlab或R，但我希望看到一些不同的解决方案。

Answer 1

如果我对这个问题的理解是正确的，那么您可以使用单个std::vector完成此操作，在读取时间戳之后对其进行排序。排序后，您可以遍历向量一次(好吧，对于要定义的每个组大小，迭代一次)，以确定每个组在向量中的起始位置：

#include <stdio.h>
#include <vector>

unsigned int CalculateSecondsSinceMidnightOnFirstDay(int whichDay, int hours, int minutes, int seconds)
{
   unsigned int ret = seconds;
   ret += (minutes*60);
   ret += (hours*60*60);
   ret += (whichDay*24*60*60);
   return ret;
}

unsigned int CalculateGroupIDFromSeconds(unsigned int secondsSinceMidnightOnFirstDay, unsigned int secondsPerGroup)
{
   return (secondsSinceMidnightOnFirstDay/secondsPerGroup);
}

int main(int, char **)
{
   std::vector<unsigned int> rows;

   // parse out the .csv files and add the timestamps
   // into (rows) here; for this example, I'll just fake it
   rows.push_back(CalculateSecondsSinceMidnightOnFirstDay(3,  6,  2, 15));
   rows.push_back(CalculateSecondsSinceMidnightOnFirstDay(0, 18, 35, 59));
   rows.push_back(CalculateSecondsSinceMidnightOnFirstDay(2,  8, 12, 17));
   rows.push_back(CalculateSecondsSinceMidnightOnFirstDay(2,  8, 12, 18));
   rows.push_back(CalculateSecondsSinceMidnightOnFirstDay(2,  8, 12, 19));
   // ... and so on

   // Now sort the data so that all timestamps are listed in increasing order
   std::sort(rows.begin(), rows.end());

   // Now that the vector is sorted, we can calculate the offset of each group within it
   const unsigned int groupSizeInSeconds = 10;

   unsigned int prevGroupID = (unsigned int) -1;
   for (size_t i=0; i<rows.size(); i++)
   {
      unsigned int curGroupID = CalculateGroupIDFromSeconds(rows[i], groupSizeInSeconds);
      if (curGroupID != prevGroupID)
      {
         printf("Group #%u starts at index #%lu in the array\n", curGroupID, i);
         prevGroupID = curGroupID;
      }
   }

   return 0;
}

如果发现除了时间戳值之外还需要跟踪来自每个CSV行的其他数据，那么可以用std::vector<MyDataRecordClass>替换std::vector<unsigned int>，其中MyDataRecordClass是您定义的class或struct，它包含时间戳值的成员变量以及与该值保持在一起所需的任何其他信息；在这种情况下，您还需要实现MyDataRecordClass to return (this->_secondsSinceMidnightOnFirstDay < rhs._secondsSinceMidnightOnFirstDay);的operator < (const MyDataRecordClass &> const方法，以便std::sort()知道如何正确地将向量按时间戳升序排序。