/java-practice

java-practice

Primary LanguageJava

Practice

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

Table of Contents

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