Dictionary access by index

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

_psx_ said:

have you read all post?

Have *you* read all the posts?

- Nowhere do the docs say that dictionary keys are ordered by hashcodes

- I literally showed an example where keys in a dictionary are *not* ordered by hashcodes

- As an example, someone asks if a Java HashMap is ordered by hashcode: https://stackoverflow.com/questions/2817695/how-does-java-order-items-in-a-hashmap-or-a-hashtable

The top answer:

java.util.HashMap is unordered; you can't and shouldn't assume anything beyond that.

I don't know why you'd expect Monkey C to be any different, especially because the documentation doesn't guarantee a given order. Even if it works the way you want today, it's not guaranteed to work that way tomorrow. But it doesn't work the way you want today.

var dict2 = {};

dict2.put("603d7912-948d-4a82-a746-11c1bee40755", "2");
dict2.put("ad0e4205-3a38-4aaa-8272-2edb64bd2585", "2");
dict2.put("38101bf3-eba8-4148-bf7b-f8b17f311af7", "2");
System.println(dict2);
System.println(dict2.keys());
System.println(dict2.keys()[0].hashCode());
System.println(dict2.keys()[1].hashCode());
System.println(dict2.keys()[2].hashCode());

Result (apparently not sorted by hashcode):

{38101bf3-eba8-4148-bf7b-f8b17f311af7=>2, ad0e4205-3a38-4aaa-8272-2edb64bd2585=>2, 603d7912-948d-4a82-a746-11c1bee40755=>2}
[38101bf3-eba8-4148-bf7b-f8b17f311af7, ad0e4205-3a38-4aaa-8272-2edb64bd2585, 603d7912-948d-4a82-a746-11c1bee40755]
972365912
-544704738
1742047169

Like how do I make this more clear?

The idea of using using hash sorting only works if a Monkey C dictionary ALWAYS produces keys which are sorted by hashcode.

^^ Here is literally an example of a dictionary which has keys which are NOT sorted by hashcode.

Therefore, the hash sorting idea doesn't seem like it will work.

Maybe you can implement your own data structure and algorithm to do hash-based sorting, but I don't think a Monkey C dictionary is going to do it for you.

But since we're talking about unix timestamps (seconds since the epoch) let's try unix timestamps. Note that you can tell from the output that the hashcode for a Number is the same as the Number itself. So let's see if the dictionary values() array is sorted by key value / hashcode.

Code:

var dict3 = {};
dict3.put(1658920000, "1"); // Wed Jul 27 2022 11:06:40 GMT+0000
dict3.put(1658921000, "2");
dict3.put(1658922000, "3");
dict3.put(1658923000, "4");
dict3.put(1658924000, "5");
dict3.put(1658925000, "6");
dict3.put(1658926000, "7");
dict3.put(1658927000, "8");
dict3.put(1658928000, "9");
dict3.put(1658929000, "10");

System.println(dict3);
System.println(dict3.keys());
System.println(dict3.keys()[0].hashCode());
System.println(dict3.keys()[1].hashCode());
System.println(dict3.keys()[2].hashCode());
System.println(dict3.keys()[3].hashCode());
System.println(dict3.keys()[4].hashCode());
System.println(dict3.keys()[5].hashCode());
System.println(dict3.keys()[6].hashCode());
System.println(dict3.keys()[7].hashCode());
System.println(dict3.keys()[8].hashCode());
System.println(dict3.keys()[9].hashCode());

Output:

{1658921000=>2, 1658920000=>1, 1658929000=>10, 1658928000=>9, 1658927000=>8, 1658926000=>7, 1658925000=>6, 1658924000=>5, 1658923000=>4, 1658922000=>3}
[1658921000, 1658920000, 1658929000, 1658928000, 1658927000, 1658926000, 1658925000, 1658924000, 1658923000, 1658922000]
1658921000
1658920000
1658929000
1658928000
1658927000
1658926000
1658925000
1658924000
1658923000
1658922000

Too bad the keys/hashcodes are not quite in sorted order. Idk why anyone would expect them to be, to be honest, since the data structure is called a "dictionary" and not "ordered hashmap" or something like that.

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.