Skip to content

Instantly share code, notes, and snippets.

@sameer
Created January 14, 2016 21:01
Show Gist options
  • Save sameer/6e122b74349ca6dfa87f to your computer and use it in GitHub Desktop.
Save sameer/6e122b74349ca6dfa87f to your computer and use it in GitHub Desktop.
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
/**
*
* @author Robotia
*/
public class MapBucketTesting
{
public static void main(String[] args) throws Exception
{
int sample_size = 1000000;
int trials = 100;
//bucket_summary(trials, sample_size);
global_summary(trials, sample_size);
}
public static void bucket_summary(int trials, int sample_size)
{
double[] bucket = new double[2];
for (int i = 0; i < trials; i++)
{
double[] temp = bucket_hash_speed(sample_size, 256);
bucket[0] += temp[0];
bucket[1] += temp[1];
}
System.out.println("Bucket add: " + (bucket[0] / trials) + "ms, get: " + (bucket[1] / trials) + "ms");
}
public static void global_summary(int trials, int sample_size)
{
double[] global = new double[2];
for (int i = 0; i < trials; i++)
{
double[] temp = global_hash_speed(sample_size);
global[0] += temp[0];
global[1] += temp[1];
}
System.out.println("Global add: " + (global[0] / trials) + "ms, get: " + (global[1] / trials) + "ms");
}
public static long now()
{
return System.currentTimeMillis();
}
public static double[] bucket_hash_speed(int sample_size, int buckets)
{
Random r = new Random();
int[][] sample = new int[sample_size][2];
for (int i = 0; i < sample_size; i++)
{
sample[i][0] = r.nextInt();
sample[i][1] = r.nextInt();
}
HashMap[] buckets_map = new HashMap[buckets];
for (int i = 0; i < buckets; i++)
buckets_map[i] = new HashMap<Integer, Object>();
long start = now();
for (int[] single : sample)
{
int hash = ch(single[0], single[1]);
buckets_map[hash % buckets / 2 + buckets / 2].put(hash, "1");
}
long end = now();
int add = (int) (end - start);
System.out.println("Bucket addition took " + (end - start) + "ms!");
start = now();
for (int[] single : sample)
{
int hash = ch(single[0], single[1]);
//buckets_map.get(magic(hash,buckets)).get(hash);
buckets_map[hash % buckets / 2 + buckets / 2].get(hash);
}
end = now();
int get = (int) (end - start);
System.out.println("Bucket get took " + (end - start) + "ms!");
return new double[]
{
add, get
};
}
public static double[] global_hash_speed(int sample_size)
{
Random r = new Random();
int[][] sample = new int[sample_size][2];
for (int i = 0; i < sample_size; i++)
{
sample[i][0] = r.nextInt();
sample[i][1] = r.nextInt();
}
HashMap<Integer, Object> global_map = new HashMap<>();
long start = now();
for (int[] single : sample)
global_map.put(ch(single[0], single[1]), r.nextInt());
long end = now();
int add = (int) (end - start);
System.out.println("Global addition took " + (end - start) + "ms!");
start = now();
for (int[] single : sample)
global_map.get(ch(single[0], single[1]));
end = now();
int get = (int) (end - start);
System.out.println("Global get took " + (end - start) + "ms!");
return new double[]
{
add, get
};
}
public static void collision_test()
{
int r = 30000;
int t = 1;
HashSet<Integer> listing = new HashSet();
for (int x = -r; x <= r; x += t)
for (int y = -r; y <= r; y += t)
if (listing.contains(ch(x, y)))
System.out.println("Conflict detected for " + x + ", " + y);
else
listing.add(ch(x, y));
}
public static int ch(int x, int y)
{
return ((x & 0xFFFF) << 16) | (y & 0xFFFF);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment