• Before We Begin: The Code
• Timing Scripts
• Before You Time: Developing Your Algorithm
• Beginning Your Timing Journey
• Statistical Timing, a.k.a., If You Give A Mouse A Cookie
• Hierarchical Timing Strategy
• Single Problem/Program/Binary
• Multiple Problem/Program/Binary
• Statistical Averaging
• Results
• Summary

Before We Begin: The Code

Note that all of the code discussed/shown in this post is available from the traveling salesperson problem repository on git.charlesreid1.com. The guava/ directory contains the guava solution to the traveling salesperson problem, along with the timing scripts discussed below, and several example output files.

Introduction

Timing a piece …

• Intro
• The Graphs We Are Solving
  • Visualizations of Graphs
• Guava TSP Solution
  • Timing the TSP Solution
• Improving the Guava TSP Solution
  • The Flaw
  • Fixing the Flaw
  • The Pessimist Algorithm
• Timing Results
• Future Work

Intro

In a prior blog post we introduced you to the traveling salesperson problem (TSP), which involves finding the shortest path through every city in a group of cities connected by a network of roads. Using Google Guava, we have implemented a solution to the TSP in Java.

Our philosophy toward timing, profiling, and optimization is that it is always best to work from data - and timing …