Added benchmark and updated README

4 files changed, 156 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
index f3060e7..9ace9f3 100644
--- a/.gitignore
+++ b/.gitignore
@@ -6,3 +6,4 @@ push_swap
 *.o
 *.ghc
 *.dSYM
+benchmark.json
diff --git a/README.md b/README.md
index dd79553..f39779a 100644
--- a/README.md
+++ b/README.md
@@ -1,3 +1,52 @@
 # push_swap
 
 push_swap project of school 42
+
+# Goal
+
+We have 2 stack at our disposal A and B.
+Stack A is given has an argument to our program,
+we have to sort it using only a limited set of operand.
+
+* `sa` swap the 2 topmost element of A
+* `sb` swap the 2 topmost element of B
+* `ss` swap the 2 topmost element of A & B
+* `pa` pop top of B and push it to A
+* `pb` pop top of A and push it to B
+* `ra` rotate A, everything is shifted up (top becomes bottom)
+* `rb` rotate B
+* `rr` rotate A & B
+* `rra` reverse rotate A,
+        everything is shifted down (bottom becomes top)
+* `rrb` reverse rotate B
+* `rrr` reverse rotate A & B
+
+# Usage
+
+```
+make all
+export ARG=$(echo ./random_stack.rb 1 20)
+./push_swap $(echo $ARG) | ./checker $(echo $ARG)
+```
+
+# Visualizer
+
+```
+export ARG=$(echo ./random_stack.rb 1 20)
+./push_swap $(echo $ARG) | ./visualizer.rb $(echo $ARG)
+```
+
+# Benchmark
+
+Make sure to have Python3.6 >=
+
+```
+python benchmark.py 10 100 5 10
+python benchmark_plot.py
+```
+
+Plot operation distribution
+
+```
+python benchmark_plot.py --dist
+```
diff --git a/benchmark.py b/benchmark.py
new file mode 100644
index 0000000..1460a5e
--- /dev/null
+++ b/benchmark.py
@@ -0,0 +1,48 @@
+import sys
+import time
+import json
+import random
+import collections
+import subprocess
+
+
+def random_stack(start, end):
+    st = list(range(start, end))
+    random.shuffle(st)
+    return st
+
+
+def run_bench_size(size, samples):
+    runs = []
+    for _ in range(samples):
+        st = random_stack(1, size + 1)
+        out = subprocess.check_output([f"./push_swap", *[str(x) for x in st]])
+        ops = out.decode().strip().split("\n")
+        runs.append({
+            "ops_num": len(ops),
+            "ops_counter": dict(collections.Counter(ops)),
+        })
+    return runs
+
+def run_bench(start, end, step, samples=1):
+    bench = {
+        "start": start,
+        "end": end,
+        "step": step,
+        "data": []
+    }
+    for i in range(start, end, step):
+        bench["data"].append(run_bench_size(i, samples))
+    return bench
+
+if __name__ == "__main__":
+    if len(sys.argv) != 4 and len(sys.argv) != 5:
+        print(f"Usage: {sys.argv[0]} start stop step [samples]")
+        sys.exit(1)
+    samples = int(sys.argv[4]) if len(sys.argv) == 5 else 1
+    with open("benchmark.json", "w") as file:
+        bench = run_bench(int(sys.argv[1]),
+                          int(sys.argv[2]),
+                          int(sys.argv[3]),
+                          samples)
+        file.write(json.dumps(bench))
diff --git a/benchmark_plot.py b/benchmark_plot.py
new file mode 100644
index 0000000..ea867ff
--- /dev/null
+++ b/benchmark_plot.py
@@ -0,0 +1,58 @@
+import sys
+import json
+import statistics
+import collections
+import numpy as np
+import matplotlib.pyplot as plt
+
+
+def read_bench():
+    with open("benchmark.json", "r") as file:
+        bench = json.loads(file.read())
+        return bench
+
+
+def plot_bench_ops(b):
+    r = np.arange(b["start"], b["end"], b["step"])
+    nlogn = r * np.log(r)
+    n_square = r ** 2
+
+    means = []
+    for runs in b["data"]:
+        means.append(statistics.mean(
+            [runs[i]["ops_num"] for i in range(len(runs))]
+        ))
+
+    fig, ax = plt.subplots()
+    ax.set(xlabel="stack length", ylabel="op number", title="push_swap benchmark")
+    ax.grid()
+    ax.plot(r, means)
+    ax.plot(r, nlogn, label=r"$n \log(n)$")
+    ax.plot(r, n_square, label=r"$n^2$")
+    ax.plot(r, r, label=r"$n$")
+
+    ax.set_ylim([0, max(means)])
+    ax.set_xlim([0, max(r)])
+    plt.legend()
+    plt.show()
+
+
+def plot_bench_distribution(b):
+    counter = collections.Counter()
+    for runs in b["data"]:
+        for run in runs:
+            counter.update(run["ops_counter"])
+
+    fig, ax = plt.subplots()
+    ax.set(xlabel="op", ylabel="time used", title="push_swap benchmark ops distribution")
+    ax.bar(counter.keys(), counter.values())
+    plt.show()
+
+
+
+if __name__ == "__main__":
+    b = read_bench()
+    if len(sys.argv) == 2 and sys.argv[1] == "--dist":
+        plot_bench_distribution(b)
+    else:
+        plot_bench_ops(b)