puzzle
in [General Programming]
|
Prev: Algorithm book recommendation?
Next: TaskScheduler.dll
From: pete on 21 Jun 2005 10:07 pete wrote: > > spinoza1111(a)yahoo.com wrote: > > One that continues not to > > work for floating point arrays. > > Note that floating point still has nothing to do with the puzzle. > > An simple O(n*log(n)) solution for floating types > would be to heapsort the array > and do a sequential check for equality. > > So, your Stupid solution is the still the worst. The fact that the puzzle specified an O(n) solution implies that n should not be assumed to be small. /* BEGIN puzzle.c */ #include <stdio.h> #define NELEM (sizeof array / sizeof *array) #define E_TYPE float #define GT(A, B) (*(A) > *(B)) #define SWAP(A, B, T) \ ((void)(*(T) = *(A), *(A) = *(B), *(B) = *(T))) typedef E_TYPE e_type; static void siftDown2(e_type *array, size_t parent, size_t end); void heapSort2(e_type *array, size_t nmemb); int main(void) { size_t index; float array[] = {-0,-7,-1,2,-3,4,5,-6,-6,5,4,-3,2,-1,-0}; heapSort2(array, NELEM); for (index = 0; index != NELEM - 1; index += 2) { if (array[index] != array[index + 1]) { break; } } printf("The unique value is %f.\n", array[index]); return 0; } static void siftDown2(e_type *array, size_t parent, size_t end) { size_t child; e_type temp; temp = array[parent]; child = parent * 2; while (end - parent > parent) { if (GT(array + child + 1, array + child)) { ++child; } if (GT(array + child, &temp)) { array[parent] = array[child]; parent = child; child *= 2; } else { array[parent] = temp; return; } } if (end == child && GT(array + child, &temp)) { array[parent] = array[child]; array[child] = temp; } else { array[parent] = temp; } } void heapSort2(e_type *array, size_t nmemb) { size_t i; e_type temp; if (nmemb > 1) { i = --nmemb / 2; do { siftDown2(array, i, nmemb); } while (i-- != 0); SWAP(array, array + nmemb, &temp); while (--nmemb != 0) { siftDown2(array, 0, nmemb); SWAP(array, array + nmemb, &temp); } } } /* END puzzle.c */ -- pete
From: pete on 21 Jun 2005 10:10 pete wrote: > > spinoza1111(a)yahoo.com wrote: > > > One that continues not to > > work for floating point arrays. > > Note that floating point still has nothing to do with the puzzle. > > An simple O(n*log(n)) solution for floating types > would be to heapsort the array > and do a sequential check for equality. > > So, your Stupid solution is the still the worst. Excuse me, I meant say "your Stupid O(n * n) solution is the still the worst." -- pete
From: Christopher Barber on 21 Jun 2005 10:38 spinoza1111(a)yahoo.com wrote: > > Chris Dams wrote: > >>On Mon, 2005-06-20 at 00:13 -0700, spinoza1111(a)yahoo.com wrote: >> >> >>>Of course, this remains a stunning irrevelance to the fact that the XOR >>>algorithm cannot be said to be O(n), because it replaces equality in an >>>operation that is from the standpoint of big O theory not valid. You >>>have to assume that "in addition to test for equality, we can regard >>>numbers as bitwise accessible". >> >>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. XOR on 1 bit costs the same as 32 bits on 32 bit machines. It is the length of the data in units of the integer type that is important. > The XOR solution continues to suck. Once you drop the assumption of an > atomic XOR, you have a BAD O(n) algorithm. One that continues not to > work for floating point arrays. As noted earlier, you can easily canonicalize the floating point representation before applying the XOR. - Christopher
From: Randy Howard on 21 Jun 2005 10:52 In article <42B81FD0.57C2(a)mindspring.com>, pfiland(a)mindspring.com says... > pete wrote: > > > > spinoza1111(a)yahoo.com wrote: > > > > > One that continues not to > > > work for floating point arrays. > > > > Note that floating point still has nothing to do with the puzzle. > > > > An simple O(n*log(n)) solution for floating types > > would be to heapsort the array > > and do a sequential check for equality. > > > > So, your Stupid solution is the still the worst. > > Excuse me, I meant say > > "your Stupid O(n * n) solution is the still the worst." He seems to have a natural preference for n*n algorithms. Anything faster is evil, not sure why. -- Randy Howard (2reply remove FOOBAR) "I don't really care about being right you know, I just care about success." --Steve Jobs
From: Richard Harter on 21 Jun 2005 10:48
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." Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Save the Earth now!! It's the only planet with chocolate. |