Kitz ADSL Broadband Information
adsl spacer  
Support this site
Home Broadband ISPs Tech Routers Wiki Forum
 
     
   Compare ISP   Rate your ISP
   Glossary   Glossary
 
Please login or register.

Login with username, password and session length
Advanced search  

News:

Author Topic: Extremely cheap and nasty sort  (Read 84 times)

Weaver

  • Addicted Kitizen
  • *****
  • Posts: 6966
  • Retd sw dev; A&A; 4 ◊ 7km ADSL2; IPv6; Firebrick
Extremely cheap and nasty sort
« on: April 12, 2019, 01:28:28 AM »

I donít seem to have a library function in the iOS Shortcuts programming framework on my iPad that will do a sort. I just needed to write the cheapest nastiest kind of sort imaginable where code size and ease of implementation is the only consideration, as the lists that I am sorting are tiny and will always be so. Only four items in this case and it will never ever become large here as Iím listing records that are per DSL line and I only have four lines. The field values I am sorting on are strings that -ignoring some minor details - each contain an ascii decimal number that is quite short, currently it will be a mere single digit. Whatever, the cost of comparison is very low and no expensive conversion steps are involved. The bulk of the cost is overhead in the Shortcuts interpreter itself. But here the total run time is not remotely an issue given the small count.

So I wrote a bubble sort, which was surprisingly cumbersome in Shortcuts. Iím thinking though that one day I should write a proper serious grown up sort for fairly large record counts because otherwise when I come to need it it wonít be there and I will be wishing that I had done the right thing ages before.

General while( cond ) loops in Shortcuts seems to be a glaring omission. What ? Youíre joking? Well I canít see it, maybe Iím hallucinating. And there is no goto so you canít diy that way. Now in the past I have managed to kludge my way around this in certain special cases. But as far as I can see it, in the completely general case where you have a while loop where there is just some generalised test and say it happens to be the case that the count of n times round the loop could be absolutely anything and you canít even begin to roughly guess it, now in that case the only way I can see out of this nightmare is recursion. And then try praying for the tail-end recursion optimisation, and thatís a prayer that is never answered either. But in your sort here it isnít tail-end anyway. Whatís more, I suspect that recursion is not going to be very fast at all. In cases where I have kludged it because of special case guarantees, one thing I have done is used a for( i = 1 to n ) loop, even though the precise loop count is unknown, and it absolutely has to be terminated on a general test. So we have n set to an absolute worst-case maximum true loop count, and was doubly lucky in that, for the first thing, there was an n in existence and secondly the value of n was reasonably accurate, reasonably low so that it did not have to be a million miles above the true loop count value. Then all that happened was that there was an if condition inside the for loop that disabled the body of the loop when the moral equivalent of the while-test fails so it flies around the loop so many times doing zilch every time until it gets out a bit belatedly.

Two questions:
  • any tips about a good algorithm for use in the case of a slow interpreted language? - and
  • what about algorithms that are very clean and fast even with tiny data sets? Say you had a sort of a list containing a mere four items and put that inside a loop with a count of a million iterations, for the sake of argument.
Logged