Как эффективно сортировать сотни тысяч вводимых данных в C ++?

Question

Предположим, у меня есть 10000+ меток времени эпохи, охватывающих месяц, которые нужно отсортировать.

В программе мне нужно отсортировать эти метки времени эпохи (состоят из 13 цифр long long int, например, 1359997200000 означает 4 февраля 2013 г. (17:00) в 16 различных дней между часами с 8:00 до 17:00, с интервалом в 10, 120 и 300 секунд.

Метки времени каждой эпохи можно преобразовать в реальное время, используя ctime

То есть, если отметка времени эпохи равна 1359964803000 (4 февраля 2013 г. 8:00:03), она будет сгруппирована в интервал 1359964800000 (4 февраля 2013 г. 8:00 : 00) и 1359964809000 (4 февраля 2013 г. 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<unsigned int> на std::vector<MyDataRecordClass>, где MyDataRecordClass - это определенное вами class или struct, которое содержит переменные-члены для значение timestamp и любую другую информацию, которую вам нужно хранить вместе с этим значением; в этом случае вам также необходимо реализовать метод operator < (const MyDataRecordClass &> const от MyDataRecordClass до return (this->_secondsSinceMidnightOnFirstDay < rhs._secondsSinceMidnightOnFirstDay);, чтобы std::sort() знал, как правильно отсортировать вектор в порядке возрастания меток времени.