/*
* [TestWaysOfFinding.java]
*
* Summary: Test relative speed of 3 methods of looking up a key to see if item is in the list of legal keys.
*
* Copyright: (c) 2009-2017 Roedy Green, Canadian Mind Products, http://mindprod.com
*
* Licence: This software may be copied and used freely for any purpose but military.
* http://mindprod.com/contact/nonmil.html
*
* Requires: JDK 1.8+
*
* Created with: JetBrains IntelliJ IDEA IDE http://www.jetbrains.com/idea/
*
* Version History:
* 1.0 2008-02-15
*/
package com.mindprod.example;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import static java.lang.System.*;
/**
* Test relative speed of 3 methods of looking up a key to see if item is in the list of legal keys.
*
* HashSet, binary search, linear search for different numbers of keys n.
*
* @author Roedy Green, Canadian Mind Products
* @version 1.0 2008-02-15
* @since 2008-02-15
*/
@SuppressWarnings( { "UnusedAssignment" } )
public class TestWaysOfFinding
{
/**
* random number generator
*/
private static final Random wheel = new Random();
/**
* lookup the random strings
*/
private static HashSet h;
/**
* list of strings we want to look up
*/
private static String[] keys;
/**
* build lookup structure
*/
private static void build()
{
// build HashSet
h = new HashSet<>( Arrays.asList( keys ) );
// build binary search
Arrays.sort( keys );
}
/**
* find all the keys by BinarySearch
*/
private static void findAllViaBinarySearch()
{
for ( String lookFor : keys )
{
int whereFound = Arrays.binarySearch( keys, lookFor );
// -ve means not found +ve tells where found.
}
}
/**
* find all the keys by HashSet
*/
private static void findAllViaHashSet()
{
for ( String lookFor : keys )
{
boolean found = h.contains( lookFor );
}
}
/**
* find all the keys by linear search
*/
private static void findAllViaLinearSearch()
{
for ( String lookFor : keys )
{
boolean found = false;
for ( String candidate : keys )
{
if ( lookFor.equals( candidate ) )
{
found = true;
break;
}
}
}
}
/**
* generate N random keys
*
* @param n how many keys to generate
*/
private static void generate( int n )
{
keys = new String[ n ];
for ( int i = 0; i < n; i++ )
{
keys[ i ] = Long.toString( wheel.nextLong() );
}
}
/**
* main method. Compare speeds of lookup methods.
*
* @param args not used
*/
public static void main( String[] args )
{
for ( int n = 1; n <= 10000; n *= 10 )
{
generate( n );
build();
final long t1 = System.nanoTime();
findAllViaBinarySearch();
final long t2 = System.nanoTime();
findAllViaHashSet();
final long t3 = System.nanoTime();
findAllViaLinearSearch();
final long t4 = System.nanoTime();
out.println( "n:" +
n +
" binary search: " +
( t2 - t1 ) +
" HashSet: " +
( t3 - t2 ) +
" Linear: " +
( t4 - t3 ) );
}
// Here is the output on my machine With Sun's JDK 1.6.0_04+, client.
// times are in nanoseconds, smaller is better.
// Linear is best for 10 or fewer, then HashSet.
// Binary search is never optimal.
// n:1 binary search: 21600 HashSet: 9720 Linear: 6400*
// n:10 binary search: 58720 HashSet: 11360 Linear: 11120*
// n:100 binary search: 707320 HashSet: 97520* Linear: 695960
// n:1000 binary search: 1294360 HashSet: 1255480* Linear: 10911040
// n:10000 binary search: 9823600 HashSet: 3920200* Linear: 1513846600
// Here is the output on my machine with JET 6.5 native compiler.
// n:1 binary search: 5520 HashSet: 4760 Linear: 1240*
// n:10 binary search: 3560 HashSet: 2480 Linear: 2400*
// n:100 binary search: 28160 HashSet: 5480* Linear: 44840
// n:1000 binary search: 408840 HashSet: 43560* Linear: 7862960
// n:10000 binary search: 9142440 HashSet: 2295320* Linear: 1852690520
}
}