Хеширование дерева выражений

Question

Я работаю над созданием некоторого псевдо-интеллектуального кэширования в LINQ query provider. Я бы хотел (в идеале) использовать дерево выражений заданного запроса в качестве ключа кеша в некоторых сценариях. Тем не менее, я не хочу хранить весь объектный граф сам, так что быстрый способ получить значение hashsum-like из дерева выражений? Или, если я пойду в неправильном направлении, есть ли лучший вариант?

Answer 1

Ум, на самом деле я думаю, что это может быть довольно просто.

Метод ToString() объекта Expression предоставит вам текстовое представление выражения, вы можете сделать хэш, если все, что вам нужно, - это оценить эквивалентность ключа.

Answer 2

Давайте подумаем об этом. Предположительно, вы хотите сохранить (хэш дерева выражений, результат) на карте.

Без сохранения всего дерева вы не можете различать идентичное дерево и столкновение хэшей.

По определению хешируют более крупный набор на меньший набор (поэтому полезен хеш), поэтому по определению у вас будут (по крайней мере, возможность) столкновения.

Когда вы получаете дерево выражения, вы хэширования, а затем посмотрите на результат в вашей карте, что приводит к двум возможностям:

1. это хэш не в карте, тот, который вы не видели раньше. Вы должны позволить этому запустить, так как у вас нет кэшированного результата.

2. это хэш на карте, но поскольку вы не сохранили дерево старых выражений, которое создало хэш на вашей карте, нет никакого способа сравнить вновь переданное выражение со старым. У вас может быть матч или у вас может быть столкновение, , но нет возможности различать эти две возможности. Вы не можете вернуть сохраненный результат, потому что это может быть столкновение.

Кроме того, даже если это не столкновение, даже если это точно такое же выражение дерева, как тот, который вы видели в последний раз, как мы знаем, что поддержка объект - база данных, список, независимо от * не было элементов, добавленных или удаленных или измененных, так что результат, возвращаемый выражением, может отличаться от результата кэширования?

Тем не менее, вы можете хэш дерева рекурсивно:

hashATree: 
if leaf node 
    return hash(node) 
else 
    return hash(node) *OP* hashATree(left.child) *OP* hashATree(right.child) 

где OP является некоторой операции (возможно умножение), или, в более общем hash(node) *OP* accumulate(children.begin(), children.end(), *OP*);

Конечно, это же рекурсии мы использовать для оценки дерева выражений (ожидаем, мы позвоним node.eval(children);)

Answer 3

Возможно, вы можете сделать это, используя представленный здесь код. http://petemontgomery.wordpress.com/2008/08/07/caching-the-results-of-linq-queries/

Это показывает, как решить проблему закрытия и поддерживает локальные коллекции.