Skip to content

Instantly share code, notes, and snippets.

@hamadu

hamadu/Main.java

Created Jun 28, 2017
Embed
What would you like to do?
CountDegree
import java.util.*;
public class Main {
public static void main(String[] args) {
long time = 0;
for (long s = 1 ; s <= 10 ; s++) {
int[] g = gen(s);
time += takeIHM(g);
}
System.out.println("done:" + time / 10 / 1000);
}
public static int[] gen(long seed) {
Random rand = new Random(seed);
int size = 2_000_000;
int[] ret = new int[size];
for (int i = 0 ; i < size ; i++) {
ret[i] = rand.nextInt(1_000_000_000);
}
return ret;
}
public static long takeHM(int[] a) {
long time = System.nanoTime();
Map<Integer,Integer> degree = new HashMap<>();
for (int i = 0 ; i < a.length ; i++) {
degree.put(a[i], degree.getOrDefault(a[i], 0)+1);
}
return System.nanoTime()-time;
}
public static long takeSHM(int[] a) {
long time = System.nanoTime();
Map<Integer,Integer> degree = new HashMap<>(a.length*2);
for (int i = 0 ; i < a.length ; i++) {
degree.put(a[i], degree.getOrDefault(a[i], 0)+1);
}
return System.nanoTime()-time;
}
public static long takeSort(int[] a) {
long time = System.nanoTime();
Arrays.sort(a);
for (int i = 0 ; i < a.length ; ) {
int j = i;
while (j < a.length && a[i] == a[j]) {
j++;
}
i = j;
}
return System.nanoTime() - time;
}
public static long takeIHM(int[] a) {
long time = System.nanoTime();
int n = a.length;
int M = (1<<22);
IntHashMap degree = new IntHashMap(M, 0);
for (int i = 0 ; i < n ; i++) {
if (degree.containsKey(a[i])) {
degree.put(a[i], degree.get(a[i])+1);
} else {
degree.put(a[i], 1);
}
}
return System.nanoTime() - time;
}
public static class IntHashMap {
int defaultValue;
int M;
int[] next;
int[] entryKey;
int[] entryValue;
int nextIndex;
public IntHashMap(int capacity, int defaultValue) {
int c = Math.max(32, Integer.highestOneBit(capacity-1)<<1);
this.defaultValue = defaultValue;
this.next = new int[c];
this.entryKey = new int[c];
this.entryValue = new int[c];
this.M = c / 2;
this.nextIndex = M;
Arrays.fill(next, -1);
Arrays.fill(entryValue, defaultValue);
}
public boolean containsKey(int key) {
return detectEntry(key) >= 0;
}
public int get(int key) {
int pos = detectEntry(key);
if (pos < 0) {
return defaultValue;
}
return entryValue[pos];
}
public void put(int key, int value) {
int pos = detectEntry(key);
if (pos < 0) {
addEntry(-pos-1, key, value);
} else {
entryValue[pos] = value;
}
}
private int detectEntry(int key) {
int pos = hashPosition(key);
while (true) {
if (entryKey[pos] == key) {
return pos;
}
if (next[pos] == -1) {
break;
}
pos = next[pos];
}
return -(pos+1);
}
private void addEntry(int pos, int key, int value) {
assert(next[pos] == -1);
next[pos] = nextIndex++;
int newpos = next[pos];
entryKey[newpos] = key;
entryValue[newpos] = value;
}
private int hashPosition(int key) {
return hash(key) & (M-1);
}
private static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.