Подтвердить что ты не робот

Эффективно объединять массивы строк в .NET, сохраняя отличные значения

Я использую .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();

но я полагаю, что это не очень эффективно для больших массивов.

Есть ли лучший способ?

4b9b3361

ОТВЕТЫ

Ответ 1

string[] result = list1.Union(list2).ToArray();

from msdn: "Этот метод исключает дубликаты из набора возвратов. Это отличается от метода Concat (TSource), который возвращает все элементы во входных последовательностях, включая дубликаты".

Ответ 2

Почему вы думаете, что это будет неэффективно? Насколько мне известно, как Concat, так и Distinct оцениваются лениво, используя HashSet за кулисами для Distinct, чтобы отслеживать элементы, которые уже были возвращены.

Я не уверен, как вам удастся сделать его более эффективным, чем это в общем случае:)

EDIT: 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;
        }
    }
}

Ответ 3

.NET 3.5 представил класс HashSet, который мог бы сделать это:

IEnumerable<string> mergedDistinctList = new HashSet<string>(list1).Union(list2);

Не уверен в производительности, но он должен победить пример Linq, который вы дали.

EDIT: Я стою исправлено. У ленивой реализации 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);

Ответ 4

Отказ от ответственности Это преждевременная оптимизация. Для ваших массивов примеров используйте методы расширения 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);

Ответ 5

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

Ответ 6

Вы не знаете, какой подход быстрее, пока вы его не измеряете. Способ LINQ является элегантным и понятным.

Другой способ - реализовать набор как хэш-массив (словарь) и добавить все элементы обоих массивов в набор. Затем используйте метод set.Keys.ToArray() для создания результирующего массива.