如何改进此搜索算法运行时？

Question

我正在努力解决几年前我遇到的一个面试问题，为即将到来的面试做准备。问题在此处的 pdf 中进行了概述。我使用 DFS 编写了一个简单的解决方案，该解决方案适用于文档中概述的示例，但我无法使程序满足以下条件

对于包含 10,000 个已占用 Geos 的 10,000 x 10,000 GeoBlock，您的代码应在不到一秒的时间内生成正确答案。

为了测试这一点，我生成了一个包含 10000 个随机条目的 CSV 文件，当我针对它运行代码时，平均只需 2 秒多一点就可以找到其中的最大地理块。除了在更快的笔记本电脑上运行之外，我不确定可以对我的方法进行哪些改进以将运行时间减少一半以上。从我的调查来看，搜索本身似乎只需要大约 8ms，所以也许我将数据加载到内存中的方式是低效的部分？

我非常感谢有关如何改进的建议。见下面的代码：

地理块分析器

package analyzer.block.geo.main;

import analyzer.block.geo.model.Geo;
import analyzer.block.geo.result.GeoResult;

import java.awt.*;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.time.format.DateTimeParseException;
import java.util.List;
import java.util.*;

public class GeoBlockAnalyzer {

  private static final DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd");
  private final int width;
  private final int height;
  private final String csvFilePath;
  private GeoResult result = new GeoResult();

  // Map of the geo id and respective geo object
  private final Map<Integer, Geo> geoMap = new HashMap<>();
  // Map of coordinates to each geo in the grid
  private final Map<Point, Geo> coordMap = new HashMap<>();

  /**
   * Constructs a geo grid of the given width and height, populated with the geo data provided in
   * the csv file
   *
   * @param width the width of the grid
   * @param height the height of the grid
   * @param csvFilePath the csv file containing the geo data
   * @throws IOException
   */
  public GeoBlockAnalyzer(final int width, final int height, final String csvFilePath)
      throws IOException {

    if (!Files.exists(Paths.get(csvFilePath)) || Files.isDirectory(Paths.get(csvFilePath))) {
      throw new FileNotFoundException(csvFilePath);
    }

    if (width <= 0 || height <= 0) {
      throw new IllegalArgumentException("Input height or width is 0 or smaller");
    }

    this.width = width;
    this.height = height;
    this.csvFilePath = csvFilePath;

    populateGeoGrid();
    populateCoordinatesMap();
    calculateGeoNeighbours();
    // printNeighbours();
  }

  /** @return the largest geo block in the input grid */
  public GeoResult getLargestGeoBlock() {
    for (final Geo geo : this.geoMap.values()) {
      final List<Geo> visited = new ArrayList<>();
      search(geo, visited);
    }
    return this.result;
  }

  /**
   * Iterative DFS implementation to find largest geo block.
   *
   * @param geo the geo to be evaluated
   * @param visited list of visited geos
   */
  private void search(Geo geo, final List<Geo> visited) {
    final Deque<Geo> stack = new LinkedList<>();
    stack.push(geo);
    while (!stack.isEmpty()) {
      geo = stack.pop();
      if (visited.contains(geo)) {
        continue;
      }
      visited.add(geo);

      final List<Geo> neighbours = geo.getNeighbours();
      for (int i = neighbours.size() - 1; i >= 0; i--) {
        final Geo g = neighbours.get(i);
        if (!visited.contains(g)) {
          stack.push(g);
        }
      }
    }
    if (this.result.getSize() < visited.size()) {
      this.result = new GeoResult(visited);
    }
  }

  /**
   * Creates a map of the geo grid from the csv file data
   *
   * @throws IOException
   */
  private void populateGeoGrid() throws IOException {
    try (final BufferedReader br = Files.newBufferedReader(Paths.get(this.csvFilePath))) {
      int lineNumber = 0;
      String line = "";
      while ((line = br.readLine()) != null) {
        lineNumber++;
        final String[] geoData = line.split(",");
        LocalDate dateOccupied = null;

        // Handle for empty csv cells
        for (int i = 0; i < geoData.length; i++) {
          // Remove leading and trailing whitespace
          geoData[i] = geoData[i].replace(" ", "");

          if (geoData[i].isEmpty() || geoData.length > 3) {
            throw new IllegalArgumentException(
                "There is missing data in the csv file at line: " + lineNumber);
          }
        }
        try {
          dateOccupied = LocalDate.parse(geoData[2], formatter);
        } catch (final DateTimeParseException e) {
          throw new IllegalArgumentException("There input date is invalid on line: " + lineNumber);
        }
        this.geoMap.put(
            Integer.parseInt(geoData[0]),
            new Geo(Integer.parseInt(geoData[0]), geoData[1], dateOccupied));
      }
    }
  }

  /** Create a map of each coordinate in the grid to its respective geo */
  private void populateCoordinatesMap() {
    // Using the geo id, calculate its point on the grid
    for (int i = this.height - 1; i >= 0; i--) {
      int blockId = (i * this.width);
      for (int j = 0; j < this.width; j++) {
        if (this.geoMap.containsKey(blockId)) {
          final Geo geo = this.geoMap.get(blockId);
          geo.setCoordinates(i, j);
          this.coordMap.put(geo.getCoordinates(), geo);
        }
        blockId++;
      }
    }
  }

  private void calculateGeoNeighbours() {
    for (final Geo geo : this.geoMap.values()) {
      addNeighboursToGeo(geo);
    }
  }

  private void addNeighboursToGeo(final Geo geo) {
    final int x = geo.getCoordinates().x;
    final int y = geo.getCoordinates().y;

    final Point[] possibleNeighbours = {
      new Point(x, y + 1), new Point(x - 1, y), new Point(x + 1, y), new Point(x, y - 1)
    };

    Geo g;
    for (final Point p : possibleNeighbours) {
      if (this.coordMap.containsKey(p)) {
        g = this.coordMap.get(p);
        if (g != null) {
          geo.getNeighbours().add(g);
        }
      }
    }
  }

  private void printNeighbours() {
    for (final Geo geo : this.geoMap.values()) {
      System.out.println("Geo " + geo.getId() + " has the following neighbours: ");
      for (final Geo g : geo.getNeighbours()) {
        System.out.println(g.getId());
      }
    }
  }
}

地理结果

package analyzer.block.geo.result;

import analyzer.block.geo.model.Geo;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class GeoResult {

    private final List<Geo> geosInBlock = new ArrayList<>();

    public GeoResult() {
    }

    public GeoResult(final List<Geo> geosInBlock) {
        this.geosInBlock.addAll(geosInBlock);
    }

    public List<Geo> getGeosInBlock() {
        this.geosInBlock.sort(Comparator.comparingInt(Geo::getId));
        return this.geosInBlock;
    }

    public int getSize() {
        return this.geosInBlock.size();
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append("The geos in the largest cluster of occupied Geos for this GeoBlock are: \n");
        for(final Geo geo : this.geosInBlock) {
            sb.append(geo.toString()).append("\n");
        }
        return sb.toString();
    }
}

地理

package analyzer.block.geo.model;

import java.awt.Point;
import java.time.LocalDate;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class Geo {

    private final int id;
    private final String name;
    private final LocalDate dateOccupied;
    private final Point coordinate;
    private final List<Geo> neighbours = new ArrayList<>();

    public Geo (final int id, final String name, final LocalDate dateOccupied) {
        this.id = id;
        this.name = name;
        this.dateOccupied = dateOccupied;
        this.coordinate = new Point();
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public LocalDate getDateOccupied() {
        return this.dateOccupied;
    }

    public void setCoordinates(final int x, final int y) {
        this.coordinate.setLocation(x, y);
    }

    public Point getCoordinates() {
        return this.coordinate;
    }

    public String toString() {
        return this.id + ", " + this.name + ", " + this.dateOccupied;
    }

    public List<Geo> getNeighbours() {
        return this.neighbours;
    }

    @Override
    public int hashCode() {
        return Objects.hash(this.id, this.name, this.dateOccupied);
    }

    @Override
    public boolean equals(final Object obj) {
        if(this == obj) {
            return true;
        }

        if(obj == null || this.getClass() != obj.getClass()) {
           return false;
        }

        final Geo geo = (Geo) obj;
        return this.id == geo.getId() &&
                this.name.equals(geo.getName()) &&
                this.dateOccupied == geo.getDateOccupied();
    }
}

Answer 1

这里可用的主要优化是概念性的。不幸的是，这种类型的优化不容易教授，也不容易在某处查找参考资料。这里使用的原理是：

使用解析公式来计算已知结果（几乎总是）比（预先）计算它更便宜。[1]

从您的代码和问题的定义可以清楚地看出您没有利用这一原则和问题规范。特别是，直接从问题规范中获取的关键点之一是：

对于包含 10,000 个占用的 Geo 的 10,000 x 10,000 GeoGeoBlock，您的代码应该在一秒内生成正确的答案。

当您阅读此声明时，您应该想到一些事情（在考虑运行时效率时）：

• 10,000^2 是一个比 10,000 大得多的数字（正好大 10,000 倍！）如果您可以维护一个 O(n) 而不是 O(n^2) 的算法（在预期情况下，因为哈希的使用。）
• 接触整个网格（即计算任何 O(1) 操作）将立即产生 O(n^2) 算法；显然，如果可能的话，这是必须避免的事情
• 从问题陈述来看，我们永远不应该期望需要触及 O(n^2) 个地理区域。这应该是关于编写问题的人正在寻找什么的主要暗示。BFS 或 DFS 是 O(N+M) 算法，其中 N,M 是接触的节点和边的数量。因此，我们应该期待 O(n) 搜索。
• 基于以上几点，很明显，对于网格大小为 10,000 x 10,000 和 10,000 个地理区域的问题输入，此处寻找的解决方案应该为 O(10,000)

您提供的解决方案是 O(n^2) 因为，

1. 您使用visited.containswhere visitedis 列表。这在您的测试中没有显示为问题区域，因为我怀疑您正在使用小型地理集群。尝试使用大型地理集群（一个包含 10,000 个地理区域）。与具有 3 个地理区域的最大集群相比，您应该会发现速度显着下降。这里的解决方案是使用高效的数据结构visited，一些想到的是位集（我不知道Java是否有任何可用的，但任何像样的语言都应该）或散列集（显然Java有一些可用的。）因为您在测试中没有注意到这一点，这对我来说表明您没有足够好地审查/测试您的代码，并提供足够多的您期望的极端情况的示例。这应该在对代码的任何彻底测试/分析中立即出现。根据我的评论，我希望在发布问题之前看到这种类型的基础工作/分析完成。
2. 您触摸 function/member 中的整个 10,000 x 10,000 网格populateCoordinatesMap。这显然已经是 O(n^2)，其中 n=10,000。coordMap请注意，在 of 之外使用的唯一位置populateCoordinatesMap是 in addNeighboursToGeo。这是一个主要瓶颈，并且无缘无故地addNeighboursToGeo可以在 O(1) 时间内计算，而不需要coordMap. 但是，我们仍然可以按原样使用您的代码，并进行下面给出的微小修改。

我希望如何修复（1）是显而易见的。要修复 (2)，请更换populateCoordinatesMap

  /** Create a map of each coordinate in the grid to its respective geo */
  private void populateCoordinatesMap() {
   for (Map.Entry<int,Geo> entry : geoMap.entrySet()) {
     int key = entry.getKey();
     Geo value = entry.getValue();
     int x = key % this.width;
     int y = key / this.width;  
     value.setCoordinates(x, y);
     this.coordMap.put(geo.getCoordinates(), geo); 
   }
  }

请注意这里使用的原理。与之前所做的那样（立即 O(n^2)）迭代整个网格不同，此方法仅迭代占用的 Geos，并使用解析公式来索引 2D 数组（而不是进行大量计算来计算同样的事情。）实际上，此更改populateCoordinatesMap从 O(n^2) 改进为 O(n)。

以下是一些一般性和固执己见的评论：

• 总的来说，我强烈不同意使用面向对象的方法而不是过程方法来解决这个问题。我认为面向对象的方法完全不合理，因为这段代码应该如此简单，但我知道面试官希望看到它。
• 这是您试图解决的一个非常简单的问题，我认为您在这里采用的面向对象的方法将其混淆得如此之多，以至于您无法看到树木的森林（或者可能看到森林的树木。）一种更简单的方法可以考虑如何实现该算法，甚至使用面向对象的方法。
• 从上面的几点可以清楚地看出，您可以从了解您正在使用的语言中使用的可用工具中受益。我的意思是您应该知道哪些容器是现成的，以及在每个容器上使用每个操作的权衡是什么。如果您打算优化代码，您还应该至少了解一种适合您正在使用的语言的合适的分析工具。鉴于您未能发布分析摘要，即使在我要求之后，这表明您不知道 Java 中有这样的工具。学一.

[1] 我没有提供该原则的参考，因为它是第一原则，并且可以通过运行较少的恒定时间操作比运行许多恒定时间操作更便宜的事实来解释。这里的假设是已知的分析形式需要较少的计算。这条规则偶尔也有例外。但应该强调的是，此类例外几乎总是因为硬件限制或优势。例如，在计算汉明距离时，使用预先计算的 LUT 来计算硬件架构上的总体计数更便宜，而无需访问 SSE 寄存器/操作。