[andrewsw]

This is probably a little too off-topic, but I'll mention it anyway:

There must be times when people don't realise the opportunity to construct the list in sorted order, depending, of course, on where the data is coming from. [What structure would help achieve this, so that it could then be inserted into a list/array?]

I suppose, in most cases, a native sort() method is very efficient, so it is simpler to just get the data and then sort() it.

But, yeah, this is probably too far at a tangent My bad!

[jon.kiparsky]

andrewsw, on 17 July 2014 - 04:15 PM, said:

This is probably a little too off-topic, but I'll mention it anyway:

There must be times when people don't realise the opportunity to construct the list in sorted order, depending, of course, on where the data is coming from. [What structure would help achieve this, so that it could then be inserted into a list/array?]

A heap is probably the best approach there. Read in the data, stick it in a heap, and then pull it out into an array. If you know you're getting all of the data at a go, this works nicely. If you're adding data later, don't worry about it, just sort it when you get it.

Quote

But, yeah, this is probably too far at a tangent My bad!

Tangents are where it's at...

[k.s110]

I'm Glad finally one of my questions did spark a conversation and not a straight BLOCK lol =] im trying everyone i seriously am...

[andrewsw]

jon said:

A heap is probably the best approach there.

A heap! That's the word I was groping for, ta

Although.. it is considered a partially ordered structure: wiki

Mmm I might look into this more tomorrow - a mini-project, or challenge (for me/someone). To construct the heap from a sequence of data, and end-up with a sorted list or array. Maybe Python. (Would a functional langauge (lazy-eval) be a winner? Dunno enough about them..)

I'm babbling now I shall desist.

[jon.kiparsky]

It's partially-ordered because its members are not guaranteed to be in order beyond satisfying the heap property. That is, an in-order traversal will not get you an ordered list. However, if you access it according to the heap discipline, you're guaranteed an ordered list, since the next item at the top of the heap is guaranteed to be the max or min, depending which way you're sorting.


A python challenge about heaps might be interesting. I would support that.

[andrewsw]

People tend to post challenges when they already have a sexy answer up their sleeve

[Skydiver]

Back in the 80's and 90's the rule of thumb was that if you had less 100 keys to search through, it was faster to do a linear search than try to do anything fancy. With the faster computers I wonder if the limit of 100 has changed.

As an aside, I got to thinking about where theoretical computer science collides with engineering like linked list vs. array by Stroustrup. Anyway along the same vein of using cache coherence, isn't there a point where thrashing the cache doing a binary search going to be slower than doing a linear search?

[andrewsw]

Really stepping outside my comfort zone here but.. aren't there ways to actually split the data into chunks and store them, physically, in different memory areas (mini caches?) so that the binary search doesn't occur against the entire structure?

It seems incongruous though, that a linear search could be faster than binary(?).

This post has been edited by andrewsw: 17 July 2014 - 04:01 PM