Я создаю решатель судоку для раскрашивания графов в Julia, поэтому первое, чем я занимаюсь, — это реализация графа. У меня закончена голая структура, то есть я могу создать граф со всеми правыми краями.
Что касается эффективности, в настоящее время она составляет
@timev s = SudokuGraph(3);
> 0.001573 seconds (16.05 k allocations: 1013.641 KiB)
> elapsed time (ns): 1573000
> bytes allocated: 1037968
> pool allocs: 16050
> non-pool GC allocs:1
> malloc() calls: 3
> realloc() calls: 1
Но, честно говоря, я не уверен, хорошо это или плохо.
Вот как это выглядит после первоначального написания и рефакторинга. Буду признателен за советы, как сделать его более идиоматичным / правильным, Джулия, или эффективным.
(Примечание, в set_cell!
я изменил //
к /
чтобы не нарушать выделение синтаксиса здесь)
#Pkg.add("Combinatorics")
using Combinatorics
mutable struct Node
row::Int
col::Int
cell::Int
value::Int
function Node(coords::Tuple{Int,Int})
row, col = coords
return new(row, col, 0, 0)
end
end
function set_cell!(node::Node, size::Int)
col = node.col - 1
row = node.row - 1
node.cell = 1 + floor(((col / size) + row) - (row % size))
end
function get_coordinates(node::Node)::Tuple{Int,Int,Int}
return (node.row, node.col, node.cell)
end
function are_adjacent(nodes::Tuple{Node,Node})::Bool
a, b = get_coordinates.(nodes)
return any(a .== b)
end
struct Edge
nodes::Tuple{Node,Node}
function Edge(nodes::Tuple{Node,Node})
return new(nodes)
end
end
function nodes_to_edges(nodes::Vector{Node})::Vector{Edge}
return Edge.(Tuple.(filter(are_adjacent, Tuple.(combinations(nodes, 2)))))
end
mutable struct SudokuGraph
nodes::Vector{Node}
edges::Vector{Edge}
function SudokuGraph(size::Int)
cols = size^2
space = Iterators.product(1:cols, 1:cols)
nodes = Node.(reshape([space...], cols^2))
set_cell!.(nodes, fill(size))
edges = nodes_to_edges(nodes)
return new(nodes, edges)
end
end
Спасибо!