This is my explanation of “Prefix Sums” a powerful and versatile algorithm technique.
It can be used for optimizations, parallelization or enabling other algorithms that are essential for all kinds of complex problems.
So it’s a very useful concept to understand, to know where and how to use it. For this post you better be familiar with Big O notation as I use it to talk about time complexity.
Trust me, it’s much easier than it sounds: given a list of numbers A, create a new list P of numbers on which each element is the sum of all the numbers from A prior to its index.
If you are a visual person, this is what it is (A is input and P is the output):
If you are a mathematical person, this is what it is: Given A = [a0, a1, a2, ... , an-1], of size n > 0
Prefix Sums is P = [a0, (a0 + a1), (a0+a1+a2), ... , (a0+a1+ ... + an-1)]
Or in other words: P[x] = P[x-1] + A[x]
Like I said, easy huh?
There are many ways of implementing this technique but I like this one because is quite readable:
As you can see, its time complexity is linear, O(n). Now that the concept is clear, let’s use it.
Imagine that you have to calculate many many times the sum of parts of an array of numbers. It could be for displaying a heat map or the average stock price. Our example just calculates the sum of all sub-arrays/slices of 5 elements from an initial big array.
The most straight forward way to do it is by repeatedly do the iterative sum as many time as needed. Maybe like so:
The function sumArrayLinear(A, start, end) from the previous Gist can be represented as: sumArrayLinear(A,x,y): Ax + Ax+1 + ... Ay-1 + Ay
And we can apply it like so: sumArrayLinear([2,3,7,5],1,3): A1 + A2 + A3 = 3 + 7 + 5 = 15
The time complexity of our example is O(n x m). Which is not bad.
But now you have another tool available for your disposal: Prefix Sums.
Let’s put it to use.
We calculate the Prefix Sums array with the numbers array. Then we define a new function which takes the Prefix Sums array as follows: sumPrefixSumArray(P,x,y): Py - Px-1
Which basically reads as: The sum of the interval is the sum at the end (y) minus the sum of everything before the start of the interval (x-1). So with just one operation we obtain the result. Its time complexity is constant, O(1). Let’s try with our example.
The Prefix Sum of A = [2,3,7,5] is P = [2,5,12,17] . sumPrefixSumArray(P,1,3): P3 - P1-1 = 17 - 2 = 15
Which is the same result as before, therefore: Ax + Ax+1 + ... + Ay-1 + Ay = Py - Px-1
We can rewrite our code to use our new function:
The total time complexity is O(n) + m x O(1) which is simply O(n+m). And that’s pretty good! Of course, it all depends on the values of m & n. For our example, the first approach needs roughly 140 operations to obtain the resulting array while the seconds needs only 61.
There you have it!
The Prefix Sums technique for all sorts of other more complex problems. A powerful simple idea.
Was I clear? Spotted any problems or bugs? Do you know other examples where Prefix Sums can be used? Speak up on the comments bellow.
Great news for us, BB10 loyal users: independent app development is not dead yet!
I have created a very simple app but which I think it’s really neat. It’s called “Memoir” and it is immensely useful to me and hopefully it will be for you too. It’s not free because I put a lot of effort in it and I value my time and effort. So, if you want more apps for BB10, please support your favorite independent dev by buying and reviewing our apps. With enough paying costumers it will enable me to continue doing what I like: cool and useful BB10 apps!
I’m giving my best with this app but even so there will be bugs. Actually, this is an unofficial BETA release. It works just fine in most cases but there are some edge cases that are not fully covered so … don’t push it too much. Or push it and break it but, please, report it to me so I can fix it.
This first version has only the core features but if reception is good, I’m planing to add more cool stuff. You can even ask for what would you like to see it doing. Just send me an email or a message in Twitter.
Grab your copy on BlackBerry World while it’s on LAUNCH SALE for 50% Off the regular price! Promo will end when I release the next version so hurry up before I release it.
Please share it with your friends and spread the word.
MEMOIR – Send your Remember Notes to Microsoft’s OneNote™
Memoir* [mem-wahr, -wawr]; noun; 1. A record of events written by a person having intimate knowledge of them and based on personal observation. 2. Usually, memoirs. An account of one’s personal life and experiences; autobiography. The published record of the proceedings of a group or organization, as of a learned society. 3. A biography or biographical sketch.
Even tough BlackBerry provides a great note taking app, Remember, it has a big shortcoming: it’s impossible to backup its data or export it, not even with BlackBerry Link. This means that you have to manually copy and paste all data somewhere safe.
Don’t let your precious memories go to waste. With the Memoir app you can secure your memories in to the cloud with just one tap.
HOW WE DO IT?
All the Notes and Folders stored on BB10’s Remember app can be easily uploaded to Microsoft™’s excellent OneNote™ note taking app/service. A Notebook named “BB10 Notes by Memoir” is created in your OneNote™/OneDrive™ account. Every Note Folder from Remember is a Section of the notebook. Every Note from Remember is a Page on OneNote™.
It’s a free cross-platform app and service. It’s has many advanced features and is deeply integrated with the latest version of Windows™ and their cloud storage service OneDrive™. It’s a perfect place for preserving your precious notes and enabling multiple ways of accessing it. To use Memoir you’ll need to have a Microsoft™ account.
– Support for Remember Notes and Folders.
– Attachments: images, audio, pdf, ppt, doc, xls e etc.
– Upload All with 1-Tap.
– Fast Native/Cascades interface. Very simple and effective.
– Secure integration with Microsoft™ Account. A Microsoft™ account is required. OneNote™ permissions must be granted.
– One-way synchronization. Only changes from Remember app are detected and uploaded.
– Support for OS 10.3.0 and higher.
– Integration with other cloud services. Google™ or EverNote™? You choose!
– Support for Tasks.
– Two-way synchronization. Changes to Notes made from OneNote™’s apps are downloaded to the device and appear on Remember app.
– Give OneNote™ permission only once. Permission is only granted for 1 hour in current version.
– Support for OS 10.2.1
– Other languages. Volunteer native speakers are welcome!
– Change OneNote™ Section by changing Notes Folder
– Change OneNote™ Master Notebook name
Yup, call me stubborn. What can I say besides that I really like the underdog, the odd, the beaten up and failed. My last post was about a project that I did in Flash and now a new post about a BlackBerry 10 app. Those are two technologies that I have very good experience and that I have a lot of fun using so on my free time I can’t help my self. What do I gain from it? What motivates me?
There’s something special about the underdogs: their despair to succeed. Much like the old saying about “Never fight a cornered animal for it will give a hell of a fight for it’s life”. A company that is in trouble will try their best to succeed – or at least they should. And what tech companies do best? They innovate! They put their best efforts into bringing great technologies hoping that it will win the market’s heart and save them. I find this situation greatly interesting so I watch closely their fight for life.
BlackBerry was – well, still is – cornered so they tried their best and as a result we have: BB10 OS and Blend on the software side and the Passport representing the hardware. Both extremely innovative products on their own merits but unfortunately they didn’t save the company. When innovation doesn’t work, companies put a fresh coat of paint on their best selling product and try to sell the hell out of it – the Classic – or they copy their competitors – the Priv with Android. Nowadays I don’t watch BlackBerry anymore… but let’s move on.
I do learn a lot about the problems at hand, like using the OneNote REST API, how to make multi-threaded programs, memory management, development of User Interface and Experience, localization, so on and so forth. These are actually the concepts that are the hardest to learn and master but the ones that I can pretty much take with me and use wherever needed. Just the implementation details will be different.
Another thing that I got used to was people frequently asking me, with an incredulous face, “Why BlackBerry?!”. There’s a strong reason and it’s quite reasonable. BlackBerry World has a little bit more than 370K apps available for download. iTunes App Store has more than 1.500K! That’s 4x times more apps, 4x more competitors. Barely any room for indie devs. There’s also lack of official support from popular services like Uber and Telegram. On BlackBerry World there’s only one very good paid app for each, a couple of odd balls.
These points show two clear things: as a costumer it sucks to have a BB10 phone because you’ll miss a lot of apps, a problem that for many experts was the crux of BlackBerry’s demise. As an independent developer it’s a gold mine! It’s all about competition and marketing power. With the same amount of effort I can have a very good compelling Sudoku game or Telegram app on BlackBerry 10 without much competition from other players. How can one indie dev compete with hundreds of other apps available on Apple’s AppStore, of which the best ones are the official ones or created by App Factories with dozens of dedicated professionals? My indie app would univocally end up in the middle of the “noise”, the sea of dead apps full of clones and ad-ware. And no matter how much I polish and improve my app it wouldn’t leave this dreadful app store deadzone. To leave it, the app must be heavily marketed! On forums, podcasts, tech blogs, forums, Twitter, Facebook and any other channel you can think of. But remember, your competitors can afford Super Bowl ads and hire Hollywood movie stars.
What’s for grabs? BlackBerry 10 has sold an estimated 15 million units world wide and shrinking. Apple has a whole f****** lot of millions and growing. The effort so sell 100K on BB10 is quite low and actually reasonable considering that if you have a unique essential app. A person will simply have to buy it from you because they are stuck with you. To sell 100k on the iTunes App Store you’ll have to invest much much more. Wanna be a billionaire? Be a CEO of a startup, get a lot of funding for development and marketing and go for Apple. Wanna be a millionaire, work hard and go for BlackBerry (while it lasts). As an indie dev, BB10 is just more reachable therefore much more motivating. Oh, and you can apply my arguments if you change Apple for Android and BB10 for Windows Phone.
I hope that the answer to my question was clear and if you are smart enough, you won’t bother with BB10. (And will let this small gold mine just for a few silly ones).
Has anyone ever teach you how to learn? Strange question, right? I did the same puzzled expression but as I thought about it I came to an easy answer: no, nobody ever taught me how to learn. For me learning is almost like an instinct, something that we’re born with and that we can’t directly control such as breathing or sleeping. No need to worry about learning about it. So I was really intrigued when I saw the online course offered by University of California, San Diego called “Learning How to Learn: Powerful mental tools to help you master tough subjects” by Dr. Barbara Oakley, Dr. Terrence Sejnowski. After checking out what it was all about I was convinced that it wouldn’t hurt to take the online classes. When I decided to enroll on the course I still didn’t know I was going to walk 120km and get married during the same period but I still managed to participate. And the course was quite cool! I indeed learned many things about learning so I’m here to teach you some of my favorite findings.
Two distinct modes of thinking
We rarely notice it but we do think in different ways in different situations. Researchers have found that we have two fundamentally different modes of thinking. The first time I encountered this concept was in 2013 when I read the best selling book “Thinking Fast & Slow” by Daniel Kahneman, a winner of the Nobel Prize in Economics. On Kahneman’s book, he calls it System 1 & System 2. On the course it’s called Diffuse and
Focused modes respectively. Barbara Oakley and Daniel Kahneman both talk about the same general concept but I prefer Daniel’s approach more. In this post I mash them together to get an even depper understanding.
When we have to manually multiply 2 big numbers we have to pay close attention to all the steps involved in the arithmetic operation, recall easier multiplication values, sum numbers and so forth. We do all that on the Focused mode of thinking, a.k.a. System 2. It is our slow, deliberate, analytical and consciously effortful mode of reasoning about the world. You can tell if a person is really engaged on this mode of thinking by observing their eyes: just note how dilated their pupils are. They call it Focused to give this sense of gathered organized thoughts.
But this mode has three big disadvantages: it requires a lot of energy, it gets tired and it is really lazy. And before we notice we already switched to another mode of thinking.
A.k.a. System 1, our fast, automatic, intuitive, creative and largely unconscious mode. It detects hostility in a voice and effortlessly completes the phrase “bread and. . . . ” or “2 + 2 = ?“. It’s so fast and so effortless that we use it most of the time and we usually do just fine with it, we even let it fool ourselves by it. And that’s great! Imagine if you had to worry and focus on every single banal activity or situation that you encounter in your life like deciding which hand to use to open a door when you have both hands free and perfectly fine. We would live in constant stress, depleting precious limited energy that could be used for more important tasks. So relying on the Diffused mode of thinking is more relaxing.
The course also teaches us another very important role that this mode of thinking has: making new brain cells connections that forms new creative ideas. It has happened to you and me many times: when we least expect it a crazy thought pops into our mind. Most of the time it’s something totally useless and silly like “What if popcorn grew on plants?” but sometimes it could lead to the birth of a new scientific discovery “Why should that apple always descend perpendicularly to the ground?“. This is the wonderful background workings of Diffused thinking, called that to give the sense of a more disorderly, spread out thoughts.
Knowing how differently both ways work is important so that we know when and how to use them. A big fallacy is to not use enough of Diffuse thinking and abuse Focused thinking. Just relax your mind and move your body for some minutes, this way you give time to your brain to recharge Focused Mode and use Diffuse Mode.
Now this is actually an answer for something that I wondered myself many times: why the heck do we sleep so much?! We’re so vulnerable and useless while sleeping and it’s such a waste of time considering the short lifespan that we humans have. It’s not like I’m a tortoise that can live for centuries! Alas, a good answer.
Brain’s waste cleanup scheme
When we’re awake, the brain produces toxins, byproducts of its own activities, which accumulate and degrade it’s functionality. Our mind becomes murky so it’s harder to concentrate, remember and construct rational thoughts. So it’s only when we sleep that the brain switches to cleaning mode: the brain cells shrink a little, a fluid called Cerebralspinal Fluid (CSF) flows through its cells, around all the blood vessels, removing all the toxins. The CSF then dumps the toxins into the blood stream. Our mind is now refreshed! This is a very elegant solution, unique to the brain. The rest of the body has the Lymphatic System, another set of vessels with fluids that runs throughout our bodies, that drains the byproducts of other organs. So it’s important to always have a good night’s sleep before an important test.
In fact, getting too little sleep doesn’t just make you do worse on tests, too little sleep, over too long of a time, can also be associated with all sorts of nasty conditions. Avoid sleeping dreprivation at all costs!
Sleep to learn and understand
But sleep does more than just allow our brain to wash away toxins. It’s actually important part of the memory and learning process. It’s seems that during sleep our brain tidies up ideas and concepts we’re thinking about and learning. It erases the less important parts of memories and simultaneously strengthens areas that we want to remember. During sleep our brain also rehearses some
of the tougher parts of whatever we’re trying to learn, going over and over neural patterns to deepen and strengthen them.
Sleep has also been shown to make a remarkable difference in our ability to figure out difficult problems and to understand what we’re trying to learn.
It’s as if the complete deactivation of the conscious you helps other areas of the brain start talking more easily to one another, allowing them to put together the neural solution to our learning task while we’re sleeping.
Of course, we must also plant the seed for our diffuse mode by first doing focused mode work. If we’re going over what we’re learning right before
going to sleep, we have an increased chance of dreaming about it. Dreaming about what we’re studying can substantially enhance our ability to understand it.
So sleep well and dream about what you want to learn. It will make the process much easier.
Illusions of Learning
Having the source material easily available for access, like having a textbook at hand or Google open right in front of us, creates the illusion that the material is also available in our brains. There are many ways to fool ourselves that we’re learning something, creating only illusions. Many techniques are very inefficient or just plain useless and we should be very careful and avoid them.
What to avoid
Here’s a list of things that are very inefficient and that should be avoided:
Re-reading: The only time rereading text seems to be effective, is if you let time pass between the rereading, so that it becomes more of an exercise in spaced repetition.
Glancing at a solution that is not yours: we need to know how and why of every step of the solution and practice it. This way we make sure that the underlying neural circuitry is created. The information must be persistent in our memory.
Mindless highlighting and underlining: it can even be misleading! Keep highlights and underline to a minimum, one word or sentence per paragraph only.
What to do
If you want maximum learning efficiency and avoid illusions of learning this is what you should start doing and doing a lot:
Recalling: after reading a material, look away from it and try to recall as much as you can or at least the main ideas presented. Research has proved that this is much more effective than re-reading and mind mapping.
Synthesizing notes: writing synthesizing notes on the margin of the book or on other places is a great way to force ourselves to think deep about a concept and simplify it in a smaller, easier way to memorize and understand. The whole process requires a big mental effort which also strengthens our new neuron connections.
Test yourself: it will force you to recall even harder and will give you the right opportunities to make mistakes. Making mistakes is important because every time you do it, you have to think even harder to fix it which strengthens the neural connections needed for learning the material. A test is a safe environment to make mistakes.
Change your learning environment: we unconsciously take visual and mood queues from our surroundings when we are studying and this affects our memory. The more varied the environment where we study, the more diverse our queues are and so we’re more prepared to recall something somewhere different. It’s specially helpful to study on the same place where you’ll be taking a test.
As you can see there’s a lot to learn about learning that nobody teaches us. There many techniques to learn that are very effective for learning new things, as there are special techniques for breathing while singing or running. Even tough it’s something almost instinctive, we can still tweak it and improve it. And many researchers are working hard, making new discoveries on how the brain works and it will help us to improve our learning skills so we must always keep learning how to learn.
Personally, I strongly believe that the most valuable and powerful skill someone can have is the ability to learn new things. It makes us more adaptable and prepared to face new challenges whatever they may be. After taking this course and learning all that I have seen, I believe that I made a great decision. And I hope I motived you to try it too.
I would like to share some little piece of code that I wrote recently in AS3. It’s been quite a while since last time I did anything with Flash technology and I must admit that I had loads of fun. Maybe too much. I still can’t believe that this technology is dying in favour of HTML considering only the technical parts. I really support what the Web and all it’s technology represents and how much it empowers people who care to learn it. I really get inspired by the folks at Mozilla and how hard they work to keep the web an open competitive place for everyone.
But dealing with browser glitches and wimps, render engines optimisations, thousands of mobile phones, hunting for bugs on hundreds of CSS rules and so on is just a freaking nightmare! Specially when you are on the frontline on release day. It’s totally doable, I get paid really well to do it, but it is not fun. There’s also that dread that every single day there’s a newer technology supposedly much better the one you’ve been learning on the past 24h. There are so many frameworks and libraries and plugins to handle every device/browser/os. Or maybe it’s your client/project/boss that demands some specific technology. Flash and Java have the same problem but it’s much much smaller. Instead of choosing between 5 Flash libraries for animating something on the screen, you have to choose between 15 in HTML. By the way, those are fictional numbers just so that you can feel the dread. Or is it really?
In my opinion, Flash will not go away anytime soon. It changed too many things, it runs in too many environments, it works for many projects, there are too many experts and tools and books and blogs and knowledge. You can’t kill something this big that easy. And it’s also a lot of fun!
Enough sentimental blabber! I implemented a small super efficient image scroller using a few 2D rendering tricks of the platform. Using Stage3D would probably give even better results but it’s out of my reach for now. This little program works really well for navigating huge panoramic images smooooothly. Check it out for yourself. The PanoViewer Demo is a release build so make sure to use a Release Flash Player plugin. You can get a really amazing effect if your monitor has very low response time and delay. My monitor failed miserably on these tests so the effect beauty is really diminished.
There are two projects: PanoViewer and Panomax.
It’s the Flash application that handles the logic of loading assets, rendering buttons and initializing the Panomax instance. It’s important to notice the SWF metadata tag with the frameRate = “1” parameter. This specifies the frame rate of the application, in frames per second. The default value is 24. Lowering it’s value gives the runtime a much longer Elastic Racetrack , roughly 1/2 second for each phase, which also means lower loads on the system. This is a key concept to understand and we’ll exploit it.
The CachingImageLoader is a very simple external image loader with very basic caching functionality and tries to deal with Security Sandbox details. The CTAButton – Call To Action – is a custom button class with different style and it makes sure the text label always fits its boundaries.
Here’s where the magic happens. The loaded panoramic image (Bitmap) and other parameters are passed to the Panomax instance. It calculates all boundaries, configure the interactions and starts a Timer. On the TimerEvent handler function that all matrix transformations are calculated and where a part of the panoramic image is painted on the canvas. If it was not obvious yet, painting a small portion of an image is much faster than moving a gigantic image around. We just need 1 Matrix object and 1 call to BitmapData.draw(…). Things start to get very interesting when we add the horizontal looping (function onTimerXLoop). To help us understand how it works I made this schematic:
You have to start from the middle, where gTx = 0. If you go reading up, gTx increases and the image is moving to the left. If you go reading down, the image is moving to the right. Let’s not forget that Matrix transformations (tx, ty) signs means that negative is to the left and positive is to the right. Here’s an awesome Matrix transformation tutorial if you are not familiar. Since the image loops horizontally, the are some states in which it needs to be rendered twice: one on the far left and the other on the far right. For that we use 2 Matrix objects and 2 BitmapData.draw(…) calls which is the heaviest state for the system.
There are some clever tricks that we can do with the transformations of the matrixes in order to use simple formulas. For instance, once the left edge of image A moves out on the right edge of the canvas, it looks exactly like image B with its right edge on the right edge of the canvas which also looks exactly like image A with it’s right edge on the right edge of the canvas. So we can swap/render B with A! Clearly, from my code, I couldn’t figure out the simple formulas so I ended up with complicated ones.
Now, for the last trick, we need to analyse just 1 line of code: e.updateAfterEvent(); // for immediate rendering! To understand this you really have to dominate the concept of the Elastic Racetrack that I mentioned earlier. With the app frame rate reduced to 1, our async code (the TimerEvent handler function) has more time to run and most probably won’t interfere with the other phases of the racetrack. So the Matrix calculations are done, the images are rendered on the canvas but the application frame is not updated yet because the rendering phase is still many milliseconds away. Thus we force the rendering with plenty of time to do so. With enough time for both racetrack phases, what we get is butter smooth scrolling performance!
This is it! I hope you liked it this tutorial. The code is on Github so go ahead and study and fork it!
This is yet another adventure start for me. My first domain! My first private spot on the internet where I can make it the way I want and fill it with stuff that I want (and is not illegal off course). I don’t think I will create a WikiLeaks or a new YouTube but I might add another cool place on the internet. Only time will tell. I must say I love to begin new projects but, like any ordinary folk, they tend not to be completed. This one is different because it doesn’t have a time limit, a dead line nor never will be completed. This domain will come along with me for the rest of my life, improving, growing and evolving as my self.
The main goal of this domain is actually very simple: the start point off my second life which is my online life. It needs to be nurtured, managed and honed because I consider it a valuable asset and part of me. I want to unify all my online presence into one single unique image that can translate into what I really am in real life. I am sure that I can get a benefit out of it. But there will be a lot of work to be done, a lot of knowledge to earn and some challenges to overcome. The good thing is that none of it scares me.
Another thing before I forget: I am more and more involved into helping saving the world. I’m not yet an eco-boring or whatever but I can clearly see what kind of shit we are diving heads first and that raised my awareness and conciousness. The decisions that we make now will have great impact tomorrow so I proudly chose to host this domain in HostPapa which is a Certified Green Web Hosting. Little by little we’ll make our time on this planet a little bit longer and more pleasant.
Oh yeah! This domain is going to be full of clichés, impact phrases, crazy talking and who knows what else can come out!
I talk and write like a dreamer.
Nice to meet you and thanks again for stopping by.