reset password
Author Message
AAdryel
Posts: 8
Posted 13:40 Feb 11, 2019 |

In case anyone was curious, here is the n_primes function created using the filter function and an infinite list (As Abbott mentioned in class) as opposed to checking new numbers against a list of primes:

 

-- Definition of while

while :: state -> (state -> Bool) -> (state -> state) -> (state -> result) -> result
while state eval bodyFn extractRes
    | eval state = while (bodyFn state) eval bodyFn extractRes
    | otherwise = extractRes state

 

n_primes n =
    while ((2:[3,5..]), [])
          (\(_, primes) -> n > length primes)
          (\(nums, primes) -> (filter (\x -> x `mod` (head nums) /= 0)  nums, head nums : primes ))
          (\(_,primes) -> reverse primes)
AAdryel
Posts: 8
Posted 13:46 Feb 11, 2019 |

Timings from my machine:

(original)

nPrimes 1000 = 4.25 seconds

(new, with filter)

n_primes 1000 = .53 seconds

Attachments:
rabbott
Posts: 1649
Posted 17:12 Feb 11, 2019 |

Well done!

Here are a couple of minor improvements.

nPrimes n =
    while ((2:[3,5..]), 0, [])
          (\(_, pCount, _) -> n > pCount)
          (\(p:nums, pCount, primes) -> (filter (\x -> x `mod` p /= 0)  nums, pCount+1, p : primes))
          (\(_, _, primes) -> reverse primes)

1. Added pCount to the tuple to count the number of primes in the primes list. That way we don't have to compute length primes over and over.

2. Used pattern matching in the first parameter of the body function. Although Python supports some pattern matching, it doesn't support pattern matching for parameters.

When I ran the original version (for 1000 primes), my time was 0.42 sec. With these changes, the time was reduced to 0.26 sec. Presumably, most of the time saving came from eliminating the call to length at each iteration.

rabbott
Posts: 1649
Posted 17:23 Feb 11, 2019 |

Here's another little trick, although it doesn't save any time

while :: state -> (state -> Bool) -> (state -> state) -> (state -> result) -> result
while state shouldContinue bodyFn extractRes = wh state
    where
       wh state
            | shouldContinue state = wh (bodyFn state) 
            | otherwise = extractRes state

We can define  wh local to the while function, which allows wh to refer to the variables (such as eval, bodyFn, and extractRes) which are defined within the while function. Since those functions never change (only the state changes) there is no point in passing those functions over and over again. Unfortunately, this didn't save any observable runtime.

Last edited by rabbott at 10:25 Feb 12, 2019.
jungsoolim
Posts: 38
Posted 09:28 Feb 12, 2019 |

This is an amazing experience!

I struggled with the size of list where I did not have to worry about it at all to begin with!

Thanks!

Soo

 

Last edited by jungsoolim at 12:57 Feb 12, 2019.