CODEWITHSUNDEEP
javaperformancevariablestreemapclosest
fluffyBall
fluffyBall

Reputation: 23

fastest way to get closest key from a map which contains keys: 5, 10, 15, 20, 25 and so on to 200

I have a few keys which go 5, 10, 15, etc., up to 200 which only contain multiples of 5. With each key there is a string connected like in this example:

5 = test5
10 = test10
15 = test15

I have a random variable which changes and might be between 0 - 500. I want to get the closest key and its string, I found a solution already but I'm wondering if there might be a better solution since this case is using only multiples of 5. 

TreeMap<Long,String> map = new TreeMap<>();
map.put(5L,"a");
map.put(10L,"b");
map.put(25L,"e");
map.put(20L,"d");
map.put(15L,"c");
Long key = 42L;
Map.Entry<Long,String> low = map.floorEntry(key);
Map.Entry<Long,String> high = map.ceilingEntry(key);
Object res = null;
if (low != null && high != null) {
    res = Math.abs(key-low.getKey()) < Math.abs(key-high.getKey())
            ?   low.getValue()
            :   high.getValue();
} else if (low != null || high != null) {
    res = low != null ? low.getValue() : high.getValue();
}
System.out.println(res);

Upvotes: 0

Views: 487

Answers (3)

WJS
WJS

Reputation: 40044

You don't need a sorted map. Just do it with some math.

      long key = ((key + 2) / 5) * 5

The way it works is like this.

  1. If the remainder of key when divided by 5 is either 0,1, or 2, then adding 2 will not affect the division by 5. The remainder will get dropped and multipying by 5 will get the closest lower multiple.

  2. If the remainder of key when divided by 5 is either 3 or 4, then adding 2 will push it to the next higher multiple after doing the same divide and multiply.

      Map<Long, String> map = new HashMap<>();
      map.put(5L, "a");
      map.put(10L, "b");
      map.put(25L, "e");
      map.put(20L, "d");
      map.put(15L, "c");
      map.put(30L, "f");
      map.put(0L, "g");

      Random r = new Random();
      for (int i = 0; i < 20; i++) {
         long key = r.nextInt(31);
         long save = key;

         // simple calculation that guarantees nearest multiple of 5.
         key = ((key + 2) / 5) * 5;

         System.out.printf("Random = %3d,  key = %3d, value = %s%n", save,
               key, map.get(key));
      }

Upvotes: 2

locus2k
locus2k

Reputation: 2935

You can use the modulus operator to get the key you are looking for

You can have a method like such that will calculate the nearest key that is a multiple of 5. 

public Long getNearestKey(Long random) {
   Long modulus = random % 5;
   Long key = modulus < 3 ? random - modulus : random + (5 - modulus);
   return key;
}

Then in your method you call getNearestKey(42L) and it will return the nearest value.

A simple test:

public static void main(String[] args) {
    for(long i = 400; i <= 405; i++) 
        System.out.println(getNearestKey(i));
}


public static Long getNearestKey(Long random) {
    Long modulus = random % 5;
    Long key = modulus < 3 ? random - modulus : random + (5 - modulus);
    return key;
}

Output:

400
400 
400
405
405
405

Upvotes: 2

Ashutosh
Ashutosh

Reputation: 1107

A simple approach can be finding the nearest multiple of 5 to your given random number and check if that number exist in map or not ( O(1)). If exist that will be the answer if does not max (200) or minimum(5) will be the answer.

Max 200 -> for the numbers greater than 200
Min 5 -> for the numbers less than 5

For numbers in between -
lets take and example as 143 so the nearest multiple of 5 will be 145. That can be found easily.

Upvotes: 0

Related Questions