Python merging lists - 


mylists = [ [1,3,5,7], [2,4,7,8], [11,15], [20] ] import time def timeit(f):     def wrapper(*args, **kw):         t = time.time()         res = f(*args, **kw)         print "%s took %s" % (f.func_name, time.time() - t)         return res      return wrapper  # merge 2 given lists def merge(l, r):     if len(l) == 0:         return r      if len(r) == 0:         return l      if l[0] <= r[0]:         return [l[0]] + merge(l[1:], r)     else:         return [r[0]] + merge(l, r[1:])  def merge2(x,y):     if len(x) == 0:         return y     if len(y) == 0:         return x      #pop lower 1 between 2 biggest items     last = y.pop() if x[-1] < y[-1] else x.pop()      merged = merge2(x,y)     merged.append(last)      return merged  def merge3(xs, ys):     ms = []     = 0     j = 0      while < len(xs) , j < len(ys):         if xs[i] <= ys[j]:             ms.append(xs[i])             = + 1         else:             ms.append(ys[j])             j = j + 1      while < len(xs) , j == len(ys):         ms.append(xs[i])         = + 1      while == len(xs) , j < len(ys):         ms.append(xs[i])         j = j + 1      return ms  # divide , conquer def lmerge(lists, m):     if len(lists) <= 1:         return lists      mid = len(lists) / 2      llists = lmerge(lists[:mid], m)     rlists = lmerge(lists[mid:], m)      # bottom merge have list of list     if isinstance(llists[0], list):         llists = llists[0]     if isinstance(rlists[0], list):         rlists = rlists[0]      return m(llists, rlists)  @timeit def a():     print lmerge(mylists, merge)  @timeit def b():     print lmerge(mylists, merge2)  @timeit def c():     print lmerge(mylists, merge3)  @timeit def d():     print sorted(reduce(lambda x,y: x + y, mylists))   a() b() c() d() 
antz@antz-90x3a:~/python/algo$ python addlists.py  [1, 2, 3, 4, 5, 7, 7, 8, 11, 15, 20] [1, 2, 3, 4, 5, 7, 7, 8, 11, 15, 20] took 7.00950622559e-05 [1, 2, 3, 4, 5, 7, 7, 8, 11, 15, 20] b took 6.103515625e-05 traceback (most recent call last):   file "addlists.py", line 101, in <module>     c()   file "addlists.py", line 13, in wrapper     res = f(*args, **kw)   file "addlists.py", line 97, in c     print lmerge(mylists, merge3)   file "addlists.py", line 82, in lmerge     if isinstance(rlists[0], list): indexerror: list index out of range antz@antz-90x3a:~/python/algo$

kinda confused why raising , index error merge3?

merge, merge2, merge3 should have same output (at least in mind) dont understand why raising indexerror because works merge , merge2

edit: can have better merge algorithm if there one?

unless missed done:

mylists = [ [1,3,5,7], [2,4,7,8], [11,15], [20] ] newlist = [] elem in mylists:     newlist.extend(elem) newlist = sorted(newlist)

Comments

Post a Comment

Popular posts from this blog

commonjs - How to write a typescript definition file for a node module that exports a function? -

consider, toml node module can use: // toml.d.ts declare module toml { export function parse(value:string):any; } declare module "toml" { export = toml; } then: /// <reference path="../../../../../defs/toml/toml.d.ts"/> import toml = require('toml'); toml.parse(...); however, node module export single function, such 'glob' ( https://github.com/isaacs/node-glob ). the node usage of module be: var glob = require("glob") glob("*.js", {}, callback(err, files) { ... }); you'd naively expect this: // glob.d.ts declare function globs(paths:string, options:any, callback:{(err:any, files:string[]):void; ...but because typescripts 'import' semantics bit strange, seems can use 'import .. = require()' statement alias modules . trying call: /// <reference path="../../../../../defs/glob/glob.d.ts"/> import blog = require('glob'); results in: error ts2072: mod...
Read more

openid - Okta: Failed to get authorization code through API call -

i'm integrating okta own idp server using okta's api. i'm implementing authorization code flow following steps below: in own server, use /api/v1/authn endpoint sessiontoken. use sessiontoken obtain authorization calling endpoint: /oauth2/v1/authorize?client_id=" + clientid + "&sessiontoken=" + sessiontoken + "&response_type=code&response_mode=query&scope=openid&redirect_uri=" + redirecturl + "&state=evanyang&nonce=" it's supposed return response status code 302 , location header containing redirect url code value. however, keep getting response status code 200 , without location header, html body saying "you using unsupported browser." , "javascript disabled on browser." according api documentation: http://developer.okta.com/docs/api/resources/oidc.html#authentication-request , sessiontoken parameter sufficient this: an okta one-time sessiontoken. allows api-based ...
Read more

ios - Change Storyboard View using Seague -

i have following code checks connection server, , depending on want change views if no connection found. nsstring *connect = [nsstring stringwithcontentsofurl:[nsurl urlwithstring:@"http://myserver.com"] encoding:nsutf8stringencoding error:nil]; if (connect == null) { [self performseguewithidentifier:@"network_failure" sender:self]; } else { // other code here } my problem not change views. have added storyboard segue between 2 views identifier of network_failure . not have navigation controller or that, problem? thanks help! no not problem. first of all, in objectivec exists nil object oriented null . must use that. so: if(connect == nil) or better: if(!connect) so due fact nil not same of null , probably code does't enter in if scope . you have been able discover breakpoint. anyway: be sure set trigger segue (line) 2 view controller , , name network_failure (that not best name. should instead view1toview2 ) as, m...
Read more