/
suffixes.jl
105 lines (71 loc) · 2.75 KB
/
suffixes.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
using PureFun
using PureFun.Linked: List
using Plots, BenchmarkTools
#=
> Exercise 2.1: Write a function `suffixes` of type List{α} -> List{List{α}}
> that takes a list `xs` and returns a list of all the suffixes of `xs` in
> decreasing order of length. For example:
>
> suffixes([1,2,3,4]) = [[1,2,3,4], [2,3,4], [3,4], [4], []]
>
> Show that the resulting list of suffixes can be generated in $\mathcal{O}(n)$
> time and represented in $\mathcal{O}(n)$ space
=#
# ## Set up a test case
test = [1,2,3,4];
expected_output = [[1,2,3,4], [2,3,4], [3,4], [4], Int[]];
# ## The `suffixes` function
#=
Our strategy is: we'll traverse the input from the right. We'll generate the
suffixes in ascending order and successively place each one at the top of our
solution, so that at the end we have the desired output:
=#
suffixes(l) = foldr( add_suffix, l, init = empty_suffixlist(eltype(l)) );
#=
We still have to define `add_suffix` and `empty_suffixlist`.
For each element, `add_suffix` creates the next suffix by adding the element to
the front of the most recently generated suffix, and then pushes the new suffix
on to the top of the suffix list.
=#
add_suffix(x, sufs) = (x ⇀ sufs[1]) ⇀ sufs;
# For the base case, we initialize a list containing just the empty suffix:
empty_suffixlist(::Type{T}) where T = List{T}() ⇀ List{List{T}}();
# ## Confirm the solution is valid
suffixes(test)
@assert all(collect.(suffixes(test)) .== expected_output)
# ## Time and space complexity
# First, we generate some data for the experiments:
input_lists = List.(1:k for k in 25:25:500);
input_lengths = length.(input_lists);
#=
Now, we measure the time and the space used to generate suffixes. I'd like to
avoid running benchmarking code on a documentation server. But it seems
reasonable by looking at the code that the time required to generate suffixes
will be proportional to the amount of memory allocated, so I'll use memory
allocated during the operation as a proxy for time:
=#
allocated = map(input_lists) do l
@allocated suffixes(l)
end;
suffix_sizes = map(suffixes.(input_lists)) do s
Base.summarysize(s)
end;
#=
Our solution satisfies the $\mathcal{O}(n)$ space requirement:
=#
plot(input_lengths, suffix_sizes/1000,
seriestype = :scatter,
xlabel = "# of input elements",
ylabel = "kB",
title = "Space required to represent all suffixes of a list",
legend = false)
#=
Similarly, the amount of memory allocated in the process of generating the
suffixes is approximately linear in the length of the input:
=#
plot(input_lengths, allocated/1000,
seriestype = :scatter,
xlabel = "# of input elements",
ylabel = "memory allocated (kB)",
title = "Total memory allocated during construction of suffixes",
legend = false)