2014-10-05

Catching Up: Writing Again!

So I just finished up this blog post, Just What the Heck is Amortized Constant Time Anyway?, over the last couple weeks. And I felt odd once I finally posted it, because of the total lack of personal context as to where this post is coming from. After all, it's been over a year since my previous post. So I wanted to write a quick "catching up" post, which is mostly about the fact the I am writing again!

2014-10-02

What the Heck is Amortized Constant Time Anyway?

Effective use of the Scala Collections Library benefits from a solid understanding of the performance characteristics of the operations on a collection. In this regard, the web page Scala Collections Performance Characteristics is a valuable resource, as it summarizes the performance characteristics of various collections in easy to read charts. We see two interesting entries on these charts: effective constant time and amortized constant time. Just what do these terms mean, and how does it affect us as Scala programmers?

In this article, we will discuss amortized constant time - a performance characteristic for mutable collections such as Java's ArrayList, HashMap and HashSet. We'll address effective constant time - seen in immutable collections such as Scala's Vector, HashMap and HashSet - in a later essay.