Created
February 11, 2018 04:30
-
-
Save ifd3f/f67a84b3b6d318a5c748478dc95973ac to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
interface LoopBuffer { | |
int push(int insert); | |
} | |
class ArrayLoopBuffer implements LoopBuffer { | |
private int[] buf; | |
private int index = 0; | |
public ArrayLoopBuffer(int size) { | |
buf = new int[size]; | |
} | |
@Override | |
public int push(int insert) { | |
int out = buf[index]; | |
buf[index] = insert; | |
index = (index + 1) % buf.length; | |
return out; | |
} | |
} | |
class LinkedLoopBuffer implements LoopBuffer { | |
private Node current; | |
public LinkedLoopBuffer(int size) { | |
current = new Node(null); | |
Node last = current; | |
for (int i=1; i < size; i++) { | |
last = new Node(last); | |
} | |
current.next = last; | |
} | |
@Override | |
public int push(int insert) { | |
int out = current.value; | |
current.value = insert; | |
current = current.next; | |
return out; | |
} | |
private class Node { | |
private int value; | |
private Node next; | |
private Node(Node next) { | |
this.next = next; | |
} | |
} | |
} | |
public class LoopBufferTest { | |
public static final int INSERTION_TEST_LENGTH = 1000; | |
public static final int INSERTION_TEST_CYCLES = 100000000; | |
public static final int CREATION_TEST_CYCLES = 1000000; | |
public static final int CREATION_TEST_LENGTH = 1000; | |
public static void main(String[] args) { | |
long start; | |
start = System.currentTimeMillis(); | |
for (int i=0; i < CREATION_TEST_CYCLES; i++) { | |
new ArrayLoopBuffer(CREATION_TEST_LENGTH); | |
} | |
System.out.println("ALB creation time: " + (System.currentTimeMillis() - start)); | |
start = System.currentTimeMillis(); | |
for (int i=0; i < CREATION_TEST_CYCLES; i++) { | |
new LinkedLoopBuffer(CREATION_TEST_LENGTH); | |
} | |
System.out.println("LLB creation time: " + (System.currentTimeMillis() - start)); | |
LoopBuffer alb = new ArrayLoopBuffer(INSERTION_TEST_LENGTH); | |
start = System.currentTimeMillis(); | |
for (int i=0; i < INSERTION_TEST_CYCLES; i++) { | |
alb.push(i); | |
} | |
System.out.println("ALB insertion time: " + (System.currentTimeMillis() - start)); | |
LoopBuffer llb = new LinkedLoopBuffer(INSERTION_TEST_LENGTH); | |
start = System.currentTimeMillis(); | |
for (int i=0; i < INSERTION_TEST_CYCLES; i++) { | |
llb.push(i); | |
} | |
System.out.println("LLB insertion time: " + (System.currentTimeMillis() - start)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment