puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: Arthur J. O'Dwyer on 21 Jun 2005 12:19 On Tue, 21 Jun 2005, Richard Harter wrote: > > On Tue, 21 Jun 2005 13:23:53 GMT, pete <pfiland(a)mindspring.com> wrote: > [snip] >> An simple O(n*log(n)) solution for floating types >> would be to heapsort the array >> and do a sequential check for equality. > > And, of course, one can do it in O(n) time and O(1) space without the > xor trick. To quote someone (me): :D The soul of modesty! > "If the array may be rearranged then we can again find the singleton > with O(1) space and O(n) time. The general idea is to select a pivot > value and then partition the array into elements smaller than the > pivot, equal to the pivot, and larger than the pivot. If the pivot is > the singleton we are done; otherwise repeat on the partition having an > odd number of elements." Once again, signal out of the noise. Thanks for reposting this solution; I for one missed it the first time around. I think it's just the sort of solution Nilges would accept, if he were the kind of person who accepts other people's good solutions. It doesn't rely on any arithmetic operations, and if my calculations are correct :) it can be modified to use an epsilon with floating-point numbers (Nilges' most recent non-nonsensical complaint about the XOR solution). Which APL variants have XOR as an atomic operator? I can't find it in the J manual. (I was going to point out that (if XOR existed in APL) the complete XOR program would be three characters long.) -Arthur
From: Randy Howard on 21 Jun 2005 13:42 In article <1119341868.873117.107560(a)g44g2000cwa.googlegroups.com>, spinoza1111(a)yahoo.com says... > > future, comuuters running on trinary logic will dominate the > > Learn to spell. A spelling flame? After all the hundreds of typos you've posted yourself? Give us a break. > > about: > > Pretty slick. Not really, it doesn't work. > Had to beat it out you as usual. You didn't even ask him politely for it, much less "beat it out" of him. Or is this just another of your "phrase of the week" deals you're known for? > STILL fails to work for floating point systems because in FP systems > there can be >1 bitwise representation of the same n. Which can be fixed, if needed (which it is *not* in this case), and this has been explained to you before. -- Randy Howard (2reply remove FOOBAR) "I don't really care about being right you know, I just care about success." --Steve Jobs
From: Randy Howard on 21 Jun 2005 13:46 In article <1119341543.541636.99590(a)g44g2000cwa.googlegroups.com>, spinoza1111(a)yahoo.com says... > Chris Dams wrote: > > Of course not. Even if the bitwise representation is not accessible any > > language that allows division by two can easily be used to make you own > > binary representation. The algorithm will still be O(n). > > Yes, but...its execution time will be n*W, a constant (the bit width) > which is rather large. So you *still* do not understand O() notation. > The XOR solution continues to suck. No, it continues to work perfectly well for the problem described. > Once you drop the assumption of an atomic XOR, you have a BAD O(n) > algorithm. Explain how this "BAD" algorithm is worse than an O(n*n) solution. Be specific. > One that continues not to work for floating point arrays. It also doesn't work for solving FFT transforms. Neither FFT or fp was a requirement for this "puzzle". If you want to solve a floating point version of the problem, it can also be done, safely, with a little extra work that doesn't change the O() of the algorithm. -- Randy Howard (2reply remove FOOBAR) "I don't really care about being right you know, I just care about success." --Steve Jobs
From: Randy Howard on 21 Jun 2005 13:48 In article <42B814ED.559E(a)mindspring.com>, pfiland(a)mindspring.com says... > spinoza1111(a)yahoo.com wrote: > > > The XOR solution continues to suck. Once you drop the assumption of an > > atomic XOR, you have a BAD O(n) algorithm. > > The one and only BAD thing about it, > is that you didn't think of it first. LOL. He still doesn't even know why it works, or he wouldn't be asking for a proof. > The clever part of your Stupid solution is especially stupid. > You have no reason to assume that the unique value is > in the middle half of the array. Therefore on average, > your search pattern just slows everything down. You better watch out pete, your lawsuit for telling the truth is just around the corner. -- Randy Howard (2reply remove FOOBAR) "I don't really care about being right you know, I just care about success." --Steve Jobs
From: pete on 21 Jun 2005 15:14
Richard Harter wrote: > > On Tue, 21 Jun 2005 13:23:53 GMT, pete <pfiland(a)mindspring.com> wrote: > > >spinoza1111(a)yahoo.com wrote: > > (almost nothing worth quoting) > > [snip] > > >An simple O(n*log(n)) solution for floating types > >would be to heapsort the array > >and do a sequential check for equality. > > And, of course, one can do it in O(n) time and O(1) space without the > xor trick. To quote someone (me): > > "If the array may be rearranged then we can again find the singleton > with O(1) space and O(n) time. The general idea is to select a pivot > value and then partition the array into elements smaller than the > pivot, equal to the pivot, and larger than the pivot. If the pivot is > the singleton we are done; otherwise repeat on the partition having an > odd number of elements." I think that algorithm suffers from the same O(n * n) worst case as simple quick sort. It's possible that in a worst case, that all of your even sized partitions might be two elements in size. In that case, the partioning will be O(n), and the iterations will be O(n). -- pete |