I now have Julia building on my machine and hacked together an implementation of Set that does not use a Dict with a value type of Nothing. I just took the Dict implementation any yanked out everything that referenced the value array. This speeds up the maximal_cliques function by 10%, not nearly as much as profiling had led me to expect. Still, it is a substantial improvement (at the not insubstantial cost of duplicating code.)
here are some timing runs for this code fragment. The maximal_clique function spends most of its time intersecting sets. srand(1) using Graphs g = erdos_renyi_graph(2000, 0.1, is_directed=false) println(length(maximal_cliques(g))) for i = 1:10 @time maximal_cliques(g); end First using the standard implementation of set: _ _ _(_)_ | A fresh approach to technical computing (_) | (_) (_) | Documentation: http://docs.julialang.org _ _ _| |_ __ _ | Type "help()" to list help topics | | | | | | |/ _` | | | | |_| | | | (_| | | Version 0.3.0-prerelease+3157 (2014-05-22 15:55 UTC) _/ |\__'_|_|_|\__'_| | Commit 78b0bb6 (0 days old master) |__/ | x86_64-apple-darwin13.2.0 julia> include("../julia/testclique.jl") 771185 elapsed time: 17.608595005 seconds (4059871816 bytes allocated) elapsed time: 21.266502518 seconds (4059871816 bytes allocated) elapsed time: 21.269725317 seconds (4059871816 bytes allocated) elapsed time: 21.470423426 seconds (4059871816 bytes allocated) elapsed time: 21.983676483 seconds (4059871816 bytes allocated) elapsed time: 22.383507234 seconds (4059871816 bytes allocated) elapsed time: 22.181896568 seconds (4059871816 bytes allocated) elapsed time: 22.666173324 seconds (4059871816 bytes allocated) elapsed time: 22.465582061 seconds (4059871816 bytes allocated) elapsed time: 22.757035778 seconds (4059871816 bytes allocated) And now an implementation of set using a hash table with no value array _ _ _ _(_)_ | A fresh approach to technical computing (_) | (_) (_) | Documentation: http://docs.julialang.org _ _ _| |_ __ _ | Type "help()" to list help topics | | | | | | |/ _` | | | | |_| | | | (_| | | Version 0.3.0-prerelease+3157 (2014-05-22 15:55 UTC) _/ |\__'_|_|_|\__'_| | Commit 78b0bb6* (0 days old master) |__/ | x86_64-apple-darwin13.2.0 julia> include("../julia/testclique.jl") 771185 elapsed time: 15.660239671 seconds (3445883848 bytes allocated) elapsed time: 18.93431285 seconds (3445883848 bytes allocated) elapsed time: 19.195180036 seconds (3445883848 bytes allocated) elapsed time: 19.240478387 seconds (3445883848 bytes allocated) elapsed time: 19.787313159 seconds (3445883848 bytes allocated) elapsed time: 20.592924772 seconds (3445883848 bytes allocated) elapsed time: 19.993166581 seconds (3445883848 bytes allocated) elapsed time: 20.102446528 seconds (3445883848 bytes allocated) elapsed time: 20.179236108 seconds (3445883848 bytes allocated) elapsed time: 20.372989869 seconds (3445883848 bytes allocated) I assume that the slowly increasing runtimes are due to memory fragmentation. I'm not sure that it is worth complicating set for such a small gain.
