Просто любопытно: какие у этого требования к пространству и времени?
dtb
10
@dtb должно быть около O (N) . Конечно, учитывая, что это «небольшой список», он будет молниеносно работать практически с любым алгоритмом. ИМО, это выигрывает по удобочитаемости и лаконичности, и, поскольку скорость не является проблемой, это делает его идеальным.
Тим С.
2
Это намного эффективнее, чем могло бы быть,
Джодрелл
74
Вот еще один подход, который более эффективен, чем Enumerable.Distinct+ Enumerable.Count(тем более, если последовательность не является типом коллекции). Он использует, HashSet<T>который удаляет дубликаты, очень эффективен при поиске и имеет свойство count:
var distinctBytes = new HashSet<byte>(theList);
bool allDifferent = distinctBytes.Count == theList.Count;
или другой, более тонкий и эффективный подход:
var diffChecker = new HashSet<byte>();
bool allDifferent = theList.All(diffChecker.Add);
HashSet<T>.Addвозвращается, falseесли элемент не может быть добавлен, поскольку он уже находится в HashSet. Enumerable.Allостанавливается на первом «ложном».
так просто и очевидно, почему я не подумал об этом первым :) Я использовал этот однострочный модуль в модульном тесте, чтобы подтвердить, что 10 миллионов элементов, сгенерированных моим потрясающим кодом, действительно уникальны Assert.IsTrue(samples.Add(AwesomeClass.GetUnique()));. Они были и есть :) +1 для тебя Тим :)
Должно быть это:bool allDifferent = theList.All(s => diffChecker.Add(s))
Майк
2
Нет, не нужно. В этом случае вы можете передать делегата напрямую
Тим
1
@ AndréReichelt - Я только что открыл ваш код, и третий сценарий ( List.All(HashSet.Add)) кажется намного быстрее, чем два других почти во всех случаях
Кайл Делани
6
Хорошо, вот самый эффективный метод, который я могу придумать, используя стандартный .Net
using System;
using System.Collections.Generic;
publicstaticclassExtension
{
publicstaticboolHasDuplicate<T>(this IEnumerable<T> source,
out T firstDuplicate)
{
if (source == null)
{
thrownew ArgumentNullException(nameof(source));
}
var checkBuffer = new HashSet<T>();
foreach (var t in source)
{
if (checkBuffer.Add(t))
{
continue;
}
firstDuplicate = t;
returntrue;
}
firstDuplicate = default(T);
returnfalse;
}
}
по сути, какой смысл перечислять всю последовательность дважды, если все, что вам нужно, - это найти первый дубликат.
Я мог бы оптимизировать это в большей степени, используя специальный корпус для пустых и одноэлементных последовательностей, но это снизит удобочитаемость / ремонтопригодность с минимальным выигрышем.
Приятно добавить повторяющееся значение из возврата, очень полезно для проверки
Pac0
Я протестировал здесь 3 решения, и это действительно самое эффективное решение на этой странице. Хотя есть несколько опечаток (например, sequenceдолжно быть source). Но отлично работает, когда они исправлены
Майк
@mikenelson, так должно быть лучше
Джодрелл
2
Для удобочитаемости, я думаю, это должно быть if (!checkBuffer.Add(t)) { firstDuplicate = t; return true }в курсе.
tia
2
Аналогичная логика Distinctиспользования GroupBy:
var isUnique = theList.GroupBy(i => i).Count() == theList.Count;
Это полезно, если вы хотите проверить уникальность по отношению к свойству, в theList.GroupBy(o => o.SomeProperty).Count() == theList.Count;то время как Distinct () не позволяет этого.
Rev1.0,
1
Также можно: использовать Hashset
var uniqueIds = new HashSet<long>(originalList.Select(item => item.Id));
if (uniqueIds.Count != originalList.Count)
{
}
И, без сомнения, более красивые, с использованием LINQ, как упоминалось "juergen d" и "Tim Schmelter".
Но, если вы лишены «сложности» и скорости, лучшим решением будет реализовать это самостоятельно. Одним из решений будет создание массива размером N (для байта это 256). И зацикливайте массив, и на каждой итерации будет проверять индекс совпадающего числа, если значение равно 1, если это так, это означает, что я уже увеличиваю индекс массива и, следовательно, массив не отличается, иначе я увеличиваю ячейку массива и продолжаю проверку .
вы можете использовать битовый вектор с 256 битами = 32 байтами = 8 целыми числами. Но ваш Big O = O (n) по-прежнему будет таким же, как при использовании Хешета, предложенного в другом ответе.
BrokenGlass
Это O (n), так что, возможно, самый быстрый (проверьте его). Будет ли проверка счета по ходу или в конце быстрее всего? Я подозреваю, что в конце концов улучшится худший случай, но по мере продвижения может улучшиться средний и лучший случай). Если нет дубликатов, это будет худшая производительность. Также для больших типов данных это не сработает, для 16-битного типа вам придется использовать 64 Кбайт счетчика, ну 64 Кбайт (8 Кбайт), но для чего-то большего использование памяти станет глупым. Однако мне нравится этот ответ для 8-битных значений.
ctrl-alt-delor
1
@TamusJRoyce, если вы хотите сохранить 4294967296 возможностей, вам понадобится 4 ГБ, а не 42 МБ (или 512 МБ, если вы используете битовую маскировку)
tigrou 01
Не уверен, о чем я думал. «Выделите 42 МБ + памяти для хранения всех 4294967296 возможностей. И используйте простые счетчики сегментов. Или даже используйте xor с маскированием битов и проверьте, не изменился ли какой-либо бит с true на false. 42 МБ + / 8 = 5 МБ + Расходы кажутся слишком большими для сегодняшнего оборудования. Но однажды это может иметь заслуги ". не совсем уместный комментарий. Хешсет был бы лучше всего. Если вы имеете дело с очень большими массивами, вы ожидаете чрезвычайно большой кусок памяти. Но в таком странном пограничном случае лучше использовать херистик с алгоритмом CRC. Преобразуйте его в полином. Если близко, оцените. Спасибо, @tigrou!
TamusJRoyce 01
0
И еще одно решение, если вы хотите найти повторяющиеся значения.
var values = new [] { 9, 7, 2, 6, 7, 3, 8, 2 };
var sorted = values.ToList();
sorted.Sort();
for (var index = 1; index < sorted.Count; index++)
{
var previous = sorted[index - 1];
var current = sorted[index];
if (current == previous)
Console.WriteLine(string.Format("duplicated value: {0}", current));
}
Ответы:
bool isUnique = theList.Distinct().Count() == theList.Count();
источник
Вот еще один подход, который более эффективен, чем
Enumerable.Distinct
+Enumerable.Count
(тем более, если последовательность не является типом коллекции). Он использует,HashSet<T>
который удаляет дубликаты, очень эффективен при поиске и имеет свойство count:var distinctBytes = new HashSet<byte>(theList); bool allDifferent = distinctBytes.Count == theList.Count;
или другой, более тонкий и эффективный подход:
var diffChecker = new HashSet<byte>(); bool allDifferent = theList.All(diffChecker.Add);
HashSet<T>.Add
возвращается,false
если элемент не может быть добавлен, поскольку он уже находится вHashSet
.Enumerable.All
останавливается на первом «ложном».источник
Assert.IsTrue(samples.Add(AwesomeClass.GetUnique()));
. Они были и есть :) +1 для тебя Тим :)bool allDifferent = theList.All(s => diffChecker.Add(s))
List.All(HashSet.Add)
) кажется намного быстрее, чем два других почти во всех случаяхХорошо, вот самый эффективный метод, который я могу придумать, используя стандартный .Net
using System; using System.Collections.Generic; public static class Extension { public static bool HasDuplicate<T>( this IEnumerable<T> source, out T firstDuplicate) { if (source == null) { throw new ArgumentNullException(nameof(source)); } var checkBuffer = new HashSet<T>(); foreach (var t in source) { if (checkBuffer.Add(t)) { continue; } firstDuplicate = t; return true; } firstDuplicate = default(T); return false; } }
по сути, какой смысл перечислять всю последовательность дважды, если все, что вам нужно, - это найти первый дубликат.
Я мог бы оптимизировать это в большей степени, используя специальный корпус для пустых и одноэлементных последовательностей, но это снизит удобочитаемость / ремонтопригодность с минимальным выигрышем.
источник
sequence
должно бытьsource
). Но отлично работает, когда они исправленыif (!checkBuffer.Add(t)) { firstDuplicate = t; return true }
в курсе.Аналогичная логика
Distinct
использованияGroupBy
:var isUnique = theList.GroupBy(i => i).Count() == theList.Count;
источник
theList.GroupBy(o => o.SomeProperty).Count() == theList.Count;
то время как Distinct () не позволяет этого.Также можно: использовать Hashset
var uniqueIds = new HashSet<long>(originalList.Select(item => item.Id)); if (uniqueIds.Count != originalList.Count) { }
источник
Есть много решений.
И, без сомнения, более красивые, с использованием LINQ, как упоминалось "juergen d" и "Tim Schmelter".
Но, если вы лишены «сложности» и скорости, лучшим решением будет реализовать это самостоятельно. Одним из решений будет создание массива размером N (для байта это 256). И зацикливайте массив, и на каждой итерации будет проверять индекс совпадающего числа, если значение равно 1, если это так, это означает, что я уже увеличиваю индекс массива и, следовательно, массив не отличается, иначе я увеличиваю ячейку массива и продолжаю проверку .
источник
И еще одно решение, если вы хотите найти повторяющиеся значения.
var values = new [] { 9, 7, 2, 6, 7, 3, 8, 2 }; var sorted = values.ToList(); sorted.Sort(); for (var index = 1; index < sorted.Count; index++) { var previous = sorted[index - 1]; var current = sorted[index]; if (current == previous) Console.WriteLine(string.Format("duplicated value: {0}", current)); }
Выход:
duplicated value: 2 duplicated value: 7
http://rextester.com/SIDG48202
источник
Я проверяю, уникален ли IEnumerable (aray, list и т.д.) следующим образом:
var isUnique = someObjectsEnum.GroupBy(o => o.SomeProperty).Max(g => g.Count()) == 1;
источник