Мне нужно оптимизировать этот код.Любые предложения, чтобы сделать это быстрее, пожалуйста, сообщите мне.У меня нет конкретной суммы, которую я хочу, чтобы она пошла быстрее, любое предложение будет полезным.С точки зрения сложности, я хочу сохранить его ниже O (n ^ 2)
Мне интересно, если я пытаюсь преобразовать массив, который я использую, в набор или хэш, потому что это быстрее, верно?Насколько быстрее в плане сложности это может позволить мне работать?
Основная проблема, я думаю, может заключаться в том, что я использую функцию комбинации ruby, которая работает довольно медленно, кто-нибудь знает точно сложность этой функции ruby?Есть ли более быстрая альтернатива этому?
смысл этого кода в основном состоит в том, чтобы найти единственную точку, которая является кратчайшим комбинированным расстоянием от всех других точек, т. Е. (Дом друзей, в который всем удобнее всего идти).здесь есть немного дополнительного кода, который имеет некоторые функции отладки / печати.
class Point
attr_accessor :x, :y, :distance, :done, :count
def initialize(x,y)
@x = x
@y = y
@distance = 0
@closestPoint = []
@done = false
@count = 0
end
end
class Edge
attr_accessor :edge1, :edge2, :weight
def initialize(edge1,edge2,weight)
@edge1 = edge1
@edge2 = edge2
@weight = weight
end
end
class AdjacencyList
attr_accessor :name, :minSumList, :current
def initialize(name)
@name = name
@minSumList = []
@current = nil
@vList = []
@edgeList = []
end
def addVertex(vertex)
@vList.push(vertex)
end
def generateEdges2
minSumNode = nil
current = nil
last = nil
@vList.combination(2) { |vertex1, vertex2|
distance = distance2points(vertex1,vertex2)
edge = Edge.new(vertex1,vertex2,distance)
if (current == nil)
current = vertex1
minSumNode = vertex1
end
vertex1.distance += distance
vertex2.distance += distance
vertex1.count += 1
vertex2.count += 1
if (vertex1.count == @vList.length-1)
vertex1.done = true
elsif (vertex2.count == @vList.length-1)
vertex2.done = true
end
if ((vertex1.distance < minSumNode.distance) && (vertex1.done == true))
minSumNode = vertex1
end
#@edgeList.push(edge)
}
return minSumNode.distance
end
def generateEdges
@vList.combination(2) { |vertex1, vertex2|
distance = distance2points(vertex1,vertex2)
@edgeList.push(Edge.new(vertex1,vertex2,distance))
}
end
def printEdges
@edgeList.each {|edge| puts "(#{edge.edge1.x},#{edge.edge1.y}) <=> (#{edge.edge2.x},#{edge.edge2.y}) weight: #{edge.weight}"}
end
def printDistances
@vList.each {|v| puts "(#{v.x},#{v.y} distance = #{v.distance})"}
end
end
def distance2points(point1,point2)
xdistance = (point1.x - point2.x).abs
ydistance = (point1.y - point2.y).abs
total_raw = xdistance + ydistance
return totaldistance = total_raw - [xdistance,ydistance].min
end
#pointtest1 = Point.new(0,1)
#pointtest2 = Point.new(2,5)
#pointtest3 = Point.new(3,1)
#pointtest4 = Point.new(4,0)
graph = AdjacencyList.new("graph1")
gets
while (line = gets)
graph.addVertex(Point.new(line.split[0].to_i,line.split[1].to_i))
end
#graph.addVertex(pointtest1)
#graph.addVertex(pointtest2)
#graph.addVertex(pointtest3)
#graph.addVertex(pointtest4)
puts graph.generateEdges2
#graph.printEdges
#graph.printDistances