Dictionary access by index

I'm not understanding why sorting by the timestamp wouldn't work.  If you have one like this

the pieces look to be in the same place, so create a Moment, grabbing the parts and then converting to a number

//2022-07-05T21:19:29.543Z
var options= {
    :year => 2022,
    :month => 07,
    :day => 05,
    :hour => 21,
    :minute => 19
}

var ts=Moment(options);

ts.value() would then give you unix time and the values would be in order.  Build an array based on that that has the small dictionary for that timestamp. Maybe two arrays as multi-dimensional ones are expensive.

I don't know, maybe we'll be enough put into dictionary as a key moment.

jim_m_58 said:

I'm not understanding why sorting by the timestamp wouldn't work.

OP tried to sort the response and ran into a watchdog timeout, so ppl are trying shortcuts, like hash-based sorting using the Monkey C dictionary type.

jim_m_58 said:

If you have one like this

the pieces look to be in the same place, so create a Moment, grabbing the parts and then converting to a number

//2022-07-05T21:19:29.543Z

For the millionth time if you're just sorting normally (i.e. not hash-based sorting) you don't have to parse anything and convert it to a number, you can just sort the timestamps using string comparison. It's literally in the design of ISO 8601 date/time strings.

https://en.wikipedia.org/wiki/ISO_8601

• Date and time values are ordered from the largest to smallest unit of time: year, month (or week), day, hour, minute, second, and fraction of second. The lexicographical order of the representation thus corresponds to chronological order, except for date representations involving negative years or time offset. This allows dates to be naturally sorted by, for example, file systems.

• Each date and time value has a fixed number of digits that must be padded with leading zeros.

When you have ISO 8601 date/time strings like this...

"2022-06-30T20:23:46.973Z"
"2022-07-22T02:06:56.544Z"

...they can literally be sorted using string comparison.

Have you ever put the date in a filename using the YYYY-MM-DD format as a prefix or suffix, so that your files would sort properly in the file system? It's literally the same concept.

It seems that the code for parsing these values and converting them to a number would be more computationally complex than the code for comparing strings. This is salient because of the watchdog timeout the OP is running into.

Comparing strings is more expensive than comparing 32 bit values, and now you do things (like even the sort) will impact the watchdog..  It's clear the dictionary isn't always sorted, or sorted the same, and using hash code doesn't really help, so another solution is needed.

jim_m_58 said:

Comparing strings is more expensive than comparing 32 bit values

But in order to get the 32-bit values, you have to parse each timestamp.

The real apples-to-apples comparison is:

A) compare two strings

vs

B) parse 2 timestamps and compare the resulting 32-bit values

The code for A) is both simpler to write (I already posted it) and undoubtedly computationally less expensive than B), since there's no parsing involving.

i.e.

A) worst case: each character of both strings has to be compared (they're both the same length)

B) best case: each character of both strings has to examined, the data has to be parsed into two 32-bit numbers, then the two numbers can be compared

From what the OP said, it sounds like the real bottleneck here is in the way that he manipulates the array at each step of the sort. I haven't really looked into the part to think about whether it could be improved.

jim_m_58 said:

It's clear the dictionary isn't always sorted, or sorted the same, and using hash code doesn't really help, so another solution is needed.

Agreed.

But you only need to create the moment once and then check the values, vs doing the string compare repeatedly.  That watch dog timer thing.

I also wouldn't be copying things around, as once you have the order instead reference the data where it is.

Have the sorted timestamps reference the keys for example

jim_m_58 said:

But you only need to create the moment once and then check the values, vs doing the string compare repeatedly. 

Good point.

It seems with two arrays you can find what you want fairly easily. Consider

var timestamps[...];

var keys[...];

you find what you are looking for in timestamps, then you use the same index to get the data using the key at the same index, without copying anything around

You get a array of the keys sorted by time, with no hashing, and little copying, so hopefully no problems with the watchdog

using unix time for the timestamps also has a memory advantage here, as that would be a simple object in the array (a Number) vs a complex object (a String)

Yeah I suggested a similar two array-based solution upthread.

My solution was actually timestamps in one array and original Dictionary.values() indices in the second array. If we combined both approaches, that would save even more memory:

timestamps array => numerical time values

"keys" / original data reference array => Dictionary.values() indices

The only slight problem I can see with this solution is that the timestamp in the OPs data has milliseconds in it, so it won't be possible to represent that as seconds since the unix epoch.

You'll need to use milliseconds since the epoch, which requires a 64-bit value. Still better than storing and comparing strings, as you pointed out.

This could be worked around by throwing away the milliseconds value, but that would be kind of a hack. If the user gets multiple notifications or events that are less than a second apart, I assume they still need to be ordered properly.