Practice

Practicing Data Structures, Algorithms, Concurrency, and more in Java!

Table of Contents

• Cool Stuff
  
  • Data Structures
    
  • Algorithms
    
• Build and Run
  
• Property-Based Testing with JUnit-Quickcheck
  
• References
  

Cool Stuff

Data Structures

1. LRU Cache
2. Red Black Tree
3. Disjoint Set
4. D-Way Heap
5. Graph
6. ArrayBlockingQueue
7. Non-blocking Queue
8. Non-blocking Stack
9. Thread-ID based Lock

Algorithms

1. Quick Sort
2. Merge Sort
3. Parallel Merge Sort
4. Shortest Path (Graph)
5. Breadth-First Search (Graph)
6. Depth-First Search (Graph)

Benchmarking

Using jmh you are able to benchmark java code.

To execute the benchmarks in src/jmh, run the following command:

$ gradle jmh

For example, you can see this in action in CacheLinesBenchmark.java where we obtain the following results:

(Run on 2021 M1 Max Macbook Pro)
Benchmark                                          Mode  Cnt  Score   Error  Units
i.w.a.gotchas.CacheLinesBenchmark.touchEveryItem       ss  100   0.167 ± 0.002  ms/op
i.w.a.gotchas.CacheLinesBenchmark.touchEveryLine       ss  100   0.136 ± 0.007  ms/op

Another example is SortingBenchmark.java where we compare the benchmark running time of different sorting algorithms:

Benchmark                                            Mode  Cnt   Score   Error  Units
i.w.a.sorting.SortingBenchmark.classicSort             ss  100  12.142 ± 0.081  ms/op
i.w.a.sorting.SortingBenchmark.heapsort                ss  100  13.768 ± 0.073  ms/op
i.w.a.sorting.SortingBenchmark.mergesort               ss  100  16.790 ± 0.112  ms/op
i.w.a.sorting.SortingBenchmark.parallelMergesort       ss  100  17.958 ± 0.835  ms/op
i.w.a.sorting.SortingBenchmark.parallelStandardSort    ss  100   2.338 ± 0.091  ms/op
i.w.a.sorting.SortingBenchmark.quicksort               ss  100  12.859 ± 0.088  ms/op
i.w.a.sorting.SortingBenchmark.standardSort            ss  100  13.733 ± 0.061  ms/op

Build and Run

This project uses Gradle. Make sure that you have Java installed.

To run the entire suite of tests:

$ ./gradlew test

To run a specific test class:

$ ./gradlew test --tests <TestClassName>

For example, I can run the tests at WeightedShortestPathTest with:

$ ./gradlew test --tests WeightedShortestPathTest

Further, we can a single test by specifying its fully qualified path like so:

$ ./gradlew test --tests io.wcygan.algorithms.graph.pathfinding.WeightedShortestPathTest.testWeightedShortestPath

Building a jar file

Builds a jar containing all dependencies of the project

$ ./gradlew shadowJar

Builds a jar containing only the application classes from the project

$ ./gradlew jar

Property-Based Testing with JUnit-Quickcheck

Property-Based Testing allows you to test the programs you write by feeding a program randomly generated inputs. See Getting Started with JUnit-Quickcheck for more details.

Once you've written a property-based test (like SortingQuickCheck) you can execute it in isolation just as we did before:

$ ./gradlew test --tests io.wcygan.algorithms.sorting.SortingQuickCheckTest.testSortingAlgorithms

You can configure the execution of your property-based test using the elements of the @Property annotation . For example, you can write @Property(trials = 10) to have the test execute 10 times.

References

I'm using the following material as a reference:

1. Introduction to Algorithms
2. Java Concurrency in Practice
3. The Art of Multiprocessor Programming
4. Effective Java