优化这个 ruby​​ 代码，将数组切换为集合/哈希？

Question

我需要优化这段代码。有什么建议可以让它运行得更快，请告诉我。我没有具体的金额，我希望它能跑得更快，任何建议都会有帮助。就复杂性而言，我想将其保持在 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

Answer 1

尝试执行此操作，然后发布更多代码：

ruby -rprofile your_script your_args

这将在探查器下运行脚本，并生成一个包含结果的漂亮表格。如果您将其发布在这里，更有可能获得更好的帮助。另外，您还可以更准确地了解 CPU 周期的消耗情况。

Answer 2

集合基本上是哈希，哈希相对于数组的优点是查找操作的复杂度为 O(1)。由于您只是迭代整个数组，因此如果您只是用散列替换数组，散列不会提供任何速度改进。

您真正的问题是算法的运行时间是 O(n^2)，因为在给定一组 n 点中，它必须执行 n^2 操作，因为您要将每个点与其他所有可能的点进行匹配。

使用哈希来缓存值可以在一定程度上改进这一点。例如，假设您想要点“a”和点“b”之间的距离。你可以有一个散列@distances，它存储@distances["a,b"] = 52（当然，你必须聪明地知道使用什么作为钥匙）。基本上只是尝试尽可能删除多余的操作。

也就是说，最大的速度提升将来自更智能的算法，但我现在想不出适用的东西。

Answer 3

有些事情很多人都知道，而且不需要你花任何钱。

当您试图猜测如何使代码更快，或者在互联网上搜索某种分析器时，只需在调试器下运行程序并在程序运行缓慢时中断它即可。

这样做几次，每次都仔细记下它在做什么以及为什么。

这是一个 python 示例。

速度越慢，问题就会越明显。