patternMinor
Phone List challenge
Viewed 0 times
listphonechallenge
Problem
To learn Haskell, I've been going at this challenge, which is to check a list of phone numbers to ensure that no number is a prefix of another. However, my code is way too slow. I am really new to Haskell so I don't know what to look for in performance optimization.
I have generated a sample input which takes 5s (uncompiled via runhaskell) on my machine. What can I do to speed this up?
I have generated a sample input which takes 5s (uncompiled via runhaskell) on my machine. What can I do to speed this up?
main = do
content Int -> [Bool]
processCases [] num = []
processCases cases 0 = []
processCases cases remaining =
let
caseLines = read (head cases) :: Int
current = take caseLines (tail cases)
in (if (checkListConsistency current) then True else False)
: (processCases (drop (caseLines+1) cases) (remaining-1))
checkListConsistency :: [[Char]] -> Bool
checkListConsistency [] = True
checkListConsistency list =
let
number = head list
rest = tail list
in if checkNumberConsistency number rest
then checkListConsistency rest
else False
checkNumberConsistency :: [Char] -> [[Char]] -> Bool
checkNumberConsistency number [] = True
checkNumberConsistency number list =
foldr (&&) True (map (checkNumberConsistencyVsNumber number) list)
checkNumberConsistencyVsNumber :: [Char] -> [Char] -> Bool
checkNumberConsistencyVsNumber number number2 =
let
numberLength = length number
number2Length = length number2
in if numberLength > number2Length
then notStartsWith number number2
else notStartsWith number2 number
notStartsWith _ [] = False
notStartsWith [] _ = True
notStartsWith (hl:tl) (hs:ts)
| hl == hs = notStartsWith tl ts
| otherwise = TrueSolution
Performance
Your program is slow because you check each number against all subsequent numbers. For a fully consistent phone book with n entries, that's O(n2).
A better strategy would be to sort each phone book first. Then you only need to check consecutive pairs. If one number is a prefix of another, then the prefix will appear just before the longer number. That's O(n log n) for the sorting, plus O(n) for the checking, which is O(n log n) in total.
Looping
The infrastructure for handling test cases is clumsy.
One problem stems for the fact that you slurp up all the input into one list right away, with
Suggested solution
Your program is slow because you check each number against all subsequent numbers. For a fully consistent phone book with n entries, that's O(n2).
A better strategy would be to sort each phone book first. Then you only need to check consecutive pairs. If one number is a prefix of another, then the prefix will appear just before the longer number. That's O(n log n) for the sorting, plus O(n) for the checking, which is O(n log n) in total.
Looping
The infrastructure for handling test cases is clumsy.
One problem stems for the fact that you slurp up all the input into one list right away, with
content
- Avoid function names like
checkSomething, which sound more imperative than functional. For example, isListConsistent would be a better name than checkListConsistency.
- Take advantage of standard library functions — use Google and Hoogle. For example,
notStartsWith is just ((not.).isPrefixOf).
-
Simplify predicate tests on a list. checkNumberConsistency can be
checkNumberConsistency :: String -> [String] -> Bool
checkNumberConsistency n ns = all (checkNumberConsistencyVsNumber n) ns
-
Avoid if … then … else. There is usually a better alternative. For example, (if (checkListConsistency current) then True else False) is just checkListConsistency current. Your checkListConsistency` function can be simplified:checkListConsistency :: [String] -> Bool
checkListConsistency [] = True
checkListConsistency (n:ns) = (checkNumberConsistency n ns) && (checkListConsistency ns)Suggested solution
import Control.Monad (replicateM, replicateM_)
import Data.List (isPrefixOf, sort)
isConsistentPhoneList :: [String] -> Bool
isConsistentPhoneList numbers = not $ any (uncurry isPrefixOf) consecutivePairs
where
sortedNumbers = sort numbers
consecutivePairs = zip sortedNumbers $ tail sortedNumbers
yesNo :: Bool -> String
yesNo True = "YES"
yesNo False = "NO"
processCase :: IO ()
processCase = do
caseSize <- readLn
inputs <- replicateM caseSize getLine
putStrLn $ (yesNo . isConsistentPhoneList) inputs
main :: IO ()
main = do
caseCount <- readLn
replicateM_ caseCount processCaseCode Snippets
checkNumberConsistency :: String -> [String] -> Bool
checkNumberConsistency n ns = all (checkNumberConsistencyVsNumber n) nscheckListConsistency :: [String] -> Bool
checkListConsistency [] = True
checkListConsistency (n:ns) = (checkNumberConsistency n ns) && (checkListConsistency ns)import Control.Monad (replicateM, replicateM_)
import Data.List (isPrefixOf, sort)
isConsistentPhoneList :: [String] -> Bool
isConsistentPhoneList numbers = not $ any (uncurry isPrefixOf) consecutivePairs
where
sortedNumbers = sort numbers
consecutivePairs = zip sortedNumbers $ tail sortedNumbers
yesNo :: Bool -> String
yesNo True = "YES"
yesNo False = "NO"
processCase :: IO ()
processCase = do
caseSize <- readLn
inputs <- replicateM caseSize getLine
putStrLn $ (yesNo . isConsistentPhoneList) inputs
main :: IO ()
main = do
caseCount <- readLn
replicateM_ caseCount processCaseContext
StackExchange Code Review Q#92218, answer score: 3
Revisions (0)
No revisions yet.