5
\$\begingroup\$

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?

main = do
    content <- getContents
    let 
        allLines = lines content
        caseCount = read (head allLines) :: Int
        cases = tail allLines
    putStr $ unlines $ map toYesNo (processCases cases caseCount)

toYesNo b 
    | b = "YES"
    | otherwise = "NO"

processCases :: [[Char]] -> 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 = True
\$\endgroup\$
  • \$\begingroup\$ For me when tested with the given example input, it outputs a single YES and then freezes waiting for input, is that the correct behaviour? \$\endgroup\$ – Caridorc May 30 '15 at 13:10
  • \$\begingroup\$ It should output a single YES but not wait for input after that. I run it like this on windows: runhaskell phonelist.hs < file \$\endgroup\$ – vakio May 30 '15 at 14:22
  • \$\begingroup\$ the performance problem is soon understood runhaskell will interpret the programme (very slow) running it after compiling is instanteneous (< 0.1 seconds) \$\endgroup\$ – Caridorc May 30 '15 at 14:32
  • \$\begingroup\$ Yeah I noticed that when I compiled. But the server does compile the code and complains that it's taking too long still. But I give up for now. I think the design is wrong from the start. \$\endgroup\$ – vakio May 30 '15 at 14:42
  • \$\begingroup\$ In terms of performance design; I recommend using a Trie \$\endgroup\$ – GeneralBecos Jun 9 '15 at 15:59
2
\$\begingroup\$

Inlining very short expressions

It is better to avoid the in dialect when the expression is really short, checkNumberConsistencyVsNumber can be written in a much shorter manner

checkNumberConsistencyVsNumber :: [Char] -> [Char] -> Bool
checkNumberConsistencyVsNumber number number2
        | length number > length number2 = notStartsWith number number2
        | otherwise = notStartsWith number2 number

Types everywhere

It is very good that your code is mostly typed, I would finish the job giving types to main and toYesNo:

main :: IO()
toYesNo :: Bool -> [Char]

Use built-ins

Built-ins make the code faster, shorter and easier, for example the below line would benefit from all

foldr (&&) True (map (checkNumberConsistencyVsNumber number) list)

Be sure to use -O2

That is to compile with ghc -O2 phone.hs for automatically faster code

\$\endgroup\$
3
\$\begingroup\$

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 content <- getContents followed by allLines = lines content. As a result processCases has to take a list of those lines as input, and parcel them out using drop (caseLines+1) cases. A further complication is that allLines contains non-homogeneous data: the first line specifies the number of test cases, the first line within each test case specifies the size of that test case, and all other lines contain phone numbers. You're basically doing I/O by dissecting the list, and you would be better off doing real I/O.

processCases performs a countdown using its second parameter. It would be better to have a processCase function instead, which is called n times. You can't make that improvement, though, given the way all the input has been slurped up into one list.

Style

  • For readability, maintainability, and performance, declare the types of all functions. You missed toYesNo and main. Instead of [[Char]], use [String], which is easier to understand.
  • 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 processCase
\$\endgroup\$
  • \$\begingroup\$ Thanks for your feedback regarding looping and style. I wasn't looking for a solution and I'm not going to use those parts, but they're useful nonetheless for my learning process. \$\endgroup\$ – vakio Jun 3 '15 at 13:51
2
\$\begingroup\$

Using the isPrefixOffunction from Data.List

The Data.Listpackage has a a function called isPrefixOf, which can be used to build a single isValidPhoneLstfunction, like this:

isValidPhoneLst :: [String] -> String
isValidPhoneLst [] = "YES"
isValidPhoneLst [p] = "YES"
isValidPhoneLst (h:t) = 
    case any (==True) [isPrefixOf h a || isPrefixOf a h | a <- t] of
        True -> "NO"
        _ -> isValidPhoneLst t

Simplifying your mainfunction with replicateM and mapM_

The replicateM function performs an action n times, gathering the results. It can be used to build a list of only the test cases that you need. As for printing the results, you can use the mapM_ function to print the results of the isValidPhoneLstfunction applied to the test cases, like this:

import Control.Monad(replicateM)
import Data.List(isPrefixOf)

main :: IO ()
main = do
    nTestCases <- readLn
    tests <- replicateM nTestCases $ do
        testCaseSize <- readLn
        replicateM testCaseSize getLine
    mapM_ (putStrLn . isValidPhoneLst) tests

isValidPhoneLst :: [String] -> String
isValidPhoneLst [] = "YES"
isValidPhoneLst [p] = "YES"
isValidPhoneLst (h:t) = 
    case any (==True) [isPrefixOf h a || isPrefixOf a h | a <- t] of
        True -> "NO"
        _ -> isValidPhoneLst t

Using the test case you provided, the main program ran in 349 Milliseconds, compiled without any optimizations.

On Kattis

I've made a kattis account and after submitting this solution I also got Time Limit Exceed. I wish they would provide more information to us users, such as websites like Hackerrank do.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your feedback. I will edit my question and explain that it took 5s uncompiled (via runhaskell). It's more like 1s compiled I think. But yeah, the sample input does not reflect Kattis' input. And my brute-force design will always be too slow; see 200_success' answer why that is. \$\endgroup\$ – vakio Jun 3 '15 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.