Проблема с IEnumerable, Where и Object.ReferenceEquals - PullRequest
Новая
       23

Проблема с IEnumerable, Where и Object.ReferenceEquals

1 голос
/ 09 апреля 2020

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

Пример: [1|2], [3,1], [3,2] -> [1|2][2|3][3|1]

Я использую Грубая сила, чтобы попробовать все комбинации. Для этого я запускаю цепочку со всеми возможными комбинациями, используя следующий код: 

using System;
using System.Collections.Generic;
using System.Linq;

public static class Dominoes
{
    private class Domino
    {
        public readonly int First;
        public readonly int Last;

        public Domino(int first, int last)
        {
            First = first;
            Last = last;
        }

        public Domino Flip() => new Domino(Last, First);
    }

    private class Chain
    {
        private readonly List<Domino> chained = new List<Domino>();

        private readonly List<Domino> remaining = new List<Domino>();

        private int First => chained[0].First;

        private int Last => chained[chained.Count - 1].Last;

        public bool Complete => remaining.Count == 0 && First == Last;

        private Chain(Domino domino, IEnumerable<Domino> remaining, IEnumerable<Domino> chained = null)
        {
            if (chained != null)
            {
                this.chained.AddRange(chained);
            }

            this.chained.Add(domino);

            this.remaining.AddRange(remaining);
        }

        public static IEnumerable<Chain> Start(IEnumerable<Domino> dominoes)
        {
            var chains = new List<Chain>();

            foreach (var domino in dominoes)
            {
                var remaining = dominoes.Where(d => d != domino);

                chains.Add(new Chain(domino, remaining));
                chains.Add(new Chain(domino.Flip(), remaining));
            }

            return chains;
        }

        public IEnumerable<Chain> Extend()
        {
            var chains = new List<Chain>();

            foreach (var domino in this.remaining)
            {
                var remaining = this.remaining.Where(d => d != domino);

                if (domino.First == Last)
                {
                    chains.Add(new Chain(domino, remaining, chained));
                }

                if (domino.Last == Last)
                {
                    chains.Add(new Chain(domino.Flip(), remaining, chained));
                }
            }

            return chains;
        }
    }

    public static bool CanChain(IEnumerable<(int, int)> dominoes)
    {
        var chains = Chain.Start(dominoes.Select(d => new Domino(d.Item1, d.Item2)));

        return chains.Any() ? Iterate(chains) : true;
    }

    private static bool Iterate(IEnumerable<Chain> chains)
    {
        var newChains = new List<Chain>();

        foreach (var chain in chains)
        {
            if (chain.Complete) return true;

            newChains.AddRange(chain.Extend());
        }

        if (newChains.Count == 0) return false;

        return Iterate(newChains);
    }
}

Тестовый код 

using System;
using Xunit;

public class DominoesTests
{
    [Fact]
    public void Singleton_that_cant_be_chained()
    {
        var dominoes = new[] { (1, 2) };
        Assert.False(Dominoes.CanChain(dominoes));
    }
}

Запуск с использованием dotnet test

Фильтрация для remaining в Chain.Start не работает.

Пример (использование new [] { (1, 2) } в качестве ввода для CanChain) 

# Expected: `Chain: [1|2] Remaining:`
# Actual:   `Chain: [1|2] Remaining: [1|2]`

Если я вызываю .ToList() на dominoes.Select(d => new Domino(d)) in CanChain начинает работать.

EDIT: добавлено больше информации

1 Ответ

3 голосов
/ 09 апреля 2020

Проблема в том, что перечисление Select выполняется не сразу, а с задержкой. Это означает, что каждый раз, когда вы обращаетесь к / 1002 *, возвращенному методом Select(), вы получаете новый список fre sh. Но это также означает, что вы постоянно создаете новые Domino объекты. И поскольку вы не перезаписываете метод Equals(), каждый из этих Domino объектов будет отличаться, даже если они имеют одинаковые значения.

Чтобы показать проблему, проверьте следующий код: 

private class Foobar {
    private readonly int value;

    public Foobar(int v) {
        Console.WriteLine("## CONSTRUCTOR ## Foobar object created with value: "+v);
        this.value = v;
    }

    public override string ToString() {
        return "Foobar("+this.value+")";
    }
}

public static void Main(string[] args) {
    int[] numbers = new [] { 1, 5};
    IEnumerable<Foobar> range = numbers.Select(i => new Foobar(i));

    Console.WriteLine(range.Count());
    foreach (Foobar entry in range) {
        Console.WriteLine("Build an enumerable without "+entry);
        IEnumerable<Foobar> remaining = range.Where(it => it != entry);
        Console.WriteLine("The length of the remaining: "+remaining.Count());
        foreach (Foobar remainingEntry in remaining) {
            Console.WriteLine("Entry of remaining: "+remainingEntry);
        }
    }
}

Когда вы запустите этот код, вы получите следующий вывод: 

## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
2
## CONSTRUCTOR ## Foobar object created with value: 1
Build an enumerable without Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
The length of the remaining: 2
## CONSTRUCTOR ## Foobar object created with value: 1
Entry of remaining: Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 5
Entry of remaining: Foobar(5)
## CONSTRUCTOR ## Foobar object created with value: 5
Build an enumerable without Foobar(5)
## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
The length of the remaining: 2
## CONSTRUCTOR ## Foobar object created with value: 1
Entry of remaining: Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 5
Entry of remaining: Foobar(5)

Как видите, конструктор слишком часто вызывается . Каждый раз, когда кто-то использует IEnumerable из вызова Select(), он снова генерирует перечислимый список, чтобы он не мешал другим параллельным итерациям на тех же данных. Однако, поскольку вы создаете новые объекты внутри оператора Select(), вы будете получать новые объекты для каждого создания IEnumerable из Select().

Как вы уже заметили, для решения проблемы вы используете что-то например, ToList() и один раз для оценки / создания Domino объектов. При одном вызове ToList() выходные изменения изменяются следующим образом: 

## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
2
Build an enumerable without Foobar(1)
The length of the remaining: 1
Entry of remaining: Foobar(5)
Build an enumerable without Foobar(5)
The length of the remaining: 1
Entry of remaining: Foobar(1)

Видите ли, создаются только два объекта, и != будет работать, как и ожидалось, поскольку существуют только эти два объекта.

...