Тестирование IsSubset-отношения для нескольких наборов

Question

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

Вот некоторый (неоптимальный) код для иллюстрации желаемой операции:

    public static bool ReachesAdditionalSuccs(
                    ISet<int>   additionalSuccCandidates,
                    ISet<int>[] succsAlreadyReachable)
    {
        ISet<int> curCombinedSuccsReachable = new HashSet<int>();
        foreach (ISet<int> set in succsAlreadyReachable)
            curCombinedSuccsReachable.UnionWith(set);
        return (!additionalSuccCandidates.IsSubsetOf(curCombinedSuccsReachable));
    }

Поскольку мне нужно выполнить эту операцию в процессе расширения и поиска динамического по времени игрового дерева, я не могу предварительно собрать объединенные наборы преемников из-за ограничений памяти. Ни одна из них не помечает узлы как посещенные. Я могу только создать прямой набор преемников, чтобы ускорить что-то.

Теперь мне интересно, какой самый быстрый способ сделать это. В приведенном выше коде я временно строю комбинированный набор в новом Hashset-объекте. Это очень много времени и, конечно, не самый умный способ. Различный подход, который мне пришел в голову, заключается в циклическом прохождении всех узлов и ручном тестировании на всех наборах деталей с использованием Hashsets. Но это также может быть не лучшим способом ...

Последнее, что я придумал, это использование SortedSets, так как они должны легко комбинироваться (в O (n), как в сортировке слиянием), а операция isSubset также имеет O (n) -сложность. Есть ли умный способ достичь этого без самостоятельного кодирования, так что, может быть, даже встроенный в Framwork? Или есть еще более быстрые подходы?

Answer 1

Я думаю, что оптимально, что вы можете сделать для Наборов, это фильтровать числа один за другим, но только до тех пор, пока вы не найдете одно число, которое не содержится ни в одном другом наборе, и не остановитесь прямо там. Выражается с помощью Linq:

public static bool ReachesAdditionalSuccs(
                    ISet<int> additionalSuccCandidates,
                    ISet<int>[] succsAlreadyReachable)
{
    return additionalSuccCandidates.Where(x => !succsAlreadyReachable.Any(set => set.Contains(x)))
                                   .Any();
}

Общее усилие для наихудшего случая (все числа, уже содержащиеся в наборе) будет O(mn) - при условии, что время поиска набора равно O (1) - где m - это число чисел в additionalSuccCandidates и * 1007. * - количество наборов в succsAlreadyReachable.

Одной из следующих оптимизаций будет использование SortedSets - вы можете использовать минимум и максимум, чтобы отфильтровать наборы, которые вам не нужно проверять в первую очередь:

public static bool ReachesAdditionalSuccs(
                    SortedSet<int> additionalSuccCandidates,
                    SortedSet<int>[] succsAlreadyReachable)
{

    var remainingSets = succsAlreadyReachable.Where(set => (set.Min <= additionalSuccCandidates.Min
                                                         && set.Max >= additionalSuccCandidates.Min)
                                                         || (set.Min <= additionalSuccCandidates.Max
                                                         && set.Max >= additionalSuccCandidates.Max))
                                             .ToList();

    return additionalSuccCandidates.Where(x => !remainingSets.Any(set => set.Contains(x)))
                                   .Any();
}