optimization - Haskell: Can this code be optimized? -


i have following code. want know whether there way can optimized runs faster.

i wanted solve using segmenttree not versed haskell, why took following list (non-tree) approach.

-- program execution begins here main :: io() main =   _ <- getline   arr <- map (read :: string -> integer) . words <$> getline   querylist <- readdata   let queries = map (read :: string -> integer) querylist   putstrln ""   mapm_ print $ compute queries arr    -- construct sublist sublist :: integer -> integer -> [integer] -> [integer] sublist start end list = take (frominteger end - frominteger start) . drop (frominteger start) $ list  -- calculate resulting list compute :: [integer] -> [integer] -> [integer] compute [_] [_] = [] compute [_] [] = [] compute [_] (_:_) = [] compute [] (_:_) = [] compute [] [] = [] compute (x1:x2:xs) list = result : compute xs list   result = frequency $ sublist x1 x2 list   -- read query list, end @ terminating condition readdata :: io [string] readdata =   x <- getline   if x == "0"     return []     else xs <- readdata             return (words x ++ xs)  -- return count of frequent element in list frequency :: [integer] -> integer frequency list = tointeger (snd $ maximumby (compare `on` snd) counts)   counts = nub [(element, count) | element <- list, let count = length (filter (element ==) list)]

thanks.

precompute frequencies of each prefix of list. compute frequencies of sublist, subtract frequencies of 2 prefixes ending @ 2 ends of sublist. reduce cost of each query o(n^2) o(n). compute frequencies, use counting sort. reduce cost of precomputation o(n^2) o(n log n).


Comments

Post a Comment

Popular posts from this blog

asynchronous - C# WinSCP .NET assembly: How to upload multiple files asynchronously -

i using winscp .net assembly uploading files. want upload multiple files asynchronous way. have created method works single upload. public class uploadingdata { private sessionoptions _sessionoptions; private session _session; //connection etc private void onconnected() { foreach (var fileinfo in localfileslist) { var task = task.factory.startnew(() => uploadfilesasync(fileinfo)); } } private async task uploadfilesasync(string file) { string remotefilepath = _session.translatelocalpathtoremote(file, @"/", "/test_data_upload"); var uploading = _session.putfiles(file, remotefilepath, false); //when done await task.run(() => thread.sleep(1000)); } } please suggest me correct way. thanks you can use backgroundworker class this: string[] images = new string[50]; foreach (var path in images) { backgroundworker
Read more

aws api gateway - SerializationException in posting new Records via Dynamodb Proxy Service in API -

i getting "__type": "com.amazon.coral.service#serializationexception" as reply in postman & in test console in api gateway trying post record directly dynamodb using api proxy services.. referring aws article - https://aws.amazon.com/blogs/compute/using-amazon-api-gateway-as-a-proxy-for-dynamodb/ here's mapping { "tablename": "tablenamegoeshere", "item": { "id" : "$context.requestid" "eventname" : "$input.path('$.eventname')", "timestamp" : $input.path('$.timestamp'), "answers": "$util.parsejson($input.path('$.answers'))" } } update: did asked ... , worked if try add array of json objects gives me above same error - here's trying now. please - couldnt find on google well #set($inputroot = $input.path('$')) { "tablename": "answer", "item": {
Read more

asp.net - Problems sending emails from forum -

i have been redesigning site has message board, has been written guy looked after site. it has few problems , written in .asp , uses .mdb files database. you can see whole thing here . feel free post if helps, test thing have set using original files , new database. the basic problem when posts message, supposed email sent them, have posted it. when replies, originator supposed message, replier has been posted. i’d have thought @ point in process there should script/file in postmessage.asp? the postmessage.asp page below. <% option explicit %> <!-- #include virtual="common/adovbs.inc" --> <html> <head> <meta http-equiv="content-type" content="text/html; charset=windows-1252"> <meta name="generator" content="microsoft frontpage 4.0"> <meta name="progid" content="frontpage.editor.document"> <title>new page 2</title> <base target="_self"
Read more