3

Начинаю изучать C#, пишу личный проект в тренировочных целях, и столкнулся с такой ситуацией:

Имеется массив inputArray, содержащий 9 экземпляров некоего класса Cell. Одним из полей в Cell является массив из девяти boolean`ов PossibleValues. Требовалось найти в inputArray такие экземпляры Cell, где в PossibleValues есть всего два true и собрать эти Cell (если таковые будут) в новый массив. Я сделал это так:

Cell[] arr = inputArray.Where(x => x.PossibleValues.Where(k => k).Count() == 2).ToArray();

Далее нужно найти в arr такие пары Cell`ов, у которых PossibleValues будут полностью совпадать (т.е. оба true у них будут по одним и тем же индексам), заранее известно, что одинаковые наборы значений PossibleValues будут встречаться не более, чем по два раза. При обнаружении такой пары, нужно запомнить индексы их true и скинуть PossibleValues по этим индексам в false всем Cell в inputArray, кроме тех, что мы только что нашли. Ожидается, что таких пар может быть от 0 до 3.

Есть способ компактно это записать с помощью LINQ?

Update: Обратите внимание, что вывод осуществляется через изменение inputArray.PossibleValues, а не arr (arr это уже выборка тех Cell, где присутствуют только два true в PossibleValues). Класс Cell включает в себя не только PossibleValues, есть и другие поля, которые в задаче не важны. В одном из ответов я выложил свой вариант решения задачи.

0

3 ответа 3

2

Вы можете легко описывать запросы к данным при помощи LINQ, но модификация данных при помощи LINQ не описывается так легко. В идеологии LINQ (как и у всего функционального программирования) предлагается не модифицировать данные, а создавать новые. Когда у вас нету модифицирующего кода, LINQ-запросы получаются легко, и функционируют так, как вы думаете. Если вы используете с LINQ код с побочными эффектами (например, изменяющий исходную последовательность), возможны «неприятности», если только вы не материализуете все LINQ-запросы заранее.

Ваша задача при помощи LINQ делается в два приёма: сначала вычисление нужных данных, а потом уж и модификация:

var result =
    from l in arr
    from r in arr
    where l != r && l.PossibleValues.SequenceEqual(r.PossibleValues)
    select new { set = new[] { l,  r }, values = l.PossibleValues.ToArray() };

foreach (var task in result.ToList())
{
    foreach (var cell in arr.Except(task.set))
    {
        for (int i = 0; i < task.values.Length; i++)
        {
            if (task.values[i])
                cell.PossibleValues[i] = false;
        }
    }
}

Обновление: Ещё немного больше LINQ:

foreach (var task in result.ToList())
{
    foreach (var cell in arr.Except(task.set))
        cell.PossibleValues =
                cell.PossibleValues.Zip(task.values, (cv, mask) => cv && !mask).ToArray();
}
11
  • а зачем ToList() у result? и почему внутренний цикл for а не foreach?
    – Grundy
    Commented 25 дек. 2015 в 20:03
  • @Grundy: ToList там в данной ситуации не обязателен. Но если мутирующий код менял бы arr, то у нас получилось бы одновременная итерация по arr и его изменение, что привело бы к исключению. Пример: var arr = new List<int> { 1, 2 }; var even = arr.Where(x => x % 2 == 0); foreach (var x in even) arr.Remove(x);. Поэтому хорошей идеей является при выполнении мутирующего кода материализовывать все последовательности.
    – VladD
    Commented 25 дек. 2015 в 20:55
  • @Grundy: Внутренний цикл не foreach потому, что нужно синхронизировать две последовательности по индексам. Хотя, этого можно достичь и при помощи Zip. Сейчас обновлю ответ.
    – VladD
    Commented 25 дек. 2015 в 20:56
  • а где проверка условия "найти в inputArray такие экземпляры Cell, где в PossibleValues есть всего два true"?
    – Stack
    Commented 25 дек. 2015 в 20:59
  • @Stack: Это в вопросе есть :) Вычисление arr.
    – VladD
    Commented 25 дек. 2015 в 21:01
1

Решил остановиться на таком варианте:

var couples = arr.SelectMany(x => arr.Select(c => new { a = x, b = c }))
                  .Where(z => z.a != z.b)
                  .Where(z => z.a.PossibleValues.SequenceEqual(z.b.PossibleValues)).ToArray();

var indexes = new List<int>();

foreach (var couple in couples)
{
    for (int n = 0; n < 9; n++)
    {
        if (couple.a.PossibleValues[n] && !indexes.Contains(n))
        {
            indexes.Add(n);
        }
    }
}

inputArray.Except(couples.Select(z => z.a)).ForEach(cell => indexes.ForEach(n => cell.PossibleValues[n] = false));
0

Если использовать hash для PossibleValues, то Cell можно сгруппировать.
И лучше определить метод Map, который возвращает новые Cells.

class Cell { public bool[] PossibleValues; }

IEnumerable<Cell> Map(IEnumerable<Cell> arr) {
    var hash = new Func<bool[], int>(v =>  // todo: заменить на оптимальный
                                       String.Concat(v).GetHashCode());
    var cells = arr.Select(cell => new { hash = hash(cell.PossibleValues), cell = cell });
    var fltrs = cells.GroupBy(cell => cell.hash)
                  .Where(kv =>  // выбираем только пары cells, с двумя true
                     kv.Count() == 2 && kv.First().cell.PossibleValues.Count(v => v) == 2)
                  .Select(kv =>  // возвращаем hash и PossibleValues
                     new { hash = kv.Key, values = kv.First().cell.PossibleValues })
                  .ToList();
    foreach (var c in cells) {
      if (fltrs.Any(f => f.hash == c.hash)) // cell - элемент фильтра, то вернуть как есть
         yield return new Cell { PossibleValues = c.cell.PossibleValues };
      else { // если cell обычный, то фильтруем значения
         // если хотя бы в одном фильтре есть true, то возвращаем false
         var values = c.cell.PossibleValues.Select(
                         (v, i) => fltrs.Any(f => f.values[i]) ? false : v);
         yield return new Cell { PossibleValues = values.ToArray() };
      }
   }
}

Если в PossibleValues, например, следующие значения

100000001
100110001
000110000
000110000
100000001

результат

100000001
000000000
000110000
000110000
100000001

Но следующий вариант работает почти в два раза быстрее,
и быстрее на 10% чем вариант VladD

static void Process(Cell[] arr) {
    var hash = new Func<bool[], int>(v => String.Concat(v).GetHashCode());
    var cells = arr
                .Select(cell => new { hash = hash(cell.PossibleValues), cell = cell })
                .ToArray();
    var fltrs = cells
                .GroupBy(cell => cell.hash)
                .Where(kv =>
                   kv.Count() == 2 && kv.First().cell.PossibleValues.Count(v => v) == 2)
                .Select(kv => 
                   new { hash=kv.Key, values=kv.First().cell.PossibleValues })
                .ToArray();
    foreach (var c in cells) {
      if (fltrs.Any(f => f.hash == c.hash) == false) {
         for (var i = 0; i < c.cell.PossibleValues.Length; i++)
            foreach (var f in fltrs)
               if (f.values[i])
                  c.cell.PossibleValues[i] = false;
        }
    }
}

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.