Skip to content

Sorting Comparison: Go vs Java

Sorting is probably the most common operation done by computers throughout their entire history. As a Java/JVM developer, I thought I’d do a quick benchmark to compare Java and Go’s sorting standard library algorithms by sorting ONE BILLION integers.

Both Java’s java.util.Arrays.sort(int[]) and Go’s sort.Ints([]int) use a version of Quicksort as their implementation. This benchmark just tests these two standard library implementations against each other. In the future I will implement a set of algorithms in both Java and Go and perform my own benchmarks for the exact same algorithm.

The “results.txt” file below contains the summary of the test results, but the spoiler is Java beat Go in sorting in all situations. Also, if we test using java.util.Arrays.parallelSort(int[])  into the comparison the test becomes even more lopsided. Java’s parallelSort uses a variation of merge sort which uses O(n) extra memory but performs X times faster where X is equal to the number of processing cores available. Read more…

Advertisements

Optimal Currency Denominations

The United States currency denominations (bills & coins) are based on a “binary decimal system” – [1, 2, 5] which is also quite popular around the world. The question is whether this popular currency denomination is optimal. And if it’s not, how can we find an optimal distribution of denominations. There are two requirements that should be imposed to any solution: first is that the choice should allow a simple (greedy algorithm) to the change making problem; second, it should allow every possible monetary amount to represented by the least amount of currency while also minimizing the denominations needed in circulation.

Greedy Change Making

A greedy algorithm for making change is optimal using United States currency denominations. Optimal is defined as minimizing the number of currency required to make a particular value. A simple example would be making $20.14 in change would require 1 $20 bill, 1 dime ($0.10), and 4 pennies ($0.01) which requires 6 pieces of currency. The way the greedy algorithm works is to pick the largest denomination that is less than or equal to the amount still due and repeating this process until zero is reached.

The property of a currency denomination that makes a greedy algorithm optimal is that the ratio between every denomination and the next one below it MUST BE GREATER THAN OR EQUAL to 2. If we look at the current US denominations, we can see this is the case which is why a greedy algorithm is optimal: $100->$50 (2x), $50->$20 (2.5x), $20->$10 (2x), $10-$5 (2x), $5->$1 (5x) and similarly for coins quarter->dime (2.5x), dime->nickel (2x), nickel->penny (5x).

So what would happen if the denominations were changed so this wasn’t true? Imagine the nickel was worth $0.06 instead of $0.05. Well then the difference between a nickel->penny (6x) would still be fine, but the dime->nickel (1.67x) which is less than 2. So now if we wanted to make change for let’s say $0.12 the greedy algorithm would pick a dime plus 2 pennies for a total of 3 coins needed. The actual optimal solution would be to use 2 $0.06 (nickels) which is not a greedy algorithm.

How can we improve on the 1-2-5 currency?

First, let’s gather some statistics about how well the USD currency currently works by tracking the average number of currency needed to represent every value from $0.01 up to $99.99. Using popular denominations ($100,$50,$20,$10,$5,$1,$0.25,$0.10,$0.05,$0.01=10 denominations) it takes approximately 8.9 currency to represent a value with 4 instances requiring 17 currency ($89.94,$89.99,$99.94,$99.99).

A far better approach would be to base currency on “powers of three”. For instance, what if the USD currency was ($27,$9,$3,$1,$0.27,$0.09,$0.03,$0.01=8 denominations). Then the average number of currency to represent all those same values would be 8.56 which is an improvement on the current USD denominations while saving the need for 2 denominations. Also the greatest number of currency required is 16 instead of 17 ($80.80,$80.98,$90.80,$90.98)

The code below can help you test out your own currency choices, assuming they satisfy the greedy algorithm for currency property.

The Audacity of Hope

The Audacity of Hopethe US Senator Barack Obama

Just as his last book, I found it difficult to stop reading Barack Obama’s narrative of the hard-work, luck, sacrifice and good intentions of public office. Hearing about the people that make the politics from an insider’s perspective gave me new appreciation and respect for those that serve in public office. Although the general public often criticize and attribute malice to unwanted political actions, truly both sides respect each other as citizens trying to do what they feel is right for the country. The details of the life of a US Senator along with the descriptions of the interactions with the public allowed me to imagine those moments and empathize.

The story was balanced between public life and personal life depicting many personal moments in each. A part of the book even described Barack’s meeting of his future wife Michelle at a law firm and his courtship of her, and being there for support after her father’s death. After their marriage, and after his public life began, Barack’s demanding schedule placed an undue burden on Michelle to manage household responsibilities and this caused more than a little resentment. While describing his demanding job, he’d often describe a family call that interrupted the chaos of his day to juxtapose those two starkly different worlds.

Overall, I didn’t enjoy this book as much as “Dream from my Father”, but it was still a great insight into public life.

Ruby 2.1 TracePoint API

The Ruby TracePoint API is simply an Object-Oriented wrapper around the now obsolete Kernel#set_trace_func. There is a performance hit associated with using TracePoint (not for production), but it can provide insight into the amount of work being done inside some Ruby code. We can learn a lot by diving into some code examples using Ruby’s favorite framework Rails.

Ruby’s TracePoint on Rails 4.0.3

Here are some interesting examples of using TracePoint to see what’s going on in Rails: I provide two simple examples. First, all the event stats for a startup of a Rails 4.0.3 application, and also the stats for a single request done on a single thread using WEBrick.

If you know the Rails Initialization Process, then you’ll understand why I put this code in config/boot.rb to begin TracePoint. I stop TracePoint on the first request to the root “/” and display the output.

So the results breakdown like this on my Macbook Air (10.9.2) running MRI Ruby 2.1.1-p76 with Rails 4.0.3:

From boot to 1st request takes: 603 classes, 2,508 different methods, and 468,873 method invocations.

Between requests: 271 classes used, 916 different methods, and 4,510 method invocations.

The numbers for method calls seem very high, but maybe not exorbitantly so when we recall that everything is a method call in Ruby even addition “+”.

:a_call -> the hidden event

I found out about this little fact during a RubyConf2013 in Miami from a core committer. It’s a combination event of b_call, call, and c_call. Even though it exists in Ruby 2.1.1, I’m not exactly sure what version it was first released in, but definitely not in Ruby 2.0.0-p451 or earlier. Even though TracePoint was released with Ruby 2.0, “:a_call” was not added until Ruby 2.1 which is why I named the title of this post “Ruby 2.1 TracePoint API” because that’s what I’m using here. It’s not documented in ri TracePoint, but still Jruby 9000 does have support for it, while Jruby 1.7.11 (latest at time of this writing) does not.

The relevant tests can be found in MRI Ruby source code under test/ruby/test_settracefunc.rb

Good To Great

Good to GreatJim Collins

I’ve worked at more than a few startups, some successful and some not, and over the years I started to see patterns in the people, culture, and technology that kept repeating in successful and unsuccessful companies. This book helped me put a vocabulary to these patterns, and supplemented my ability to explain and describe these patterns to others based on my personal work experience. Jim Collins studied some fairly “old” companies – none were software technology or SaaS companies – but his findings definitely translate, as he predicted, right into these new types of companies.

First, exemplary leaders are usually “Level 5” which means they are a mix of humility and professional will. They also usually are promoted from within rather than being brought in from the outside as some kind of rockstar. Their primary goal is to build the right team by hiring and retaining the right people and removing the wrong people. The idea being to build a great team before defining exactly what the team will try to accomplish. This follows the startup adage often repeated as “hire slow, but fire fast” to maintain a top notch team. The “Level 5” leader should also build a culture that encourages brutal truthful communication by leading with questions, engaging in dialogue, and performing root cause analysis to learn rather than place blame.

The “hedgehog concept” describes what a company can be the best at, is passionate about, and can be the company’s economic engine. The hedgehog concept is an understanding of the company’s greatest chance of success. This understanding when collectively shared by all members of an organization produces a culture of discipline by providing self-disciplined people with a common vision with the flexibility on how to reach that goal. Flexibility and common vision enable creativity and a sense of ownership that increases the odds of success. I believe of all the factors discussed in this book that the hedgehog concept and the culture of discipline are the most valuable.

The organization described in Good to Great is exactly why I gravitate towards the startup culture environments rather than large corporate bureaucracies. I’ve worked in both types of environments and I absolutely thrive in places with traits Jim Collins describes. Now that I better understand these traits, I’ll be more aware of them in my workplace and can better help fill in the gaps by raising others’ awareness.

A Short History of Nearly Everything

A Short History of Nearly EverythingBill Bryson

The claim made by the title caught my attention, and then finding out the author was a travel writer and not some accomplished scientist really shocked me. When I started reading the Introduction chapter, I appreciated the author’s desire to learn and answer questions that school textbooks didn’t try to explain. Bill Bryson committed 3 years of his life reading science journals, books and interviewing experts to collect and digest all this information and the result was a 30 chapter book that is fairly easy to read (non-technical) and understand.

Aside from all the great summaries and explanations of scientific theories and discoveries from the unimaginably large cosmos to the unperceived quantum, geology and the biology of life, the author deftly reminds the reader of the smallness of mankind’s understanding and perception of these complex systems. Each subject provides examples of how mankind’s evolution influenced our perceptions and assumptions in scientific pursuits and illustrates how those have changed over time. One interesting contradiction (of many) to popular knowledge was that space is the great unknown, when actually we know more about the cosmos than we do about the internals, history, and operation of our own planet. We can all peer into space and the speed of light gives us ancient views of galaxies, but we currently do not have anything nearly as reliable for probing our own planet’s internals and history.

I really enjoy books like these because they momentarily extract me from my daily tasks and goals and give me a vast perspective on what must have occurred to allow this beautiful existence. So much of what we take for granted has immense complexity and age.

The Female Brain

The Female Brain by LouAnn Brizendine

I stumbled upon this book by accident and I’m happy to have read it. It’s a short read with only 7 chapters that mostly cover the different phases in a woman’s life and why and how she responds to them. Chapter 1 starts from early childhood and describes how hormonal differences between girls and boys change the development of physical structures in the brain. Chapter 2 moves into the next major hormonal change in girls during puberty and teenage years. Chapter 3 dives into early adulthood for women and how they treat relationships at that stage versus teenage years. Chapter 4 is titled “Sex: The Brain Below the Belt” and describes a lot of the interactions between hormones and emotional state to enjoyment of sex. Chapter 5 goes into the mommy brain and how hormones drastically change priorities and perceptions of woman that are programmed by millions of years of evolution. Chapter 6 is a chance for the book to tie up many threads about emotions and how hormonal changes cause intense feelings of those emotions. Finally, Chapter 7 is the “mature brain” which means perimenopause into menopause.

Although many men “sort of know” many of the things described in this book, it was very interesting to read about it with supporting medical and scientific information. The other great source of information in the book was from anecdotal evidence from the author’s family counseling practice. Finally, the author’s attempts to tie medical observation with family counseling and evolutionary reasons to make all 3 sources of information converge was well done and effective.

The book was targeted at women, so they could better understand objectively the stages of a woman’s life and how it’s drastically effected by hormones, but I believe it’s also a good read for men. If gives you a better understanding of why men and women think, act and perceive differently than a lifetime collection of cliches and relationship quotes. I do believe every woman should read this book, because it helps women to understand what options are available for their health from youthful hormonal imbalances to post-menopause hormone replacement which can improve health and quality of life as well as longevity.

Behind Deep Blue

Behind Deep Blue (wikipedia)

I’ve always had interest in computing power’s ability to overtake professional human players in abstract strategy games. IBM’s Deep Blue win over then World Champion Garry Kasporov in 1997 was historic. Since then, computing power has grown immensely and while chess is not a solved game, it’s much closer than other games. The shear size of chess’s game tree complexity is 10^123 and is quite impressive what computers have been able to accomplish with this size of complexity. A more interesting game is Go which has a game tree complexity of 10^361 which just eclipses Chess.

Back to the book, Feng-hsiung Hsu was a Carnegie Mellon University (CMU) graduate student who worked for many years on the hardware and software necessary to build a computer that could play chess. Once IBM noticed his achievements they brought him in with an ambitious marketing idea of building a computer that could beat the world chess champion. The book described the history, and the bumpy road of successes and failures along the way to the championship game against Kasporov.

Even though the book was a fun read, because it was so heavily based on technology it felt very dated. The processing power they were trying to achieve and data sizes they dealt with are tiny by today’s standards, but their efforts were Herculean at the time. By today’s standards, a relatively cheap chess engine named Houdini would destroy Deep Blue in a chess match. In fact, at the time of this writing, the current Chess World Champion, Magnus Carlsen with an Elo rating of less than 2900 would have problem with Houdini 4 with a rating of 3251As it stands today, there are many computer chess engines with ratings beyond the highest a human player has achieved.

Dreams from My Father

Dreams from My Father (wikipedia)

I really enjoyed the memoirs of then pre-public official Barack Obama: his style of writing frequently evoked the senses by comparisons which helped to visualize his experiences. The book runs fairly chronologically from his early life in Hawaii to his move to Indonesia and life in the continental USA. The end of the book went into great detail about his trip to Kenya prior to starting in Harvard Law School.

The challenges in Barack Obama’s early childhood taught him to adapt, fight for what he wanted, and not to expect too much from others. His multiracial heritage and absent father caused him to frequently question his place in the world. His mother’s life choices as she lived her life and followed her instincts took them to the other side of the world and exposed him to different cultures and environments. Through all of this, the constant values and support provided by his mother gave him the courage to change the circumstances of his life with confidence.

His work ethic was clearly demonstrated by his actions in nearly all stages of his life. His work as a community organizer was difficult and impoverished with few rewards during the early years. It is only through his patience and perseverance did he accomplish so much for the south-side of Chicago. His energy and commitment to helping others is what brought together these communities in Altgeld Gardens despite their reluctance and lack of faith.

I’m looking forward to reading his new book “The Audacity of Hope”: the title of that book was referenced as the title of one of the first sermons he attended in Chicago.

The Art of Non-Conformity

The Art of Non-Conformity by Chris Guillebeau

I’ve read many books like this before. They advocate the road less traveled. Focusing on the life you want to live rather than doing things that you don’t want to, but have to do or the opposite want to do, but can’t because of [insert excuse]. The book claims to be written for those that wish to dramatically change their lives and thinking, but I believe its true audience is people that just want to mentally fantasize about the road not taken.

I credit the author for his honesty in not characterizing his path through life as more exciting or as better and definitely not financially wealthy. But it made him happy, and that was the point. Living life exactly as he wanted without regrets was challenging, but those challenges grew him as a person.

The advice I most valued was around facing fears and not making excuses for why you’re not accomplishing your goals. Books like this just remind me to redouble my efforts as my determination fades in the hustle of daily responsibilities and commitments.