Use a programming language of your choice (but has Berkeley APIs) to create a fi

Question

Use a programming language of your choice (but has Berkeley APIs) to create a file-based B-Tree table, to store 16 millions key-value pairs, < K, V >, where K is an integer ranging from 1 to 16 millions, and V is K + 1

Explanation / Answer

import java.util.Arrays; import java.util.Random; public class LongIntParallelHashMultimap { private static final long NULL = Long.MIN_VALUE; private final long[] keys; private final int[] values; private int size; public LongIntParallelHashMultimap(int capacity) { keys = new long[capacity]; values = new int[capacity]; Arrays.fill(keys, NULL); } public void put(long key, int value) { if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL); if (size == keys.length) throw new IllegalStateException("map is full"); int index = indexFor(key); while (keys[index] != NULL) { index = successor(index); } keys[index] = key; values[index] = value; ++size; } public int get(long key, int[] hits) { if (key == NULL) throw new IllegalArgumentException("key cannot be " + NULL); int index = indexFor(key); int hitIndex = 0; while (keys[index] != NULL) { if (keys[index] == key) { hits[hitIndex] = values[index]; ++hitIndex; if (hitIndex == hits.length) break; } index = successor(index); } return hitIndex; } private int indexFor(long key) { return Math.abs((int) (key % keys.length)); } private int successor(int index) { index++; return index >= keys.length ? index - keys.length : index; } public int size() { return size; } public static class PerfTest { public static void main(String... args) { int values = 110* 1000 * 1000; long start0 = System.nanoTime(); long[] keysValues = generateKeys(values); LongIntParallelHashMultimap map = new LongIntParallelHashMultimap(222222227); long start = System.nanoTime(); addKeyValues(values, keysValues, map); long mid = System.nanoTime(); int sum = lookUpKeyValues(values, keysValues, map); long time = System.nanoTime(); System.out.printf("Generated %.1f M keys/s, Added %.1f M/s and looked up %.1f M/s%n", values * 1e3 / (start - start0), values * 1e3 / (mid - start), values * 1e3 / (time - mid)); System.out.println("Expected " + values + " got " + sum); } private static long[] generateKeys(int values) { Random rand = new Random(); long[] keysValues = new long[values]; for (int i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.