Hello Andrey,
On 07/09/21 7:50 pm, Andrey Turbanov wrote:
On Sun, 5 Sep 2021 12:38:20 GMT, Jaikiran Pai <jai.forums2...@gmail.com> wrote:
Do you mean that converting the keySet() of an
existing Map into an array and then sorting that array and then using
that sorted array to iterate and using these keys to do an additional
lookup for value against the original Map would be more efficient in
this case?
You can convert entrySet() to array. Not a keySet. In this case there is no
need to lookup for values.
I experimented this in a JMH test and the results matched your
expectations. So, I've updated the PR to use array sorting instead of
creating a TreeMap. For reference, here's the JMH benchmark code and the
results:
package org.myapp;
import org.openjdk.jmh.annotations.Benchmark;
import java.util.*;
import java.util.concurrent.*;
import org.openjdk.jmh.annotations.*;
public class MyBenchmark {
@State(Scope.Thread)
public static class TestData {
static final Map<Object, Object> tenItems;
static final Map<Object, Object> hundredItems;
static final Map<Object, Object> thousandItems;
static {
tenItems = new ConcurrentHashMap<>(8);
hundredItems = new ConcurrentHashMap<>(8);
thousandItems = new ConcurrentHashMap<>(8);
for (int i = 0; i < 1000; i++) {
thousandItems.put("foo" + i, "bar");
if (i < 100) {
hundredItems.put("hello" + i, "world");
}
if (i < 10) {
tenItems.put("good" + i, "morning");
}
}
System.out.println("Test data created with " +
tenItems.size() + ", "
+ hundredItems.size() + " and " + thousandItems.size()
+ " Map keys");
}
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public void testTenItemsTreeMapSorting(TestData testData) {
final Map<Object, Object> sorted = new TreeMap(testData.tenItems);
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public void testHundredItemsTreeMapSorting(TestData testData) {
final Map<Object, Object> sorted = new
TreeMap(testData.hundredItems);
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public void testThousandItemsTreeMapSorting(TestData testData) {
final Map<Object, Object> sorted = new
TreeMap(testData.thousandItems);
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public void testTenItemsArraySorting(TestData testData) {
var entries = testData.tenItems.entrySet().toArray(new
Map.Entry<?, ?>[0]);
Arrays.sort(entries, new Comparator<Map.Entry<?, ?>>() {
@Override
public int compare(Map.Entry<?, ?> o1, Map.Entry<?, ?> o2) {
return ((String) o1.getKey()).compareTo((String)
o2.getKey());
}
});
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public void testHundredItemsArraySorting(TestData testData) {
var entries = testData.hundredItems.entrySet().toArray(new
Map.Entry<?, ?>[0]);
Arrays.sort(entries, new Comparator<Map.Entry<?, ?>>() {
@Override
public int compare(Map.Entry<?, ?> o1, Map.Entry<?, ?> o2) {
return ((String) o1.getKey()).compareTo((String)
o2.getKey());
}
});
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public void testThousandItemsArraySorting(TestData testData) {
var entries = testData.thousandItems.entrySet().toArray(new
Map.Entry<?, ?>[0]);
Arrays.sort(entries, new Comparator<Map.Entry<?, ?>>() {
@Override
public int compare(Map.Entry<?, ?> o1, Map.Entry<?, ?> o2) {
return ((String) o1.getKey()).compareTo((String)
o2.getKey());
}
});
}
}
Results:
Benchmark Mode Cnt Score Error Units
MyBenchmark.testHundredItemsArraySorting avgt 25 8.330 ± 0.147
us/op
MyBenchmark.testHundredItemsTreeMapSorting avgt 25 8.637 ± 0.333
us/op
MyBenchmark.testTenItemsArraySorting avgt 25 0.261 ± 0.006
us/op
MyBenchmark.testTenItemsTreeMapSorting avgt 25 0.422 ± 0.007
us/op
MyBenchmark.testThousandItemsArraySorting avgt 25 151.566 ± 1.660
us/op
MyBenchmark.testThousandItemsTreeMapSorting avgt 25 163.767 ± 1.911
us/op
-Jaikiran
