C# Programmer Challenge!

[Mr. Analog]

You have a typed list of POCO objects, each contains an integer that represents a start of a range and an end of a range

What's the fastest, most efficient way of finding out of any items in that list contain ranges that overlap.

I've tried out a few solutions to this including some fairly clever Linq queries that can create tuples and compare them in lambda expressions, the trouble is it's not easy to debug nor is it particularly efficient. I went back to basics and just cast my typed list into an array and created a compare method to try to blast through the lists and find overlaps

I feel like there is a better / faster way of doing this though but it's not obvious.

SO, the challenge is: Find an efficient way of determining overlaps

NOTE: If you find it via Stack Exchange or somewhere else, post a link

[Lazybones]

Some discussion on an efficient compare method here

http://stackoverflow.com/questions/13513932/algorithm-to-detect-overlapping-periods

But nothing about optimizing the hunt though the list

[Mr. Analog]

Yep, saw that one before, it's specifically about date comparison, if you are comparing other ranges (e.g. integers) you have to build your own comparator (which I did)

I think I may have found the optimal solution for this I'm just surprised that there aren't very many mathematical formulas for doing this (though maybe I should do some more reading on set theory, I feel like I've solved this problem before using set theory).

Ugh, when did maths become important to programming!

[Tom]

Ugh, when did maths become important to programming!

My limited math knowledge is my current biggest flaw as a programmer After that comes the shotgun debugging I devolve into when I get confused and of course my lack of concentration tied to chronic fatigue but yeah, that math thing. it limits me fairly significantly in what I can do as a programmer.

[Mr. Analog]

Good thing we all have giant throbbing brains and the urge to learn stuff though

Sometimes a "fancy" high level mathematical solution isn't the best way either (aka maintainability)

[Tom]

Good thing we all have giant throbbing brains and the urge to learn stuff though

Sometimes a "fancy" high level mathematical solution isn't the best way either (aka maintainability)

Turns out fancy algorithms actually hurt my brain. so does reading mathematical formulae.

And I've been avoiding the math thing for a long time... Always struggled with basic trig for some reason.

[Mr. Analog]

Through programming I've learned to really love algebra

[Thorin]

I'm not sure there's a really efficient way of doing "period overlap" that isn't also difficult to debug.

I think you did what I would've done - create a list of the objects with pointers to all the other objects that fall within their range.  Sounds like you used Tuple to do this, where in older C# you might've had to use List of Lists.  My first instinct was to suggest KeyValuePair, but then you'd only have the key of the first object tied to a list of the other objects, which would make things harder to debug.

How big is the list of items you're processing?  Are you sure that's really a bottleneck compared to the rest of your code?

[Darren Dirt]

Yep, saw that one before, it's specifically about date comparison, if you are comparing other ranges (e.g. integers) you have to build your own comparator (which I did)

I think I may have found the optimal solution for this I'm just surprised that there aren't very many mathematical formulas for doing this (though maybe I should do some more reading on set theory, I feel like I've solved this problem before using set theory).

Ugh, when did maths become important to programming!

Bit shifting. It usually comes down to magical bit shifting.




Joking, but not entirely. It's frightening how many times I have seen "optimized" algorithms that accomplished a task that I understood and would accomplish with English-reader-friendly code, but these advanced algos used some crazy >>> and ~~ and whatever else to take advantage of the cool Maths stuff that most of us wouldn't even expect to be happening under the hood, let alone know how to nail it down. Heck, the Wikipedia page about pseudo-random number generators* (or something like that) occupied my curious mind for almost an hour then I gave up.


More on-topic -- and my brain now a bit tired, so maybe not applicable to your needs -- an idea...
Perhaps if each data "chunk" can be broken down into distinct elements, then your overlap check can utilize http://en.wikipedia.org/wiki/Element_distinctness_problem

Or http://en.wikipedia.org/wiki/Collision_detection might stir up a Eureka moment or get your brain on the right track (if there is one, i.e. some Maths-based more efficient way of accomplishing your goal)

OR look at something called http://en.wikipedia.org/wiki/Quadtree or https://en.wikipedia.org/wiki/Sweep_and_prune -- both are new to me so unsure if helpful, but mentioned @ http://stackoverflow.com/questions/1597500/human-inspector-vs-programmer-was-algorithm-to-detect-if-any-circles-overlap/1597553#1597553 )





* (IIRC it was mainly because I really wanted to "get" exactly why the simple-at-first-glance http://en.wikipedia.org/wiki/Xorshift works ; click some of the links @ http://en.wikipedia.org/wiki/List_of_random_number_generators#Pseudorandom_number_generators_.28PRNGs.29 and you'll see what I mean, the Maths behind RNG = one freakin' fascinating field of study