Timeline for Haskell Hamming Sequence Logic
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2018 at 7:50 | comment | added | Will Ness |
I copy-pasted your code from Github to my GHCi and ran hamx n with n in [200,300,400,500] and each time the run time increased three-fold. This means the algorithm is exponential in n. The other, classic, algo is of course linear, so there is no one speedup factor to give between the two (re "several orders of magnitude"). It simply does not exist. Saying that one code is X times faster than the other implies that both are in the same Theta complexity class. --- (a side note: I'd use a descriptive name for predicate, like keep.)
|
|
| Dec 18, 2018 at 11:25 | history | edited | max taldykin | CC BY-SA 4.0 |
added 428 characters in body
|
| Dec 18, 2018 at 3:00 | comment | added | fp_mora |
The top rendition is faster. Neither require reverse because res is not constructed in reverse. My result ls was constructed in reverse for speed of ':' vs. ++ and for search from the end of the list which was closer to a match.
|
|
| Dec 17, 2018 at 22:30 | comment | added | fp_mora |
Ha, I had my logic in a foldl', too but with elem also but also with a function to divide the candidate numbers by a select factor of one of [2,3,5].
|
|
| Dec 17, 2018 at 21:25 | history | answered | max taldykin | CC BY-SA 4.0 |