Как проверить в списке элементов типа string наличие двух одинаковых строк?

Question

[Георгий Кузнецов]

Допустим есть список строк, в котором неприемлемо нахождение двух одинаковых элементов. Использование любых циклов (for, foreach) нежелательно.
Каким образом можно написать такой метод под следующую сигнатуру?

public bool Check (List<string> Input) {}

Answer 1

[Сергей Соловьев]

Используй HashSet. Если при Add вернет true - значит есть дубликат

Answer 2

[Василий Банников]

Под капотом в любом случае всё упрётся в цикл.

Если просто синтаксический не хочешь видеть цикл, то .Distinct().Count() и сравни с длиной исходного списка.

Но по хорошему лучше пойти путём AshBlade

И вообще если обязательна уникальность элементов - изначально работать с HashSet, а не List

Comments

[Георгий Кузнецов]

Прошу оценить Вас насколько через пятую точку написан этот код (в плане читаемости и вообще CleanCode и насколько сильное тут отклонение от стандартов)

public static OutputListData<DictionaryElement> GetElementsByUserList(HashSet<string> InputUserList, List<DictionaryElement> InputTargetList)
        {
            OutputListData<DictionaryElement> answer = new OutputListData<DictionaryElement>();
            answer.Data = new List<DictionaryElement>();
            answer.ErrorMessage = "";
            answer.IsSucsess = true;
            var counter = 0;

            foreach (var curStr in InputUserList)
            {
                counter++;
                bool IsFind = false;
                foreach(var curEl in InputTargetList)
                {
                    if (curEl.RussianWord.Contains(curStr))
                    {
                        answer.Data.Add(curEl);
                        IsFind = true;
                        break;
                    }
                }
                if (!IsFind)
                {
                    answer.IsSucsess = false;
                    answer.ErrorMessage = "Ошибка в строке #" + counter + ". Обнаружен элемент пользовательского списка, которого нет в словаре.";
                }
            }

            return answer;
        } 
    }

[Василий Банников]

Георгий Кузнецов,

(HashSet InputUserList, List InputTargetList)

Нейминг соглашения, которые приняты в большинстве проектов.

OutputListData<DictionaryElement> answer = new OutputListData<DictionaryElement>();
            answer.Data = new List<DictionaryElement>();
            answer.ErrorMessage = "";
            answer.IsSucsess = true;

Это можно было бы инициализировать и внутри OutputListData

Ну и для чистоты можно было бы этот объект создать в самом конце.

curEl

Стрёмное сокращение.

curStr

Стрёмное сокращение

Ну и совершенно не понятно, что именно этот код делает - следует переименовать метод + добавить документирующий комментарий.

OutputListData - выглядит как Result или Either для бедных.

if (curEl.RussianWord.Contains(curStr))

Что-то подсказывает, что есть какая-то другая структура данных, которая будет такую проверку делать быстрее, чем цикл.

foreach(var curEl in InputTargetList)
                {
                    if (curEl.RussianWord.Contains(curStr))
                    {
                        answer.Data.Add(curEl);
                        IsFind = true;
                        break;
                    }
                }

Можно заменить на FirstOrDefault

Если бы у меня цель была переписать этот код, сохранив его поведение, то я бы сделал что-то типа:

record DictionaryElement(string RussianWord);
public struct Result<TItem, TError> {
  public bool Success {get;}
  public bool Failure => !Success;
  private readonly bool _success;
  private readonly TItem? _ok;
  private readonly TError? _error;
  public TItem Ok {get => Success ? _ok! : throw new InvalidOperationException();}  
  public TError Error {get => Failure ? _error!: throw new InvalidOperationException(); }
  private Result(bool success, TItem? data, TError? error) {
    _success = success;
    _ok = data;
    _error = error;
  }
  public static Result<TItem, TError> CreateSuccess(TItem result) => new(true, result, (TError?)default);  
  public static Result<TItem, TError> CreateFailure(TError error) => new(false, (TItem?) default, error);
}

static Result<List<DictionaryElement>, string> GetElementsByUserList(HashSet<string> InputUserList, List<DictionaryElement> InputTargetList) {
  var result = new List<DictionaryElement>();
  var counter = 0;
  foreach(var pattern in InputUserList) {
    counter++;
    var dictionaryElement = InputTargetList.FirstOrDefault(x=>x.RussianWord.Contains(pattern));
    if (dictionaryElement == null) {
      return Result<List<DictionaryElement>, string>.CreateFailure($"Ошибка в строке #{counter}. Обнаружен элемент пользовательского списка, которого нет в словаре");      
    }
    result.Add(dictionaryElement);
  }
  
  return Result<List<DictionaryElement>, string>.CreateSuccess(result);
}

Answer 3

[mayton2019]

Использование любых циклов (for, foreach) нежелательно.

Вот скажи что за душный у тебя тех-лид? Это надож такое требование придумать!!

Вот насколько я помню квантовые компьютеры как-то работают без циклов. У них - другие
свойства более сложные и труднообъяснимые. Но как-то они работают. Так что тебе дружище
дорога либо в квантовую физику либо смирись с циклами.

Под капотом любых шарповых функций которые работают с коллекциями мы найдем либо
цикл либо хвостовую рекурсию. А если тебя как разработчика пугает такая инкапсуляция
то тебе наверное не стоит программировать. С такими страхами - лучше быть пользователем.

Comments

[MVV]

Вот скажи что за душный у тебя тех-лид? Это надож такое требование придумать!!

На самом деле, это ограничение тут по делу. Потому что если иначе, то так вот и появляются в программе "квадраты": куски кода имеющие квадратичную сложность по длине данных. При наивной реализации проверки - через два вложенных цикла - именно "квадрат" и получится. Тогда как при варианте с .Distinct().Count() от Василий Банников сложность будет N*log(N). А при работе чез HashSet - вообще N. Но там могут быть нюансы: нужно правильно угадать размер хэш-таблицы, чтобы не нарваться на рехэширование при изменении ее размера, т.е. увеличении емкости, и памяти под эту хэш-таблицу должно хватать.
Нет, конечно, если вы уверены, что этот код не станет узким местом в программе - можно и вложенные циклы лепить, только вот откуда взять ее, уверенность эту?

[Василий Банников]

MVV,

Тогда как при варианте с .Distinct().Count() от Василий Банников сложность будет N*log(N).

Не факт. Очень вероятно, что там тоже будет линейная сложность, тк:
1. Distinct также использует HashSet под капотом
2. Count вместо прохода по коллекции может попробовать извлечь количество элементов, если оно сохранено в объекте, который реализует IEnumerable - это точно реализовано в коллекциях, но не уверен, что это реализовано в DistinctEnumerable

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

[MVV]

Василий Банников,

Distinct также использует HashSet под капотом

Верю: я не проверял, просто привык с давних времен работы с SQL что SELECT DISTINCT - это про сортировку, вот и написал ее сложность.
Ну, тогда, все, что написано ниже про HashSet - и про плюсы, и про минусы - применимо и к .Distinct().Count().