kmsquire

module DD

import Base: similar, sizehint, empty!, setindex!, getindex, get,
             pop!, delete!, start, next, done, isempty, length


export DefaultDict

type DefaultDict{K,V,F} <: Associative{K,V}
    d::Dict{K,V}

kmsquire

let ops_prec = (Symbol=>Int)[], prec=0, _op_str, _op, tight
    ops_by_prec = ["= := += -= *= /= //= .//= .*= ./= \\= .\\= ^= .^= %= .%= |= &= \$= => <<= >>= >>>= ~ .+= .-=",
                   "?",
                   "||",
                   "&&",
                   "-- -->",
                   "> < >= <= == === != !== .> .< .>= .<= .== .!= .= .! <: >:",
                   "|> <|",
                   ": ..",
                   "+ - .+ .- | \$",

kmsquire

julia> func(0,.1,.1); @time func(0,.1,10000)
elapsed time: 1.43696256 seconds (800264048 bytes allocated)

julia> func3(0,.1,.1); @time func3(0,.1,10000)
elapsed time: 0.838369673 seconds (800264048 bytes allocated)

julia> func5(0,.1,.1); @time func5(0,.1,10000)
elapsed time: 0.409506126 seconds (1000312 bytes allocated)

kmsquire

# To test pre-patch Dict performance

n = 100000
srand(0x123456)
strs = [randstring(10) for i = 1:n];
nums = rand(Int, n);

# regular map

function dict_insertion_test(d::Dict)

kmsquire

module sp

export sortperf, std_sort_tests

import Base.Sort: InsertionSort, QuickSort, MergeSort, TimSort, Algorithm, Ordering

using DataFrames

# rand functions for testing
randstr(n::Int) = [randstring() for i = 1:n]

kmsquire

macro memoize(ex)
    local f, u, g
    g = randstring(6)
    if isa(ex,Expr) && (ex.head == :function || ex.head == symbol("=")) &&
       !isempty(ex.args) && ex.args[1].head == :call && !isempty(ex.args[1].args)
        f = ex.args[1].args[1]
        ex.args[1].args[1] = u = symbol(string(f,"_unmemoized"))
    else
        error("@memoize must be applied to a method definition")
    end

kmsquire

Here are 3 implemenations of an `OrderedDict` for julia.  The first
creates a `DictItem` class, which is stored as the value in a wrapped
Dict.  The second only stores a vector of keys, and the third
reimplements the standard julia hash-based dictionary inline, and adds
just enough information to maintain key-value order.  

I had other, similar versions along the way, with minor tweaks that 
didn't change the timings much.  This includes a version where
DictItem was immutable.

kmsquire

## modeled after sort tests in python's sortperf.py
##
## Note: as written, it requires DataFrames + https://github.com/HarlanH/DataFrames.jl/pull/83
##
## Kevin Squire
##
##
#
# julia> load("timsort")
#

kmsquire

function _julia_re(name, re)
    sym = symbol("julia_$(string(name))")
    quote
        $(esc(sym)) = $re
        $(esc(sym)) = "(?<"*$(string(name))*">"*$(esc(sym))*")"
    end
end

macro julia_re(name, re)
   _julia_re(name, re)

kmsquire

# Generate sort$n(vs), sortk(n1,...,nk) functions
function gen_sort(n)
    # Generate n symbols to manipulate
    vs = [gensym("v") for i=1:n]
    
    ## These two lines are setup for the sort$n functions

    # Set each symbol equal to an element of the input list
    vss = {:($v = vs[$i]) for (v,i) in enumerate(vs)}