B-tree and Binary Search Tree Data Structures

B-tree and Binary Search Tree data structures are similar but different ways to store data. The advantage of using search trees is that the test for membership can be performed efficiently provided that the tree is reasonably balanced, that is, the leaves of the tree are at comparable depths.

B-tree Implementations

B-tree implementations are normally commercial. Languages don't typically provide direct B-tree support. To find B-tree implementations, search Google for B-tree software.

Binary Search Tree Implementations

Some languages do provide support for Binary Search Trees. In Java, see the TreeMap class, which implements a variant of the Binary Search Tree, the Red-Black Tree.

Binary Tree Data Structure Comparison

Both structures operate in the average in O(log n) time. Note that in the worst case, B-tree, at O(log n), is faster than Binary Search Tree at O(n).

P Versus NP Complexity Theory

The P Versus NP issue deals with whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. This is a major unsolved problem in computer science.

In common, practical terms, it deals with how to identify problems that are either extremely difficult or impossible to solve.  In order of difficulty from easy to hard, problems are classified as P, NP, NP-Complete and NP-Hard.

So why do we care? When approaching complex problems, it's useful to have at least some idea of whether the problem is precisely solvable, or if an approximation is the best that can be accomplished. 

Using Randomized Variable Values to Enhance HTML5 Canvas Animations

The HTML5 Canvas feature is bringing additional animation power to web pages.  HTML5 Canvas allows web developers to embed sophisticated bit map animated graphics directly into web pages. 

In developing examples for my book on HTML5 Canvas (HTML5 Canvas for Dummies) I experimented with using randomized variable values to improve the realism of an animated fireworks display. I used random values within specified ranges for parameters such as fireworks colors, number of exploding particles, trajectory of particles, lifespan of particles and flight trajectories. I found that adding well constructed values (not too much or too little randomization) significantly increased the realism and appeal of the results.  Here's one example from the Fireworks app of setting a randomized value:

     part[newPart].life = lifeMin +(Math.random()*(lifeMax-lifeMin));

See what you think ... click here to see it in action.

HTML5 vs. Native App Development

As you're likely aware, there's a big debate going on about whether HTML5 web sites are a better platform for mobile apps than native code development using Android, iOS and Windows.

The main selling point for HTML5 is the write-once-run-anywhere advantage. Web browsers on mobile devices can access web sites from any mobile platform. HTML5 is providing features that allow web page JavaScript code to access phone features like devices sensors and geo positioning. In theory, a well constructed HTML5 web page will look and perform like a mobile device native code app.

However, currently not all device features are available to HTML5 JavaScript code and native code apps have a performance advantage over HTML5 web pages viewed using a browser. Native code apps are presently the dominant choice among developers.

In HTML5's corner, though, the technology is improving and web browsers are ramping up their implementation of HTML5 features. Life would certainly be simpler for mobile developers if they could develop for only one platform, HTML5, instead of multiple native platforms.

Longer term, HTML5 will certainly continue to get better. But so will native platforms. In fact, native platforms may improve more rapidly than HTML5. HTML5 is a global standard developed by the W3C. It takes years of effort to change the standard and have these changes adopted by the various browsers. The individual native platforms (Android, iOS, Windows) can change as quickly as their developers (Google, Apple and Microsoft) want them to. So will HTML5 ever catch up?

Maybe not. Google, Apple and Microsoft have lots of developers and big budgets. They want their products to be competitive ... and that means constant improvements.

So, what's likely to happen? In my opinion, we'll have a blend of the two. In fact, this is taking place today. Native code platforms have Application Programming Interfaces (APIs) that support displaying web pages from within native code apps. Developers can use native code for what it does best and HTML5 web pages for what they do best. The exact mix will shift over time as all the platforms change and improve. 

For developers, this means that separate native code platforms will likely continue to exist. Write-once-run-anywhere will remain an elusive goal probably not realized for a long time, if ever. This doesn't mean that development costs can't be managed or reduced. HTML5 web pages can be developed and used by native code apps where appropriate. Functions specific to those pages can be write-once-run-anywhere. This may not be an optimal solution, but it's the game on the ground.

Smartphone Website with Laptop 2.png

Which is the Best Browser

An analysis of Internet browsers by Top Ten Reviews places Google Chrome at the head of the list. The analysis shows, however, that it's a real horse race between the top five: Chrome, Firefox, Internet Explorer, Opera and Safari. Here are some of my observations based on this analysis and personal tests and experience:

Change after new releases: All of the browser developers are working hard to improve their products. With each new browser version release, the competitive landscape can change. For example, Internet Explorer had recently lagged in speed due to the lack of graphics hardware acceleration. Based on my tests, they're now the fastest running HTML5 Canvas animations.

Graphics hardware acceleration: GPU (Graphics Processing Unit) hardware acceleration is an important factor in browser speed. A browser displaying video or animation with GPU acceleration will outperform a browser without it by a factor of 3-4. That's right, 300-400%. A computer using just the CPU to manipulate graphics displays simply can't keep up with one using the combination of CPU and GPU. Hardware acceleration is a fairly complex topic. Basically, the browser offloads calculations from the CPU to the GPU. If you're interesting in some of the details, take a look at this discussion of hardware acceleration from the Chromium Projects.

Mobile lags desktop: Especially in speed, the mobile browsers lag desktop versions. Mobile devices simply don't have the computing power to match desktop devices. 

HTML5 Status

Transient

The World Wide Web Consortium (W3C) has announced that a final recommendation for HTML 5.0 will be released in the 4th quarter of 2014. In spite of the "recommendation" terminology that W3C uses, this is official release of HTML5. This is a big deal and great news. Browser developers will have a firm definition of HTML5 they can use to bring their products up to a complete level of support for this latest version of HTML.

W3C has also defined the follow-on version, HTML 5.1, to be released in the 4th quarter of 2016. This release will include features that have been pushed out in order to get release 5.0 completed in 2014. Without this stragegy, W3C was looking at an indefinite specification development timeframe. 

Browser developers are not waiting for 2014 to begin implementation of HTML5. You can use www.html5test.com to check the status of your browser to see which features are supported and www.caniuse.com for a summary of the status of support by all the major browsers.

Integrating Audio with HTML5 Canvas

One of the useful features of HTML5 Canvas is the ability to integrate audio, either with or without an audio player. Click here or on the image to see if it works on your browser ... click on my dog Daisy and/or the pelican to test simultaneous sounds.

When the new browser window opens, you can view the page source to see the code that generates the Canvas display.

This is one of the sample applications from HTML5 Canvas for Dummies.

HTML5 Canvas Performance Test

Browser support for HTML5 Canvas is constantly improving. More features are being supported and performance is improving. Click here or on the image below to see how your browser performs. The app rotates a ten layer gradient and displays the Frame Rate.

What's Up with HTML5?

Android HTML5 Test Screen 1 230px.png

HTML5 is the first major update to the HTML standard since HTML4 was standardized in 1994. Full approval by standards bodies and complete implementation may take another decade, but parts of HTML5 are already being implemented.

Android HTML5 Test Screen 2 230px.png

Each browser supports HTML5 to a different degree. The www.html5test.com website can be used to test the extent to which a browser currently supports HTML5. 

The screens to the right were taken from a test of a Droid X running Android version 2.3.3. It scored 177 points out of a total of 450. As is evident from this test, smartphone browsers are not very far along in implementing HTML5 features. The lower screen to the right shows the status of some desktop browsers.

Possibly the most well known of the HTML5 features is the new tag that will avoid the need for Flash in playing videos. This is especially important now that Adobe has announced it will stop development of Flash for mobile devices.

HTML5 contains many new features. A number of these are focused on eliminating the need for proprietary plugins and Application Programming Interfaces (APIs.) This advances the idea of being able to develop applications that will run on any device that supports HTML5, including multiple smartphone, tablet and desktop brands.

Google Improving Mobile Ad Relevance

Non Relevant Ads 200px.png

Google has just announced improvements in mobile search advertising. (See the Google Blog post for more information.) Apps that incorporate search capabilities will see more relevant ads appearing on their screens.

To date, mobile ads appearing on smartphones have not been particularly relevant to the nature of the apps displaying them. In contrast, desktop search ads are highly relevant to the search terms used. So, for example, if I'm searching for information on bicycles, I'll see ads related to this topic.

Making mobile ads more targeted should improve ad click through rates and improve user satisfaction.

If I'm searching on my smartphone for bicycles, I'll see ads related to bicycles, including information on bicycle shops near my current location.

Mobile Internet Users to Outnumber Wireline Users by 2015

Smartphone with PC 1 225px.jpg

According to a new study by IDC, mobile internet access via smartphones and tablets will soon outpace wireline access via PCs and other fixed position devices. Mobile device use is growing rapidly and wireline use is expected to level off and then decline.

This is expected to alter the very nature of how the internet is used. Consider some characteristics of mobile devices that will contribute to this change:

  • Location sensing.
  • Touch screen.
  • Device mobility.
  • Always on status.
  • App centric user interface.

It looks like the shift from fixed to mobile devices may be every bit as significant as the historic shift from mainframes to PCs.