Tech cheat sheets - Maps

Also sometimes called an associative array, symbol table or dictionary - Maps are collections of key-value pairs and are probably one of the other most common data structures you might come across day-to-day.

HashMap

The most commonly used Map implementation in Java is probably the HashMap. The HashMap makes use of the equals() and hashCode() method on Java's Object API.

The basic premise is that the HashMap has a collection of "buckets", each which can hold several objects. When an object is added to a HashMap the hashCode() method on the key is used to select the bucket to use, the object is then added in that bucket.  For retrieval, its the same process - hashCode() is used to determine the bucket, then the entries in the bucket are inspected and the equals() method is used to determine the match.  In Java's HashMap, the buket is essentially implemented as a linked list (not a LinkedList - but Entry<k,v> has a pointer to the next entry)

The obvious implication of this, is that the performance is dependent largely on the design of a good equals() and hashCode() method.  For example, if you designed a hashCode() method that always returned the constant 1 (which would be legal, as the Java contract is that if two Objects are equal() then they must have the same hashCode(), but if two Objects have the same hashCode() they do not need to be equals()) - then it would mean all entries would be put in a single bucket.

The hashCode() method

Designing a good hash code implementation is very important - for performance (see this stackoverflow discussion on the performance impact of large HashMaps with poor hashCode implementations), but also if your hash code is erroneous then your HashMaps might just not work and you may insert objects in your Map and never be able to retrieve them (if hashCode() doesn't return consistent values for example, it could be placed in a bucket, then when trying to retrieve it generates a different hashCode() so looks in a different bucket).

If you know the complete key set, and it fits in to the Integer range (hashCode() returns an int) then you could design a perfect hashing algorithm that allows every unique key to have its own bucket, so guarantees O(1) time for insert/retrieve. However, in practice this is also quite unlikely, so ideally want to design for as even a spread across buckets as possible.

Performance

Due to the dependency on the implementation of the objects used as keys, and the data set, the worst case vs best case performance is varying.

Search/insert/remove - All these operations suffer the same problem - in best/average case performance these can be done in constant O(1) - However, the worst case (all elements in one bucket) the performance drops to linear O(n)

In practice, HashMaps are usually more efficient than search trees and other look ups, which is why they are very commonly used.

Tech cheat sheets - Stacks & queues

A Stack data structure is a Last-In-First-Out (LIFO) list.  There is a Stack<T> Interface, but the recommended Java structure is the Deque (another interface featuring an Array and Linked implementation).

A Queue data structure is simply the opposite, First-In-First-Out (FIFO) structure. The current Java recommendation is also to use the Deque (noramlly pronounced "deck" if you were interested,  and stands for Double-Ended Queue)

Having read the discussion of ArrayList vs LinkedList, many of the same considerations apply - but given the common use-pattern of stacks/queues, the different implementations make sense.

Deque

Java's Deque implements the Queue interface, and can be used as either a Queue or a Stack, offering methods appropriate for either use.

ArrayDeque vs LinkedDeque

Similar to ArrayList, the Array based implementation is the most popular, and, by-and-large the most recommended implementation to use.

Based on what we already know about ArrayList and LinkedLists, and what we know about Stack vs Queue behaviour, there would be a natural use for each (e.g. LinkedList seems like a good option Stack/LIFO - we can easily add to the list by adding new objects to the front of the list, and then popping objects off the stack by removing from the head of the List - both operations O(1) - compared to the cost of adding to the front of an ArrayList that requires a lot of copying ).

However, in the ArrayDeque implementation it is a circular array - so no copying is required and add/remove is a constant O(1), and the LinkedList implementation creates a very slight performance overhead by using additional memory creating "nodes" for each object in the list.

iWatch & wearable tech

Much has been made lately of Apple's latest announcements of the iPhone 6 and their new Apple watch, and really, I'm pretty late to the party on this one.  I don't normally comment much on Apple announcements, but this time I fancied a rant.


Personally, it's not to my tastes. I know the strap is inter-changeable, and you can change the watch face screen, but I'm not a fan.  In part, because I am more of a fan of classic watch design (so really, some of the photos of the Moto-360 look closer to what I would want a smartwatch to look like), but generally, it feels a little garish, and a bit like something designed 5 years ago.  The curved, almost bubble like glass shape of the device, the square watch face.



I'm not sure what it is.

Maybe its because it feels at odds with current web design trends on flat design. Maybe its because it feels like the original iPhone matured/evolved from it's original curved shape to the current sharper, flatter designed shape and this still seems to hark back to the original iPhone design.

Anyway, as an aside, I think if I was going to spend hundreds on a flash-y digital watch, I would quite like this one:



Sure, I can't check emails on it, but it looks nice.  But then I'm not really someone who should be commenting on style and fashion, so will stick to tech trends..

Is wearable tech the next big thing?

Honestly, I think probably not. Not for the time being at least. I'm sure some smart people will work the market out eventually, but for the time being, and with the current incarnations of smartwatches, I don't think the market is really there.


So, here's the thing - I'm not really sure what the point of the apple watch is (and I guess that is what needs to be cracked before the market can take off). I think, it's going to face the same challenges that tablets have faced - it needs to grow up and work out what it is. It needs to understand what its purpose is and find its niche - it's not going to be good enough to be the same as a smartphone but a different form.


Let's have a look at the markets:

Smartphones:

• Defined and fairly standard "upgrade-cycles" - the expectation and standard of upgrading devices every 12-24 months is fairly established in the west, and this is both driving existing customers to newer, better devices, but is also slowly migrating existing feature phone users to smartphones.
• Everyone has one - at its core, as a phone/communication device it provides that roaming communication functionality and is at least one per-person (not shared)
• Convenience - easy to carry and roam.

Tablets:

• No real defined upgrade-cycle (in terms of device contracts) and too early to see patterns being established - optimistically will fall back to traditional PC cycles of approximately every 5 years
• Not per-person devices - You might be safe to typically expect everyone in an average household to have a (smart)phone, but probably only one/two tablets per house.
• It doesn't solve any real problem - sure, its a little better for watching movies than a smartphone, but apps, browsing, emails and other comms are not noticably better. Further, tasks that might need greater control, or screen real estate - like creating spreadsheets, or presentation slides for example - people still fall back on using regular PCs. There needs to be a purpose/task/app that is made for a tablet sized device - where tablets solve a problem that only they can. As of yet, we're still waiting.

Smartwatches:

• Still yet to see upgrade cycles - will be interesting if carriers/manufacturers try to tie these into existing mobile contract structuring. It will make adoption even harder if they try to sell it with a 1-2 year lifecycle for sure.
• Aimed to be per-person, as a sidekick to your smartphone - but if all it offers is your smartphone in a slightly different form, its again going to be a tough sell - Sure, its slightly more convenient than getting your phone out of your pocket, but that seems like a dubious USP to base an entire market on.
• It doesn't solve a problem - Again, there needs to be a task/area/job where the smart watch is the answer. Where it fills a need that simply can't be filled by a smartphone (or can be, but is a pain in the ass)

For a change, let's have a look at some smartphone/tablet data:


Tablet sales struggle: Apple iPad growth projections by quarter

(Source: Computer World: As tablet growth slows, Apple may face a year-long iPad sales contraction )

Just focusing on Apple for the moment, Benedict Evans presents some interesting data analysis of their recent sales/revenue numbers. Firstly, we see that iPad sales have flattened out and basically settled where they are for the last two years, whilst iPhones have continued to see growth year on year:

(Source: Benedict Evans - iPad growth - Apple's trailing 12months sales)


More generally, if we look at the comparison of sales across PC vs Android/Apple smartphones, we see that PCs have levelled out, but the smartphone continues to see huge growth:

(Source: Benedict Evans - iPad growth - General shipping - PCs vs Smartphones)




It really looks like the smartphone market is continuing to surge. With standard upgrade-cycles, and low end Android smartphones becoming more widely accessible, this trend seems set to continue.

On the other hand, until the tablet market works out its purpose and finds a niche, I think it will continue to stagnate with fairly flat growth. 

It feels to me like a similar fate awaits smartwatches, until someone comes up with a compelling problem that the watch form factor solves, I think it will struggle to see big growth in the market.

BBQ Sauce

Continuing the recipe theme, I also created a bbq sauce last summer. It's a sweet, tomato sauce based recipe, and went down pretty well when I served it.

Ingredients

• 400ml tomato sauce (I just used sainsburys own brand)
• 50ml Southern Comfort (optional)
• 1 table spoon yellow mustard (just normal hot-dog mustard, like Frenchs)
• 1 table spoon chilli powder
• 80g sugar
• 60ml cider vinegar
• 1 teaspoon garlic powder
• 60ml Worcestershire sauce
• 1 teaspoon smoked paprika

Just slam the ingredients in a sauce pan for a while and reduce to a bbq-sauce consistency.

(to be honest, you can knock out a quick "cheats" bbq suace in two minutes that will go down pretty well - as above but reduce the ketchup to roughly 250ml, sugar to about 60g and then just a few glugs of cider and a few of worcestershire sauce and mix it up - tweaking ingredients to taste and it should be ok!)




Here it is on some chicken legs..

Tech cheat sheets - Lists & arrays

In Java, arrays and lists are an ordered collection of non-unique elements. They are probably one of the most common data structures you might have come across in your day-to-day programming.

Array vs List

In most cases, in Java you are more likely to use Lists over arrays - Lists provide more functionality as part of the API than the array does, so given the option, most people will use a list.

The two most common use cases for an array in java are:

1. An array of primitive types - Java generics only supports object references. Although Java autoboxing reduces the need for this, as you can still insert int type values into List<Integer> for example.
2. Micro optimization in performance critical systems

Most other cases, people generally use Lists, as the List interface offers more/convenient functionality, and also offers further control over type of List:

ArrayList

Array list is a simple array based implementation of the List interface.

Performance

add( T item ) - Adding a single element to an ArrayList using this add method will just add the element at the end of the list, which is very cheap - O(1)

add( T item, int index) - Adding a single element to an ArrayList at a specified position is less performant, as it needs to copy all elements to the right of the specified position, so this is more expensive and runs in linear time - O(n)

remove( T item ) - Similar to adding at a specified position, this is less performant  as it involves an array copy (plus, if we remove a specific Object rather than an item at a given position, it still potentially needs to access all items in the list). Again, linear time - O(n)

set/get( int index ) - This is very cheap in an arraylist, as it is just backed by an array, so can be looked up in constant O(1)

LinkedList

LinkedList in Java is a double linked list implementation of the List interface (e.g. every element in the list stores a pointer to the previous & next elements in the list - and these pointers are used to access/traverse the list).

Performance

add( T item ) - Adding a single element to a LinkedList using this add method will also just add the element at the end of the list same as the ArrayList, which is very cheap - O(1)

add( T item, int index) -Again, adding at a given position (** using this method!) is more expensive - Insertion in a linked list is cheap, as the pointers just need to be adjusted, however, you have to traverse the list to find the position, which puts you back into running in linear time - O(n)

remove( T item ) - Again, this method has the same performance/issues as the above add at position method, having to traverse the list to find the element to remove. So again, runs in linear time - O(n)

set/get( int index ) - As we need to traverse the list to find the position, it also needs to potentially traverse every element in the list, so runs at linear time O(n)


** As you will note from the above summary, ArrayList is better for get & set methods and equal performance for add remove methods. However, LinkedList does have the benefit of being able to use an Iterator to add/delete elements in constant O(1) time - e.g. if you are iterating a list and already at the position you wish to insert/delete then it is very cheap - see JavaDocs

Conclusion

By and large, for most simple List cases (not considering wanting to use Sets, Queues, Stacks etc) the most common choice is ArrayList as it offers, generally, the best performance.

If you know you need to have a very large list, and know that you will always be inserting new elements towards the head of the list, then LinkedList may be a better alternative - if you only ever insert at the start of a list, LinkedList will perform in constant O(1) time, where as ArrayList will perform O(n) time.

There are futher implementations of the List interface in Java, such as Stack, Vector.  I will look at some of those in different posts.

Cream money management - A Side project

Cash rules everything around me, it's all about the money, dollar dollar bill yo



I have for some time been bemoaning the state of online banking in the UK offered by the major banks I have banked with. It feels like they just can't be bothered - they are confident that no-one is going to disrupt them so they just don't make any effort.

My current bank makes it almost impossible to manually pay off your own credit card online, and all it really offers is a list of transactions against an account - the only good thing it offers is the ability to download your transactions.

It's frustrating. They have so much information, but provide so little.  So I told my wife I would make us an app to make this better.

Features of the app are:

• create multiple accounts to manage together
• upload statement/transaction lists as exported from online bank providers
• automatically categorise and tag as many imported transactions as possible based on a set of rules
• using sensible full text search, attempt to categorise and tag any remaining transactions based on other similar transactions that have been tagged
• allow manual tagging/categorisation of transactions (that will then feed back into later imports of transactions etc)
• link together transaction groups - identify recurring transactions and group them so they can be automatically categorised and tagged and also provide alerts/warnings on changes in payments (e.g. if a recurring transaction suddenly increases in cost, then it likely suggests that a fixed price deal has come to an end etc, so the system identifies this and alerts the user to the change
• easy filtering and cutting up of data based on category, tags, date, price, description etc.. basically anything
• tonnes of charts to show the different cuts of data and interesting points