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

Question

我正试图解决几年前我在为即将到来的面试做准备时遇到的一个面试问题。这个问题在一个pdf 这里中得到了概述。我使用DFS编写了一个简单的解决方案，对于文档中概述的示例来说，这个解决方案很好，但是我无法使程序满足

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

为了测试这一点，我生成了一个包含10000个随机条目的CSV文件，当我对它运行代码时，它平均超过2秒才能找到其中最大的geo块。我不知道除了在一台更快的笔记本上运行之外，我的运行时减少一半以上的方法还能做什么改进。从我的调查来看，搜索本身似乎只需要大约8ms，所以我将数据加载到内存中的方式可能是效率低下的部分吗？

我非常希望能就如何改进这个问题提出建议。见下面的代码：

GeoBlockAnalyzer

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());
      }
    }
  }
}

GeoResult

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();
    }
}

Geo

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 Geo GeoBlock，您的代码应该在一秒钟内生成正确的答案。

当你读到这句话时，有几件事应该在你的脑海中浮现(当你想到运行时的效率时)：

• 10,000^2比10,000大得多(正好是10,000倍！)如果您能够维护一个算法，即O(n)，而不是O(n^2) (在预期的情况下，由于使用了散列)，那么就会获得明显的效率增益。
• 对于整个网格，触摸(即计算任意O(1)操作)将立即产生O(n^2)算法；显然，如果可能的话，这是必须避免的。
• 从问题陈述来看，我们不应该期望O(n^2) geo需要被触及。这应该是一个重要的提示，说明写问题的人在寻找什么。BFS或DFS是一种O(N+M)算法，其中N，M是接触到的节点数和边数。因此，我们应该期待一个O(n)搜索。
• 基于以上各点，很明显，对于网格大小为10,000 x 10,000和10,000个地理位置的问题输入，这里所寻找的解决方案应该是O( 10,000 )。

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

1. 您使用visited.contains，其中visited是一个列表。这在您的测试中没有显示为一个问题区域，因为我怀疑您使用的是小型地理集群。尝试使用一个大型的地理集群(一个有10,000个地理集群)。你应该会看到一个主要的减速，比如说最大的集群，有3个地球。这里的解决方案是为visited使用一个高效的数据结构，其中一些在我看来是一个位集 (如果位集有可用的话，我不知道，但是任何合适的语言都应该是)或一个散列集(很明显，Java有一些可用的)。因为您在测试中没有注意到这一点，这对我来说意味着您没有对代码进行足够好的检查/测试，您所期望的角落案例中有足够多的示例。在对您的代码进行彻底的测试/分析时，应该立即提到这一点。根据我的评论，我希望在发布问题之前看到这种基础/分析。
2. 您可以触摸函数/成员populateCoordinatesMap中的整个10,000 x 10,000网格。这显然已经是O(n^2)，其中n=10,000。注意，在coordMap之外使用populateCoordinatesMap的唯一位置是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)。

以下是一些一般性意见和意见：

• 总的来说，对于这个问题，我强烈反对使用面向对象的方法而不是程序性的方法。我认为OO方法是完全没有道理的，因为这个代码应该是多么简单，但我理解面试官想要看到它。
• 这是你想要解决的一个非常简单的问题，我认为你在这里采取的面向对象的方法让它非常混乱，以至于你看不到树木的森林(也许是森林的树木)。即使使用面向对象的方法，该算法的实现方式也可以采用一种简单得多的方法。
• 从上面的要点可以清楚地看到，了解您正在使用的语言中的可用工具会使您受益。我的意思是，您应该知道哪些容器是现成的，以及在每个容器上使用每个操作的代价是什么。如果要研究优化代码，您还应该知道至少有一个用于您所使用的语言的体面的分析工具。考虑到您没有发布分析摘要，即使在我要求之后，这也表明您不知道使用Java的这种工具。学一个。

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

Answer 2

如果不进行测试，在我看来，这里的主要块是地图的字面创建，它可能高达1亿个单元。如果我们使用贴标每个CSV条目，并有一个函数getNeighbours(id, width, height)返回可能的邻居if列表(考虑模块化算法)，那么就不需要这样做了。当我们依次遍历每个CSV条目时，如果(1)邻居ID已经被看到所有的ID都有相同的标签，我们将用该标签标记新的ID；(2)如果没有看到邻居，我们将为新ID使用一个新的标签；如果(3)相邻ID之间存在两个或更多不同的标签，则通过让一个散列将标签映射到它的“最终”标签，将它们组合成一个标签(例如最小标签)。还存储每个标签的总和和大小。当前的解决方案是O(n)，其中n是width x height。这里的想法是O(n)，其中n是被占领的Geos的数量。

在Python中有一些非常粗糙的东西，我不希望所有场景都能被处理，但希望能给您一个想法(对不起，我不懂Java)：

def get_neighbours(id, width, height):
  neighbours = []

  if id % width != 0:
    neighbours.append(id - 1)
  if (id + 1) % width != 0:
    neighbours.append(id + 1)
  if id - width >= 0:
    neighbours.append(id - width)
  if id + width < width * height:
    neighbours.append(id + width)

  return neighbours

def f(data, width, height):
  ids = {}
  labels = {}
  current_label = 0
        
  for line in data:
    [idx, name, dt] = line.split(",")
    idx = int(idx)
    this_label = None
    neighbours = get_neighbours(idx, width, height)
    no_neighbour_was_seen = True

    for n in neighbours:
      # A neighbour was seen
      if n in ids:
        no_neighbour_was_seen = False

        # We have yet to assign a label to this ID
        if not this_label:
          this_label = ids[n]["label"]
          ids[idx] = {"label": this_label, "data": name + " " + dt}
          final_label = labels[this_label]["label"]
          labels[final_label]["size"] += 1
          labels[final_label]["sum"] += idx
          labels[final_label]["IDs"] += [idx]

        # This neighbour has yet to be connected
        elif ids[n]["label"] != this_label:
          old_label = ids[n]["label"]
          old_obj = labels[old_label]
          final_label = labels[this_label]["label"]
          ids[n]["label"] = final_label
          labels[final_label]["size"] += old_obj["size"]
          labels[final_label]["sum"] += old_obj["sum"]
          labels[final_label]["IDs"] += old_obj["IDs"]
          del labels[old_label]

    if no_neighbour_was_seen:
      this_label = current_label
      current_label += 1
      ids[idx] = {"label": this_label, "data": name + " " + dt}
      labels[this_label] = {"label": this_label, "size": 1, "sum": idx, "IDs": [idx]}

  for i in ids:
    print i, ids[i]["label"], ids[i]["data"]
  print ""
  for i in labels:
    print i
    print labels[i]

  return labels, ids
  
          
data = [
  "4, Tom, 2010-10-10",
  "5, Katie, 2010-08-24",
  "6, Nicole, 2011-01-09",
  "11, Mel, 2011-01-01",
  "13, Matt, 2010-10-14",
  "15, Mel, 2011-01-01",
  "17, Patrick, 2011-03-10",
  "21, Catherine, 2011-02-25",
  "22, Michael, 2011-02-25"
]

f(data, 4, 7)
print ""
f(data, 7, 4)

输出：

"""
4 0  Tom  2010-10-10
5 0  Katie  2010-08-24
6 0  Nicole  2011-01-09
11 1  Mel  2011-01-01
13 2  Matt  2010-10-14
15 1  Mel  2011-01-01
17 2  Patrick  2011-03-10
21 2  Catherine  2011-02-25
22 2  Michael  2011-02-25

0
{'sum': 15, 'size': 3, 'IDs': [4, 5, 6], 'label': 0}
1
{'sum': 26, 'size': 2, 'IDs': [11, 15], 'label': 1}
2
{'sum': 73, 'size': 4, 'IDs': [13, 17, 21, 22], 'label': 2}

---

4 0  Tom  2010-10-10
5 0  Katie  2010-08-24
6 0  Nicole  2011-01-09
11 0  Mel  2011-01-01
13 0  Matt  2010-10-14
15 3  Mel  2011-01-01
17 2  Patrick  2011-03-10
21 3  Catherine  2011-02-25
22 3  Michael  2011-02-25

0
{'sum': 39, 'size': 5, 'IDs': [4, 5, 6, 11, 13], 'label': 0}
2
{'sum': 17, 'size': 1, 'IDs': [17], 'label': 2}
3
{'sum': 58, 'size': 3, 'IDs': [21, 22, 15], 'label': 3}
"""