Return to Answer

added 428 characters in body

edited Dec 18, 2018 at 11:25

1.5k
10
13

The main problem is that elem traverses list and that is slow. It is better to use Data.Set or HashMap as this data structures allow sub-linear membership checking.

import qualified Data.Set as Set hamx :: [Integer] -> [Integer] -> [Integer] hamx ls = reverse . Set.toList . loop (Set.fromList ls) where loop res [] = res loop res (x:xs) | even x && Set.member (div x 2) res = loop (Set.insert x res) xs | mod x 3 == 0 && Set.member (div x 3) res = loop (Set.insert x res) xs | mod x 5 == 0 && Set.member (div x 5) res = loop (Set.insert x res) xs | otherwise = loop res xs

Or a bit shorter (but less readable) version:

import Data.List (foldl') import qualified Data.Set as Set hamx :: [Integer] -> [Integer] -> [Integer] hamx ls = reverse . Set.toList . loop (Set.fromList ls) where loop = foldl' (\res x -> if predicate res x then Set.insert x res else res) predicate res x = any (\y -> mod x y == 0 && Set.member (div x y) res) [2, 3, 5]

Using IntSet instead of Set is several times faster, but Daniel Fischer's solution is still several orders of magnitude faster.

I put a project with criterion benchmark here.

The main problem is that elem traverses list and that is slow. It is better to use Data.Set or HashMap as this data structures allow sub-linear membership checking.

import qualified Data.Set as Set hamx :: [Integer] -> [Integer] -> [Integer] hamx ls = reverse . Set.toList . loop (Set.fromList ls) where loop res [] = res loop res (x:xs) | even x && Set.member (div x 2) res = loop (Set.insert x res) xs | mod x 3 == 0 && Set.member (div x 3) res = loop (Set.insert x res) xs | mod x 5 == 0 && Set.member (div x 5) res = loop (Set.insert x res) xs | otherwise = loop res xs

Or a bit shorter (but less readable) version:

import Data.List (foldl') import qualified Data.Set as Set hamx :: [Integer] -> [Integer] -> [Integer] hamx ls = reverse . Set.toList . loop (Set.fromList ls) where loop = foldl' (\res x -> if predicate res x then Set.insert x res else res) predicate res x = any (\y -> mod x y == 0 && Set.member (div x y) res) [2, 3, 5]

The main problem is that elem traverses list and that is slow. It is better to use Data.Set or HashMap as this data structures allow sub-linear membership checking.

import qualified Data.Set as Set hamx :: [Integer] -> [Integer] -> [Integer] hamx ls = reverse . Set.toList . loop (Set.fromList ls) where loop res [] = res loop res (x:xs) | even x && Set.member (div x 2) res = loop (Set.insert x res) xs | mod x 3 == 0 && Set.member (div x 3) res = loop (Set.insert x res) xs | mod x 5 == 0 && Set.member (div x 5) res = loop (Set.insert x res) xs | otherwise = loop res xs

Or a bit shorter (but less readable) version:

import Data.List (foldl') import qualified Data.Set as Set hamx :: [Integer] -> [Integer] -> [Integer] hamx ls = reverse . Set.toList . loop (Set.fromList ls) where loop = foldl' (\res x -> if predicate res x then Set.insert x res else res) predicate res x = any (\y -> mod x y == 0 && Set.member (div x y) res) [2, 3, 5]

Using IntSet instead of Set is several times faster, but Daniel Fischer's solution is still several orders of magnitude faster.

I put a project with criterion benchmark here.

Source Link

answered Dec 17, 2018 at 21:25

max taldykin

1.5k
10
13

The main problem is that elem traverses list and that is slow. It is better to use Data.Set or HashMap as this data structures allow sub-linear membership checking.

import qualified Data.Set as Set hamx :: [Integer] -> [Integer] -> [Integer] hamx ls = reverse . Set.toList . loop (Set.fromList ls) where loop res [] = res loop res (x:xs) | even x && Set.member (div x 2) res = loop (Set.insert x res) xs | mod x 3 == 0 && Set.member (div x 3) res = loop (Set.insert x res) xs | mod x 5 == 0 && Set.member (div x 5) res = loop (Set.insert x res) xs | otherwise = loop res xs

Or a bit shorter (but less readable) version:

import Data.List (foldl') import qualified Data.Set as Set hamx :: [Integer] -> [Integer] -> [Integer] hamx ls = reverse . Set.toList . loop (Set.fromList ls) where loop = foldl' (\res x -> if predicate res x then Set.insert x res else res) predicate res x = any (\y -> mod x y == 0 && Set.member (div x y) res) [2, 3, 5]