Deliberately bad algorithms

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Deliberately bad algorithms

Postby Wildcard » Tue Jun 02, 2015 2:15 pm UTC

We've all experienced that warm fuzzy feeling that comes from taking a O(lg n) algorithm and replacing it with an elegant, 5-line implementation of a O(n!) algorithm....

Or maybe not.

Truthfully, I think we all strive so much for efficiency and good practices that we could have a lot of fun with this idea and perhaps get some benefit in the process.

Get the bad algorithms out of your system! Seize the bull by the horns!

Or if seizing the bull by the horns seems like too straightforward of an algorithm, then try throwing peanuts in the bull's face using a teaspoon until he stomps you into the dust and has a heart attack from overexertion.
Maybe that's still too efficient, though? :)

Rube Goldberg approaches are welcome, but what I really want to shoot for here is very simple algorithms which are astonishingly, elegantly inefficient.

I'll get the ball rolling:

Code: Select all

Stupid sort:
Start at the beginning of the list and move forward.
Compare each item to the previous item.
    If an item is smaller than the previous one, move it to the very beginning of the list and restart.
When you get all the way through the list, it will be sorted smallest to biggest.
Runs in O(2^n).

:)
There's no such thing as a funny sig.

Tub
Posts: 311
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: Deliberately bad algorithms

Postby Tub » Tue Jun 02, 2015 9:30 pm UTC

You cannot beat the simplicity and inefficiency of bogosort.

Code: Select all

bogosort:
  while the list is not sorted
    shuffle the list
  return list

Guaranteed to terminate successfully with P = 1, but it's impossible to derive an O notation since the running time has no upper bound.


A more practical example, I once replaced a sequential O(n*k) algorithm (for a small fixed k) with an OpenCL kernel that ended up being O(n*n). Initial testing proved the GPU to be faster. But as n grew larger than the amount of shaders on our GPU, performance became slightly sluggish. Oops.

Now it's a sequential O(n) step on the CPU with some O(n*k) postprocessing on the GPU and everything is fine.

User avatar
hotaru
Posts: 1021
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Deliberately bad algorithms

Postby hotaru » Tue Jun 02, 2015 11:03 pm UTC

Code: Select all

factorial = product . enumFromTo 1
isPrime n = factorial (n - 1) `mod` n == n - 1

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Deliberately bad algorithms

Postby EvanED » Wed Jun 03, 2015 12:18 am UTC

Tub wrote:Guaranteed to terminate successfully with P = 1, but it's impossible to derive an O notation since the running time has no upper bound.
You can still talk about the complexity of the average case, which would be n! iterations of the outer loop.

hotaru wrote:

Code: Select all

factorial = product . enumFromTo 1
isPrime n = factorial (n - 1) `mod` n == n - 1
Very nice

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Deliberately bad algorithms

Postby Wildcard » Wed Jun 03, 2015 3:07 am UTC

hotaru wrote:

Code: Select all

factorial = product . enumFromTo 1
isPrime n = factorial (n - 1) `mod` n == n - 1

Wow. Perfect example. It's not merely inefficient, it's actually elegantly bad. :lol: It took me several seconds to think it through and check that it's correct.

Finding a median in O(n^2):

Code: Select all

for each number in list
   if count of smaller numbers in list == (length of list - 1) / 2
      then return number
But I feel I could improve on its badness, given time. :)
There's no such thing as a funny sig.

User avatar
LucasBrown
Posts: 293
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Re: Deliberately bad algorithms

Postby LucasBrown » Wed Jun 03, 2015 3:48 am UTC

Or you could just bogosort the list and then extract the middle element.

Elegantly bad: deterministic primality test via trial division implemented in regular expressions. Uses O(n2) time and O(n) memory.

Code: Select all

import re
def isprime(n): return not re.match(r'^1?$|^(11+?)\1+$', '1'*n)

User avatar
PM 2Ring
Posts: 3619
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Deliberately bad algorithms

Postby PM 2Ring » Wed Jun 03, 2015 8:34 am UTC

hotaru wrote:

Code: Select all

factorial = product . enumFromTo 1
isPrime n = factorial (n - 1) `mod` n == n - 1


<voice="Tom Hanks">Wilson!</voice>

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Deliberately bad algorithms

Postby benneh » Wed Jun 03, 2015 5:46 pm UTC

There's the obvious:

Code: Select all

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Or, another (slightly less) stupid sort:

Code: Select all

sort (a:as) = if isSorted as' then as' else sort (as ++ [a]) where
    as' = a : sort as
sort [] = []
EDIT: Actually, I think this is O(n!). In which case, I name this algorithm 'stupider sort'.

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Deliberately bad algorithms

Postby Wildcard » Wed Jun 03, 2015 8:22 pm UTC

Hmmm, I'm not getting the syntax. What language is that? Can you write it in Java or C?

Edit: Wait, maybe I get it. I'm not sure how to do linked lists in Java, though—I'm still learning. So would the following pseudocode capture your algorithm?

Code: Select all

sort(list)
    if the list is empty return the empty list
    else
        set a = first item of the list
        set as = the rest of the list
        set as' = a followed by sort(as)
        if as' is sorted then return as'
        else return sort(as followed by a)
If so, I think you're right, that's O(n!). Nicely done :P
There's no such thing as a funny sig.

User avatar
Flumble
Yes Man
Posts: 1944
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Deliberately bad algorithms

Postby Flumble » Wed Jun 03, 2015 8:57 pm UTC

That reminds me of SlowSort (not an alias of bogosort)
http://www.c2.com/cgi/wiki?SlowSort wrote:

Code: Select all

   def slowsort(A, i, j):
      # This procedure sorts the subarray A[i]...A[j]
      if i >= j:
         return
      m = (i+j)/2
      slowsort(A, i, m)
      slowsort(A, m+1, j)
      if A[m] > A[j]:
         A[m],A[j] = A[j],A[m]
      slowsort(A, i, j-1)


It has an alledged complexity of O(nlog n)=O(e(log n)^2), which is the weirdest time complexity I've seen so far. Today I learned: that's called quasi-polynomial time.


[edit] Forgot the code tag
Last edited by Flumble on Wed Jun 03, 2015 10:51 pm UTC, edited 1 time in total.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 5497
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Deliberately bad algorithms

Postby Thesh » Wed Jun 03, 2015 9:50 pm UTC

Not the worst in terms of performance(O(n^2)), but certainly the least clever. Basically selection sort, but with a hell of a lot more swaps.

Code: Select all

void dumbsort(int *a, size_t len)
{
   int temp;
   size_t i, j;
   for(i=0; i<len-1; i++)
   {
      for (j=i+1; j<len; j++)
      {
         if (a[j] < a[i])
         {
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
         }
      }
   }
}
Last edited by Thesh on Wed Jun 03, 2015 10:04 pm UTC, edited 2 times in total.
Honesty replaced by greed, they gave us the reason to fight and bleed
They try to torch our faith and hope, spit at our presence and detest our goals

User avatar
somehow
Posts: 99
Joined: Wed Aug 14, 2013 8:31 pm UTC

Re: Deliberately bad algorithms

Postby somehow » Wed Jun 03, 2015 9:52 pm UTC

Wildcard wrote:Hmmm, I'm not getting the syntax. What language is that? Can you write it in Java or C?

Edit: Wait, maybe I get it. I'm not sure how to do linked lists in Java, though—I'm still learning. So would the following pseudocode capture your algorithm?

Code: Select all

sort(list)
    if the list is empty return the empty list
    else
        set a = first item of the list
        set as = the rest of the list
        set as' = a followed by sort(as)
        if as' is sorted then return as'
        else return sort(as followed by a)
If so, I think you're right, that's O(n!). Nicely done :P


Yes, your psuedocode correctly translates benneh's code, which was written in Haskell (as was hotaru's factorial-based primality tester).
Xenomortis wrote:O(n2) takes on new meaning when trying to find pairs of socks in the morning.

Derek
Posts: 2148
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Deliberately bad algorithms

Postby Derek » Wed Jun 03, 2015 10:00 pm UTC

Wildcard wrote:Hmmm, I'm not getting the syntax. What language is that? Can you write it in Java or C?

Edit: Wait, maybe I get it. I'm not sure how to do linked lists in Java, though—I'm still learning. So would the following pseudocode capture your algorithm?

Code: Select all

sort(list)
    if the list is empty return the empty list
    else
        set a = first item of the list
        set as = the rest of the list
        set as' = a followed by sort(as)
        if as' is sorted then return as'
        else return sort(as followed by a)
If so, I think you're right, that's O(n!). Nicely done :P

I believe it's basically the same as your stupid sort, but it works back to front instead of front to back, and uses an inefficient O(n) swap. Therefore, based on your analysis in the OP, I believe it is O(n*2^n)

EvanED
Posts: 4324
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Deliberately bad algorithms

Postby EvanED » Wed Jun 03, 2015 10:09 pm UTC

Flumble wrote:That reminds me of SlowSort (not an alias of bogosort)

For purposes of readability...

Code: Select all

def slowsort(A, i, j):
      # This procedure sorts the subarray A[i]...A[j]
      if i >= j:
         return
      m = (i+j)/2
      slowsort(A, i, m)
      slowsort(A, m+1, j)
      if A[m] > A[j]:
         A[m],A[j] = A[j],A[m]
      slowsort(A, i, j-1)

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 5497
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Deliberately bad algorithms

Postby Thesh » Wed Jun 03, 2015 10:33 pm UTC

I forgot I had already written a quickperm implementation in python:

Code: Select all

class quickperm: #Based on the QuickPerm algorithm from http://www.quickperm.org/
    def __init__(self, size):
        self.permutation = [x for x in range(size)]
        self._p = [x for x in range(size+1)]
        self._i = 1
   
    def next_permutation(self):
        if self._i >= len(self.permutation):
            return False
        self._p[self._i] -= 1
        if self._i%2 == 1:
            j = self._p[self._i]
        else:
            j = 0
        self.permutation[self._i],self.permutation[j] = self.permutation[j],self.permutation[self._i]
        self._i = 1
        while self._i < len(self._p) and self._p[self._i] == 0:
            self._p[self._i] = self._i
            self._i += 1
        return True

def is_sorted(a):
    for i in range(1, len(a)):
        if a[i] < a[i-1]:
            return False;
    return True

def permsort(a):
    perm = quickperm(len(a))
    b = [a[x] for x in perm.permutation]
    while not is_sorted(b):
        perm.next_permutation()
        b = [a[x] for x in perm.permutation]
    return b

O(n!) in the worst case.
Honesty replaced by greed, they gave us the reason to fight and bleed
They try to torch our faith and hope, spit at our presence and detest our goals

Derek
Posts: 2148
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Deliberately bad algorithms

Postby Derek » Wed Jun 03, 2015 11:05 pm UTC

Stooge sort is fun. Sort the first two thirds of the array, sort the second two thirds, sort the first two thirds again. Runs in O(n^2.7095).

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Deliberately bad algorithms

Postby Nitrodon » Wed Jun 03, 2015 11:21 pm UTC

Derek wrote:
Wildcard wrote:Hmmm, I'm not getting the syntax. What language is that? Can you write it in Java or C?

Edit: Wait, maybe I get it. I'm not sure how to do linked lists in Java, though—I'm still learning. So would the following pseudocode capture your algorithm?

Code: Select all

sort(list)
    if the list is empty return the empty list
    else
        set a = first item of the list
        set as = the rest of the list
        set as' = a followed by sort(as)
        if as' is sorted then return as'
        else return sort(as followed by a)
If so, I think you're right, that's O(n!). Nicely done :P

I believe it's basically the same as your stupid sort, but it works back to front instead of front to back, and uses an inefficient O(n) swap. Therefore, based on your analysis in the OP, I believe it is O(n*2^n)

I thought the same thing at first, but the "as" in the last line is not sorted.

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: Deliberately bad algorithms

Postby Wildcard » Wed Jun 03, 2015 11:32 pm UTC

EDIT: Ninja'd. Nice to see this topic so active. :) I'll post what I wrote anyways. As an additional note, I have a good intuitive grasp on this stuff but I'm actually only now working through Cormen from the very beginning. I haven't done any formal analysis of algorithm running times yet, so the following may look a little will probably look very peculiar to you.

Derek wrote:I believe it is O(n*2^n)
Try sorting a reverse sorted list with stupider-sort.
Spoiler:

Code: Select all

4321
    321
        21
            1
                []
                return []
            1 is sorted = true
            return 1
        21 is sorted = false
        12
            2
                []
                return []
            2 is sorted = true
            return 2
        12 is sorted = true
        return 12
    312 is sorted = false
    213
        13
            3
                []
                return []
            3 is sorted = true
            return 3
        13 is sorted = true
        return 13
    213 is sorted = false
    132
        32
            2
                []
                return []
            2 is sorted = true
            return 2
        32 is sorted = false
        23
            3
                []
                return []
            3 is sorted = true
            return 3
        23 is sorted = true
        return 23
    123 is sorted = true
    return 123
4123 is sorted = false
3214
    214
        14
            4
                []
                return []
            4 is sorted = true
            return 4
        14 is sorted = true
        return 14
    214 is sorted = false
    142
        42
            2
                []
                return []
            2 is sorted = true
            return 2
        42 is sorted = false
        24
            4
                []
                return []
            4 is sorted = true
            return 4
        24 is sorted = true
        return 24
    124 is sorted = true
    return 124
3124 is sorted = false
2143
    143
        43
            3
                []
                return []
            3 is sorted = true
            return 3
        43 is sorted = false
        34
            4
                []
                return []
            4 is sorted = true
            return 4
        34 is sorted = true
        return 34
    134 is sorted = true
    return 134
2134 is sorted = false
1432
    432
        32
            2
                []
                return []
            2 is sorted = true
            return 2
        32 is sorted = false
        23
            3
                []
                return []
            3 is sorted = true
            return 3
        23 is sorted = true
        return 23
    423 is sorted = false
    324
        24
            4
                []
                return []
            4 is sorted = true
            return 4
        24 is sorted = true
        return 24
    324 is sorted = false
    243
        43
            3
                []
                return []
            3 is sorted = true
            return 3
        43 is sorted = false
        34
            4
                []
                return []
            4 is sorted = true
            return 4
        34 is sorted = true
        return 34
    234 is sorted = true
    return 234
1234 is sorted = true
return 1234
I've shown each recursive call in its own indentation level, unless the recursive call is in a return statement (i.e. return sort(as followed by a)).
If you're sorting 54321, after you sort 4321 and check if 51234 is sorted, you then throw away all that work by just rotating the list to 43215. Then after you sort 3215 and check if 41235 is sorted, you just rotate the original list again, to 32154, and so on.

Simply put, you have 5 top-level recursive calls to sort a 4 item list before your 5 item list is sorted (worst case). You have 17 calls to sort a 16 item list before your 17 item list is sorted. And so on. Doesn't that make it O(n!)?

I can see that not all the recursive calls will be worst case running time themselves, because due to the rotation based iteration, the worst case input must have the smallest item at the end of the list. And after the first top level recursive call completes, the smallest item will become the 2nd to last item in the list and will never move backwards in the list again.

...Hmmm. Actually, I think that 23451 is the worst case running time. Or is it? Not sure. :?
There's no such thing as a funny sig.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 5497
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Deliberately bad algorithms

Postby Thesh » Thu Jun 04, 2015 12:01 am UTC

How about this one:

Code: Select all

def is_permutation(a,b):
   for i in a:
      counta = 0
      countb = 0
      for j in a:
         if i == j:
            counta += 1
      for j in b:
         if i == j:
            countb += 1
      if counta != countb:
         return False
   return True

def next_sorted_array(a, bound):
   i = len(a)-1
   a[i] += 1

   while a[i] > bound and i > 0:
      i -= 1
      a[i] += 1

   if a[i] > bound:
      return False

   while i<len(a)-1:
      a[i+1] = a[i]
      i += 1

   return True

def reallydumbsort(a):
   lbound = min(a)
   ubound = max(a)
   s = [lbound for x in range(len(a))]
   while not is_permutation(a,s):
      next_sorted_array(s,ubound)
   return s


Sorting the array [0,100,100,100,100] takes 4,598,125 iterations.
Honesty replaced by greed, they gave us the reason to fight and bleed
They try to torch our faith and hope, spit at our presence and detest our goals

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Deliberately bad algorithms

Postby phlip » Thu Jun 04, 2015 2:26 am UTC

Why make sure your iterator is only generating sorted arrays? Have it generate everything, and just make sure the sorted permutation comes first...

Code: Select all

import itertools

def sort(tosort):
  for candidate in itertools.product(range(min(tosort), max(tosort) + 1), repeat=len(tosort)):
    if any(list(tosort) == list(i) for i in itertools.permutations(candidate)):
      return list(candidate)
  else:
    raise ValueError("Could not find sorted list")
Spoiler:
Intentionally looping through the permutations of candidate to see if tosort is one, instead of vice-versa, to avoid "well, if we're looping through the permutations if tosort anyway...".

By my eye, this is something like O(2knn!n) to sort a list of n ints where each int is k bits long (ie max(a)-min(a) is O(2k)).


[edit]
Wildcard wrote:...Hmmm. Actually, I think that 23451 is the worst case running time. Or is it? Not sure. :?

5,4,3,2,1 is the slowest, it seems:
Spoiler:

Code: Select all

def issorted(a):
   return all(i<j for i,j in zip(a[:-1], a[1:]))
def stupidersort(a):
   if not a:
      return []
   while True:
      first, rest = a[0:1], a[1:]
      candidate = first + stupidersort(rest)
      if issorted(candidate):
         return candidate
      a = rest + first

import timeit, itertools, pprint
results = []
timer = timeit.Timer("stupidersort(i)", "from __main__ import stupidersort, i")
for i in itertools.permutations([1,2,3,4,5]):
   i = list(i)
   results.append((i, min(timer.repeat(number=100000))))
results.sort(key=lambda x:x[1]) # yes, using the "real" sort here... so sue me
pprint.pprint(results)

Code: Select all

[([1, 2, 3, 4, 5], 0.009999990463256836),
 ([1, 2, 3, 5, 4], 0.019999980926513672),
 ([1, 2, 4, 3, 5], 0.019999980926513672),
 ([1, 2, 5, 3, 4], 0.019999980926513672),
 ([1, 5, 2, 3, 4], 0.019999980926513672),
 ([1, 4, 2, 3, 5], 0.029999971389770508),
 ([4, 1, 2, 3, 5], 0.029999971389770508),
 ([5, 1, 2, 3, 4], 0.029999971389770508),
 ([1, 2, 4, 5, 3], 0.030000925064086914),
 ([1, 4, 2, 5, 3], 0.030000925064086914),
 ([1, 2, 5, 4, 3], 0.039999961853027344),
 ([1, 3, 2, 4, 5], 0.039999961853027344),
 ([1, 4, 5, 2, 3], 0.039999961853027344),
 ([4, 1, 2, 5, 3], 0.039999961853027344),
 ([4, 1, 5, 2, 3], 0.039999961853027344),
 ([5, 1, 2, 4, 3], 0.039999961853027344),
 ([1, 5, 2, 4, 3], 0.04000091552734375),
 ([1, 3, 2, 5, 4], 0.04999995231628418),
 ([1, 5, 4, 2, 3], 0.04999995231628418),
 ([3, 1, 2, 4, 5], 0.04999995231628418),
 ([4, 5, 1, 2, 3], 0.04999995231628418),
 ([5, 1, 4, 2, 3], 0.04999995231628418),
 ([3, 1, 2, 5, 4], 0.05000019073486328),
 ([5, 4, 1, 2, 3], 0.05000019073486328),
 ([1, 3, 4, 2, 5], 0.05000114440917969),
 ([1, 3, 5, 2, 4], 0.059999942779541016),
 ([3, 1, 4, 2, 5], 0.06000018119812012),
 ([3, 1, 5, 2, 4], 0.06000113487243652),
 ([1, 5, 3, 2, 4], 0.06999993324279785),
 ([3, 4, 1, 2, 5], 0.06999993324279785),
 ([3, 5, 1, 2, 4], 0.06999993324279785),
 ([1, 3, 4, 5, 2], 0.07000017166137695),
 ([3, 1, 4, 5, 2], 0.07000088691711426),
 ([5, 1, 3, 2, 4], 0.07000088691711426),
 ([5, 3, 1, 2, 4], 0.07000088691711426),
 ([1, 3, 5, 4, 2], 0.07999992370605469),
 ([4, 3, 1, 2, 5], 0.07999992370605469),
 ([3, 1, 5, 4, 2], 0.08000016212463379),
 ([1, 4, 3, 2, 5], 0.0800008773803711),
 ([4, 1, 3, 2, 5], 0.0800008773803711),
 ([3, 4, 1, 5, 2], 0.0800011157989502),
 ([1, 4, 3, 5, 2], 0.08999991416931152),
 ([1, 5, 3, 4, 2], 0.08999991416931152),
 ([3, 4, 5, 1, 2], 0.09000015258789062),
 ([5, 1, 3, 4, 2], 0.09000015258789062),
 ([2, 1, 3, 4, 5], 0.09000086784362793),
 ([4, 1, 3, 5, 2], 0.09000110626220703),
 ([1, 4, 5, 3, 2], 0.10000085830688477),
 ([2, 1, 3, 5, 4], 0.10000085830688477),
 ([3, 5, 1, 4, 2], 0.10000085830688477),
 ([5, 3, 1, 4, 2], 0.10000085830688477),
 ([4, 3, 1, 5, 2], 0.10000109672546387),
 ([3, 5, 4, 1, 2], 0.1100008487701416),
 ([4, 1, 5, 3, 2], 0.1100008487701416),
 ([5, 3, 4, 1, 2], 0.1100008487701416),
 ([1, 5, 4, 3, 2], 0.1100010871887207),
 ([2, 1, 5, 3, 4], 0.1100010871887207),
 ([4, 3, 5, 1, 2], 0.1100010871887207),
 ([4, 5, 1, 3, 2], 0.1100010871887207),
 ([5, 1, 4, 3, 2], 0.1100010871887207),
 ([2, 3, 1, 4, 5], 0.12000083923339844),
 ([2, 5, 1, 3, 4], 0.12000083923339844),
 ([2, 1, 4, 3, 5], 0.12000107765197754),
 ([2, 4, 1, 3, 5], 0.12000107765197754),
 ([4, 5, 3, 1, 2], 0.12000107765197754),
 ([5, 4, 1, 3, 2], 0.12000107765197754),
 ([5, 2, 1, 3, 4], 0.13000106811523438),
 ([5, 4, 3, 1, 2], 0.13000106811523438),
 ([2, 1, 4, 5, 3], 0.1400008201599121),
 ([2, 3, 1, 5, 4], 0.1400008201599121),
 ([2, 3, 4, 1, 5], 0.1400010585784912),
 ([2, 4, 1, 5, 3], 0.1400010585784912),
 ([4, 2, 1, 3, 5], 0.14000201225280762),
 ([2, 1, 5, 4, 3], 0.15000104904174805),
 ([2, 3, 5, 1, 4], 0.15000200271606445),
 ([2, 3, 4, 5, 1], 0.16000103950500488),
 ([2, 4, 5, 1, 3], 0.16000103950500488),
 ([2, 5, 1, 4, 3], 0.16000103950500488),
 ([2, 5, 3, 1, 4], 0.16000103950500488),
 ([4, 2, 1, 5, 3], 0.1600019931793213),
 ([2, 5, 4, 1, 3], 0.17000198364257812),
 ([5, 2, 1, 4, 3], 0.17000198364257812),
 ([2, 4, 3, 1, 5], 0.18000102043151855),
 ([4, 2, 5, 1, 3], 0.18000102043151855),
 ([3, 2, 1, 4, 5], 0.18000197410583496),
 ([5, 2, 3, 1, 4], 0.18000197410583496),
 ([5, 2, 4, 1, 3], 0.18000197410583496),
 ([2, 3, 5, 4, 1], 0.1900019645690918),
 ([2, 5, 3, 4, 1], 0.20000195503234863),
 ([3, 2, 4, 1, 5], 0.20000195503234863),
 ([4, 2, 3, 1, 5], 0.20000195503234863),
 ([4, 5, 2, 1, 3], 0.20000195503234863),
 ([2, 4, 3, 5, 1], 0.21000194549560547),
 ([3, 2, 1, 5, 4], 0.21000194549560547),
 ([3, 2, 5, 1, 4], 0.2200019359588623),
 ([5, 2, 3, 4, 1], 0.2200019359588623),
 ([5, 4, 2, 1, 3], 0.2200019359588623),
 ([2, 4, 5, 3, 1], 0.23000192642211914),
 ([3, 2, 4, 5, 1], 0.23000192642211914),
 ([4, 2, 3, 5, 1], 0.23000192642211914),
 ([3, 5, 2, 1, 4], 0.24000310897827148),
 ([2, 5, 4, 3, 1], 0.2500019073486328),
 ([3, 4, 2, 1, 5], 0.2500019073486328),
 ([3, 2, 5, 4, 1], 0.2500021457672119),
 ([4, 2, 5, 3, 1], 0.2500030994415283),
 ([5, 2, 4, 3, 1], 0.26000189781188965),
 ([5, 3, 2, 1, 4], 0.26000213623046875),
 ([4, 5, 2, 3, 1], 0.2700018882751465),
 ([3, 4, 2, 5, 1], 0.2700028419494629),
 ([3, 5, 2, 4, 1], 0.29000210762023926),
 ([4, 3, 2, 1, 5], 0.29000282287597656),
 ([5, 4, 2, 3, 1], 0.29000282287597656),
 ([5, 3, 2, 4, 1], 0.3000028133392334),
 ([3, 4, 5, 2, 1], 0.31000280380249023),
 ([4, 3, 2, 5, 1], 0.31000304222106934),
 ([3, 5, 4, 2, 1], 0.330003023147583),
 ([5, 3, 4, 2, 1], 0.34000277519226074),
 ([4, 3, 5, 2, 1], 0.34000396728515625),
 ([4, 5, 3, 2, 1], 0.37000298500061035),
 ([5, 4, 3, 2, 1], 0.3900032043457031)]
Alternatively, counting iterations:

Code: Select all

def issorted(a):
   return all(i<j for i,j in zip(a[:-1], a[1:]))
def stupidersort(a):
   if not a:
      return []
   while True:
      global count
      count += 1
      first, rest = a[0:1], a[1:]
      candidate = first + stupidersort(rest)
      if issorted(candidate):
         return candidate
      a = rest + first

import itertools, pprint
results = []
for i in itertools.permutations([1,2,3,4,5]):
   count = 0
   stupidersort(list(i))
   results.append((i, count))
results.sort(key=lambda x:x[1])
pprint.pprint(results)

Code: Select all

[((1, 2, 3, 4, 5), 5),
 ((1, 2, 3, 5, 4), 7),
 ((1, 2, 5, 3, 4), 8),
 ((1, 5, 2, 3, 4), 9),
 ((1, 2, 4, 3, 5), 10),
 ((5, 1, 2, 3, 4), 10),
 ((1, 4, 2, 3, 5), 11),
 ((4, 1, 2, 3, 5), 12),
 ((1, 2, 4, 5, 3), 13),
 ((1, 4, 2, 5, 3), 14),
 ((1, 2, 5, 4, 3), 15),
 ((4, 1, 2, 5, 3), 15),
 ((1, 4, 5, 2, 3), 16),
 ((1, 5, 2, 4, 3), 16),
 ((1, 3, 2, 4, 5), 17),
 ((4, 1, 5, 2, 3), 17),
 ((5, 1, 2, 4, 3), 17),
 ((1, 5, 4, 2, 3), 18),
 ((3, 1, 2, 4, 5), 18),
 ((4, 5, 1, 2, 3), 19),
 ((5, 1, 4, 2, 3), 19),
 ((1, 3, 2, 5, 4), 21),
 ((5, 4, 1, 2, 3), 21),
 ((3, 1, 2, 5, 4), 22),
 ((1, 3, 4, 2, 5), 23),
 ((1, 3, 5, 2, 4), 23),
 ((3, 1, 4, 2, 5), 24),
 ((3, 1, 5, 2, 4), 24),
 ((1, 5, 3, 2, 4), 26),
 ((3, 4, 1, 2, 5), 26),
 ((3, 5, 1, 2, 4), 26),
 ((5, 1, 3, 2, 4), 27),
 ((1, 3, 4, 5, 2), 28),
 ((3, 1, 4, 5, 2), 29),
 ((5, 3, 1, 2, 4), 29),
 ((1, 4, 3, 2, 5), 30),
 ((3, 4, 1, 5, 2), 31),
 ((4, 1, 3, 2, 5), 31),
 ((1, 3, 5, 4, 2), 32),
 ((2, 1, 3, 4, 5), 33),
 ((3, 1, 5, 4, 2), 33),
 ((4, 3, 1, 2, 5), 33),
 ((1, 4, 3, 5, 2), 35),
 ((1, 5, 3, 4, 2), 35),
 ((3, 4, 5, 1, 2), 35),
 ((3, 5, 1, 4, 2), 35),
 ((4, 1, 3, 5, 2), 36),
 ((5, 1, 3, 4, 2), 36),
 ((4, 3, 1, 5, 2), 38),
 ((5, 3, 1, 4, 2), 38),
 ((2, 1, 3, 5, 4), 39),
 ((3, 5, 4, 1, 2), 39),
 ((1, 4, 5, 3, 2), 40),
 ((4, 1, 5, 3, 2), 41),
 ((4, 3, 5, 1, 2), 42),
 ((5, 3, 4, 1, 2), 42),
 ((2, 1, 5, 3, 4), 43),
 ((4, 5, 1, 3, 2), 43),
 ((1, 5, 4, 3, 2), 44),
 ((2, 1, 4, 3, 5), 45),
 ((2, 5, 1, 3, 4), 45),
 ((5, 1, 4, 3, 2), 45),
 ((2, 3, 1, 4, 5), 46),
 ((2, 4, 1, 3, 5), 47),
 ((4, 5, 3, 1, 2), 47),
 ((5, 4, 1, 3, 2), 47),
 ((5, 2, 1, 3, 4), 50),
 ((5, 4, 3, 1, 2), 51),
 ((2, 1, 4, 5, 3), 53),
 ((2, 3, 1, 5, 4), 54),
 ((2, 3, 4, 1, 5), 54),
 ((2, 4, 1, 5, 3), 55),
 ((4, 2, 1, 3, 5), 56),
 ((2, 3, 5, 1, 4), 58),
 ((2, 1, 5, 4, 3), 59),
 ((2, 4, 5, 1, 3), 59),
 ((2, 5, 1, 4, 3), 61),
 ((2, 3, 4, 5, 1), 63),
 ((2, 5, 3, 1, 4), 64),
 ((4, 2, 1, 5, 3), 64),
 ((2, 5, 4, 1, 3), 65),
 ((5, 2, 1, 4, 3), 66),
 ((2, 4, 3, 1, 5), 68),
 ((4, 2, 5, 1, 3), 68),
 ((5, 2, 3, 1, 4), 69),
 ((3, 2, 1, 4, 5), 70),
 ((5, 2, 4, 1, 3), 70),
 ((2, 3, 5, 4, 1), 71),
 ((4, 5, 2, 1, 3), 76),
 ((2, 4, 3, 5, 1), 77),
 ((2, 5, 3, 4, 1), 77),
 ((4, 2, 3, 1, 5), 77),
 ((3, 2, 4, 1, 5), 78),
 ((3, 2, 1, 5, 4), 80),
 ((5, 2, 3, 4, 1), 82),
 ((5, 4, 2, 1, 3), 82),
 ((3, 2, 5, 1, 4), 84),
 ((4, 2, 3, 5, 1), 86),
 ((2, 4, 5, 3, 1), 87),
 ((3, 2, 4, 5, 1), 87),
 ((3, 5, 2, 1, 4), 92),
 ((3, 4, 2, 1, 5), 94),
 ((2, 5, 4, 3, 1), 95),
 ((4, 2, 5, 3, 1), 96),
 ((3, 2, 5, 4, 1), 97),
 ((5, 2, 4, 3, 1), 100),
 ((5, 3, 2, 1, 4), 100),
 ((3, 4, 2, 5, 1), 103),
 ((4, 5, 2, 3, 1), 104),
 ((3, 5, 2, 4, 1), 105),
 ((4, 3, 2, 1, 5), 110),
 ((5, 4, 2, 3, 1), 112),
 ((5, 3, 2, 4, 1), 113),
 ((3, 4, 5, 2, 1), 116),
 ((4, 3, 2, 5, 1), 119),
 ((3, 5, 4, 2, 1), 126),
 ((4, 3, 5, 2, 1), 132),
 ((5, 3, 4, 2, 1), 134),
 ((4, 5, 3, 2, 1), 144),
 ((5, 4, 3, 2, 1), 154)]

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 5497
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Deliberately bad algorithms

Postby Thesh » Thu Jun 04, 2015 3:28 am UTC

I really should learn more of the Python library functions, but yeah, that does make a lot more sense; a lot cleaner than my function to check if it's a permutation.
Honesty replaced by greed, they gave us the reason to fight and bleed
They try to torch our faith and hope, spit at our presence and detest our goals

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Deliberately bad algorithms

Postby benneh » Thu Jun 04, 2015 8:42 am UTC

For anyone confused by my 'stupider sort' algorithm, it is essentially just this:

Code: Select all

stupiderSort list:
    for perm in permutations(list):
        if perm is sorted:
            return perm

I was originally going for something O(n^n), by doing something similar to phlip. After seeing phlip's solution, I've come up with this, which I'm fairly sure is O(n^n) (phlip, are you sure yours isn't at least as bad as this?):

Code: Select all

stupidestSort list:
    for candidate in list^(length list):
        if candidate is sorted and candidate is a permutation of list:
            return candidate
"list^n" is the collection of all lists of length n consisting of elements of 'list'.

If you want to go really over the top, you could provide a method of determining whether a list is sorted which then recalls your list sorting algorithm:
Spoiler:

Code: Select all

import Prelude hiding (minimum)

import Control.Applicative (liftA2)
import Data.List (permutations)

stupidesterSort :: (Ord a) => [a] -> [a]
stupidesterSort as = find' (\ bs -> isSorted bs && bs `elem` permutations as) (listPower (length as) as)

listPower :: Int -> [a] -> [[a]]
listPower n as = foldr (liftA2 (:)) [[]] (replicate n as)

isSorted :: (Ord a) => [a] -> Bool
isSorted [] = True
isSorted [_] = True
isSorted (a:as) = a <= minimum as && isSorted as

minimum :: (Ord a) => [a] -> a
minimum = head . sort

find' :: (a -> Bool) -> [a] -> a
find' condition = head . filter condition
This is essentially the same as stupidestSort, but with a small modification. In order to check that a list is sorted, it checks that the first element is less than or equal to the minimum of the rest of the list, then checks that the rest of the list is sorted. But to find the minimum of a list, it sorts the list (!) and returns the first element. I have no idea how to work out the running time of that monstrosity. It can sort a 5 element list in less than a second, but I started sorting a 6 element list when I started writing this post, and it hasn't finished yet.

EDIT: For a maximum balance of simplicity and inefficiency:

Code: Select all

sort(list):
    if length(list) < 2:
        return list
    else:
        if head(list) <= minimum(tail(list)):
            return head(list) followed by sort(tail(list))
        else:
            return sort(tail(list) followed by head(list))

minimum(list):
    return head(sort(list))

EDIT: The 6 element list took just over 3 hours to sort.

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Deliberately bad algorithms

Postby phlip » Thu Jun 04, 2015 2:19 pm UTC

benneh wrote:O(n^n) (phlip, are you sure yours isn't at least as bad as this?)

Well, in mine the "n"s aren't quite measuring the same thing... so it's O(k'^n) loops of the main loop where k' is the range of the list (max minus min) and n is the length. Except complexities are usually given in terms of the length, not just the number of values, so k'=2k (ie max minus min is k bits long), and the outer loop runs O(2kn) times. Inside that it loops through every permutation of a list of length n, O(n!), and inside that it checks if two lists of length n are equal, O(n). Hence the full O(2knn!n) I came up with.

benneh wrote:<horrific sort/minimum recursive mess>
I like it. Essentially an inefficient selection sort, but where the "selection" step is in turn defined recursively using sort...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Deliberately bad algorithms

Postby benneh » Thu Jun 04, 2015 5:15 pm UTC

phlip wrote:Well, in mine the "n"s aren't quite measuring the same thing... so it's O(k'^n) loops of the main loop where k' is the range of the list (max minus min) and n is the length. Except complexities are usually given in terms of the length, not just the number of values, so k'=2k (ie max minus min is k bits long), and the outer loop runs O(2kn) times. Inside that it loops through every permutation of a list of length n, O(n!), and inside that it checks if two lists of length n are equal, O(n). Hence the full O(2knn!n) I came up with.
Ah, I see. So if the length of the list is significantly larger than the range, duplicates become inevitable, which don't inconvenience your algorithm as much, and your algorithm performs better than mine; whereas if the range is significantly larger than the length of your list, your algorithm produces far more unnecessary 'permutations' to check, and my algorithm performs better than yours.

In a similar vein, a number is prime if it has no non-trivial prime factors, right?

Code: Select all

isPrime n = length (filter (\ k -> isPrime k && n `mod` k == 0) [2 .. n-1]) == 0

User avatar
Flumble
Yes Man
Posts: 1944
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Deliberately bad algorithms

Postby Flumble » Thu Jun 04, 2015 6:28 pm UTC

benneh wrote:In a similar vein, a number is prime if it has no non-trivial prime factors, right?

Code: Select all

isPrime n = length (filter (\ k -> isPrime k && n `mod` k == 0) [2 .. n-1]) == 0

You're evil.

Then again, real-life Haskell will optimize the shit out of that line. The only inefficiency left is that it checks for factors larger than √n.

A quick test to see if an integer is even:

Code: Select all

isEven n = (lcm n 2) == n
   where lcm a b = minimum (intersect [a,2*a..b*a] [b,2*b..a*b])

(Sorry for the finite lists; haskell wants to iterate over one of the lists completely, instead of doing a 'diagonal' search.)

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Deliberately bad algorithms

Postby benneh » Thu Jun 04, 2015 7:07 pm UTC

Flumble wrote:You're evil.

Then again, real-life Haskell will optimize the shit out of that line. The only inefficiency left is that it checks for factors larger than √n.
Thank you :). My tests indicate that GHC doesn't optimise it much at all, though. I wrote a quick program to print out a list of prime numbers using that algorithm; after 2 hours, it's got up to 37.

User avatar
hotaru
Posts: 1021
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Deliberately bad algorithms

Postby hotaru » Thu Jun 04, 2015 11:56 pm UTC

benneh wrote:My tests indicate that GHC doesn't optimise it much at all, though.

speaking of things that GHC doesn't optimize much at all...

Code: Select all

loeb = fix (fmap . flip id =<<)

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

User avatar
Flumble
Yes Man
Posts: 1944
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Deliberately bad algorithms

Postby Flumble » Fri Jun 05, 2015 12:48 am UTC

benneh wrote:My tests indicate that GHC doesn't optimise it much at all, though. I wrote a quick program to print out a list of prime numbers using that algorithm; after 2 hours, it's got up to 37.

I was promised (maybe not exactly promised) by my professor that GHC would cache all the intermediate results of isPrime and short-cut the list-building. Although, it appears that GHCi doesn't know that a list, once non-empty, can never reach a length of 0. (not.).any /= (((==0).length).).filter in manner of execution.

Derek
Posts: 2148
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Deliberately bad algorithms

Postby Derek » Fri Jun 05, 2015 1:58 am UTC

Flumble wrote:
benneh wrote:My tests indicate that GHC doesn't optimise it much at all, though. I wrote a quick program to print out a list of prime numbers using that algorithm; after 2 hours, it's got up to 37.

I was promised (maybe not exactly promised) by my professor that GHC would cache all the intermediate results of isPrime and short-cut the list-building. Although, it appears that GHCi doesn't know that a list, once non-empty, can never reach a length of 0. (not.).any /= (((==0).length).).filter in manner of execution.

Memoization is not free. It can result in significant speedups, but can also consume significant memory if applied naively. I sort of doubt that any compiler could decide automatically whether to memoize or not in all situations.

I was doing an Euler problem once, one of the harder ones, and wrote some code to memoize the results of a function. It very quickly consumed all the memory on my system. I had to go back and break up the function so that it had one part that could be effectively memoized, and the rest was not.

User avatar
benneh
Posts: 74
Joined: Tue Aug 26, 2008 8:24 am UTC

Re: Deliberately bad algorithms

Postby benneh » Sat Jun 06, 2015 5:17 pm UTC

hotaru wrote:speaking of things that GHC doesn't optimize much at all...

Code: Select all

loeb = fix (fmap . flip id =<<)
What is this supposed to do?

User avatar
hotaru
Posts: 1021
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Deliberately bad algorithms

Postby hotaru » Sun Jun 07, 2015 3:18 am UTC

benneh wrote:
hotaru wrote:speaking of things that GHC doesn't optimize much at all...

Code: Select all

loeb = fix (fmap . flip id =<<)
What is this supposed to do?

if you replace fmap with map and look at the type signature, it's usual use (as a "spreadsheet" function) should become apparent:

Code: Select all

loeb $ const 0 : const 1 : map (\n xs -> (xs !! n) + (xs !! succ n)) [0..]


but it can also be used with other things, not just lists.

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

User avatar
LucasBrown
Posts: 293
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

Re: Deliberately bad algorithms

Postby LucasBrown » Sun Jun 07, 2015 9:51 am UTC

Could you explain that for people who don't know Haskell?

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Deliberately bad algorithms

Postby phlip » Sun Jun 07, 2015 10:18 am UTC

Spoilered for offtopic (ie not deliberately bad)
Spoiler:
It's kinda the "fix" function lifted over a list of functions... a more readable version (for people that don't Haskell) could be written like how "fix" is written:

Code: Select all

fix f = x
  where x = f x

loeb fs = x
  where x = [f x | f <- fs]

That is, fix calls a function with the parameter being the return value from the same function (thanks to lazy evaluation)... essentially finding a fixed point of the function. So, for instance:

Code: Select all

f x = [0] ++ (map (+1) x)
fix f -- returns [0, 1, 2, 3, 4, ...]
You can see that if you take that resulting list, and pass it to f, you get the same list back out.

"loeb" does the same thing, to a list of functions:

Code: Select all

fs = [const 1, head, length]
loeb fs -- returns [1, 1, 3]
Those three functions, when passed the resulting list, return 1, 1 and 3, so that's the list.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Derek
Posts: 2148
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Deliberately bad algorithms

Postby Derek » Sun Jun 07, 2015 8:10 pm UTC

One thing that has always bugged me about Haskell is the community's fetish for point free function definitions, resulting in the most unreadable mess of symbols since APL. This,

Code: Select all

loeb = fix (fmap . flip id =<<)


is unreadable, and should never be used outside of a golf competition. This,

Code: Select all

loeb fs = x
  where x = [f x | f <- fs]


Is perfectly readable to anyone who has seen list comprehensions before (and can probably be understood by many people who haven't), and didn't even need to use helper functions that the reader also needs to understand.

User avatar
hotaru
Posts: 1021
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Deliberately bad algorithms

Postby hotaru » Sun Jun 07, 2015 10:14 pm UTC

Derek wrote:One thing that has always bugged me about Haskell is the community's fetish for point free function definitions, resulting in the most unreadable mess of symbols since APL. This,

Code: Select all

loeb = fix (fmap . flip id =<<)


is unreadable, and should never be used outside of a golf competition. This,

Code: Select all

loeb fs = x
  where x = [f x | f <- fs]


Is perfectly readable to anyone who has seen list comprehensions before (and can probably be understood by many people who haven't), and didn't even need to use helper functions that the reader also needs to understand.

that doesn't actually work, tho:

Code: Select all

f g = loeb . flip (,) (g . fst)


also, this happened.

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

DR6
Posts: 171
Joined: Thu Nov 01, 2012 1:44 pm UTC

Re: Deliberately bad algorithms

Postby DR6 » Sun Jun 21, 2015 10:47 pm UTC

Derek wrote:One thing that has always bugged me about Haskell is the community's fetish for point free function definitions, resulting in the most unreadable mess of symbols since APL. This,

Code: Select all

loeb = fix (fmap . flip id =<<)


is unreadable, and should never be used outside of a golf competition. This,

Code: Select all

loeb fs = x
  where x = [f x | f <- fs]


Is perfectly readable to anyone who has seen list comprehensions before (and can probably be understood by many people who haven't), and didn't even need to use helper functions that the reader also needs to understand.


Only your example only works for lists. Try:

Code: Select all

loeb fs = x
    where x = fmap ($x) fs


As long as you know what the ($x) means, it's pretty understandable. Otherwise, I get your point: I have no idea what on earth fmap . flip id =<< is supposed to do.

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Deliberately bad algorithms

Postby phlip » Mon Jun 22, 2015 12:36 am UTC

DR6 wrote:Only your example only works for lists.

That's because I was explicitly trying to write something that would be readable to someone unfamiliar with Haskell, and a list comprehension fills that role better than map. Agreed that "fmap ($x)" is better if you have a passing familiarity for the language.

DR6 wrote:Otherwise, I get your point: I have no idea what on earth fmap . flip id =<< is supposed to do.

You can get a bit of a head-start by recognising that ($) is equivalent to "id" restricted to functions. So the ($x) in your version is equivalent to "flip id x".

From there you some manipulations to make it point-free, so it can use "fix" rather than explicit self reference, and that's where you end up.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Deliberately bad algorithms

Postby Yakk » Mon Jun 22, 2015 5:30 pm UTC

benneh wrote:I have no idea how to work out the running time of that monstrosity. It can sort a 5 element list in less than a second, but I started sorting a 6 element list when I started writing this post, and it hasn't finished yet.

EDIT: For a maximum balance of simplicity and inefficiency:

Code: Select all

sort(list):
    if length(list) < 2:
        return list
    else:
        if head(list) <= minimum(tail(list)):
            return head(list) followed by sort(tail(list))
        else:
            return sort(tail(list) followed by head(list))

minimum(list):
    return head(sort(list))

EDIT: The 6 element list took just over 3 hours to sort.

Strange. I'm getting merely n! from that:

Code: Select all

Let S(n) be the cost of sorting n elements.

Let S(n,m) be the cost where the first element is m away from the right place.
S(n) <= S(n, n-1)

S(1) = 1
S(n,0) <= 1 + 2S(n-1) (the case where head(list)<=min(tail(list)))
S(n,k) <= 1 + S(n-1) + S(n, k-1) (otherwise)

So S(n) <= n + (n+1) S(n-1)

which works out to (n+1)! no?

So the n=6 case should be only 7 times slower than the n=5 case.

What did I miss?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
hotaru
Posts: 1021
Joined: Fri Apr 13, 2007 6:54 pm UTC

Re: Deliberately bad algorithms

Postby hotaru » Mon Jun 22, 2015 9:14 pm UTC

DR6 wrote:

Code: Select all

loeb fs = x
    where x = fmap ($x) fs


As long as you know what the ($x) means, it's pretty understandable.

why not just write it as

Code: Select all

loeb fs = fmap ($loeb fs) fs

? once someone goes through the process of figuring out how that works, they're 99% of the way to understanding "fix". from there, "flip id" is the same as "flip ($)", and "(=<<)" is just "flip (>>=)".

Code: Select all

factorial product enumFromTo 1
isPrime n 
factorial (1) `mod== 1

Derek
Posts: 2148
Joined: Wed Aug 18, 2010 4:15 am UTC

Re: Deliberately bad algorithms

Postby Derek » Mon Jun 22, 2015 9:26 pm UTC

And if you need two posts on a forum, hell if you need even one post, to explain how your single line of code works, your code is unreadable and should be rewritten.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 1 guest