Hacker News Reader

Comment by brudgers | Hacker News Reader

[Vague response that probably misses the mark]

Your description of the problem smells a bit like job-shop scheduling. Optimizing job-shop scheduling is NP-Hard, so at best one general purpose algorithm might be better than another, but you can't determine which by simple inspection. Efficiency will vary based on the actual details of your data.

The standard approach (after managing IO) is to tune for the regularities in your data. Regularities are what makes your arbitrary data arbitrary data and not random values. Tuning the algorithm can get you a long way in the time domain. No data structure alone can get you out of NP. Good luck.

View on HN

Thank you! Absolutely, the problem I'm solving is closer to the resource-constrained project scheduling problem (RCPSP) but it's also closely related to job shop scheduling.

I've mostly focused on reducing the search space so far, but I've always wondered if there's a way to significantly accelerate range queries. My B-tree map implementation is already very fast in practice, but intuitively it seems like a data structure should be able to advantage of the fact that intervals are disjoint to greatly improve performance. For example, inversion lists take advantage of disjointedness to reduce storage cost - I'd like to do the same but for performance. Many range queries also have a minimum duration requirement, so it could be useful if a data structure could take advantage of this to quickly exclude intervals during the search.

Thanks I hadn't heard of RCPSP, but that's not surprising. My first thought was "can RCPSP be expressed as job shop scheduling?" because I have a mild interest in scheduling problems. The mathematics of scheduling provides insight into why-are-things-that-way questions when when it seems like there ought to be something better than that-way...anyway...

My intuition is that "available ranges" sounds like a sorted index and that suggests "SQLite" (or "SQLserver" etc.) as data structure. I mean if you are already building on B-trees, you're conceptually on the way to a RDBMS, just without the robust tooling and low level IO optimizations and tuning interfaces already built and tested and supported with maintenance contracts.

Or to put it another way data is always snowflake. RDBMS's are a great tool for handling snowflakes. And reasoning about them.

Of course I might be wrong about the particulars of your use case and in any organization there's NIH and politics. And maybe an RDBMS was where you started, etc. etc. It's a brownfield project.

> Many range queries also have a minimum duration requirement, so it could be useful if a data structure could take advantage of this to quickly exclude intervals during the search.

Check out priority search trees. They search two dimensions, one of them being half-open (that would be your minimum duration requirement). Depends if the other half of your queries fits the closed dimension of a priority tree or if you can adapt it to fit your needs.

The representation I suggested in https://news.ycombinator.com/item?id=41053437 takes advantage of intervals being disjoint.

> Optimizing job-shop scheduling is NP-Hard, so at best one general purpose algorithm might be better than another, but you can't determine which by simple inspection. Efficiency will vary based on the actual details of your data.

Lots of job scheduling can be solved in P. And even most instances of most NP hard problems aren't that hard to solve in practice.

Reply on news.ycombinator.com