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

Question

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

Your code should produce correct answers in under a second for a10,000 x 10,000 Geo GeoBlock containing 10,000 occupied Geos.

为了测试这一点，我生成了一个包含 10000 个随机条目的 CSV 文件，当我针对它运行代码时，平均只需 2 秒多一点就可以找到其中的最大地理块。除了在更快的笔记本电脑上运行之外，我不确定可以对我的方法进行哪些改进以将运行时间减少一半以上。从我的调查来看，搜索本身似乎只需要大约 8 毫秒，所以也许我将数据加载到内存中的方式是低效的部分？
我非常感谢有关如何改进的建议。见下面的代码:
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();
    }
}

地理

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

如果没有测试，在我看来，这里的主要块是 map 的文字创建，可能多达 100,000,000 个单元格。如果我们改为 labeled 就没有必要了每个 CSV 条目并有一个函数 getNeighbours(id, width, height)返回可能的邻居 ID 列表(想想模块化算法)。当我们依次迭代每个 CSV 条目时，如果 (1) 已经看到所有邻居 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}
"""