Don't be lazy about lazy sequences. 33
Coding with infinite sequences is very powerful, but also very bizarre. If you aren’t careful you can get algorithms that work fine, but are O(N^2) instead of O(N).
Consider the (partial-sums) function that I used in my previous blog on generating pi.
(defn partial-sums [s]
(lazy-seq
(cons (first s) (add-streams (next s) (partial-sums s)))))
This function takes in a list of (a b c…) and returns a list of partial sums (a a+b a+b+c…). Trying to figure out how this function works is a bit mind-bending; at least for me; but here’s how I visualize it.
It adds (next s) to (partial-sums s).
(next s)
|
V
s: (a b c d ...)
(partial-sum s): (a a+b a+b+c ...)
Notice how the vertical columns are the sums that we want. Notice also that each result is the sum of the previous result and the next element of s. So verbally and visually this all makes sense. But algorithmically it can still be challenging to understand. I mean, how do those values get calculated really?
Oh… And I should note… The function above doesn’t work this way at all. It’s actually horrifically inefficient. But I’ll get to that, and to the solution. First things first.
What allows this function to run is lazy-evaluation. All that really means is that an element of a list does not really exist until you ask for it. At that point the program calculates what the element of the list should be and then returns it to you as if it was there all along.
In Clojure, when you build a sequence inside the (lazy-seq) form, it simply defers the execution of the procedures that generate the values of the sequence until those values are requested. Look again at the function above. When you call it, it simply returns immediately without doing anything. The (lazy-seq) form simply short-circuits the execution of the function, deferring it for later.
So when (partial-sums) returns it gives you a sequence, but there’s nothing in it! However, as soon as you ask for the first element, the body of the (partial-sums) function will execute just enough to give you the value of the first element. No other elements are calculated. When you ask for the next value, (partial-sums) will execute again, just enough to give you that value. And so on.
Knowing that, let’s trace the execution.
- We call (partial-sums s) which returns a list (let’s call it ps)
- To get the first element of ps, (partial-sums) is lazily-invoked and simply returns (first s)
- For the second element it returns the first element of the sequence produced by (add-streams (next s) (partial-sums s))
which will be: (+ (first (next s)) (first s)) - For the third element it returns the second element of the added streams, but the element is composed of yet another stream addition invoked by the recursive (partial-sums) So it looks like this:
(+ (first (next (next s)) (+ (first (next s)) (first s))
“Uh… Wait.” I hear you say. “You mean that in order to calculate the third element, you have to add three elements? Didn’t we say that we could add the next element of s to the previous element of the partial sums? Why do we have to do three additions? Why does it seem to be doing this:”
(a b c)
(a b c)
(a b c)
Notice that the vertical columns are the sums we are looking for; but calculating them requires a lot more work than just adding the next value to the previous sum!.
“But wait,” you say again. “I know something about Clojure. Clojure memoizes the list values. Once you ask for a list element the first time, it never has to recalculate it again! So when we get the third element of the result it shouldn’t have to recalculate the second.”
Partly right. Once you lazily evaluate a list element, that element never has to be evaluated again. It’s in the list, and will simply be returned from the list. But let me ask you this: In the function above, where is the list that being asked again? Look closely. There is no partial-sums result that is being asked for a value more than once. Indeed, every time we need a value we create a new (partial-sums) list. So we aren’t taking advantage of the previous values because we’re always creating a new list.
If you’d like to prove this to yourself, you can run this fun little program.
(defn p [a b] (println a '+ b) (+ a b))
(defn add_streams [a b] (map p a b))
(defn partial-sums [s]
(lazy-seq
(cons (first s)
(add_streams (next s) (partial-sums s)))))
(def w (iterate inc 1))
(println (take 5 (partial-sums w)))
Notice how I print every addition in the (p) function. If you run this you’ll get the following result:
(2 + 1 1 2 + 1 3 + 3 3 2 + 1 3 + 3 4 + 6 6 2 + 1 3 + 3 4 + 6 5 + 10 10 15)
The jumble of numbers is evidence that the lazy evaluation is working. As the println marches through the 5 partial sums, it causes each to be evaluated, causing each sum to be printed. Notice how many sums are taken! Ten additions for 5 partial sums. It’ll be 15 for 6, and 21 for 7. Indeed, the number of additions required to calculate ps[n] is equal to ps[n-1]. A little thought will convince you that this is O(n^2).
To reduce this back to O(n), we need to stop creating a new list of partial-sums at each recursion, and use a single copy of the partial-sums result. We can do this by saving the partial sums result in a var, and then using that in the add-streams call.
(defn partial-sums [s]
(def result (lazy-seq
(cons (first s)
(add_streams (next s) result)))) result)
This may bend your brain just a little bit more. We are using the result before we are done calculating it! But that’s ok, since we never use more than has already been calculated…
Running the program with this change yields the following output.
(2 + 1 1 3 + 3 3 4 + 6 6 5 + 10 10 15)
That’s the O(n) behavior we wanted! Each sum is calculated by adding the next element to the previous sum! Hooray!
There’s a lesson here. You don’t get the benefit of lazy sequences unless you use the lazy sequences. Creating a brand new one each time may generate the right answer, but it’s lazy, and can burn a lot of execution cycles.
One problem I have with this solution is the creation of the global var ‘result’. I’m sure there’s a way to create a local result; but I haven’t found it yet. (I tried using various let forms, but I haven’t stumbled upon one that works yet.)
There’s a function in clojure-contrib that does what you want, and demonstrates how to do it:
(use ‘clojure.contrib.seq-utils)
(reductions + (range 10))
=> (0 1 3 6 10 15 21 28 36 45)
suddenly reminded me of a book that I read five years ago. Donald Knuth’s “Surreal numbers”, but I just vaguely remember it.
You want to emphasize quadratic lower bounds, but write O(n²). It should be Ω(n²) or Θ(n²).
Living without an aim is like sailing without a compass. with a new http://www.handbags4buy.com/ idea is a crank until the idea succeeds.
Very quietly I take my leave.To seek a dream in http://www.edhardy-buy.com/ starlight.
fgd thanks,the post is really good PDF to BMP Converter will give you the satisfied
output quality and conversion speed. Whether you are professional or novice, you can apply it without any errors. You can even set
the personalized output effect
that real significant changes are often the ones that go unnoticed, because they Make Things Work As They Are Supposed To.
This is a good,common sense article.Very helpful to one who is just finding bamboo kitchen the resouces about this part.It will certainly help educate me.
ul, but also very bizarre. If you aren’t careful you can get algorithms that work
I know something about Clojure. Clojure memoizes the list values. Once you ask for a list element the first time, it never has to recalculate it again! So when we get the third element of the result it shouldn’t have to recalculate the second
we offer you canada goose to enjoy the winter!! canada goosewarm canada goose parka protection canada goose expeditionfashionable canada goose jakkerlet you have Happy winter canada goose jakkeGood quality
Canada goose jakkesnug Goose jakkeYou’re Worth It Canada goose jakkerremain stylish Canada goose parkais a trustworthy brand Canada goose tilbudis the best one
canada goose jacka vogue goose jacka pretty canada goose jackordifferent designs outlet canada goose amazing canada goose Expedition smooth welcome to buy!thank you!
but that all attempts to improve quality would be short lived and followed by a larger drive to decrease quality even further.
Moncler jackets are not ordinary.
Very few has the knack of writing such beautiful post like you do.. !!moncler mens I have been following this blog and i feel different energy while reading your post. Keep it dear buddy.. !!moncler women
We are engaged in gearbox,radial piston motor,axial piston motor,piston motor,slewing transmission,danfoss motor,hydraulic orbital motor,hydraulic steering,hydraulic steering unit,hydraulic winch. All products are strictly tested before delivery by testing bench and comprehensive testing facilities to ensure the quality.
This is a great source of stuff, worth reading. Thanks for this awesome information.
This article is very usefull for me! I can see that you are putting a lots of efforts into your blog. I will keep watching in your blog, thanks.
This may bend your brain just a little bit more. We are using the result before we are done calculating it! But that’s ok, since we never use more than has already been calculated…
Sunglass Sunglass Sunglass
We got a fine book on that matter from our local library and most books were not as descriptive as your information
A bad beginning makes a bad ending. A bird in the hand is worth than two in the bush. A year’s plan starts with
spring. Bad news has wings. Better to ask the way than go astray. By reading we enrich the mind, by conversation we
polish it. Custom makes all things easy. He is not fit to command others that cannot command himself. He laughs best
who laughs last. tiffany and co outlet
A bad beginning makes a bad ending. A bird in the hand is worth than two in the bush. A year’s plan starts with
spring. Bad news has wings. Better to ask the way than go astray. By reading we enrich the mind, by conversation we
polish it. Custom makes all things easy. He is not fit to command others that cannot command himself. He laughs best
who laughs last. tiffany and co outlet
good information. Thanks.
internette görüntülü olarak okey oyunu oyna, gerçek kisilerle tanis, turnuva heyecanini yasa.
It is really a nice post, it is always great reading such posts, this post is good in regards of both knowledge as well as information. Very fascinating read, thanks for sharing this post here.
Online UK costume and fashion jewellery shop with, i
Some beats by dr dre solo purple training routines that will improve Your Voice instantly when you exercise Them!These training routines are extremely effective at erasing bad habits, and replacing them using a “successful”, fabulous sounding voice. The headphone’s exterior is produced from an ultra glossy complete that’s particular to garner some attention in beats by dr dre pro black.
Enwoo enjoys a leading position among the industry with its advanced technology and management concept after years of hardworking. Electron beam welding machine China enwoo Electron beam, Beam Welding Machine,Beam Welding Machine Beam Welding Machine,beam welding Multiplex electron-beam welding , High-efficient electron, Electron beam welding machine,Enwoo high-pressure tank
Very fascinating read, thanks for sharing this post here.cheap beats by dre beats by dre store
The reason sport is attractive to many of the general public is that it’s filled with reversals. What you think may happen doesn’t happen. A champion is beaten, an unknown becomes a champion.
Slewing bearing called slewing ring bearings, is a comprehensive load to bear a large bearing, can bear large axial, radial load and overturning moment. http://www.1stbearing.com
Om canada goose jakke spørgsmål vedrørende fødevaresikkerhed, canada goose Gruppen af otte forventes canada goose outlet at lancere “Aquila fødevarer belstaff outlet security initiative”, vil være os $ 10-15 milliarderi belstaff støtte begået for landbrugs udvikling i fattigere Canada Goose Ungdom Freestyle lande.Med hensyn til finansforordningen forventes gruppen af otte ledere at være “Lecce rammen” Hot Salg på grundlag af vedtagelsen canada goose jakke af en politikfil, cross-domæne Canada Goose Banff Parka for at styrke tilsynet med banker, institutioner og virksomhedsledelse, og I am legend og har Hot Salg for nylig udgivet selvmord.I dag, efteråret Canada Goose Handsker på ny hylden, ikke kun mode, men vil holde dig tilsluttet på legender af læder.
The professional design make you foot more comfortable. Even more tantalizing,this pattern make your legs look as long as you can,it will make you looked more attractive.Moveover,it has reasonable price.If you are a popular woman,do not miss it.
Technical details of Christian Louboutin Velours Scrunch Suede Boots Coffee:
Fashion, delicate, luxurious Christian louboutins shoes on sale, one of its series is Christian Louboutin Tall Boots, is urbanism collocation. This Christian louboutins shoes design makes people new and refreshing. Red soles shoes is personality, your charm will be wonderful performance.
water into water,
Every women always has Christian Louboutins Wedding Shoes turn of fame but it also has its own goodbyes.