1

我正在开发一个 Java 项目，该项目大量使用观察者模式来确保每个数据对象状态都是最新的。我厌倦了维护这种混乱，并试图实现一个解决方案，将观察者模式的恐惧与我宝贵的数据对象分离。

我能够抽象出这个项目的细节，说我要解决的问题如下：

存在一组表示表达式的对象，每个对象都可以依赖于其他表达式的值。

需要以下两个操作：

eval()：检索给定表达式的值

此操作应返回表达式的最新值，如果所有表达式依赖项现在将重新评估，则将返回该值。但是，除非第二个操作使它的缓存无效，否则不应对表达式进行多次评估：

update()：修改给定的表达式

此操作使表达式和所有当前缓存的直接或传递依赖它的表达式的缓存无效。

此外，还需要一些方便的无内存泄漏方式来管理表达式的生命周期。

伪代码中的所需用法示例：

Expression a = variable(1);
Expression b = variable(3);
Expression s = sum(a,b);
assert(4 == eval(s));    // causes evaluation of expressions a, b and s
assert(4 == eval(s));    // does not cause any evaluations,
                         //     the result should be taken from cache
setValue(a,2);           // contains update() internally, 
                         //     invalidating caches for a and s
assert(5 == eval(s));    // causes evaluation of a and s

OK，功能部分讲完了，接下来就是内存管理部分了。

开发人员必须有一些简单的方法来管理表达式图。理想情况下，分配应该使用 来完成new Sum(a,b)，开发人员应该可以自由地传递表达式实例，而无需太多关于缓存的知识，并且释放应该自动发生，无需开发人员付出任何努力。

并且不能有任何内存泄漏。也就是说，当一个表达式被释放时，与它相关的内存中不能有任何东西。例如，如果要使用观察者模式进行失效，则必须从所有观察者列表中删除该表达式。

问题是：

你用你最喜欢的语言实现这个的方法是什么？

非垃圾收集和函数式语言也受到欢迎，尤其是函数式，因为我根本不明白如何在纯函数式中解决这个问题。

从我的角度来看，最好的解决方案是开发人员错误可能性最小的解决方案。

我故意不发布我当前的实现细节，因为我认为我在我的实现中发现了一个根本缺陷，而且我看不到任何解决方法。不过我稍后会发布。

4

2 回答 2

1

如果有人感兴趣（可能没人感兴趣），我不得不放弃全局缓存的想法并通过使我Expression的 s 自我缓存来解决问题。

我在一个名为ExpressionBase.

该解决方案包括以下内容：

  • 表达式包含对其依赖项的弱引用列表，并在更改时通知它们。这样就没有内存泄漏，也不需要取消订阅。
  • 在表达式评估期间，它会以类似于我之前回答中描述的方式自动检测依赖关系并订阅它们。
  • 保留依赖项列表以防止过早地对中间表达式进行垃圾收集（SumProxyExpression我之前的回答中的情况）。这样，每个弱引用都有其反向强引用，因此弱引用链不会被 GC 破坏，除非这些链无处可去。
于 2010-12-25T05:10:09.507 回答
0

好的，在这里我将尝试解释我使用 Java 语言解决问题的方法。

一切都将在 SumExpression 的示例中进行解释 - 用于将其他两个表达式的结果相加的表达式。

用户代码

我从最直接的方法开始——观察者模式。每个表达式都将侦听其依赖项以查找缓存失效。这是以这种方式实现的 SumExpression 的版本：

public class SumExpression implements Expression<Integer> {
    private final Expression<Integer> a;
    private final Expression<Integer> b;

    Integer value;
    private Listener invalidator = new Listener() {
        @Override
        public void changed() {
            invalidate();
        }
    };

    public SumExpression(SimpleVariable<Integer> a, SimpleVariable<Integer> b) {
        this.a = a;
        this.b = b;
        a.listeners().addListener(invalidator);// don't forget to call it!
        b.listeners().addListener(invalidator);
    }

    public Integer getValue()
    {
        validate();
        return value;
    }

    private void validate() {
        if(value == null)
            value = evaluate;
    }

    private void evaluate() {
        value = null;
    }

    public void dispose() { // USER, DON'T FORGET TO CALL IT!!!
        a.removeListener(invalidator);
        b.removeListener(invalidator);
    }

    ListenerCollection listeners = new ListenerCollection();

    @Override
    public void addListener(Listener l) {
        listeners.addListener(l);
    }

    @Override
    public void removeListener(Listener l) {
        listeners.removeListener(l);
    }
}

但是，有很多地方可能会出错，而且像两个数字相加这样简单的事情应该要简单得多。因此，我通过以下方式将逻辑与缓存分离：

public class SumExpression implements Expression<Integer> {
    private final Expression<Integer> a;
    private final Expression<Integer> b;

    public SumExpression(Expression<Integer> a, Expression<Integer> b)
    {
        this.a = a;
        this.b = b;
    }

    public Integer evaluate(EvaluationContext context)
    {
        return context.getValue(a)+context.getValue(b);
    }
}

简单很多吧？请注意，这里EvaluationContext的职责是双重的：它从缓存中检索值并收集SumExpressionand 表达式a和之间的依赖关系列表b。

核心代码

接下来，我EvaluationContext由全局缓存类提供，它将缓存数据存储在类似于 的结构中WeakHashMap<Expression, Object>，并将依赖图数据存储在 DAG 中，节点类型为WeakReference<Expression>。

这是我对eval和update的实现：

public <T1> T1 eval(final Expression<T1> expression)
{
    Weak weak = weaken(expression);
    T1 result = (T1) cache.get(weak);
    if(result == null) {
        result = expression.evaluate(new EvaluationContext()
        {
            @Override
            public <T2> T2 getValue(Expression<T2> dependency) {
                registerDependency(expression, dependency);
                return eval(dependency);
            }
        });
        cache.put(weak, result);
    }
    return result;
}

public void update(Expression<?> ex) {
    changed(weaken(ex));
}

public void changed(Weak weak) {
    cache.remove(weak);

    dependencies.removeOutgoingArcs(weak);
    for(Weak dependant : new ArrayList<Weak>(dependencies.getIncoming(weak))) {
        changed(dependant);
    }
}

当我的缓存管理器被要求提供一个对象时，它首先检查缓存。如果缓存中没有值，它会要求表达式进行评估。然后，该表达式要求缓存管理器通过调用 getValue() 方法来解决其依赖关系。这会在依赖图中创建一条弧线。该图稍后用于缓存失效。

当表达式无效时，将探索依赖图并且所有依赖缓存都无效。

一旦垃圾收集器（通过 ReferenceQueue）通知我们某些表达式对象的死亡，就会执行缓存和依赖图清理。

一切都按原样工作。但是，有一些棘手的情况。

棘手的案例

第一种情况是悬挂的中间依赖。假设我们有以下类：

class SumProxyExpression implements Expression<Integer> {
    private final Expression<Integer> a;
    private final Expression<Integer> b;

    public SumProxyExpression(Expression<Integer> a, Expression<Integer> b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public Integer evaluate(EvaluationContext context) {
        Expression<Integer> s = new SumExpression(a, b);
        return context.getValue(s);
    }
}

如果我们创建一个实例c=SumProxyExpression(a,b)并为a以后更改值，我们也希望c更改它的值。但是，如果中间体SumExpression已经被垃圾回收，这可能不会发生。为了解决这个问题，我不会从依赖图中删除节点，除非它们是叶节点（只有传入或传出弧）。

另一种情况，我不知道如何解决，如下：

class SelfReferencingExpression implements Expression<List<?>> {
    class Result extends ArrayList<Integer> {
    }

    @Override
    public List<?> evaluate(EvaluationContext resolver) {
        return new Result();
    }
}

如果我缓存这样一个表达式的结果，它永远不会被垃圾回收，因为我保留对缓存值的硬引用（Result），并且它有一个对包含类（表达式）的引用，所以表达式总是可以访问的，但是永远无法使用。

这是内存泄漏，我不知道如何消除它。告诉用户永远不要有这样的参考是可能的，但非常危险，所以我想找到一个更好的解决方案。

替代解决方案

我还考虑过从一个通用的自缓存表达式类继承来实现它，而不是将所有内容都保存在全局缓存中。此解决方案将解决最后一个测试用例（SelfReferencingExpression），但会因第一个测试用例（SumProxyExpression）而失败。所以，我不知道该怎么办。请帮忙。

于 2010-11-14T16:06:00.033 回答