设计问题：如何最好地使用构图

Question

我正在做一个项目，对它的设计有一些疑问。我怎样才能最好地设计以下问题（在 JAVA 中）：

具有以下属性的A 类：

• HashSet 像素，其中每个像素具有 x,y 坐标和值 v 介于 0-1 之间。
• B类的实例。

B类具有以下功能：

• 一个获取像素并返回其左邻居的函数。

当我在课堂上时，AI 想在 A 中的每个像素上使用 B.function 并仅在它尚未存在时将其添加到 HashSet 中。问题是我不想将 HashSet 发送到函数，如果它可能已经存在，从函数返回新的 Pixel 实例有多糟糕（该函数将在许多像素上运行并将创建许多未使用的实例像素）。

我还有什么其他选择？

Answer 1

由于您使用，Set<Pixel>您必须创建新 Pixel实例来检查它是否存在于集合中。

如果N调用方法后 set 包含元素，B.function您将创建额外的N Pixel节点。如果所有元素都是新的，则只需将它们添加到集合中，否则Garbage Collection需要清除它们。缺点之一是我们需要创建m（其中m <= N- 集合中已存在的 -s 数量Pixel），然后我们需要通过 收集它们GC。比率有多大m/N取决于您的算法和您实际在做什么。

N = 1_000_000让我们计算一下集合中的像素需要消耗多少内存。我们知道intis a4 bytes和doubleis 8 bytes，让我们8 bytes为对象和8 bytes引用添加额外的内容。它给出了对象32 bytes的每个实例Pixel。我们需要创建N给出 的对象32MB。假设我们的比率是50%这样，16MB我们分配只是为了检查它是否需要。

如果这是您无法支付的成本，您需要开发允许您按Set<Pixel>顺序迭代的算法left-to-right。所以， 的左邻居Pixel X是 before X。

假设 的左邻居Pixel X(x, y)是像素X'(x - 1, y)。Pixel B(0, y)没有离开邻居。您需要在类中使用TreeSet和实现Comparable<Pixel>接口Pixel。简单的实现可能如下所示：

@Override
public int compareTo(Pixel o) {
    return this.y == o.y ? this.x - o.x : this.y - o.y;
}

这允许您按从左到右的顺序迭代集合：(0, 0), (1, 0), ...., (x - 1, y), (x, y), (x + 1, y), ... , (maxX, maxY)。因此，当您迭代它时，您可以检查前一个元素是否是 current 的左邻居Pixel。示例实现如下所示：

void addNeighboursIfNeeded() {
    Set<Pixel> neighbours = new HashSet<>(pixels.size());
    Pixel last = null;
    for (Pixel p : pixels) {
        if (p.getX() == 0 || p.isLeftNeighbour(last)) {
            // a left border pixel
            // or last checked element is a left neighbour of current pixel.
            last = p;
            continue;
        }
        // last element was not our left-neighbour so we need to call b method
        Pixel left = b.getLeft(p);
        neighbours.add(left);
        last = p;
    }
    // add all new neigbours
    pixels.addAll(neighbours);
}

这应该允许您保存为重复Pixel对象分配的内存。