• Johnny Cage (unregistered) in reply to Xepol

    I heard people use pennies instead of dollars to fix the problem of floats not being exact. Is this not true?

  • Willie (unregistered) in reply to Stan Rogers

    Shell sort is awesome with its Big O funky behavior.

  • Z (unregistered) in reply to Stan Rogers
    Stan Rogers:

    Unless, like myself, you're stuck on a platform with a short call stack, in which case Shell is the only way to fly (bubble and simple insertion being the only alternatives, really, since recursion is a no-no). All we can argue about is the interval set....


    Why do you think that you need recursion for quicksort and mergesort? For quicksort, you could have a stack where you push the next interval to sort. The the procedure would be wrapped tith a loop that iterates until the stack is empty, always sorting the top partition.

    To make it really fly, you should skip pushing intervals to sort onto the stack if they are less than some constant size K (which, depending on platform&implementation, often lies between 10 and 25), and then do an insertion-sort over all of the array. This is a good thing since the constant-factor for insertion-sort is really low. If you want more info on implementing quicksort, I recommend reading Robert Sedgewicks PhD-thesis.

    Also, bubble is _never_ an alternative, insertion-sort is simpler and always more efficient.
  • Z (unregistered) in reply to Gene Wirchenko
    Gene Wirchenko:
    ZeoS:
    qsort is O(n^2) in worst case, O(nLog n ) in average.

    http://en.wikipedia.org/wiki/Quick_sort


    Big O notation is worst-case.

    Sincerely,

    Gene Wirchenko



    Yes, Big O notation is a measure worst-case behaviour, but for a function. ZeoS talks about two different functions, one being the time it takes for quicksort to run, the other being the average time quicksort takes to run. Both are valid computable functions, and can be described using Big O-notation.
  • (cs) in reply to Z
    Z:

    Why do you think that you need recursion for quicksort and mergesort? For quicksort, you could have a stack where you push the next interval to sort. The the procedure would be wrapped tith a loop that iterates until the stack is empty, always sorting the top partition.


    This would be the same as recursion, done by hand. The important thing to consider is the memory requirement for the stack.
  • some guy (unregistered)

    Seems fairly common... A teller at my bank once told me, on the hush hush, that they still calculate interest BY HAND.

  • (cs) in reply to Johnny Cage
    Anonymous:
    I heard people use pennies instead of dollars to fix the problem of floats not being exact. Is this not true?


    It is, sort of. Anyone who uses a float value to represent money in an accounting app should be fired immediately. However, what you use instead is usually a "big decimal" data type that can represent numbers of arbitrary length and precision with an explicitly specified number of fractional digits. This is usually implemented by an array of ints to hold the data and another int to say how many fractional digits to keep. That way, you can use the same code for things like exchange rates, where you need a higher number of fractional digits, and don't have to worry about overflows.
  • (cs) in reply to ammoQ
    ammoQ:
    Z:

    Why do you think that you need recursion for quicksort and mergesort? For quicksort, you could have a stack where you push the next interval to sort. The the procedure would be wrapped tith a loop that iterates until the stack is empty, always sorting the top partition.

    In fact, ANY recursive function can be rewritten to be iterative, sometimes even without a "data stack", when you have tail recursion, which is the case with heap sort. Actually, this may apply only to primitive-recursive functions (not sure), but you rarely have to deal with anything else anyway.

    Z:
    This would be the same as recursion, done by hand. The important thing to consider is the memory requirement for the stack.


    If, as in any sane sorting algorithm, the recursion depth is log(n), the memory requirement is tiny compared to the data you're sorting. The implicit stack you use implicitly with recursion may have tight limitations that make recursion unviable, but it would be a very weird system where you get a huge amount of data to sort but not one iota of additional space for an explicit stack.
  • (cs) in reply to ammoQ
    ammoQ:
    Z:

    Why do you think that you need recursion for quicksort and mergesort? For quicksort, you could have a stack where you push the next interval to sort. The the procedure would be wrapped tith a loop that iterates until the stack is empty, always sorting the top partition.

    In fact, ANY recursive function can be rewritten to be iterative, sometimes even without a "data stack", when you have tail recursion, which is the case with heap sort. Actually, this may apply only to primitive-recursive functions (not sure), but you rarely have to deal with anything else anyway.

    Z:
    This would be the same as recursion, done by hand. The important thing to consider is the memory requirement for the stack.


    If, as in any sane sorting algorithm, the recursion depth is log(n), the memory requirement is tiny compared to the data you're sorting. The implicit stack you use implicitly with recursion may have tight limitations that make recursion unviable, but it would be a very weird system where you get a huge amount of data to sort but not one iota of additional space.
  • Homer Jay (unregistered) in reply to some guy
    Anonymous:
    Seems fairly common... A teller at my bank once told me, on the hush hush, that they still calculate interest BY HAND.


    My teller told me the word 'gullible' was not in the dictionary ...
  • (cs) in reply to brazzy
    brazzy:
    Z:

    Why do you think that you need recursion for quicksort and mergesort? For quicksort, you could have a stack where you push the next interval to sort. The the procedure would be wrapped tith a loop that iterates until the stack is empty, always sorting the top partition.

    In fact, ANY recursive function can be rewritten to be iterative, sometimes even without a "data stack", when you have tail recursion, which is the case with heap sort. Actually, this may apply only to primitive-recursive functions (not sure), but you rarely have to deal with anything else anyway.

    ammoQ:
    This would be the same as recursion, done by hand. The important thing to consider is the memory requirement for the stack.


    If, as in any sane sorting algorithm, the recursion depth is log(n), the memory requirement is tiny compared to the data you're sorting. The implicit stack you use implicitly with recursion may have tight limitations that make recursion unviable, but it would be a very weird system where you get a huge amount of data to sort but not one iota of additional space.


    (correct wrong quotes)

    The memory requirement for quicksort has to consider the worst case, so it's n. If you are only sorting numbers (or pointer), the range stack can be twice as large than the array you sort. It probably doesn't hurt on a PC or server, but it can hurt e.g. on a PDA or smartphone.
  • (cs) in reply to a_villacis
    a_villacis:
    I did raise the issue about the whole purpose of the hack, that the proper place to fix it was in the mainframe, not in VB. But my bosses mentioned something about not messing with programs without proper approval - I was only authorized to fix the VB hack, not the COBOL program. I can only think the guy who wrote the original VB hack raised the exact same issue, and was met with the exact same objection.


    Bank can't afford COBOL peepz anymore?
  • (cs)

    Alex Villacis Lasso:
    My bosses were worried at first because the improved program did the task in under half a second on a 486, and thought I forgot to do some operation.

    This is my favorite part of the story.  I've repeatedly had this experience where the 'old' guy has convinced management that his code is the best possible and that it's impossible to improve upon.

  • (cs)

    The fastest quicksort implementations are usually hybrids, switching to an insert sort or bubble sort once the subset of unsorted items is four or less (something relatively short, anyway).  In fact, you could quicksort down to a certain size and leave the small (unsorted) sets for a final bubble sort pass.

    In this case, the bubble sort (or insert sort) would double as an input validation on the order of the data.  If the order assumption is correct, the validation pass requires N-1 item comparisons, performs in O(N), and stops after the first pass.  If a swap takes place, the decision can be made to continue with this inefficient (on average) algorithm or switch to quicksort, compensating for a violation of the input ordering assumption.

  • (cs) in reply to Z
    Anonymous:
    Stan Rogers:

    Unless, like myself, you're stuck on a platform with a short call stack, in which case Shell is the only way to fly (bubble and simple insertion being the only alternatives, really, since recursion is a no-no). All we can argue about is the interval set....


    Why do you think that you need recursion for quicksort and mergesort? For quicksort, you could have a stack where you push the next interval to sort. The the procedure would be wrapped tith a loop that iterates until the stack is empty, always sorting the top partition.

    To make it really fly, you should skip pushing intervals to sort onto the stack if they are less than some constant size K (which, depending on platform&implementation, often lies between 10 and 25), and then do an insertion-sort over all of the array. This is a good thing since the constant-factor for insertion-sort is really low. If you want more info on implementing quicksort, I recommend reading Robert Sedgewicks PhD-thesis.

    Also, bubble is _never_ an alternative, insertion-sort is simpler and always more efficient.


    Amazing -- I would have thought that anyone would have noticed the implied memory and language constraints in my statement. Moving the point of failure does not eliminate it. If you want to sling Sedgewick around, you might want to look at his work on Shell (with and without Incerpi). And if you thought I was seriously considering bubble or an unconstrained single-interval insertion....
  • Simon H (unregistered)
    Alex Papadimoulis:

    The bank in question (along with several others) was involved in a huge financial collapse around 1999-2000. Many people were unable to use their savings for months and months. Having seen some of the programs used internally, I suspect the less-than-ideal quality of them might have played a role in this collapse.



    That, and the political corruption, as I understand it.

    Fortunate for me who turned up in Ecuador as the collapse happened to find my money went a LOT further. Unfortunate for the 200+ campesinos (country folk) who we saw in one town lined up at the F-word Bank to try and extract their savings.
  • Z (unregistered) in reply to ammoQ
    ammoQ:
    brazzy:
    Z:

    Why do you think that you need recursion for quicksort and mergesort? For quicksort, you could have a stack where you push the next interval to sort. The the procedure would be wrapped tith a loop that iterates until the stack is empty, always sorting the top partition.

    In fact, ANY recursive function can be rewritten to be iterative, sometimes even without a "data stack", when you have tail recursion, which is the case with heap sort. Actually, this may apply only to primitive-recursive functions (not sure), but you rarely have to deal with anything else anyway.

    ammoQ:
    This would be the same as recursion, done by hand. The important thing to consider is the memory requirement for the stack.


    If, as in any sane sorting algorithm, the recursion depth is log(n), the memory requirement is tiny compared to the data you're sorting. The implicit stack you use implicitly with recursion may have tight limitations that make recursion unviable, but it would be a very weird system where you get a huge amount of data to sort but not one iota of additional space.


    (correct wrong quotes)

    The memory requirement for quicksort has to consider the worst case, so it's n. If you are only sorting numbers (or pointer), the range stack can be twice as large than the array you sort. It probably doesn't hurt on a PC or server, but it can hurt e.g. on a PDA or smartphone.


    Well, the memory-requirements for quicksort can easily be bounded by cutting off the quick-sort and switching algorithms if the sorting goes down more than, say 3*log(n) levels. This is used, for example,  in Stepanovs implementation of std::sort for C++.

    My point with using an explicit stack, is that it requires much less memory per level than using the call-stack. Also, the possible inherent limits for the call-stack are not there.
  • Z (unregistered) in reply to Stan Rogers
    Stan Rogers:
    Anonymous:
    Stan Rogers:

    Unless, like myself, you're stuck on a platform with a short call stack, in which case Shell is the only way to fly (bubble and simple insertion being the only alternatives, really, since recursion is a no-no). All we can argue about is the interval set....


    Why do you think that you need recursion for quicksort and mergesort? For quicksort, you could have a stack where you push the next interval to sort. The the procedure would be wrapped tith a loop that iterates until the stack is empty, always sorting the top partition.

    To make it really fly, you should skip pushing intervals to sort onto the stack if they are less than some constant size K (which, depending on platform&implementation, often lies between 10 and 25), and then do an insertion-sort over all of the array. This is a good thing since the constant-factor for insertion-sort is really low. If you want more info on implementing quicksort, I recommend reading Robert Sedgewicks PhD-thesis.

    Also, bubble is _never_ an alternative, insertion-sort is simpler and always more efficient.


    Amazing -- I would have thought that anyone would have noticed the implied memory and language constraints in my statement. Moving the point of failure does not eliminate it. If you want to sling Sedgewick around, you might want to look at his work on Shell (with and without Incerpi). And if you thought I was seriously considering bubble or an unconstrained single-interval insertion....


    I did not mean to sling Sedgewick around, I just wanted to give you a nice reference, beacause I really enjoyed reading his material. I'm sorry if I gave the wrong impression.

    As for bubble, I must have confused you with some other people when I wrote my reply. There has been some comments advocating using bubblesort in the thread, and I was reacting to them.

    As for memory-constraints. I do wonder what kind of application does not have log(n) space as a scratch-area to use?
  • Ben (unregistered) in reply to Gene Wirchenko

    Big O notation is worst-case.


     Hell no. Big-O is asymptotic upper bound.

  • Rain dog (unregistered) in reply to Gene Wirchenko
    Gene Wirchenko:
    ZeoS:
    qsort is O(n^2) in worst case, O(nLog n ) in average.

    http://en.wikipedia.org/wiki/Quick_sort


    Big O notation is worst-case.

    Sincerely,

    Gene Wirchenko



    No it's not.
  • nonesuch (unregistered)
    The bank in question (along with several others) was involved in a huge financial collapse around 1999-2000. Many people were unable to use their savings for months and months. Having seen some of the programs used internally, I suspect the less-than-ideal quality of them might have played a role in this collapse.

    Banks have a reputation for reliability and a reality resembling swiss cheese, I'll agree.  But the bank failures in South America were due to scams.  Uunscrupulous parties found a lending loophole that let them 'loan' each other larger and larger sums of money (akin to a multi-person check kiting ring).  Once the amounts got high enough, they grabbed the cash and vanished... quite literally to the tune of billions of dollars.  When anyone bitches about checks taking *days* to clear, blame the con artists that exploit polite society like this.


Leave a comment on “A Careful Balancing Act”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article