Abstract Fibonaccii Hack
A Fibonacci algorithm that runs using an abstract parent class.
Introduction
This notebook uses Class definitions, ArrayLists, and Hash Maps. My hypothosis is these data structures are probably the most widely used in the Java language.
Popcorn Hacks
- Provide some reasons why you agree with my hypothesis?
Since Java is centered around object-oriented programming, it would make sense if class definitions were extremely frequently used. ArrayLists are useful for storing any data that might change in length during runtime and HashMaps are useful since you often need to link two pieces of information together.
- Provide some data structures that you think might rival my hypothesis?
Arrays are probably used just as much as ArrayLists and HashMaps since they’re more efficient and are useful in a lot of scenarios since you don’t always need to have variable length.
- Categorize data structure mentioned, tested by college board tested, widely used, fast.
Arrays are tested by college board, widely used, and fast.
/*
* Creator: Nighthawk Coding Society
* Mini Lab Name: Fibonacci sequence, featuring a Stream Algorithm
*
*/
import java.util.ArrayList;
import java.util.HashMap;
import java.util.stream.Stream;
/* Objective will require changing to abstract class with one or more abstract methods below */
abstract class Fibo {
String name; // name or title of method
int size; // nth sequence
int hashID; // counter for hashIDs in hash map
ArrayList<Long> list; // captures current Fibonacci sequence
HashMap<Integer, Object> hash; // captures each sequence leading to final result
public String getName() {
return this.name;
}
/*
Zero parameter constructor uses Telescoping technique to allow setting of the required value nth
@param: none
*/
public Fibo() {
this(8); // telescope to avoid code duplication, using default as 20
}
/*
Construct the nth fibonacci number
@param: nth number, the value is constrained to 92 because of overflow in a long
*/
public Fibo(int nth) {
this.size = nth;
this.list = new ArrayList<>();
this.hashID = 0;
this.hash = new HashMap<>();
//calculate fibonacci and time mvc
this.calc();
}
/*
This Method should be "abstract"
Leave method as protected, as it is only authorized to extender of the class
Make new class that extends and defines calc()
Inside references within this class would change from this to super
Repeat process using for, while, recursion
*/
protected abstract void calc();
/*
Number is added to fibonacci sequence, current state of "list" is added to hash for hashID "num"
*/
public void setData(long num) {
list.add(num);
hash.put(this.hashID++, list.clone());
}
/*
Custom Getter to return last element in fibonacci sequence
*/
public long getNth() {
return list.get(this.size - 1);
}
/*
Custom Getter to return last fibonacci sequence in HashMap
*/
public Object getNthSeq(int i) {
return hash.get(i);
}
/*
Console/Terminal supported print method
*/
public void print() {
System.out.println("Calculation method = " + this.name);
System.out.println("fibonacci Number " + this.size + " = " + this.getNth());
System.out.println("fibonacci List = " + this.list);
System.out.println("fibonacci Hashmap = " + this.hash);
for (int i=0 ; i<this.size; i++ ) {
System.out.println("fibonacci Sequence " + (i+1) + " = " + this.getNthSeq(i));
}
}
}
public class FiboFor extends Fibo {
public FiboFor() {
super();
}
public FiboFor(int nth) {
super(nth);
}
@Override
protected void calc() {
super.name = "FiboFor extends Fibo";
long limit = this.size;
// for loops are likely the most common iteration structure, all the looping facts are in one line
for (long[] f = new long[]{0, 1}; limit-- > 0; f = new long[]{f[1], f[0] + f[1]})
this.setData(f[0]);
}
/*
Tester class method.
*/
static public void main(int... numbers) {
for (int nth : numbers) {
Fibo fib = new FiboFor(nth);
fib.print();
System.out.println();
}
}
}
FiboFor.main(2, 5, 8);
Calculation method = FiboFor extends Fibo
fibonacci Number 2 = 1
fibonacci List = [0, 1]
fibonacci Hashmap = {0=[0], 1=[0, 1]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
Calculation method = FiboFor extends Fibo
fibonacci Number 5 = 3
fibonacci List = [0, 1, 1, 2, 3]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
Calculation method = FiboFor extends Fibo
fibonacci Number 8 = 13
fibonacci List = [0, 1, 1, 2, 3, 5, 8, 13]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
fibonacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
public class FiboStream extends Fibo {
public FiboStream() {
super();
}
public FiboStream(int nth) {
super(nth);
}
@Override
protected void calc() {
super.name = "FiboStream extends Extends";
// Initial element of stream: new long[]{0, 1}
// Lambda expression calculate the next fibo based on the current: f -> new long[]{f[1], f[0] + f[1]}
Stream.iterate(new long[]{0, 1}, f -> new long[]{f[1], f[0] + f[1]})
.limit(super.size) // stream limit
.forEach(f -> super.setData(f[0]) ); // set data in super class
}
/*
Tester class method.
*/
static public void main(int... numbers) {
for (int nth : numbers) {
Fibo fib = new FiboFor(nth);
fib.print();
System.out.println();
}
}
}
FiboStream.main(2, 5, 8);
Calculation method = FiboFor extends Fibo
fibonacci Number 2 = 1
fibonacci List = [0, 1]
fibonacci Hashmap = {0=[0], 1=[0, 1]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
Calculation method = FiboFor extends Fibo
fibonacci Number 5 = 3
fibonacci List = [0, 1, 1, 2, 3]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
Calculation method = FiboFor extends Fibo
fibonacci Number 8 = 13
fibonacci List = [0, 1, 1, 2, 3, 5, 8, 13]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
fibonacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
public class FiboRecursion extends Fibo {
public FiboRecursion() {
super();
}
public FiboRecursion(int nth) {
super(nth);
}
@Override
protected void calc() {
super.name = "FiboRecursion extends Fibo";
// keep repeating the fibbonacci function until the size is reached
for (int i = 0; i < super.size; i++) {
this.setData(fib(i));
}
}
private long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
/*
Tester class method.
*/
static public void main(int... numbers) {
for (int nth : numbers) {
Fibo fib = new FiboFor(nth);
fib.print();
System.out.println();
}
}
}
FiboRecursion.main(2, 5, 8);
Calculation method = FiboFor extends Fibo
fibonacci Number 2 = 1
fibonacci List = [0, 1]
fibonacci Hashmap = {0=[0], 1=[0, 1]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
Calculation method = FiboFor extends Fibo
fibonacci Number 5 = 3
fibonacci List = [0, 1, 1, 2, 3]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
Calculation method = FiboFor extends Fibo
fibonacci Number 8 = 13
fibonacci List = [0, 1, 1, 2, 3, 5, 8, 13]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
fibonacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
public class FiboDp extends Fibo {
public FiboDp() {
super();
}
public FiboDp(int nth) {
super(nth);
}
@Override
protected void calc() {
// basically just start w/ 0 and 1, then keep adding the previous two numbers
// similar to for loop approach but we don't use a separate array for the first two numbers, we just look at the array itself
super.name = "FiboDp extends Fibo";
long[] dp = new long[super.size];
this.setData(0);
if (super.size > 1) this.setData(1);
for (int i = 2; i < super.size; i++) {
this.setData(super.list.get(i - 1) + super.list.get(i - 2));
}
}
/*
Tester class method.
*/
static public void main(int... numbers) {
for (int nth : numbers) {
Fibo fib = new FiboFor(nth);
fib.print();
System.out.println();
}
}
}
FiboDp.main(2, 5, 8);
Calculation method = FiboFor extends Fibo
fibonacci Number 2 = 1
fibonacci List = [0, 1]
fibonacci Hashmap = {0=[0], 1=[0, 1]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
Calculation method = FiboFor extends Fibo
fibonacci Number 5 = 3
fibonacci List = [0, 1, 1, 2, 3]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
Calculation method = FiboFor extends Fibo
fibonacci Number 8 = 13
fibonacci List = [0, 1, 1, 2, 3, 5, 8, 13]
fibonacci Hashmap = {0=[0], 1=[0, 1], 2=[0, 1, 1], 3=[0, 1, 1, 2], 4=[0, 1, 1, 2, 3], 5=[0, 1, 1, 2, 3, 5], 6=[0, 1, 1, 2, 3, 5, 8], 7=[0, 1, 1, 2, 3, 5, 8, 13]}
fibonacci Sequence 1 = [0]
fibonacci Sequence 2 = [0, 1]
fibonacci Sequence 3 = [0, 1, 1]
fibonacci Sequence 4 = [0, 1, 1, 2]
fibonacci Sequence 5 = [0, 1, 1, 2, 3]
fibonacci Sequence 6 = [0, 1, 1, 2, 3, 5]
fibonacci Sequence 7 = [0, 1, 1, 2, 3, 5, 8]
fibonacci Sequence 8 = [0, 1, 1, 2, 3, 5, 8, 13]
import java.util.ArrayList;
import java.util.Collections;
public class FiboTester {
static void testFiboPerformance(Fibo fib, int runs) {
ArrayList<Long> times = new ArrayList<>();
for (int i = 0; i < runs; i++) {
long start = System.nanoTime();
fib.calc();
long end = System.nanoTime();
times.add(end - start);
}
// remove the lowest/highest times
Collections.sort(times);
times.remove(0); // lowest
times.remove(times.size() - 1); // highest
// Calculate average
long averageTime = times.stream().mapToLong(Long::longValue).sum() / times.size();
System.out.println(fib.getName() + " average execution time: " + averageTime + " ns");
}
public static void main(String[] args) {
int n = 50; // uhhhh this is a bit high, but it's fine it gives decent data
// do 12 runs on each of these
testFiboPerformance(new FiboFor(n), 12);
testFiboPerformance(new FiboStream(n), 12);
testFiboPerformance(new FiboRecursion(n), 12);
testFiboPerformance(new FiboDp(n), 12);
}
}
FiboTester.main(null);
FiboFor extends Fibo average execution time: 678448 ns
FiboStream extends Extends average execution time: 708901 ns
FiboRecursion extends Fibo average execution time: 162127755009 ns
FiboDp extends Fibo average execution time: 1091509 ns
Popcorn Hacks
Objectives of these hacks are …
- Understand how to fullfill abstract class requirements using two additional algoritms.
- Use inheritance style of programming to test speed of each algorithm. To test the speed, a.) be aware that the first run is always the slowest b.) to time something, my recommendation is 12 runs on the timed element, through out highest and lowest time in calculations.
- Be sure to make a tester and reporting methods.
.85 basis for text based comparison inside of Jupyter Notebook lesson
My timing results
I got the following for fib(30):
FiboFor extends Fibo average execution time: 19450 ns
FiboStream extends Extends average execution time: 49510 ns
FiboRecursion extends Fibo average execution time: 10486949 ns
FiboDp extends Fibo average execution time: 15200 ns
I think this makes sense for the most part.
- Recursion was extremely slow becaue a lot of calculations were called multiple times, since we do
fib(n-1)andfib(n-2). so when we runfib(5),fib(3)will be run multiple times when bothfib(4)andfib(5)are run. - Stream was a lot faster since it simply went through an array and stored the values by slowly adding to it. However, having to assign these values again at the end to the data array slows it down.
- For was much faster since we only store the two values we need (plus another junk value) and assign the data to the desired array without creating a whole other array and having to assign the values at the end.
- DP was the fastest since we only have to use a single array and keep looking at the final values. It is very similar to the stream approach but uses a direct for loop and uses the original array since it doesn’t have to go through the stream object.
Hacks
Assign in each Team to build a Thymeleaf UI for portfolio_2025 using this example https://thymeleaf.nighthawkcodingsociety.com/mvc/fibonacci as basis. Encorporate into Algorithms menu.
Since there are three teams, one team can do Fibo, others Pali and Factorial. Assign this to people that are struggling for contribution and presentation to checkpoints.
.90 basis for FE presentation in Thymmeleaf to BE call in Spring