Эффективно объединяйте массивы строк в .NET, сохраняя разные значения.
https://stackoverflow.com/questions/146358
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я использую .NET 3.5.У меня есть два массива строк, которые могут иметь одно или несколько значений:
string[] list1 = new string[] { "apple", "orange", "banana" };
string[] list2 = new string[] { "banana", "pear", "grape" };
Мне нужен способ объединить их в один массив без повторяющихся значений:
{ "apple", "orange", "banana", "pear", "grape" }
Я могу сделать это с помощью LINQ:
string[] result = list1.Concat(list2).Distinct().ToArray();
но я думаю, что это не очень эффективно для больших массивов.
Есть ли способ лучше?
Решение
string[] result = list1.Union(list2).ToArray();
от MSDN:«Этот метод исключает дубликаты из возвращаемого набора.Это поведение отличается от поведения метода Concat(TSource), который возвращает все элементы входных последовательностей, включая дубликаты».
Другие советы
Почему вы думаете, что это будет неэффективно?Насколько мне известно, и Concat, и Distinct оцениваются лениво, используя HashSet за кулисами, чтобы Distinct отслеживал уже возвращенные элементы.
Я не уверен, как вам удастся сделать это более эффективным в целом :)
РЕДАКТИРОВАТЬ:Distinct фактически использует Set (внутренний класс) вместо HashSet, но суть по-прежнему верна.Это действительно хороший пример того, насколько удобен LINQ.Самый простой ответ в значительной степени настолько эффективен, насколько вы можете достичь без дополнительных знаний предметной области.
Эффект эквивалентен:
public static IEnumerable<T> DistinctConcat<T>(IEnumerable<T> first, IEnumerable<T> second)
{
HashSet<T> returned = new HashSet<T>();
foreach (T element in first)
{
if (returned.Add(element))
{
yield return element;
}
}
foreach (T element in second)
{
if (returned.Add(element))
{
yield return element;
}
}
}
В .NET 3.5 появился класс HashSet, который мог это сделать:
IEnumerable<string> mergedDistinctList = new HashSet<string>(list1).Union(list2);
Не уверен в производительности, но он должен превзойти приведенный вами пример Linq.
РЕДАКТИРОВАТЬ:Я исправляюсь.Ленивая реализация Concat и Distinct имеет ключевое преимущество в памяти и скорости.Concat/Distinct работает примерно на 10 % быстрее и сохраняет несколько копий данных.
Я подтвердил через код:
Setting up arrays of 3000000 strings overlapping by 300000
Starting Hashset...
HashSet: 00:00:02.8237616
Starting Concat/Distinct...
Concat/Distinct: 00:00:02.5629681
это результат:
int num = 3000000;
int num10Pct = (int)(num / 10);
Console.WriteLine(String.Format("Setting up arrays of {0} strings overlapping by {1}", num, num10Pct));
string[] list1 = Enumerable.Range(1, num).Select((a) => a.ToString()).ToArray();
string[] list2 = Enumerable.Range(num - num10Pct, num + num10Pct).Select((a) => a.ToString()).ToArray();
Console.WriteLine("Starting Hashset...");
Stopwatch sw = new Stopwatch();
sw.Start();
string[] merged = new HashSet<string>(list1).Union(list2).ToArray();
sw.Stop();
Console.WriteLine("HashSet: " + sw.Elapsed);
Console.WriteLine("Starting Concat/Distinct...");
sw.Reset();
sw.Start();
string[] merged2 = list1.Concat(list2).Distinct().ToArray();
sw.Stop();
Console.WriteLine("Concat/Distinct: " + sw.Elapsed);
Отказ от ответственности Это преждевременная оптимизация.Для ваших примеров массивов используйте методы расширения 3.5.Пока вы не узнаете, что у вас проблемы с производительностью в этом регионе, вам следует использовать библиотечный код.
Если вы можете сортировать массивы или они сортируются, когда вы доходите до этого места в коде, вы можете использовать следующие методы.
Они будут извлекать один элемент из обоих и производить «самый низкий» элемент, а затем извлекать новый элемент из соответствующего источника, пока оба источника не будут исчерпаны.В случае, когда текущий элемент, полученный из двух источников, равен, он создаст элемент из первого источника и пропустит их в обоих источниках.
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2)
{
return Merge(source1, source2, Comparer<T>.Default);
}
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2, IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source1))
throw new ArgumentNullException("source1");
if (Object.ReferenceEquals(null, source2))
throw new ArgumentNullException("source2");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T>
enumerator1 = source1.GetEnumerator(),
enumerator2 = source2.GetEnumerator())
{
Boolean more1 = enumerator1.MoveNext();
Boolean more2 = enumerator2.MoveNext();
while (more1 && more2)
{
Int32 comparisonResult = comparer.Compare(
enumerator1.Current,
enumerator2.Current);
if (comparisonResult < 0)
{
// enumerator 1 has the "lowest" item
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
else if (comparisonResult > 0)
{
// enumerator 2 has the "lowest" item
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
else
{
// they're considered equivalent, only yield it once
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
more2 = enumerator2.MoveNext();
}
}
// Yield rest of values from non-exhausted source
while (more1)
{
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
while (more2)
{
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
}
}
Обратите внимание: если один из источников содержит дубликаты, вы можете увидеть дубликаты в выходных данных.Если вы хотите удалить эти дубликаты в уже отсортированных списках, используйте следующий метод:
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source)
{
return CheapDistinct<T>(source, Comparer<T>.Default);
}
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source,
IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source))
throw new ArgumentNullException("source");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T> enumerator = source.GetEnumerator())
{
if (enumerator.MoveNext())
{
T item = enumerator.Current;
// scan until different item found, then produce
// the previous distinct item
while (enumerator.MoveNext())
{
if (comparer.Compare(item, enumerator.Current) != 0)
{
yield return item;
item = enumerator.Current;
}
}
// produce last item that is left over from above loop
yield return item;
}
}
}
Обратите внимание, что ни один из них не будет внутренне использовать структуру данных для хранения копии данных, поэтому они будут дешевыми, если входные данные будут отсортированы.Если вы не можете или не хотите этого гарантировать, вам следует использовать методы расширения версии 3.5, которые вы уже нашли.
Вот пример кода, который вызывает вышеуказанные методы:
String[] list_1 = { "apple", "orange", "apple", "banana" };
String[] list_2 = { "banana", "pear", "grape" };
Array.Sort(list_1);
Array.Sort(list_2);
IEnumerable<String> items = Merge(
CheapDistinct(list_1),
CheapDistinct(list_2));
foreach (String item in items)
Console.Out.WriteLine(item);
Вероятно, жизнеспособным решением может быть создание хеш-таблицы с вашими значениями в качестве ключей (добавление только тех, которых еще нет), а затем преобразование ключей в массив.
Вы не знаете, какой подход быстрее, пока не измерите его.Способ LINQ элегантен и прост для понимания.
Другой способ — реализовать набор как хеш-массив (Словарь) и добавить в набор все элементы обоих массивов.Затем используйте метод set.Keys.ToArray() для создания результирующего массива.
