Last active
September 5, 2024 05:58
-
-
Save coderodde/054eee59bfeb0a8a8ba87a0430bcbefc to your computer and use it in GitHub Desktop.
IncreasingEntropyOfFingerList.java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment