Station Names - can I assume I know the list of station names beforehand?

[sternr]

The CreateMeasurements has a closed list of ~400 station names, can I use this knowledge or should I support "new" station names?

[khmarbaise]

I think the answer is no here, because the FAQ area tells this:

Q: Can I make assumptions on the names of the weather stations showing up in the data set?
A: No, while only a fixed set of station names is used by the data set generator, any solution should work with arbitrary UTF-8 station names (for the sake of simplicity, names are guaranteed to contain no ; character).

[ddimtirov]

Furthermore, performance characteristics of different algorithms would depend on the number of station names - what performs well with 150 names may not perform so well wqith 10 or 10,000 names (case in point the performance of mine would depend on the hash collisions).

Other things to take into account is that right now the test data produces even number of temperatures for each city - is that a given? Does a solution need to handle pathological cases such as 1000 cities with 1 temp each and 2 cities with ~5e8 temp records each?

I am asking because the test does not test that and the conditions do not stipulate it, so in search of best performance it is natural to try to exploit specifics of the input.

[gunnarmorling]

I understand the desire to have more specific guidance on the distribution of the data, but to keep things somewhat simple, I'd strongly prefer to not go there. Keep in mind that the primary motivation for this challenge is to provide a nucleus for folks to learn something new (and in particular help communicate that Java is a great tool for these kinds of tasks) and inspire others to learn something new, rather than "winning" per se (but yes, of course I totally can relate to that aspect).

So I think the answer to

Does a solution need to handle pathological cases such as 1000 cities with 1 temp each and 2 cities with ~5e8 temp records each

should be "Yes". Just like a real-world database engine would have to work for both cases (that spirit may help to provide guidance on questions like this). That said, I (and surely many others) would be very curious to learn about the specific considerations folks would apply when one could make certain assumptions about the data distribution, for instance in a blog post.

the test data produces even number of temperatures for each city - is that a given?

No, it's not. If that's actually the case, it's a coincidence, just a consequence of how the data generator is programmed. Again it helps to ask whether an actual DB engine working on a realworld data set could rely on this fact. In all likelihood, it couldn't.

[ddimtirov]

Jist to provide an alternative perspective, for somewhat similar process (market data), usually we assume maximum number of ticks, maximum frequency, may assume maximum deviation from base value. These things can be used for delta compression, encoding, capacity planning, and in many cases it is acceptable if the processing breaks if the real world data goes outside these assumptions. Profiling your data can give you competitive advantage. In particular, virtually no one uses a generic DBMS for this kind of latency sensitive applications.

In real world weather processing, I expect that weather stations don't pop out of the thin air, but get added through some onboarding process that may involve recalculating the hash modulus divisor.

That said, I agree with what you say, and it makes sense to require handling the general case, just I find it tricky as the algorithm will always be sensitive to the input data (e.g. bubblesort would beat quicksort for already-sorted array).

[gunnarmorling]

Gotcha, and that totally makes sense. In fact, I think that would also make for a great (just a different) challenge, as would having to retrieve the data set from disk, i.e. making it much larger than available RAM. The current constraints are a function of keeping things managable for me (it already took a fair bit of time to prepare it even in the current form, and I need to evaluate everything in finite time) and contenders (I didn't want to ask people to create an actual database ;).

[padreati]

@ddimtirov I totally agree. Somehow I came to think that I am from the same programmer species which exploits any sign of regularity to convert it into performance, memory, whatever. My assumptions were based on what @gunnarmorling defined as problem statement. I have no preference for rule other than to be fixed, precise and known to all.

[padreati]

The answer to the original question looks clear: we should not assume a fixed list. There is however a related question, which is the usage of a hash value over byte array as an identifier without collision check. I don't remember precisely, but I think that I saw in more than one place that thing. In my humble opinion that does not look right, because that kind of trick will not be allowed in production ready code.

[gunnarmorling]

Yes, exactly, this is not allowed (exactly because it wouldn't be guaranteed to work for data sets with other station names). Unfortunately, I had missed this detail when evaluating these submissions. After discussing with the authors of these submissions (@ddimtirov, @ebarlas, @royvanrijn), they are being reworked and re-submitted, no relying on hash functions specific to a given data set.

[padreati]

I feel somehow bad about it, I hope nobody gets upset because it. In my opinion I think it is reasonable to specify limits for some things like max char length for station names, max ranges for temp values, etc. In real life those limits are known or established somehow. Also, some requirements like existent ones (don't rely on fixed number of stations) are totally fine as long as they are specified somewhere. That being said, I don't believe we need to test that at execution time since there are many things to be tested, the effort is large, and most important, I totally assume that we know what we are doing, we trust each other, share everything and enjoy that challenge.

[gunnarmorling]

No need feel bad at all, it's great to see all these questions popping up.

In my opinion I think it is reasonable to specify limits for some things like max char length for station names, max ranges for temp values, etc. In real life those limits are known or established somehow.

Yepp, totally agreed. I should have done that from the get go, but well 🤷 ... . Just clarified this in the README:

Input value ranges are as follows:

• Station name: non null UTF-8 string of min length 1 character and max length 100 characters
• Temperature value: non null double between -99.9 (inclusive) and 99.9 (inclusive), always with one fractional digit

Implementations must not rely on specifics of a given data set, e.g. any valid station name as per the constraints above and any data distribution (number of measurements per station) must be supported

I think this should describe the requirements and spirit at reasonable depth?

[padreati]

I have read the README and looks more than enough for me. Best.

[gunnarmorling]

Moved this thread to a new category "Rule clarifications".

[gunnarmorling]

Note after discussing some more with @royvanrijn et al. on Twitter, I've added a limit of 10,000 distinct station names, so as to keep effort for submissions somewhat at check (also I didn't feel like having to test with 1B different ids). With this additional constraint, are we good here overall?