performance - Trying to optimize this algorithm/code to compute the largest subset of mutually coprime integers between a and b -


i'm writing function in haskell takes in 2 integers , b , computes length of largest subset(s) of [a,b] such elements mutually coprime. now, reason because believe investigating such values might yield means of producing trivial lesser bounds (possibly one's large enough imply actual primes in various per conjectured ranges such consecutive squares). naturally i'm trying run pretty large numbers.

unfortunately below code not running fast enough practical me use. think flaw haskell's laziness policy causing issues, neither know syntax nor place need force execution prevent operations accumulating.

subsets [] = [[]] subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)  divides b = (mod b == 0)  coprime b = ((gcd b) == 1)  mutually_coprime []  = true mutually_coprime (x:xs) | (coprime_list x xs) = mutually_coprime xs                         | otherwise = false  coprime_list _ [] = true coprime_list (x:xs) | (coprime x) = coprime_list xs                       | otherwise = false  coprime_subsets b = coprime_subsets_helper (subsets [a..b])  coprime_subsets_helper [] = [] coprime_subsets_helper (x:xs) | (mutually_coprime x) = [x] ++ (coprime_subsets_helper xs)                               | otherwise = coprime_subsets_helper xs  coprime_subset_length b = max_element (map list_length (coprime_subsets b))  list_length [] = 0 list_length (x:xs) = 1 + list_length xs  max_element = max_element_helper 0  max_element_helper [] = max_element_helper (x:xs) | (x > a) = max_element_helper xs x                             | otherwise = max_element_helper xs

just make clear sort of input hanging upon, "coprime_subsets 100 120" never seems halt me. left running, got up, did other stuff , came later. it still running. suspect large bottleneck computing subsets immediately. however, don't want put artificial lower bound on subsets generated. might sieve out of coprime sets leaving me nothing.

what have tried far:

  • i replaced original coprime function had gcd. used modulo , iterative checking integers. presume gcd used euclid's algorithm should run faster, in theory.

  • i've been trying think of way build generation of subsets coprime set generator. far haven't been able come anything. i'm not sure if anything.

  • i've been looking anywhere haskell's laziness policy might hurting me. nothing stands out, i'm sure.

i'm aware efficiency issue environment use (winhugs). i'd issue; however, when asked how determine largest subset (for general n sized ranges) on math stack exchange answers received indicated computationally speaking slow thing calculate. if so, that's fine. hoping maybe able run through of ranges interested in without taking forever.

i know efficiency not allowed on site; however, have tried quite bit , i'm not trying lazy here. know haskell has quite few weird quirks can force being deceptively inefficient. it's been while since i've coded in it, , suspect i've landed in 1 of quirks.

first, must find out slow.

when working numbers, 1 should use fastest representation provides required accuracy , range. code doesn't have top-level type signatures, ghc infers type signature coprime_subsets as

coprime_subsets :: integral => -> -> [[a]]

this allows ghc choose integral , happily choose integer, slower int. integer, program spends huge amount of time computing gcds. forcing ghc use int takes run time down 6 seconds 1 second, since ghc can integer math on machine integers directly.

nb: practice provide top-level type signatures. when compiler doesn't benefit them, humans do.

now, on meat of problem. running

main = print . length $ coprime_subsets (100 :: int) 120 main :: io ()

with profiling enabled (stack build --profile stack) , passing +rts -p -h executable (-p time , -h space) gives breakdown:

cost centre            module  src                            %time %alloc  subsets                coprime src/coprime.hs:(4,1)-(5,52)     52.5  100.0 coprime                coprime src/coprime.hs:11:1-26          25.5    0.0 coprime_list           coprime src/coprime.hs:(19,1)-(21,41)   18.5    0.0 coprime_subsets_helper coprime src/coprime.hs:(27,1)-(29,69)    1.8    0.0 mutually_coprime       coprime src/coprime.hs:(14,1)-(16,43)    1.7    0.0

when using integer, vast majority (~78%) of time spent in coprime test. majority spent constructing powerset, let's there first.

next, must understand why slow.

there 3 strategies speed up:

  1. improve asymptotic complexity.
  2. improve constant factors.
  3. call fewer times.

which of these might apply subsets? (1) obvious choice. constructing powerset o(2^n), asymptotic improvements here helpful indeed. can find any? theoretically, should able to. daniel suggests, problem equivalent maximal cliques problem, exponential. however, maximal cliques has solution smaller base, means should able find asymptotic improvement problem well.

the key insight reducing asymptotic complexity (and number of times call it) generating vast majority of subsets throw them away later on when check them coprimality. if can avoid generating bad subsets initially, generate fewer subsets , perform fewer checks coprimality. if number of pruned results proportional size of entire computation tree, yield asymptotic improvement. sort of pruning common in functional algorithm optimization; can see instructive example in richard bird's sudoku solver. in fact, if can write function generates non-mutually-coprime subsets, have solved entire problem!

finally, ready fix it!

we can modifying original generator subsets filter out non-coprime terms goes:

coprimesubsets [] = [[]] coprimesubsets (x:xs)   = coprimesubsets xs ++ map (x :) (coprimesubsets (filter (coprime x) xs))

(there clever fold can use here if think hard explicit recursion fine too.)

once this, can find coprime subsets of [100..120] in ~0.1 seconds, order of magnitude improvement. cost centre report tells story:

cost centre    module          src                            %time %alloc  main           main            <built-in>                      42.9    0.5 coprimesubsets coprime         src/coprime.hs:(33,1)-(35,75)   28.6   67.4 caf            ghc.io.encoding <entire-module>                 14.3    0.1 coprime        coprime         src/coprime.hs:13:1-26          14.3   31.1

now spend of our time doing io , such. furthermore, number of calls our coprime test 3,848, improvement of several orders of magnitude. can find coprime subsets of [100..150] in 3 seconds, compared to... well, didn't wait finish, @ least few minutes.

the next place speedups might in memoizing coprime function, since problem involves computing same arguments many times.


Comments

Post a Comment

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m...
Read more

python Tkinter Capturing keyboard events save as one single string -

is possible store keyboard events 1 string? code below stores 1 char , prints it. card reader or bar code reader, contains collection of character/ string not 1 character @ time. goal save char pressed text variable. from tkinter import * root = tk() def key(event): text= event.char text+= event.char print ("pressed", text) def callback(event): frame.focus_set() print ("clicked at", event.x, event.y) frame = frame(root, width=100, height=100) frame.bind("<key>", key) frame.bind("<button-1>", callback) frame.pack() root.mainloop() currently, creating text variable , everytime key() function gets called, , text stores last character typed. you can define text module level variable , , use module level text inside key function - text = '' def key(event): global text text+= event.char print("pressed", text)
Read more

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -

here tables: create table customer ( cid int primary key, name varchar(32) ) create table ord ( oid int primary key, cid int foreign key references customer, address varchar(20) ) here's linq-to-sql statement: var aaa = c in db.customer select new { c, o = c.ord.tolist() }; and here's inexplicable query generated linq-to-sql: select [t0].[cid] [cid], [t0].[name] [name], [t1].[oid] [oid], [t1].[cid] [cid2], [t1].[address] [address], (select count(*) [dbo].[ord] [t2] [t2].[cid] = [t0].[cid]) [value] [dbo].[customer] [t0] left outer join [dbo].[ord] [t1] on [t1].[cid] = [t0].[cid] order [t0].[cid], [t1].[oid] i want understand how rid of count(*) part. it's entirely uncalled for! linq needs count(*) in order determine number of entries returned o = c.ord.tolist() .
Read more