CuboidStatsUtil { public static Map<Long, List<Long>> createDirectChildrenCache(final Set<Long> cuboidSet) { final List<Long> cuboidList = Lists.newArrayList(cuboidSet); Collections.sort(cuboidList); List<Integer> layerIdxList = Lists.newArrayListWithExpectedSize(cuboidList.size()); for (int i = 0; i < cuboidList.size(); i++) { layerIdxList.add(i); } Collections.sort(layerIdxList, new Comparator<Integer>() { @Override public int compare(Integer i1, Integer i2) { Long o1 = cuboidList.get(i1); Long o2 = cuboidList.get(i2); int nBitDiff = Long.bitCount(o1) - Long.bitCount(o2); if (nBitDiff != 0) { return nBitDiff; } return Long.compare(o1, o2); } }); int[] toLayerIdxArray = new int[layerIdxList.size()]; final List<Long> layerCuboidList = Lists.newArrayListWithExpectedSize(cuboidList.size()); for (int i = 0; i < layerIdxList.size(); i++) { int cuboidIdx = layerIdxList.get(i); toLayerIdxArray[cuboidIdx] = i; layerCuboidList.add(cuboidList.get(cuboidIdx)); } int[] previousLayerLastIdxArray = new int[layerIdxList.size()]; int currentBitCount = 0; int previousLayerLastIdx = -1; for (int i = 0; i < layerIdxList.size(); i++) { int cuboidIdx = layerIdxList.get(i); int nBits = Long.bitCount(cuboidList.get(cuboidIdx)); if (nBits > currentBitCount) { currentBitCount = nBits; previousLayerLastIdx = i - 1; } previousLayerLastIdxArray[i] = previousLayerLastIdx; } Map<Long, List<Long>> directChildrenCache = Maps.newHashMap(); for (int i = 0; i < cuboidList.size(); i++) { Long currentCuboid = cuboidList.get(i); LinkedList<Long> directChildren = Lists.newLinkedList(); int lastLayerIdx = previousLayerLastIdxArray[toLayerIdxArray[i]]; if (i - 1 <= lastLayerIdx) { for (int j = i - 1; j >= 0; j--) { checkAndAddDirectChild(directChildren, currentCuboid, cuboidList.get(j)); } } else { for (int j = lastLayerIdx; j >= 0; j--) { checkAndAddDirectChild(directChildren, currentCuboid, layerCuboidList.get(j)); } } directChildrenCache.put(currentCuboid, directChildren); } return directChildrenCache; } private  CuboidStatsUtil(); static Map<Long, Double> calculateCuboidHitProbability(Set<Long> selectionCuboidSet,
            Map<Long, Long> hitFrequencyMap, long nTotalCuboids, double queryUncertaintyRatio); static Map<Long, Long> generateSourceCuboidStats(Map<Long, Long> statistics,
            Map<Long, Double> cuboidHitProbabilityMap, Map<Long, Map<Long, Pair<Long, Long>>> rollingUpSourceMap); static Map<Long, Long> complementRowCountForCuboids(final Map<Long, Long> statistics, Set<Long> cuboids); static Map<Long, Long> adjustCuboidStats(Map<Long, Long> statistics); static void adjustCuboidStats(Map<Long, Long> mandatoryCuboidsWithStats, Map<Long, Long> statistics); static Map<Long, List<Long>> createDirectChildrenCache(final Set<Long> cuboidSet); static boolean isDescendant(long cuboidToCheck, long parentCuboid);  }
@Test public void createDirectChildrenCacheStressTest() { Stopwatch sw = new Stopwatch(); sw.start(); Set<Long> cuboidSet = generateMassCuboidSet(); System.out.println("Time elapsed for creating sorted cuboid list: " + sw.elapsedMillis()); sw.reset(); sw.start(); checkDirectChildrenCacheStressTest(CuboidStatsUtil.createDirectChildrenCache(cuboidSet)); System.out.println("Time elapsed for creating direct children cache: " + sw.elapsedMillis()); sw.stop(); }