Calculating running variance in Python and C++

It’s fairly obvious that an average can be calculated online, but interestingly, there’s also a way to calculate a running variance and standard deviation. Read all about it here.

I’m playing around with the Netflix Prize data of 100 million movie ratings, and a huge problem is figuring out how to load and calculate everything in memory. I’m having success with NumPy, the numeric library for Python, because it compactly stores arrays with C/Fortran binary layouts. For example, 100 million 32-bit floats = 100M * 4 = 400MB of memory, which is manageable. And it’s much easier to play around interactively in ipython/matplotlib rather than write C++ for everything.

Unfortunately, the simple ways to calculate variance on an array of that size create wasteful intermediate data structures as long as the original array.

>>> mean( (x-mean(x)) ** 2 )            # two intermediate structures
>>> tmp=x-mean(x); tmp**=2; mean(tmp)   # one intermediate structure

That’s an extra 400 or 800 megs of memory being thrown around. (And if x was an array of integers, the x-mean(x) step implicitly converts to 64-bit doubles which, well, doubles things again!)

So, following John Cook’s explanation, I wrote running_stat, a C++ and Python implementation of running variance. It takes almost no memory and is faster than NumPy’s native variance function. Demo:

In [1]: from numpy import *
In [2]: x = arange(1e8)                      # python RSIZE = 774 MB

In [3]: timeit -n1 -r5 std(x)                # RSIZE goes as high as 2.2 GB
1 loops, best of 5: 4.01 s per loop

In [4]: import running_stat
In [5]: timeit -n1 -r5 running_stat.std(x)   # RSIZE = 774 MB the whole time
1 loops, best of 5: 1.66 s per loop

The C++ implementation is very simple and can be ripped out of running_stat.cc.

Link: github.com/brendano/running_stat

I wonder if Haskell’s laziness, perhaps along with my friend Patrick’s Haskell BLAS bindings, might magically solve some of the memory usage in the naive implementation.

This entry was posted in Uncategorized. Bookmark the permalink.

80 Responses to Calculating running variance in Python and C++

  1. Patrick says:

    Thanks for the plug but BLAS is pretty irrelevant here. Any decent array library will support a fold opration to give you the result with a constant amount of memory.

    Also, in python, couldn’t you just use a for loop?

  2. brendano says:

    could use a python for loop, but it’s slower than having numpy do an array operation because it’s in C :)

    i guess figuring out how to push array operation into low-level libraries is a step simpler than matrix operations in low-level libraries…

  3. I thought you were after an windowed variance.

    If you are ever interested, you can compute the windowed max-min in constant time, irrespective of the window size! This is not entirely trivial, by the way. See my code:

    http://code.google.com/p/maxminfilters/

  4. brendano says:

    Pretty cool, thanks!

    Is windowed variance even harder?

  5. Thanks for posting this code! It was super-informative and a great shortcut to implementing standard deviation & variation in javascript with streams – https://github.com/tmcw/stream-statistics

  6. Coloring books are normally utilized by children,
    though coloring books for adults will also be
    available. The etiquette of business may be the set of written and unwritten rules
    of conduct that will make social interactions run more smoothly.
    Keep your vision and ears open for virtually any new site polices regarding this issue.

  7. Asking questions are actually pleasant thing if
    you are not understanding anything entirely, however this post gives good understanding even.

  8. Hey there! This is kind of off topic but I need some help from an established blog.
    Is it hard to set up your own blog? I’m not very techincal but I can
    figure things out pretty quick. I’m thinking about setting up my own but I’m not
    sure where to start. Do you have any tips or suggestions?
    Thanks

    my webpage – tanki online cheats

  9. Quality posts is the key to interest the people
    to pay a quick visit the website, that’s what this website
    is providing.

  10. I think the admin of this web site is really working hard in favor of his website,
    as here every information is quality based data.

  11. Greetings from Carolina! I’m bored at work so I decided to check out your blog on my iphone during lunch break.

    I love the information you provide here and can’t wait to take a look when I get home.

    I’m surprised at how quick your blog loaded on my cell phone ..
    I’m not even using WIFI, just 3G .. Anyhow, great blog!

  12. It seems that there are some differences from one manufacturer car 3d
    games to another. The used car salesmen will use. The very used car you are interested in any model you can put doctor on the car since the dealership
    purchased it?

  13. You are in reality a fantastic webmaster. The website loading pace
    is incredible. It appears that you’re doing any special trick.
    Additionally, the contents are a masterpiece. you have performed a wonderful task on this subject!

    my web site :: baking soda acne mask

  14. warez mp3 says:

    It makes it the first choice of the users and also the most wanted and cozy P2P torrent engine ever produced in the world.
    Sometimes your ISP may limit your bandwidth per month. Agora is the first film to get
    shot entirely on Malta.

  15. Pretty! This has been an incredibly wonderful post. Thank you for supplying this information.

    My homepage :: best robotic pool cleaner

  16. It’s in fact very complicated in this busy life to listen news on
    Television, thus I simply use web for that purpose, and take the hottest
    news.

    my website … inversion table reviews

  17. Great goods from you, man. I have understand your stuff previous
    to and you are just extremely great. I actually like what you’ve acquired here,
    certainly like what you are saying and the way in which you say
    it. You make it enjoyable and you still take care
    of to keep it wise. I can not wait to read far more from you.
    This is really a terrific website.

    My weblog: best masticating juicer

  18. There is definately a lot to learn about this issue. I really like all of the points
    you’ve made.

    Feel free to visit my homepage … best skate shoes

  19. Wow that was unusual. I just wrote an incredibly long comment but after I clicked submit my comment didn’t appear.
    Grrrr… well I’m not writing all that over again.

    Anyhow, just wanted to say superb blog!

    My website … chainsaw reviews

  20. A glass splash back for kitchen, bathrooms and wall paneling.
    A splash back is a surface that lines the wall behind your cooker and hob to protect
    the splash 7 a celebration of light surface from spills and splashes.
    Now there is another innovative use glass splash backs
    are available in every size to fit any type of kitchens and bathrooms.

  21. Its like you read my mind! You appear to know so much
    about this, like you wrote the book in it or something.
    I think that you could do with some pics to
    drive the message home a bit, but instead of that, this is excellent blog.
    A fantastic read. I’ll certainly be back.

  22. wiersze says:

    What’s up to every one, it’s truly a good for me to go to see this web page, it consists of important Information.

  23. Customers can travel up and down Stop & Shop’s aisles without getting up
    off of their sofas. Freelance – By – U’s Forum – sign
    up for the forum ASAP for the best and more recent freebies
    and opportunities here:. Consider shopping at specific places or
    checking for coupon matching before going out, since something like Staples coupons for office supplies may only be good for someone
    living near a Staples if a trip isn’t carefully planned to
    avoid extra gas and time expense.

  24. I rarely drop responses, however i did some searching and wound up
    here Calculating running variance in Python and C++ | AI and Social Science –
    Brendan O’Connor. And I do have some questions for
    you if it’s allright. Is it only me or does it appear like some of these responses
    look like written by brain dead folks? :-P And, if
    you are writing on additional online sites, I’d like to follow anything new
    you have to post. Would you make a list of every one of
    your community pages like your Facebook page, twitter feed, or linkedin profile?

  25. Bart says:

    Wonderful goods from you, man. I’ve understand your stuff previous
    to and you’re just extremely magnificent. I actually like
    what you’ve acquired here, certainly like what you’re stating and the way in which
    you say it. You make it enjoyable and you still take care of to keep it smart.

    I can not wait to read far more from you. This is actually a tremendous web site.

  26. telecharger fifa 14 gratuit incorporates a big role with United states
    Traditions. Lots of people are frequently observed involved in activities regarding telecharger fifa 14 gratuit.

    This is partly simply because folks of all age range could be required and also family members are usually delivered collectively
    by simply this particular. Normally an individual exactly who exhibits his or her hate regarding telecharger fifa 14 gratuit could possibly
    be thought to be a great outcast.

    Economic Components

    It’s not necessarily typical train to help affiliate economics with telecharger fifa 14 gratuit.

    Normally, telecharger fifa 14 gratuit will
    be thought to don’t have a impact on the financial status, although
    presently there have been a number of results. The gross sales business linked to
    telecharger fifa 14 gratuit is really a 2. 3 billion dollars greenback annually marketplace and growing every year.
    A uses almost one hundred fifty, 000 people in the states on your own.
    It will be safe to express that telecharger fifa 14 gratuit engage in an important purpose throughout National economics along
    with shouldn’t be taken for granted.

    Environmental Aspects

    From a a few 30 days long study, I have been previously in a position to determine
    that telecharger fifa 14 gratuit isn’t going to adversely result the planet whatsoever.
    A telecharger fifa 14 gratuit would not manage to end in waste materials as well as could hardly become within woods, jungles, waters,
    seas, seas, etc… In reality, telecharger fifa 14 gratuit developed
    several positive effects with the special small mother nature.

    Political Factors

    Oh may telecharger fifa 14 gratuit ever before impact governmental policies.
    This past year 5 candidates jogging for getting some sort of placement utilised telecharger fifa 14 gratuit because the
    main subject with their campaign. Someone may possibly believe telecharger fifa 14 gratuit is a
    undesirable subject to direct some sort of campaign having, but in
    actuality with the societal and also environment effect can be provides, this particular topic could achieve lots of fans.
    These kind of 5 job hopefuls travelled four regarding 5 with successful their roles.

    Conclusion

    telecharger fifa 14 gratuit are a more crucial indisputable fact
    that most offer credit rating for. Next time the thing is that or think about telecharger fifa 14 gratuit,
    think about what we just go through and also understand
    what exactly is genuinely taking. It is likely a person within respected
    telecharger fifa 14 gratuit prior to, yet will certainly right now learn to give the acknowledged needed and also
    deserved.

  27. My spouse and I absolutely love your blog and find
    many of your post’s to be just what I’m looking for.
    Would you offer guest writers to write content to
    suit your needs? I wouldn’t mind writing a post or elaborating on a number of the subjects you write
    related to here. Again, awesome weblog!

  28. social empires triche features a big role in Us Culture.
    Many people are frequently viewed enjoying activities related to social empires hack.

    My blog – social empires cheats

  29. At the end of the day it is all about keeping these criminals away
    from your loved ones because you do not want to see some kind of harm befalling on them.

    Here is my site inteligator reviews

  30. youtube.com says:

    Fat Loss four Idiots – How To Shed 9bls In 11 Days The greatest point
    that has ever occurred in the dieting and weight loss globe
    has to be Fat loss four idiots.

    my webpage: fat loss 4 idiots diet (youtube.com)

  31. 3 billion $ a year industry and rising each and
    every year. The industry engages practically one hundred
    fifty, 000 people in the usa by itself. It could be safe to mention of which
    real racing 3 triche perform a
    significant part inside Us economics and really should not be taken for granted.

  32. I blog quite often and I seriously thank you for your information.
    Your article has really peaked my interest.
    I’m going to book mark your blog and keep checking for new details about once per
    week. I subscribed to your RSS feed as well.

  33. He then went on to Lenox Hill Hospital, exactly where he spent 3 extra years of fellowship in Cardiovascular Ailments.

    my page :: the 21 day sugar detox program review

  34. This assistance is totally free to you upon buy of the starter pack and registration at the site.

    Look into my web site customized fat loss reviews

  35. Thanks for finally talking about > Calculating running
    variance in Python and C++ | AI and Social Science – Brendan O’Connor < Loved it!

    Feel free to visit my homepage :: best bike lights

  36. Advocare says:

    It’s actually a nice and useful piece of information. I am glad that you just shared this useful info with us.
    Please stay us up to date like this. Thanks for sharing.

    Here is my page … Advocare

  37. protoss says:

    I am no longer sure the place you are getting your
    info, but good topic. I must spend a while studying more or understanding more.
    Thank you for fantastic info I was on the lookout for this
    info for my mission.

  38. I don’t know whether it’s just me or if perhaps everybody else experiencing problems with
    your blog. It looks like some of the written text in your posts are running off the
    screen. Can somebody else please provide feedback and let me know if this is happening to them too?

    This might be a problem with my browser because I’ve had this happen before.
    Appreciate it

  39. When someone writes an piece of writing he/she keeps the plan of a user in his/her
    brain that how a user can be aware of it. So that’s why this piece of writing is amazing.
    Thanks!

    Review my website :: la légende d’hercule telecharger

  40. What’s up, just wanted to mention, I liked this post. It was practical.
    Keep on posting!

    Feel free to visit my webpage – une promesse telecharger

  41. I couldn’t refrain from commenting. Well written!

    My web blog – arrête ou je continue telecharger

  42. Pretty nice post. I just stumbled upon your weblog and wished to say that I
    have really enjoyed browsing your blog posts.
    In any case I’ll be subscribing to your feed and I hope you write
    again soon!

    Take a look at my page; the den telecharger

  43. You’re so awesome! I don’t believe I’ve read
    through a single thing like this before. So wonderful to discover somebody
    with a few unique thoughts on this topic. Seriously.. thanks
    for starting this up. This site is something that’s needed on the internet, someone with a bit of originality!

    Take a look at my web site … the unknown known telecharger

  44. Can I simply say what a comfort to find someone who
    actually understands what they’re discussing online. You actually know how to bring a problem to light and make it important.
    More people must look at this and understand this side of
    the story. I was surprised that you’re not more popular
    because you certainly possess the gift.

    My webpage; noor telecharger

  45. Thanks for finally writing about > Calculating running variance in
    Python and C++ | AI and Social Science – Brendan O’Connor < Liked it!

    My blog post nymphomaniac part one telecharger

  46. When I originally commented I seem to have clicked the -Notify me when
    new comments are added- checkbox and now every time a comment is added I get 4 emails with the same comment.
    There has to be a means you are able to remove me from
    that service? Many thanks!

    Also visit my site … jinn telecharger

  47. Hola! I’ve been following your weblog for a while now and
    finally got the courage to go ahead and give you a shout out from New
    Caney Tx! Just wanted to say keep up the great work!

    My blog nymphomaniac part two telecharger

  48. Great site you’ve got here.. It’s hard to find quality
    writing like yours nowadays. I seriously appreciate people like you!
    Take care!!

    Visit my webpage: la crème de la crème telecharger

  49. Way cool! Some extremely valid points! I appreciate you penning this write-up plus the rest of
    the website is very good.

    my weblog … man of tai chi telecharger

  50. I do believe all of the ideas you have presented for your post.
    They’re really convincing and can certainly work. Nonetheless,
    the posts are too brief for starters. Could you please lengthen them a bit from next time?
    Thank you for the post.

    Here is my site la mante religieuse telecharger

  51. Hello, i think that i saw you visited my web site so i came to “return the favor”.I’m attempting to find things to enhance my site!I suppose its ok to use
    a few of your ideas!!

    my site; chlorine telecharger

  52. Hi, always i used to check website posts here early in the daylight, since i enjoy to learn more and more.

    Here is my web blog patrick evil awakens telecharger

  53. I every time used to study paragraph in news papers but now as I am a user of internet thus from now I am using net for articles, thanks to web.

    Also visit my blog :: leçons d’harmonie telecharger

  54. Hey there, You have done a fantastic job. I’ll certainly digg it and personally recommend to my friends.
    I’m confident they will be benefited from this website.

    My weblog … breathe in telecharger

  55. I blog quite often and I seriously thank you for your information.
    This great article has really peaked my interest. I am going to
    book mark your website and keep checking for new information about once per week.
    I opted in for your Feed too.

    Also visit my web-site special id telecharger

  56. My brother suggested I would possibly like this website.
    He was entirely right. This put up truly made my day. You can
    not consider just how a lot time I had spent for this information!
    Thanks!

    Feel free to visit my website – best refrigerators

  57. Ambit says:

    I leave a response each time I like a post on a website or I have something to add to the
    conversation. Usually it’s a result of the passion displayed in the article I read.
    And on this post Calculating running variance in Python and C++ | AI and Social Science – Brendan O’Connor.
    I was actually moved enough to post a leave a responsea
    response ;-) I do have 2 questions for you if it’s okay.
    Is it only me or does it look as if like some of these comments look like they are coming from brain dead folks?

    :-P And, if you are posting on other online social sites, I’d like
    to keep up with everything new you have to post. Could you
    make a list the complete urls of all your communal sites like your Facebook page, twitter feed,
    or linkedin profile?

    Stop by my blog post :: Ambit

  58. 31 says:

    This is my first time pay a visit at here and i am truly impressed to read everthing
    at one place.

    Feel free to surf to my website – 31

  59. OMG! an incredible article dude. Thanks for sharing it.

    Also visit my web blog :: male enhancement products reviews

  60. Cleveland says:

    Substantial Six Figure Settlement Reached in Montgomery County Workers’ Compensation Claim – In Makuach v.
    No wonder so many people try to represent themselves during their divorce.
    Fonts are absolutely critical when it comes to any business card, and business cards
    for lawyers are no different.

  61. Even though many authorities of fashion find the 80′s
    principle awful, the aggressive colors and spandex-full type of
    many 1980′s costumes are even now used by many.
    t believe me just look at their shopping habits, most of the time in shop they spent trying-on things they are not going to buy later.
    They have a good mixture of black and white and color movies,
    most of them are not popular movies.

    my page; Robocop Game Online

  62. It isn’t widespread process to be able to link economics with jurassic park builder triche.
    Normally, jurassic park builder triche 2014 will be considered to haven’t any
    impact on each of our economy, but generally there have been
    several outcomes. This revenue industry associated with jurassic park builder triche android is
    actually a two.

  63. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored subject matter stylish.
    nonetheless, you command get got an nervousness over that you wish be delivering the following.
    unwell unquestionably come more formerly again as exactly the same nearly a lot
    often inside case you shield this increase.

    Feel free to surf to my blog post :: driver genius professional 14 crack

  64. The i – Phone a few and cheaper iphone rumors have been awfully hot lately, still
    it will usually the 5S that the majority of leads the way for Apple path
    of its next version. A very nice feature with the new i – Phone is the ability to zoom when taking video.
    A lot of speculation has come from both analysts and the Apple community about what
    features and specs the handset will have.

    Have a look at my site gagner des gems clash of clans

  65. These are genuinely enormous ideas in regarding blogging.
    You have touched some good things here. Any
    way keep up wrinting.

    My weblog – Survival Library

  66. Εxercise can be a simple աalk around the park fοr 30
    to 45 minսtes. If you’ve tried other skin solutions and
    they’ve fallen ѕhort of your expectations, try African Black Soap today to resolve your skin problems.

    Well, there is a train of thought that Ƅelieves you can indeed prevent acne by food aloոe.

  67. Vigrx says:

    You’ve made a variety of nice points here. I see something
    truly special in this internet site. Thank you for
    posting.

    my blog post … Vigrx

  68. always i used to read smaller posts which as well clear their motive, and that is also happening
    with this post which I am reading at this time.

    My web blog awesome deals

  69. We are a gaggle of volunteers and opening a brand new scheme in our community.
    Your website offered us with helpful information to work on.
    You’ve performed an impressive process and our whole neighborhood shall be grateful to you.

  70. I simply must tell you that you have written a great as well as unique
    article that I really enjoyed reading. I’m fascinated with how well you
    laid out your material and presented your views.

    Thank you.

    Feel free to surf to my web-site best acne treatment

  71. Awesome blog you have here but I was curious about if you knew of any user discussion forums
    that cover the same topics discussed here?

    I’d really like to be a part of group where I can get opinions from other
    experienced individuals that share the same interest.
    If you have any recommendations, please let me know. Bless you!

    Also visit my blog post un kraut wachst fuhrungs

  72. What’s up it’s me, I am also visiting this web site on
    a regular basis, this web page is really good and the viewers are actually sharing fastidious thoughts.

    My weblog … cannabis cultivation

  73. Can you tell us more about this? I’d love to find out some additional information.

    Feel free to surf to my blog – culture de la marijuana

  74. Hi there, the whole thing is going fine here
    and ofcourse every one is sharing information, that’s truly fine,
    keep up writing.

    Feel free to surf to my blog post … marihuana anbau

  75. Quality articles or reviews is the secret to be a focus
    for the viewers to go to see the web page, that’s what this website is
    providing.

  76. I hafe read so many posts concerning the blogger lovers but
    this piece of wriring is trulpy a nice paragraph, keep iit up.

  77. That is a great tip particularly to those new to the
    blogosphere. Brief but very accurate information… Thanks for sharing this one.
    A must read article!

  78. Thօse ѡho don’t аre the people who speոd years struggling
    with their weight, never feeling utterly happy աith themselves or their
    lives. If you thiոk that thе word misuse is a bit strong then thiոk again, ɑs what we put into our system, is what we
    arе. You should concentrate on eating just natural and organic produce to minimize the quantity of chemicals yoս may ingest.

  79. The experts know the NFL very well and these projections are based on the player.
    If the pain is too great Whenever any pain gets too great and if
    it goes on too long and turns into full-blown depression, a visit to the doctor for anti-depressants, or counselling, may be in order.
    Have you always wondered how you can control stress management
    in the workplace.

    Here is my webpage: Download Hack token Top eleven 2013

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>