Сортировка дат

[Limit79]

Доброго времени суток, уважаемые форумчане! Прошу помощи со следующей задачей:

Есть некоторая структура:

Используется синтаксис C++

struct Task 
{
    int h;              // Часы
    int m;              // Минуты
    int day;    // День
    int month;  // Месяц
    int year;   // Год
}
 

Задача состоит в сортировке массива таких структур.

Первая идея - просто преобразовать дату к минутам, взяв за начальный момент времени некоторую дату, а дальше сортировать эти даты по минутам. Идея простая, но, на мой взгляд, не рациональная (или же рациональная?).

Вторая идея - сначала сортировать по году, далее в пределах одного года - по месяцу и так далее. Идея, вроде бы, хорошая, но тут проблема с самой ее реализацией. Если кто подскажет примерный алгоритм - буду премного благодарен!

Возможно, есть какие-нибудь иные способы сортировки подобной информации?
Заранее спасибо за ответы!

[Joker_vD]

Используется синтаксис C++

bool compareTasks(const Task& left, const Task& right) {
    return (left.year <= right.year)
        && (left.month <= right.month)
        && (left.day <= right.day)
        && (left.h <= right.h)
        && (left.m <= right.m);
}

Отдаете это последним аргументом в std::sort или std::stable_sort.

[Xaositect]

Если вдруг это не C++, а C, то смотреть функцию qsort, компаратор будет выглядеть например так:

int cmp_Task(const void * ptr1, const void * ptr2)
{
  struct Task * task1 = (struct Task *) ptr1;
  struct Task * task2 = (struct Task *) ptr2;
  int result = task1->year - task2->year;
  if (result) return result;
  result = task1->month - task2->month;
  if (result) return result;
  result = task1->day - task2->day;
  if (result) return result;
  result = task1->h - task2->h;
  if (result) return result;
  result = task1->m - task2->m;
  return result;
}

[venco]

Joker_vD в сообщении #741771 писал(а):

Используется синтаксис C++

bool compareTasks(const Task& left, const Task& right) {
    return (left.year <= right.year)
        && (left.month <= right.month)
        && (left.day <= right.day)
        && (left.h <= right.h)
        && (left.m <= right.m);
}

Отдаете это последним аргументом в std::sort или std::stable_sort.

Совершенно неправильная реализация. Сравнение не транзитивное, и для равных элементов вернёт true. Обе ошибки приведут к неправильной работе sort(), а то и к segfault.
Вариант Xaositect лучше, но надо адаптировать его к требованиям С++.

[_Ivana]

Не вдаваясь в особенности реализации типов и библиотечных функций в конкретных языках, скажу, что оба варианта в первом посте вполне рабочие: и перевод дат в абсолютные минуты (да-да, от Рождества Христова), что позволяет, помимо всего прочего, удобно получать временнЫе интервалы между датами простым вычитанием с последующим переводом обратно в часы/дни если надо, и запись даты в формате ГГГГММДДЧЧММ - хоть в число хоть в строку, с последующим простым сравнением или вызовом стандартной функции сортировки по одному полю.

ЗЫ в 1С7.7 есть тип "Дата", но без часов и минут, сам применял подобные варианты неоднократно для разных случаев. Да и даже когда просто в одном каталоге надо хранить несколько файлов архивов с удобной возможностью выбора по хронологии, задаю имена так

arch_20130621.zip
arch_20130622.zip
arch_20130627.zip
.....

ЗЗЫ а вообще, для сортировки массива элементов любого типа (самописной функцией, а не библиотечной), необходима и является ключевой функция сравнения двух значений этих типов на больше/меньше/равно, которая в данном случае делается тривиально.

ЗЗЗЫ и еще, нередко переменные типа флаг (0/1) на 32-разрядных машинах задают типом int, чтобы компилятор помещал ее в отдельный регистр для быстрого последующего доступа/сравнения, но в данном случае, создавать массив дат со столькими разрядами для хранения чисел от 1 до 12/24/31/60, да еще и с возможностью знака в типе, мне кажется излишне расточительным. Хотя, сейчас память дешевая, ОЗУ навалом, кто будет заботиться о таких мелочах....

[Joker_vD]

venco
Код, который я пишу в 4 утра без тестирования, редко является верным. Но чтоб написать нетранзитивное сравнение... compareTasks(t1, t2) == compareTasks(t2, t3) == true означает, что true == (compareTasks(t1, t2) && compareTasks(t2, t3)) == ((t1.year <= t2.year) && (t1.month <= t2.month) && (t1.day <= t2.day) && (t1.h <= t2.h) && (t1.m <= t2.m) && (t2.year <= t3.year) && (t2.month <= t3.month) && (t2.day <= t3.day) && (t2.h <= t3.h) && (t2.m <= t3.m)) == ((t1.year <= t3.year) && (t1.month <= t3.month) && (t1.day <= t3.day) && (t1.h <= t3.h) && (t1.m <= t3.m)) == compareTasks(t1, t3), так что с транзитивностью все в порядке. А вот со стабильностью все действительно плохо. Ну что ж:

Используется синтаксис C++

bool compareTasks(const Task& left, const Task& right) {
    return (left.year <= right.year)
        && (left.month <= right.month)
        && (left.day <= right.day)
        && (left.h <= right.h)
        && (left.m <= right.m)
        && ((left.year != right.year)
            || (left.month != right.month)
            || (left.day != right.day)
            || (left.h != right.h)
            || (left.m != right.m));
}

[EtCetera]

Четыре умножения (или просто сдвига) и четыре сложения могут оказаться и побыстрее такого количества сравнений.

Я бы предложил использовать третий вариант $\text{---}$ объединения, но этот вариант не является кроссплатформенным (во всех смыслах):

Используется синтаксис C++

struct DateInformation
{
        UnsignedInteger8 m;
        UnsignedInteger8 h;
        UnsignedInteger8 day;
        UnsignedInteger8 month;
        SignedInteger32 year;
};

union Date
{
        DateInformation dateInfo;
        SignedInteger64 dateAsInteger;
};

struct Task
{
        Date date;
};

Здесь намеренно не использовались анонимные/безымянные структуры и объединения, чтобы код не зависел от компилятора. Названия типов данных взяты из головы. Их надо заменить на применяемые в используемом компиляторе или, если он поддерживает последний стандарт (C++11), воспользоваться такими переопределениями:

Используется синтаксис C++

typedef unsigned char UnsignedInteger8;
typedef unsigned short UnsignedInteger16;
typedef unsigned int UnsignedInteger32;
typedef int SignedInteger32;
typedef unsigned long long UnsignedInteger64;
typedef long long SignedInteger64;

Функция сравнения в данном случае будет выглядеть очень просто:

Используется синтаксис C++

bool CompareTasks
        (
                const Task& task1,
                const Task& task2
        )
{
        return task1.date.dateAsInteger < task2.date.dateAsInteger;
}

Чтобы такой код работал везде, нужно учитывать порядок байт. Достигнуть этого можно и средствами программного кода (с помощью шаблонов, к примеру).
Чтобы угодить _Ivana, можно попытаться утрамбовать данные с помощью битовых полей. В 4 байта, правда, все не влезет. Но можно начать отсчитывать лета с какого-нибудь близкого к нам года (собственно, название класса намекает на то, что он вряд ли будет использоваться для работы с данными времен египетских фараонов или галактических императоров), тогда надо при взятии данных прибавлять этот год, а при изменении $\text{---}$ вычитать. На сравнении дат это никак не скажется, впрочем. Но независимый от платформы код при использовании битовых полей будет трудновато получить (разве что, воспользоваться возможностями препроцессора), так как следует учитывать еще и порядок бит.

[Joker_vD]

Вот такой ерундой пускай компилятор занимается — у него кодогенератор мощный, а у программистов есть дела и поинтереснее.

[venco]

Joker_vD в сообщении #741841 писал(а):

так что с транзитивностью все в порядке. А вот со стабильностью все действительно плохо.

Да, с транзитивностью я ошибся. Нет другого свойства: $(a\ne b) \equiv (compare(a, b) || compare(b, a))$.
Что ваш вариант даст на $compare(11/11/2012, 12/12/2011)$?

[_Ivana]

Кстати, подумал, что перевод в абсолютные минуты корректно сравнит, например 20.06.2013 02:30 и 19.06.2013 78:95 в отличие от остальных предложенных вариантов
ЗЫ и по моим прикидкам, если упаковать в 4 байта, то влезут все года от Рождества Христова до свыше 8000 лет по нашему летоисчислению.

[EtCetera]

Joker_vD

Joker_vD в сообщении #741868 писал(а):

Вот такой ерундой пускай компилятор занимается

Какой "такой"? Я много разной ерунды написал.

_Ivana

_Ivana в сообщении #741891 писал(а):

по моим прикидкам, если упаковать в 4 байта, то влезут все года от Рождества Христова до свыше 8000 лет по нашему летоисчислению

Это если использовать перевод в минуты. А если воспользоваться битовыми полями, то надо 4 бита на месяц, 5 бит на день, 5 $\text{---}$ на час и 6 $\text{---}$ на минуты. На год остается 12 бит, что дает 4096 различных значений. Довольно неплохо. Значит, в предыдущем посте я обсчитался. Все влезает и в 4 байта (с поправкой на решаемую задачу, конечно).

[_Ivana]

EtCetera, это без перевода в минуты. Можно не выделять отдельные биты на день/месяц/час, а упаковать почти "без дырок" (считая для простоты, что в любом месяце бывает 31 день), и тогда на год остается более 8000 значений. Но это уже по видимому неоправданная ловля блох. Хотя, могут быть такие условия, что это будет оправдано.

[Joker_vD]

EtCetera в сообщении #741901 писал(а):

Какой "такой"?

Как бы это поплотнее поупаковать да поменьше операций для сравнения выполнить. Этим должен оптимизатор внутри компилятора заниматься — который пишут люди, специализирующиеся на трюках уровня процессорных команд. Вот почему бы тут не воспользоваться MMX/SSE?

[EtCetera]

_Ivana

_Ivana в сообщении #741914 писал(а):

EtCetera, это без перевода в минуты.

Насколько я понимаю, "это" равносильно переводу в минуты.

Joker_vD

Joker_vD в сообщении #741917 писал(а):

Как бы это поплотнее поупаковать да поменьше операций для сравнения выполнить.

Я как раз на это и намекал. Перевод в минуты значительно проще алгоритмически, а по производительности еще не факт, что хуже. Так зачем платить больше?
Кстати говоря, Ваш второй вариант функции сравнения тоже неправильный (обратите внимание на замечание venco).

Joker_vD в сообщении #741917 писал(а):

Этим должен оптимизатор внутри компилятора заниматься — который пишут люди, специализирующиеся на трюках уровня процессорных команд.

Пока что это остается мечтой. Хотя для большинства областей и производительность, и потребление памяти не так уж важны.

Joker_vD в сообщении #741917 писал(а):

Вот почему бы тут не воспользоваться MMX/SSE?

Не знаю, я не вижу, как их тут можно использовать. Точнее, могут ли они дать выигрыш по сравнению с приведенными вариантами.

[_Ivana]

EtCetera

EtCetera в сообщении #741930 писал(а):

Насколько я понимаю, "это" равносильно переводу в минуты.

Смотря что понимать под равносильностью. Если количество возможных вариантов в 4 байтах, то да, примерно равносильно. Но перевод в минуты далеко не единственный вариант такой плотной упаковки, со своими плюсами (разница временных интервалов через простое вычитание) и минусами (необходимость отслеживания високосных лет, медленнее распаковка если нужны от каждой даты только, например, часы и т.п.). Можно придумать несколько разных плотно упакованных форматов, со своими преимуществами. Хоть те же ваши битовые поля - проблема 4096 в ближайшей перспективе не светит, а получать отдельные поля проще, чем при абсолютных минутах.