2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Сортировка дат
Сообщение30.06.2013, 02:34 
Доброго времени суток, уважаемые форумчане! Прошу помощи со следующей задачей:

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

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


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

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

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

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

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 03:08 
Используется синтаксис 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.

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 03:24 
Аватара пользователя
Если вдруг это не 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;
}

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 05:45 
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 лучше, но надо адаптировать его к требованиям С++.

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

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

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

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

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 15:46 
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));
}

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 16:53 
Четыре умножения (или просто сдвига) и четыре сложения могут оказаться и побыстрее такого количества сравнений. :wink:

Я бы предложил использовать третий вариант $\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{---}$ вычитать. На сравнении дат это никак не скажется, впрочем. Но независимый от платформы код при использовании битовых полей будет трудновато получить (разве что, воспользоваться возможностями препроцессора), так как следует учитывать еще и порядок бит.

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 17:30 
Вот такой ерундой пускай компилятор занимается — у него кодогенератор мощный, а у программистов есть дела и поинтереснее.

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 19:15 
Joker_vD в сообщении #741841 писал(а):
так что с транзитивностью все в порядке. А вот со стабильностью все действительно плохо.
Да, с транзитивностью я ошибся. Нет другого свойства: $(a\ne b) \equiv (compare(a, b) || compare(b, a))$.
Что ваш вариант даст на $compare(11/11/2012, 12/12/2011)$?

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

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 19:58 
Joker_vD
Joker_vD в сообщении #741868 писал(а):
Вот такой ерундой пускай компилятор занимается
Какой "такой"? Я много разной ерунды написал. :-)

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

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

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 20:12 
EtCetera в сообщении #741901 писал(а):
Какой "такой"?

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

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 20:47 
_Ivana
_Ivana в сообщении #741914 писал(а):
EtCetera, это без перевода в минуты.
Насколько я понимаю, "это" равносильно переводу в минуты.

Joker_vD
Joker_vD в сообщении #741917 писал(а):
Как бы это поплотнее поупаковать да поменьше операций для сравнения выполнить.
Я как раз на это и намекал. Перевод в минуты значительно проще алгоритмически, а по производительности еще не факт, что хуже. Так зачем платить больше?
Кстати говоря, Ваш второй вариант функции сравнения тоже неправильный (обратите внимание на замечание venco).
Joker_vD в сообщении #741917 писал(а):
Этим должен оптимизатор внутри компилятора заниматься — который пишут люди, специализирующиеся на трюках уровня процессорных команд.
Пока что это остается мечтой. Хотя для большинства областей и производительность, и потребление памяти не так уж важны.
Joker_vD в сообщении #741917 писал(а):
Вот почему бы тут не воспользоваться MMX/SSE?
Не знаю, я не вижу, как их тут можно использовать. Точнее, могут ли они дать выигрыш по сравнению с приведенными вариантами.

 
 
 
 Re: Сортировка дат
Сообщение30.06.2013, 21:55 
EtCetera
EtCetera в сообщении #741930 писал(а):
Насколько я понимаю, "это" равносильно переводу в минуты.

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

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group