IncreasingEntropyOfFingerList.java

IncreasingEntropyOfFingerList.java

package fi.helsinki.coderodde.util;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class IncreasingEntropyOfFingerList {
    
    public static void main(String[] args) {
        FingerList fingerList = new FingerList();
        Random random = new Random(13L);
        double previousEntropy = Double.NEGATIVE_INFINITY;
        
        System.out.println(">>> Finger packed at the beginning of the list:");

        for (int i = 0; i < 100; i++) {
            double currentEntropy = fingerList.getEntropy();
            System.out.printf("i = %d, H = %.9f, improved = %b\n",
                              i,
                              currentEntropy,
                              FingerList.isLarger(currentEntropy,
                                                  previousEntropy));
            
            fingerList.touch(random.nextInt(FingerList.LIST_SIZE));
            previousEntropy = currentEntropy;
        }
        
        System.out.println(Arrays.toString(fingerList.fingers));
        System.out.println();
        
        System.out.println(">>> Finger distributed evenly:");

        fingerList = new FingerList();
        fingerList.optimize();
        previousEntropy = Double.NEGATIVE_INFINITY;
        
        for (int i = 0; i < 100; i++) {
            double currentEntropy = fingerList.getEntropy();
            System.out.printf("i = %d, H = %.9f, improved = %b\n",
                              i,
                              currentEntropy,
                              FingerList.isLarger(currentEntropy,
                                                  previousEntropy));
            
            fingerList.touch(random.nextInt(FingerList.LIST_SIZE));
            previousEntropy = currentEntropy;
        }
        
        System.out.println(Arrays.toString(fingerList.fingers));
        System.out.println();
        
        System.out.println(">>> Finger distributed randomly:");

        fingerList = new FingerList();
        fingerList.randomize();
        previousEntropy = Double.NEGATIVE_INFINITY;
        
        for (int i = 0; i < 100; i++) {
            double currentEntropy = fingerList.getEntropy();
            System.out.printf("i = %d, H = %.9f, improved = %b\n",
                              i,
                              currentEntropy,
                              FingerList.isLarger(currentEntropy,
                                                  previousEntropy));
            
            fingerList.touch(random.nextInt(FingerList.LIST_SIZE));
            previousEntropy = currentEntropy;
        }
        
        System.out.println(Arrays.toString(fingerList.fingers));
        System.out.println();
    }
}

class FingerList {
    static final int LIST_SIZE = 10_000;
    static final int FINGER_LIST_SIZE = 100;
    final int[] fingers = new int[FINGER_LIST_SIZE + 1];
    
    FingerList() {
        for (int i = 0; i < FINGER_LIST_SIZE; i++) {
            fingers[i] = i;
        }
        
        fingers[FINGER_LIST_SIZE] = LIST_SIZE;
    }
    
    void optimize() {
        final int offset = FINGER_LIST_SIZE;
        
        for (int i = 0; i < FINGER_LIST_SIZE; i++) {
            fingers[i] = offset + i * FINGER_LIST_SIZE;
        }
    }
    
    void randomize() {
        final Random random = new Random(666);
        final Set<Integer> set = new HashSet<>();
        
        while (set.size() < FINGER_LIST_SIZE) {
            set.add(random.nextInt(LIST_SIZE));
        }
        
        final Integer[] array = set.toArray(new Integer[set.size()]);
        
        Arrays.sort(array);
        
        for (int i = 0; i < FINGER_LIST_SIZE; i++) {
            fingers[i] = array[i];
        }
    }
    
    void touch(final int elementIndex) {
        final int fingerIndex = getFingerIndex(elementIndex);
        
        if (fingerIndex == 0) {
            fingers[0] = fingers[1] / 2;
            return;
        }
        
        if (fingerIndex == FINGER_LIST_SIZE - 1) {
            fingers[FINGER_LIST_SIZE - 1] =
                    (LIST_SIZE - fingers[FINGER_LIST_SIZE - 2]) / 2; 
            return;
        }
        
        if (fingerIndex == FINGER_LIST_SIZE) {
            fingers[FINGER_LIST_SIZE - 1] =
                    (LIST_SIZE - fingers[FINGER_LIST_SIZE - 2]) / 2; 
            return;
        }
        
        final int f1 = fingers[fingerIndex - 1];
        final int f3 = fingers[fingerIndex + 1];
        
        final int distance = f3 - f1;
        
        fingers[fingerIndex] = f1 + distance / 2;
    }
    
    double getEntropy() {
        double sum = 0;
        
        for (int i = 0; i < FINGER_LIST_SIZE; i++) {
            sum += Math.abs(fingers[i + 1] - fingers[i] - FINGER_LIST_SIZE);
        }
        
        return 1.0 - sum / LIST_SIZE;
    }
    
    private int getFingerIndex(final int elementIndex) {
        for (int i = FINGER_LIST_SIZE - 1; i >= 0; i--) {
            if (elementIndex >= fingers[i]) {
                return i;
            }
        }
        
        return 0;
    }
    
    static boolean isLarger(final double a, final double b) {
        return a >= b;
    }
}