Re^2: Challenge: Find median string in a list

ysth,
It turns out one of those was not safe for the reason listed below:

The N^2 is reduce to N^2 / 2 by assuming that every string up to the current string has already been tested against the current string and all that need be tested is the current string against all later strings. If you know that the current string can't be the median string, it is not safe to skip it because it may also disqualify later strings. Without doing the work, you can't know for sure.

Cheers - L~R

Comment on Re^2: Challenge: Find median string in a list

Replies are listed 'Best First'.
Re^3: Challenge: Find median string in a list by ysth (Canon) on Jul 04, 2007 at 19:56 UTC
As we discussed in the chatterbox, and you determined experimentally, it's better to remove that assumption and make the inner loop go over all the strings, but keep the bailing out when the previously determined minimum maximum distance (I chortle as I write that) is met or exceeded. The current iteration of your code still has the "next if" commented out; I don't see a reason for this.	[reply]
Re^4: Challenge: Find median string in a list by Limbic~Region (Chancellor) on Jul 05, 2007 at 01:09 UTC
ysth, Thanks. Removing the comment from next really didn't make a difference by itself. Having all the optimizations in tandem is a signficant improvement. Hopefully someone will find something completely different that is also very fast. Cheers - L~R	[reply]