Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
303 lines (258 sloc) 7.53 KB
defmodule Vector do
@moduledoc """
This is my (woefully inadequate) attempt at building a Vector with constant-time
lookup using a Hash Array Mapped Trie (HAMT).
While it is blazing fast for getting the value at an index,
it's way slower (than just using a list) in the case of adding values and iterating.
Another shortcoming is the hash function will certainly create collisions and
I didn't bother to account for that in the storage. Sorry :-(
And last, the tree structure isn't compressed, so it gets big fast... don't bother
trying to IO.inspect the sucker!
But this is good enough for a single day's excercise, and I learned a ton
in the process... Yay for learning! :-)
"""
@template :erlang.make_tuple(10, nil)
require Record
Record.defrecordp :vec, Vector, size: 0, children: {nil, @template}
@doc """
Builds a new empty vector.
iex> Vector.new
{Vector, 0, {nil, {nil, nil, nil, nil, nil, nil, nil, nil, nil, nil}}}
"""
def new do
vec()
end
@doc """
Builds a new vector from the given list.
iex> v = Vector.new(["tim", "jen", "mac", "kai"])
iex> Vector.size(v)
4
iex> Vector.get(v, 1)
"jen"
"""
def new(list) do
from_list(list, new)
end
@doc """
Builds a new vector with count items initialized to given value
iex> v = Vector.new(4, "foo")
iex> Vector.size(v)
4
iex> Vector.get(v, 3)
"foo"
"""
def new(count, val) do
Enum.reduce 0..(count-1), new, fn i, v ->
Vector.put(v, i, val)
end
end
@doc """
Get the size of the vector.
"""
def size(vec(size: size)) do
size
end
@doc """
Gets the value from the vector at the given index.
iex> v = Vector.put(nil, 10, "tim")
iex> Vector.get(v, 10)
"tim"
"""
def get(vec(children: children), index) do
do_get(children, hash(index))
end
@doc """
Puts the value in a vector at the given index.
iex> v = Vector.new
iex> v = Vector.put(v, 10, "tim")
iex> Vector.get(v, 10)
"tim"
"""
def put(v = vec(size: size, children: children), index, value) do
children = do_put(children, hash(index), value)
if index >= size do
vec(size: index + 1, children: children)
else
v
end
end
def put(nil, index, value), do: put(new, index, value)
@doc """
Given a vector, an accumulator, and a function, iterate over
each item in the vector passing the item and the accumulator
to the function. The function should return the modified
accumulator.
iex> v = Vector.new([1,2,3])
iex> Vector.reduce(v, 0, &(&2 + &1))
6
"""
def reduce(v = vec(size: size), acc, fun) do
Enum.reduce 0..(size-1), acc, fn index, acc ->
fun.(get(v, index), acc)
end
end
def find(v = vec(size: size), value, index \\ 0) do
cond do
index >= size -> nil
get(v, index) == value -> index
true -> find(v, value, index+1)
end
end
def from_list(list, v), do: from_list(list, v, 0)
def from_list([val | rest], v, index) do
v = put(v, index, val)
from_list(rest, v, index+1)
end
def from_list([], v, _), do: v
# traversed down to a non-existent key
defp do_get(nil, _) do
nil
end
# at the last node of our tree, so we should have a value!
defp do_get({val, _}, []) do
val
end
# traverse down the tree to get the value
defp do_get({_, children}, [pos | hash_rest]) do
node = elem(children, pos)
do_get(node, hash_rest)
end
# at the last leaf of our branch, so store the value
# FIXME our hash function will have collisions, so we really should
# store duplicates properly here, but we don't yet
defp do_put(_, [], value) do
{value, @template}
end
# build a new branch
defp do_put(nil, hash, value) do
do_put({nil, @template}, hash, value)
end
# traverse down the tree to store the value
defp do_put({val, children}, [pos | hash_rest], value) do
tree = do_put(elem(children, pos), hash_rest, value)
{val, put_elem(children, pos, tree)}
end
# generate a hash of the index,
# i.e. a list of positions for each level of depth in the tree
defp hash(index) do
chars = index
|> :erlang.phash2
|> Integer.to_char_list
for c <- chars, do: List.to_integer([c])
end
end
defimpl Enumerable, for: Vector do
def count(v) do
{:ok, Vector.size(v)}
end
# FIXME this is broke
def reduce(v, acc, fun) do
Vector.reduce(v, acc, fun)
end
def member?(v, val) do
{:ok, Vector.index(v, val) != nil}
end
end
ExUnit.start
defmodule VectorTest do
use ExUnit.Case
test "stores a value at an index in a tree structure" do
v = Vector.new
v = Vector.put(v, 0, "tim")
assert v == {Vector, 1, {nil, {
nil, nil, nil, nil, nil, nil, nil, nil,
{nil, {
nil, nil, nil, nil, nil, nil, nil, nil,
{nil, {
nil, nil, nil, nil, nil, nil, nil,
{nil, {
nil, nil,
{nil, {
nil, nil, nil,
{nil, {
nil, nil, nil, nil, nil, nil, nil,
{nil, {
nil, nil,
{nil, {
nil, nil, nil, nil, nil,
{"tim", {nil, nil, nil, nil, nil, nil, nil, nil, nil, nil}},
nil, nil, nil, nil}},
nil, nil, nil, nil, nil, nil, nil}},
nil, nil}},
nil, nil, nil, nil, nil, nil}},
nil, nil, nil, nil, nil, nil, nil}},
nil, nil}},
nil}},
nil}}}
end
test "size" do
v = Vector.new
v = Vector.put(v, 0, "tim")
v = Vector.put(v, 1, "jen")
assert Vector.size(v) == 2
v = Vector.put(v, 9, "mac")
assert Vector.size(v) == 10
end
test "get" do
v = Vector.new
v = Vector.put(v, 0, "tim")
v = Vector.put(v, 1, "jen")
v = Vector.put(v, 2, "mac")
assert Vector.get(v, 0) == "tim"
assert Vector.get(v, 1) == "jen"
assert Vector.get(v, 2) == "mac"
end
test "get non-existent key" do
v = Vector.new
assert Vector.get(v, 10) == nil
end
test "count" do
v = Vector.new([1,2,3])
assert tuple_size(v) == 3
end
test "reduce" do
v = Vector.new([1,2,3])
sum = Vector.reduce(v, 0, &(&1 + &2))
assert sum == 6
end
test "find" do
v = Vector.new([1,2,3])
index = Vector.find(v, 3)
assert index == 2
end
@size 100_000
test "creation speed" do
{microsecs, _} = :timer.tc fn ->
List.duplicate("foo", @size)
end
IO.puts "List creation took #{microsecs} microsecs" # 3,525 microsecs
{microsecs, _} = :timer.tc fn ->
Vector.new(@size, "foo")
end
IO.puts "Vector creation took #{microsecs} microsecs" # 265,647 microsecs
end
test "iteration speed" do
list = List.duplicate("foo", @size)
{microsecs, _} = :timer.tc fn ->
Enum.reduce list, 0, fn _, count -> count + 1 end
end
IO.puts "List traversal took #{microsecs} microsecs" # 1605 microsecs
vector = Vector.new(@size, "foo")
{microsecs, _} = :timer.tc fn ->
Vector.reduce vector, 0, fn _, count -> count + 1 end
end
IO.puts "Vector traversal took #{microsecs} microsecs" # 105,732 microsecs
end
test "access speed" do
list = List.duplicate("foo", @size)
{microsecs, _} = :timer.tc fn ->
assert Enum.at(list, @size-1) == "foo"
end
IO.puts "List access took #{microsecs} microsecs" # 997 microsecs
vector = Vector.new(@size, "foo")
{microsecs, _} = :timer.tc fn ->
assert Vector.get(vector, @size-1) == "foo"
end
IO.puts "Vector access took #{microsecs} microsecs" # 3 microsecs
end
end
Jump to Line
Something went wrong with that request. Please try again.