Algorithm to compare two date time stamps

Question

I need to implement a timestamp comparison in C (not using any libraries).

I am trying to figure out an optimal algorithm as the routine is going to be used intensively.

My input data is two time stamps, a and b, each of one comprises the following:

year
month
day
hour
minute

In C pseudocode:

struct Timestamp {
    int year;
    int month;
    int day;
    int hour;
    int minute;
};

struct Timestamp a;
struct Timestamp b;

I am trying several approaches including nested if's and a switch combining each value:

int timestamp_comparison(int a, int b) {
    if(a>b) return 2;
    if(a=b) return 1;
    if(a<b) return 0;
}
...
c_year = timestamp_comparison(a.year, b.year);
c_month = timestamp_comparison(a.month, b.month);
c_day = timestamp_comparison(a.day, b.day);
c_hour = timestamp_comparison(a.hour, b.hour);
c_minute = timestamp_comparison(a.minute, b.minute);

comparison = c_year * 10000 + c_month * 1000 + c_day * 100 + c_hour * 10 + c_minute;
...

But I would like to know if there is an already algorithm I could leverage on. I do not like to use external libraries.

Answer 1

here a minor improvement:

Your PC is working in binary so base 2 is what he can best

You could replace:

comparison = c_year * 10000 + c_month * 1000 + c_day * 100 + c_hour * 10 + c_minute;

by (your values are all lower than 4) so you can:

comparison = c_year * 256 + c_month * 64 + c_day * 16 + c_hour *4 + c_minute;

Or this (less readable but 'without' arithmetic):

comparison = c_year << 8 | c_month <<6 | c_day <<4 | c_hour <<2 | c_minute;

But if you really have a speed improvement by this, can only be validated with profiling.

depending on your data it could be faster only to compare what you need:

int val;
if(1!=(val=timestamp_comparison(a.year, b.year)))
  return val;
if(1!=(val=timestamp_comparison(a.month, b.month)))
  return val;
if(1!=(val=timestamp_comparison(a.c_day, b.c_day)))
  return val;
if(1!=(val=timestamp_comparison(a.c_hour, b.c_hour)))
  return val;
return timestamp_comparison(a.c_minute, b.c_minute);

But as I mentioned above, profiling is you friend when it is about optimization.

---

P.s.

if(a>b) return 2;
if(a=b) return 1;
if(a<b) return 0;

is a bit unusual definition. More common is :

if(a>b) return value >=1
if(a=b) return 0;
if(a<b) return value <=-1

Answer 2

Instead of using return values 0, 1 and 2, I suggest to use <0, 0 and >0. This is more common, matches the semantics of strcmp etc., qsort or bsearch and can be implemented using simple subtraction and comparison with 0.

/*
 * @retval <0 if a < b
 * @retval 0 if a == b
 * @retval >0 if a > b
 */
int compare_timestamps(struct Timestamp a, struct Timestamp b)
{
    int result;

    result = a.year - b.year;
    if(result != 0) return result;

    result = a.month - b.month;
    if(result != 0) return result;

    result = a.day - b.day;
    if(result != 0) return result;

    result = a.hour - b.hour;
    if(result != 0) return result;

    result = a.minute - b.minute;

    return result;
}

As mentioned in Jim Mischel's comment, the algorithm assumes that the subtraction doesn't result in integer rollover. This is valid for normal values of month, day, hour and minute fields. It is a reasonable assumption for "usual" year values. It will not be valid for the year field if abs(a.year) + abs(b.year) > INT_MAX. To handle year values in the full range of INT_MIN..INT_MAX the algorithm would have to be changed.

Answer 3

If your struct contains its members in a sorted manner, like in your case, (year is more significant than month, and so on...) and since in a struct, members are 'most likely' to be stored in a contiguous manner:

see: Using Contiguous Memory of C Struct Members

you can try using byte by byte comparison like so:

#include <stdlib.h>

// members of struct are stored contigously
struct Timestamp
{
    int year;
    int month;
    int day;
    int hour;
    int minute;
};


int timestamp_comparison(const struct Timestamp a, const struct Timestamp b)
{
    unsigned i;
    unsigned struct_size = sizeof(struct Timestamp) / sizeof(int);
    const int* t1 = (const int*)&a;
    const int* t2 = (const int*)&b;

    // compare byte by byte
    for (i = 0; i < struct_size; i++)
    {
        if (*t1 != *t2)
            return *t1 - *t2;

        ++t1;
        ++t2;
    }

    return 0;
}

int main()
{
    // example
    struct Timestamp a = {1, 1, 2, 1, 1};
    struct Timestamp b = {1, 1, 1, 7, 1};
    int comp = timestamp_comparison(a, b);

    return 0;
}

I'm not saying this is better, than the already posted answer, just different. And for any other structs like yours, it'll work the same way.

Answer 4

When comparing the timestamps, 2 concerns come into play

Range of year

If the used range of .year is [INT_MIN...INT_MAX], avoid a.year - b.year as it may overflow.

Primary values

Are the members always in their primary range? Example: Is minute in the range 0-59?

Is so, a simple compare and returning -1,0,1 uses the common C idiom (a>b) - (a<b), something many compilers recognize and emit efficient code.

int timestamp_compare(const struct Timestamp *ts2, const struct Timestamp *ts1) {
  if (ts1->year  != ts2->year)  return (ts2->year  > ts1->year)  - (ts2->year  < ts1->year);
  if (ts1->month != ts2->month) return (ts2->month > ts1->month) - (ts2->month < ts1->month);
  if (ts1->day   != ts2->day)   return (ts2->day   > ts1->day)   - (ts2->day   < ts1->day);
  if (ts1->hour  != ts2->hour)  return (ts2->hour  > ts1->hour)  - (ts2->hour  < ts1->hour);
  return (ts2->day > ts1->day) - (ts2->day < ts1->day);
}

If not, form a linear count of minutes and then compare.

long long minutes(const struct Timestamp *ts) {
  return ((tbd_day_number(ts->year, ts->month, ts->day)*24LL + ts->hour)*60 + ts->minute;
}

int timestamp_compare(const struct Timestamp *ts2, const struct Timestamp *ts1) {
  long long m1 = minutes(ts1);
  long long m2 = minutes(ts2);
  return (m2 > m1) - (m2 < m1);
}