Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
abstract UTree{T}
immutable UTreeBranch{T} <: UTree{T}
left::UTree{T}
right::UTree{T}
end
immutable UTreeLeaf{T} <: UTree{T}
v::T
end
islead(u::Uint128) = (u >> 127) != 0
islead(u::Uint64) = (u >> 63) != 0
islead(u::Uint32) = (u >> 31) != 0
islead(u::Uint16) = (u >> 15) != 0
islead(u::Uint8) = (u >> 7) != 0
import Base.getindex, Base.rand, Base.show
getindex{T}(t::UTreeBranch{T},u) = islead(u) ? getindex(t.right, u << 1) : getindex(t.left, u << 1)
getindex{T}(t::UTreeLeaf{T},u) = t.v
function additem{T}(t::UTreeLeaf{T},r::T,u)
if u == 0
return UTreeLeaf(r)
elseif islead(u)
return UTreeBranch(t,additem(t,r,u << 1))
else
return UTreeBranch(additem(t,r,u << 1),UTreeLeaf(r))
end
end
function additem{T}(t::UTreeBranch{T},r::T,u)
if u == 0
return UTreeLeaf(r)
elseif islead(u)
return UTreeBranch(t.left,additem(t.right,r,u << 1))
else
return UTreeBranch(additem(t.left,r,u << 1),UTreeLeaf(r))
end
end
function utree(probs,labels)
n = length(probs)
t = UTreeLeaf(labels[1])
u = uint64(round(probs[1]*2.0^64))
for i = 2:n
t = additem(t, labels[i],u)
u += uint64(round(probs[i]*2.0^64))
end
t
end
rand{T}(t::UTree{T}) = t[rand(Uint64)]
show{T}(io::IO, t::UTree{T}) = show(io,typeof(t))
n = 100_000
probs = fill(1/n,n)
labels = 1:n
t = utree(probs,labels)
@time for i = 1:100; t = utree(probs,labels); end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment