8000 Arrays, collections and data structures · githubcs/Java-Coding-Problems@4b208b6 · GitHub
[go: up one dir, main page]
Skip to content

Commit 4b208b6

Browse files
AnghelLeonardAnghelLeonard
committed
Arrays, collections and data structures
1 parent b9dd146 commit 4b208b6

File tree

6 files changed

+247
-0
lines changed

6 files changed

+247
-0
lines changed

‎Chapter05/BONUS_1_ChunkList/README.md

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
**[How To Efficiently Chunk A Java List](https://github.com/AnghelLeonard/Hibernate-SpringBoot/tree/master/ChunkList)**
2+
3+
<b><a href="https://persistencelayer.wixsite.com/springboot-hibernate/post/how-to-efficiently-chunk-a-java-list">If you prefer to read it as a blog-post containing the relevant snippets of code then check this post</a></b>
4+
5+
**Description:** Is a common scenario to have a big `List` and to need to chunk it in multiple smaller `List` of a given size. For example, if we want to employ a concurrent batch implementation we need to give each thread a sublist of items. Chunking a list can be done via Google Guava, `Lists.partition(List list, int size)` [method](https://guava.dev/releases/22.0/api/docs/com/google/common/collect/Lists.html#partition-java.util.List-int-) or Apache Commons Collections, `ListUtils.partition(List list, int size)` [method](https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/ListUtils.html#partition(java.util.List,%20int)). But, it can be implemented in plain Java as well. This application exposes 6 ways to do it. The trade-off is between the speed of implementation and speed of execution. For example, while the implementation relying on grouping collectors is not performing very well, it is quite simple and fast to write it.
6+
7+
**Key points:**
8+
- the fastest execution is provided by `Chunk.java` class which relies on the built-in `List.subList()` method
9+
10+
**Time-performance trend graphic for chunking 500, 1_000_000, 10_000_000 and 20_000_000 items in lists of 5 items:**\
11+
![](https://github.com/AnghelLeonard/Hibernate-SpringBoot/blob/master/ChunkList/head-to-head.png)
12+
13+
-----------------------------------------------------------------------------------------------------------------------
14+
<table>
15+
<tr><td><b>If you need a deep dive into the performance recipes exposed in this repository then I am sure that you will love my book "Spring Boot Persistence Best Practices"</b></td><td><b>If you need a hand of tips and illustrations of 100+ Java persistence performance issues then "Java Persistence Performance Illustrated Guide" is for you.</b></td></tr>
16+
<tr><td>
17+
<a href="https://www.apress.com/us/book/9781484256251"><p align="left"><img src="https://github.com/AnghelLeonard/Hibernate-SpringBoot/blob/master/Spring%20Boot%20Persistence%20Best%20Practices.jpg" height="500" width="450"/></p></a>
18+
</td><td>
19+
<a href="https://leanpub.com/java-persistence-performance-illustrated-guide"><p align="right"><img src="https://github.com/AnghelLeonard/Hibernate-SpringBoot/blob/master/Java%20Persistence%20Performance%20Illustrated%20Guide.jpg" height="500" width="450"/></p></a>
20+
</td></tr></table>
21+
22+
-----------------------------------------------------------------------------------------------------------------------
23+

‎Chapter05/BONUS_1_ChunkList/head-to-head.png

46.4 KB
Loading

‎Chapter05/BONUS_1_ChunkList/pom.xml

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
3+
<modelVersion>4.0.0</modelVersion>
4+
<groupId>com.app</groupId>
5+
<artifactId>BONUS_1_ChunkList</artifactId>
6+
<version>1.0-SNAPSHOT</version>
7+
<packaging>jar</packaging>
8+
<properties>
9+
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
10+
<maven.compiler.source>13</maven.compiler.source>
11+
<maven.compiler.target>13</maven.compiler.target>
12+
</properties>
13+
<name>BONUS_1_ChunkList</name>
14+
</project>

‎Chapter05/BONUS_1_ChunkList/src/main/java/modern/challenge/Chunk.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package modern.challenge;
2+
3+
import java.util.AbstractList;
4+
import java.util.ArrayList;
5+
import java.util.List;
6+
7+
public final class Chunk<T> extends AbstractList<List<T>> {
8+
9+
private final List<T> list;
10+
private final int chunkSize;
11+
12+
public Chunk(List<T> list, int chunkSize) {
13+
this.list = new ArrayList<>(list);
14+
this.chunkSize = chunkSize;
15+
}
16+
17+
public static <T> Chunk<T> ofSize(List<T> list, int chunkSize) {
18+
return new Chunk<>(list, chunkSize);
19+
}
20+
21+
@Override
22+
public List<T> get(int index) {
23+
int start = index * chunkSize;
24+
int end = Math.min(start + chunkSize, list.size());
25+
26+
if (start > end) {
27+
throw new IndexOutOfBoundsException(
28+
"Index should range: 0, " + (size() - 1));
29+
}
30+
31+
return new ArrayList<>(list.subList(start, end));
32+
}
33+
34+
@Override
35+
public int size() {
36+
return (int) Math.ceil((double) list.size() / (double) chunkSize);
37+
}
38+
}

‎Chapter05/BONUS_1_ChunkList/src/main/java/modern/challenge F438 /Lists.java

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
package modern.challenge;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collection;
5+
import java.util.List;
6+
import java.util.concurrent.atomic.AtomicInteger;
7+
import java.util.stream.Collector;
8+
import java.util.stream.Collectors;
9+
10+
public final class Lists {
11+
12+
private Lists() {
13+
throw new AssertionError();
14+
}
15+
16+
public static <T> Collection<List<T>> toChunkV1(List<T> list, int chunkSize) {
17+
18+
if (list == null || list.size() < 2) {
19+
throw new IllegalArgumentException("The list must have at least 1 element");
20+
}
21+
22+
if (chunkSize < 1) {
23+
throw new IllegalArgumentException("Chunk size should be minimum 1");
24+
}
25+
26+
AtomicInteger counter = new AtomicInteger();
27+
Collection<List<T>> result = list.stream()
28+
.collect(Collectors.groupingBy(c -> counter.getAndIncrement() / chunkSize))
29+
.values();
30+
31+
return result;
32+
}
33+
34+
public static <T> Collection<List<T>> toChunkV2(List<T> list, int chunkSize) {
35+
36+
if (list == null || list.size() < 2) {
37+
throw new IllegalArgumentException("The list must have at least 1 element");
38+
}
39+
40+
if (chunkSize < 1) {
41+
throw new IllegalArgumentException("Chunk size should be minimum 1");
42+
}
43+
44+
AtomicInteger counter = new AtomicInteger();
45+
Collection<List<T>> result = list.parallelStream()
46+
.collect(Collectors.groupingBy(c -> counter.getAndIncrement() / chunkSize))
47+
.values();
48+
49+
return result;
50+
}
51+
52+
public static <T> List<List<T>> toChunkV3(List<T> list, int chunkSize) {
53+
54+
if (list == null || list.size() < 2) {
55+
throw new IllegalArgumentException("The list must have at least 1 element");
56+
}
57+
58+
if (chunkSize < 1) {
59+
throw new IllegalArgumentException("Chunk size should be minimum 1");
60+
}
61+
62+
AtomicInteger counter = new AtomicInteger();
63+
List<List<T>> result = new ArrayList<>();
64+
for (T item : list) {
65+
if (counter.getAndIncrement() % chunkSize == 0) {
66+
result.add(new ArrayList<>());
67+
}
68+
result.get(result.size() - 1).add(item);
69+
}
70+
71+
return result;
72+
}
73+
74+
public static <T> List<List<T>> toChunkV4(List<T> list, int chunkSize) {
75+
76+
if (list == null || list.size() < 2) {
77+
throw new IllegalArgumentException("The list must have at least 1 element");
78+
}
79+
80+
if (chunkSize < 1) {
81+
throw new IllegalArgumentException("Chunk size should be minimum 1");
82+
}
83+
84+
List<List<T>> result = list.stream()
85+
.collect(chunkIt(chunkSize));
86+
87+
return result;
88+
}
89+
90+
public static <T> List<List<T>> toChunkV5(List<T> list, int chunkSize) {
91+
92+
if (list == null || list.size() < 2) {
93+
throw new IllegalArgumentException("The list must have at least 1 element");
94+
}
95+
96+
if (chunkSize < 1) {
97+
throw new IllegalArgumentException("Chunk size should be minimum 1");
98+
}
99+
100+
List<List<T>> result = list.parallelStream()
101+
.collect(chunkIt(chunkSize));
102+
103+
return result;
104+
}
105+
106+
public static <T> List<List<T>> toChunkV6(List<T> list, int chunkSize) {
107+
108+
if (list == null || list.size() < 2) {
109+
throw new IllegalArgumentException("The list must have at least 1 element");
110+
}
111+
112+
if (chunkSize < 1) {
113+
throw new IllegalArgumentException("Chunk size should be minimum 1");
114+
}
115+
116+
List<List<T>> result = Chunk.ofSize(list, chunkSize);
117+
118+
return result;
119+
}
120+
121+
private static <T> Collector<T, List<T>, List<List<T>>> chunkIt(int chunkSize) {
122+
return Collector.of(ArrayList::new, List::add, (x, y) -> {
123+
x.addAll(y);
124+
return x;
125+
}, x -> Chunk.ofSize(x, chunkSize), Collector.Characteristics.UNORDERED
126+
);
127+
}
128+
}

‎Chapter05/BONUS_1_ChunkList/src/main/java/modern/challenge/MainApplication.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package modern.challenge;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
import java.util.concurrent.TimeUnit;
6+
7+
public class MainApplication {
8+
9+
public static void main(String[] args) {
10+
List<Integer> list = new ArrayList<>();
11+
for (int i = 1; i <= 1_000_000; i++) {
12+
list.add(i);
13+
}
14+
15+
long startTimeV1 = System.nanoTime();
16+
Lists.toChunkV1(list, 5);//.forEach(System.out::println);
17+
displayExecutionTime(System.nanoTime() - startTimeV1);
18+
19+
long startTimeV2 = System.nanoTime();
20+
Lists.toChunkV2(list, 5);//.forEach(System.out::println);
21+
displayExecutionTime(System.nanoTime() - startTimeV2);
22+
23+
long startTimeV3 = System.nanoTime();
24+
Lists.toChunkV3(list, 5);//.forEach(System.out::println);
25+
displayExecutionTime(System.nanoTime() - startTimeV3);
26+
27+
long startTimeV4 = System.nanoTime();
28+
Lists.toChunkV4(list, 5);//.forEach(System.out::println);
29+
displayExecutionTime(System.nanoTime() - startTimeV4);
30+
31+
long startTimeV5 = System.nanoTime();
32+
Lists.toChunkV5(list, 5);//.forEach(System.out::println);
33+
displayExecutionTime(System.nanoTime() - startTimeV5);
34+
35+
long startTimeV6 = System.nanoTime();
36+
Lists.toChunkV6(list, 5);//.forEach(System.out::println);
37+
displayExecutionTime(System.nanoTime() - startTimeV6);
38+
}
39+
40+
private static void displayExecutionTime(long time) {
41+
System.out.println("Execution time: " + time + " ns" + " ("
42+
+ TimeUnit.MILLISECONDS.convert(time, TimeUnit.NANOSECONDS) + " ms)");
43+
}
44+
}

0 commit comments

Comments
 (0)
0