[prev in list] [next in list] [prev in thread] [next in thread] 

List:       haskell-cafe
Subject:    Re: [Haskell-cafe] One-Off detection. Question about Space/Time complexity
From:       "Richard A. O'Keefe" <ok () cs ! otago ! ac ! nz>
Date:       2017-03-23 23:21:59
Message-ID: 397DB787-04C8-4EE3-932E-89BD038E9862 () cs ! otago ! ac ! nz
[Download RAW message or body]


> On 23/03/2017, at 9:52 PM, Andrew Butterfield <Andrew.Butterfield@scss.tcd.ie> wrote:
> 
> It can be done in one sweep down both strings together - look for the first difference,
> and then test hypotheses regarding the 5 possible edits
> 
> oneOff :: String -> String -> Bool
> 
> oneOff [] [] = False
> oneOff [] (_:rest) = null rest
> oneOff (_:rest) [] = null rest
> oneOff s1@(c1:s1') s2@(c2:s2')
>  | c1 == c2  =  oneOff s1' s2'  -- keep looking
>  | otherwise  
>      =    s1' == s2   -- s2 is s1 with c1 deleted or s1 is s2 with c1 inserted 
>        || s2' == s1   -- s1 is s2 with c2 deleted or s2 is s1 with c2 inserted
>        || s1' == s2'  -- c1 is s1 was replaced by c2 in s2, or v.v.
> 
> I guess the above should be O(1) in space

The question is what "O(1) in space" means here.

If you discount the storage required for the strings, fine.
If however you think in terms of lazy lists of characters,
the fact that this code will look at the tails of the lists
up to 3 times means that those tails will be stored, so we
are talking about O(n) space.

I believe it is possible to walk down s1 s1' s2 s2' in a
single pass, maintaining "streaming".

Whether it is _worth_ doing that is another matter.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
[prev in list] [next in list] [prev in thread] [next in thread] 

Configure | About | News | Add a list | Sponsored by KoreLogic