[Haskell-cafe] Optimization problem
Bruno Oliveira
bruno.oliveira at comlab.ox.ac.uk
Thu Sep 14 14:03:24 EDT 2006
Hello Magnus,
You are right. Silly me. I was thinking of Rel as a kind of Hashtable. In this case,
I think it should be possible to have O(n), since "cons" would only need constant
time.
Cheers,
Bruno
On Thu, 14 Sep 2006 13:11:05 -0400 (EDT), Magnus Jonsson wrote:
>Thanks Bruno.
>However I think this is still O(n*m). As far as I understand your code it
>is a longwinded way to say "[b | (a,b) <- input, b ==
>myChannelOfInterest]". This is fine if you are only interested in one
>channel, and for that case I agree it's O(n), but if you are interested in
>many different channels, it will take O(n*m). Here's why I think your
>code is equivalent to using a filter/list-comprehension:
>>> cons :: Eq a => (a,b) -> Rel a b -> Rel a b
>>> cons (x,y) l z
>>> | x == z = y : l x
>>> | otherwise = l z
>z is the channel that the user is interested in.
>x is the channel of the current message in the list.
>y is the message content.
>l is a function for searching the rest of the list.
>For each element of the list you create a function that compares the
>requested channel to a (in (a,b)). If it's the same, you return that
>element followed by a continued search down the list. If you don't find
>it, you forward the request to the next function down the list. That's
>exactly the same as what the filter function does.
>It is possible I made a mistake somewhere and if I did, let me know.
>/ Magnus
>On Thu, 14 Sep 2006, Bruno Oliveira wrote:
>> Hello,
>>
>> I think it is possible to do it in O(n) (if you change the representation
>> of the output stream).
>>
>> Note that the solution is quite similar toTwan van Laarhoven,
>> and it should be trivial use "Map" instead of "Rel".
>>
>> Here is my take on it:
>>
>> The type of the output stream:
>>
>>> type Rel a b = a -> [b]
>>
>> Here are cons and nil:
>>
>>> nil :: Rel a b
>>> nil _ = []
>>
>> and a lookUp function:
>>
>>> lookUp :: Rel a b -> a -> [b]
>>> lookUp = id
>>
>> Finally the splitStreams algorithm:
>>
>>> splitStreams :: Eq a => [(a,b)] -> Rel a b
>>> splitStreams = foldr cons nil
>>
>> Here is a test with finite lists:
>>
>>> fin = splitStreams [(3,'x'),(1,'y'),(3,'z'),(2,'w')]
>>
>> and here are the console tests:
>>
>> *General7> lookUp fin 1
>> "y"
>> *General7> lookUp fin 2
>> "w"
>> *General7> lookUp fin 3
>> "xz"
>>
>> Now with infinite lists:
>>
>>> inf = splitStreams (map (\x -> (0, x)) [1..])
>>
>> and here a case where it terminates with infinite lists:
>>
>> *General7> take 10 (lookUp inf 0)
>> [1,2,3,4,5,6,7,8,9,10]
>>
>> Cheers,
>>
>> Bruno Oliveira
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20060914/a7142e74/attachment-0001.htm
More information about the Haskell-Cafe
mailing list