Created
January 31, 2020 20:20
-
-
Save JeffBezanson/e381ea9cbe790d6d8f9bcf473a664f8c to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const CC = Core.Compiler | |
using Base: IdSet | |
# count total number of nodes reachable from a given point | |
function edgecount(G, from, counts = IdDict{Any,Int}()) | |
if haskey(counts, from) | |
return 0 | |
end | |
if !CC.haskey(G, from) | |
return 0 | |
end | |
next = CC.collect(CC.getindex(G, from)) | |
counts[from] = 0 | |
counts[from] = sum(x->edgecount(G, x, counts), next) + length(next) | |
end | |
# sorted list of (node, count) for all nodes | |
function flat_count(G) | |
nodes = CC.collect(CC.keys(G)) | |
sort([(n, edgecount(G, n)) for n in nodes], by = x->x[2]) | |
end | |
# print a tree from the given starting point | |
function showtree(io, G, from, level = 0, seen = IdSet{Any}()) | |
for i = 1:level | |
print(io, " ") | |
end | |
println(io, from, " ", edgecount(G, from)) | |
if !in(from, seen) | |
push!(seen, from) | |
if CC.haskey(G, from) | |
next = CC.collect(CC.getindex(G, from)) | |
for n in next | |
showtree(io, G, n, level+1, seen) | |
end | |
end | |
end | |
end | |
# print the "worst" path through the tree from a given point; i.e. at each | |
# level only follow the (not-yet-seen) link with the highest count. | |
function badpath(io, G, from, seen = IdSet{Any}(), count = edgecount(G, from)) | |
println(io, from, " ", count) | |
push!(seen, from) | |
if CC.haskey(G, from) | |
next = filter(x->!in(x,seen), CC.collect(CC.getindex(G, from))) | |
counts = map(n->edgecount(G, n), next) | |
m = argmax(counts) | |
badpath(io, G, next[m], seen, counts[m]) | |
end | |
end | |
#= | |
Sample run: | |
G = CC.inference_graph; | |
CC.empty!(G); | |
CC.record_edges[] = true | |
using CSV; using REPL; @time precompile(Tuple{typeof(REPL.REPLCompletions.completions), String, Int64}) | |
flat_count(G) | |
4351-element Array{Tuple{Type,Int64},1}: | |
... | |
(Tuple{typeof(*),T,Char} where T<:FilePathsBase.AbstractPath, 9348) | |
(Tuple{typeof(REPL.REPLCompletions.completions),String,Int64,Any}, 10429) | |
(Tuple{typeof(REPL.REPLCompletions.completions),String,Int64}, 10430) | |
(Tuple{typeof(REPL.REPLCompletions.completions),String,Int64,Module}, 10445) | |
(Tuple{typeof(REPL.LineEdit.complete_line),REPL.REPLCompletionProvider,Any}, 11980) | |
f = open("inftree.txt", "w") | |
showtree(f, G, Tuple{typeof(REPL.LineEdit.complete_line),REPL.REPLCompletionProvider,Any}) | |
close(f) | |
badpath(stdout, G, Tuple{typeof(REPL.LineEdit.complete_line),REPL.REPLCompletionProvider,Any}) | |
Tuple{typeof(REPL.LineEdit.complete_line),REPL.REPLCompletionProvider,Any} 12003 | |
Tuple{typeof(REPL.REPLCompletions.completions),String,Int64} 10453 | |
Tuple{typeof(REPL.REPLCompletions.completions),String,Int64,Any} 10452 | |
Tuple{typeof(*),T,String} where T<:FilePathsBase.AbstractPath 9368 | |
Tuple{typeof(string),FilePathsBase.AbstractPath} 9030 | |
... | |
Tuple{Type,DataFrames.SubDataFrame} 4586 | |
Tuple{typeof(convert),Type{Union{}},DataFrames.SubDataFrame} 3 | |
Tuple{Type{MethodError},typeof(convert),Tuple{Core.TypeofBottom,DataFrames.SubDataFrame}} 2 | |
Tuple{Type{MethodError},typeof(convert),Tuple{Core.TypeofBottom,DataFrames.SubDataFrame},UInt64} 1 | |
Tuple{typeof(Core.convert),Type{UInt64},UInt64} 0 | |
=# |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment