Prefix Sums – Alternative explanation to Codility’s

Intro

Hello there fellow coder!

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.

My other motivation was Codility’s material on the subject and how confusing it is. Hopefully my explanation will be clearer than theirs. My code examples are all in JavaScript so you can test it right in your browser.

The concept

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):

Prefix Sum - P of A
A diagram showing how the Prefix Sum algorithm technique works. P[1] = P[0] + A[1] = 2 + 3 = 5.
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?

A JavaScript Implementation

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.

Simple Example

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.

Fin

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.

Cheers!

Flattr this!

Memoir: Send your Remember Notes to Microsoft OneNote™

Hello everybody,

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.
Cheers!

Get It At BlackBerry World

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™.

MICROSOFT 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.

MAIN FEATURES:
– 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.

PLANNED FEATURES:
– 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

Ask for what feature you want most on the app review or by email: bb10support@williamrjribeiro.com

If you have any issues please contact our support email or reach me on Twitter.

Thanks for your time!

Here are some screenshots of the running on a Z10 and Q10:

Flattr this!

Why bother with BB10 development?

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.

There’s a lot of value in mastering a programming language, framework or another tool. Many times I had to help a fellow senior developer on my team to deal with JavaScript craziness. Oh so many bugs on which the fix was some insane language detail that they didn’t know. I coined a phrase that I used multiple times on my code reviews: “JavaScript is a bitch”. So definitely yes, my expertise with Flash and Cascades – BlackBerry’s own native framework for app development based on Qt – won’t get me that broad advantage on the market place but there are still COBOL experts being hired right?

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).

Cheers!

Flattr this!

Still having fun with Flash

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.

PanoViewer

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.

Panomax

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:

Panomax schematics

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!

Panorama Image Credits

  1. SonyCenter 360 panorama: Homepage, Download, Author: François Reincke

    Full resolution: 3,500 × 1,096 pixels, file size: 922 KB, MIME type: image/jpeg, License: CC-BY-SA 3.0.

  2. Trafalgar Square: Homepage, DownloadAuthor: David Iliff alias DiliffFull resolution: 9.932 × 2.075 pixels, File size: 5.67 MB, MIME type: image/jpeg, Camera location: 51° 30′ 29.39″ N, 0° 7′ 41.31″ W, License: CC-BY-SA 3.0.
  3. Lac de Joux: Homepage, Download,Author: Lausanne De Suisse alias 100zaxFull resolution: 6.000 × 697 pixels, File size: 759 KB, MIME type: image/jpeg, Camera location: ??? N, ??? W,License: CC-BY-SA 3.0.

Flattr this!