Algorithms Techniques - Part 2: Brute Force
An overview of brute force algorithms.
A brute force algorithm is a simple and very general technique that evaluates all possible candidates of a solution until a final solution is found. Brute force algorithms are not very efficient - most of the time - and rely on sheer computing power instead of using a more efficient implementation.
Say you have a safe that requires a 4-digit pin to access and you forgot what the pin is. Using brute force, you would try every possible combination until the safe opens. Start with 0000, 0001, 0002, …, all the way to 9999. That’s 104, or 10,000 possible combinations! Now, 10,000 attempts is not a lot when you are running that on a computer, but what if the pin had 8 digits, or 12, or 20? That’s 1 followed by a lot of zeroes.
Now, as a wise man once said, Talk is cheap. Show me the code.
Two Sum
Let’s start with a very simple problem and solve it using brute force and then a more efficient algorithm and compare their performances. Here is the problem:
Given an array of integers numbers and a integer target, return true if there are two numbers in that array that sums to target. If there are no pair of numbers that sum to target, return false.
For example:
numbers: [2, 3, 4, 5]
target: 8
Answer: true (numbers 3 and 5)
The brute force algorithm would try all possible pairs and see if they sum to target:
2 + 3, 2 + 4, 2 + 5, 3 + 4, 3 + 5, 4 + 5.
Let’s see the implementation in Go. Create a new file and name it brute_force.go and add the code below:
package main
import "fmt"
func twoSumBruteForce(numbers []int, target int) bool {
for i := 0; i < len(numbers); i++ {
for j := i + 1; j < len(numbers); j++ {
if numbers[i]+numbers[j] == target {
return true
}
}
}
return false
}
// Create and initialize a large array of numbers.
func setUp() ([]int, int) {
max := 10000
numbers := make([]int, max)
for i := 1; i <= max; i++ {
numbers[i-1] = i
}
// We set target to a number so that no pair can satisfy it, to force
// the loop to run over the entire array.
return numbers, max * 2
}
func main() {
numbers, target := setUp()
res := twoSumBruteForce(numbers, target)
fmt.Printf("Hello, Brute Force: %t\n", res)
}Using Big Oh notation, that algorithm runs in O(n2), which is usually bad. We will use Go’s benchmark support to test that implementation. Benchmark tests will follow Go’s testing rules so the code below needs to go in a file named brute_force_test.go:
package main
import (
"testing"
)
var globalRes bool
// This is our benchmark for the brute force implementation.
func BenchmarkTwoSumBruteForce(b *testing.B) {
// Before running the benchmark, we create the numbers array and the target.
numbers, target := setUp()
// Since twoSum returns a value, we make sure we store it.
var res bool
// Reset the timer so the time taken to initialize the array is not taken into account.
b.ResetTimer()
// This in fact runs the benchmark. b.N is provided by Go during runtime.
for i := 0; i < b.N; i++ {
res = twoSumBruteForce(numbers, target)
}
// Just because we need to use res.
globalRes = res
}We run the benchmark above with the command:
go test -bench=.
And the output (on my computer, of course) was:
BenchmarkTwoSumBruteForce-4 28 54827876 ns/op
PASS
ok _/src/brute_force 1.215s
Notice that the time to run each loop in my benchmark (the loop limited by b.N, not the loop in the two sum method) was 54827876 ns, which is about 54 ms. If we increase the size of the array in setUp() to, say, 100,000, the time per loop increased to about 5s. That is… slow.
A better two sum
Now, let’s see a better implementation just to see how they compare. Let’s add a new method to our file:
func twoSumBetter(numbers []int, target int) bool {
cache := make(map[int]bool)
for i := 0; i < len(numbers); i++ {
need := target - numbers[i]
_, exists := cache[need]
if exists {
return true
}
cache[numbers[i]] = true
}
return false
}This improved version of the algorithm uses a map to keep track of the numbers we’ve found in the array and, for each number we are visiting, we check if there is a number in the map that if added to the current number results in the target. The advantage is that this algorithm iterates over the array only once, and thus runs in O(n), which is much better than the previous version.
Let’s add a benchmark for it:
func BenchmarkTwoSumBetter(b *testing.B) {
numbers, target := setUp()
var res bool
b.ResetTimer()
for i := 0; i < b.N; i++ {
res = twoSumBetter(numbers, target)
}
globalRes = res
}And compare the results:
BenchmarkTwoSumBruteForce-4 31 36952413 ns/op
BenchmarkTwoSumBetter-4 1021 1330232 ns/op
PASS
ok _/src/brute_force 3.629s
As we can see, the brute force version took ~36ms per loop compared to ~1.33ms in the improved version. Quite the difference!
Is brute force really that bad?
Most of the time, yes. There are some problems, however, where a better approach just can’t be used. One example is the problem at the beginning of this post, where we try to guess the pin of the safe; without any clues (such as a dictionary with the most probable pins), the only option is to try every possible combination.
However, brute force implementations are usually easier to implement, and sometimes you just need something done quickly and the optmization is left to be done later. Also, if the inputs are not too large, a brute force algorithm might be good enough.
Cover picture by Stephen Radford via Unsplash