Вопрос:

Лучший алгоритм синхронизации двух IList в C # 2.0

c# .net algorithm optimization list

5347 просмотра

6 ответа

10273 Репутация автора

Представьте себе следующий тип:

public struct Account
{
    public int Id;
    public double Amount;
}

Какой лучший алгоритм для синхронизации двух IList<Account>в C # 2.0? (Нет linq)?

Первый список (L1) - это список ссылок, второй (L2) - это список для синхронизации в соответствии с первым:

  • Все учетные записи в L2, которых больше нет в L1, должны быть удалены из L2
  • Все счета в L2, которые все еще существуют в L1, должны быть обновлены (атрибут количества)
  • Все учетные записи, которые находятся в L1, но еще не в L2, должны быть добавлены в L2

Идентификатор идентифицирует учетные записи. Нетрудно найти наивный и работающий алгоритм, но я хотел бы знать, есть ли разумное решение для такого сценария, не нарушая удобочитаемость и производительность.

РЕДАКТИРОВАТЬ :

  • Тип учетной записи не имеет значения, он может быть классом, имеет свойства, элементы равенства и т. Д.
  • L1 и L2 не отсортированы
  • Элементы L2 не могут быть заменены элементами L1, они должны быть обновлены (поле за полем, свойство за свойством)
Автор: Romain Verdier Источник Размещён: 02.10.2008 08:56

Ответы (6)


5 плюса

1086244 Репутация автора

Для начала я бы избавился от изменяемой структуры. Изменяемые типы значений - это принципиально плохая вещь. (Как и общедоступные поля, ИМО.)

Вероятно, стоит создать словарь, чтобы вы могли легко сравнить содержимое двух списков. Если у вас есть такой простой способ проверки наличия / отсутствия, все остальное должно быть простым.

Хотя, если честно, звучит так, будто вы хотите, чтобы L2 была полной копией L1 ... очистить L2 и просто вызвать AddRange? Или дело в том, что вы также хотите предпринять другие действия во время смены L2?

Автор: Jon Skeet Размещён: 02.10.2008 08:59

0 плюса

16682 Репутация автора

В дополнение к комментарию Джона Скита сделайте вашу учетную запись структурой класса и переопределите методы Equals () и GetHashCode (), чтобы получить хорошую проверку на равенство.

Автор: VVS Размещён: 02.10.2008 09:01

0 плюса

0 Репутация автора

L2 = L1.clone ()?

... но я думаю, вы забыли упомянуть что-то.

Автор: anon Размещён: 02.10.2008 09:06

2 плюса

56208 Репутация автора

Если ваши два списка отсортированы, вы можете просто просмотреть их в тандеме. Это операция O (m + n). Следующий код может помочь:

class Program
{
    static void Main()
    {
        List<string> left = new List<string> { "Alice", "Charles", "Derek" };
        List<string> right = new List<string> { "Bob", "Charles", "Ernie" };

        EnumerableExtensions.CompareSortedCollections(left, right, StringComparer.CurrentCultureIgnoreCase,
            s => Console.WriteLine("Left: " + s), s => Console.WriteLine("Right: " + s), (x,y) => Console.WriteLine("Both: " + x + y));
    }
}

static class EnumerableExtensions
{
    public static void CompareSortedCollections<T>(IEnumerable<T> source, IEnumerable<T> destination, IComparer<T> comparer, Action<T> onLeftOnly, Action<T> onRightOnly, Action<T, T> onBoth)
    {
        EnumerableIterator<T> sourceIterator = new EnumerableIterator<T>(source);
        EnumerableIterator<T> destinationIterator = new EnumerableIterator<T>(destination);

        while (sourceIterator.HasCurrent && destinationIterator.HasCurrent)
        {
            // While LHS < RHS, the items in LHS aren't in RHS
            while (sourceIterator.HasCurrent && (comparer.Compare(sourceIterator.Current, destinationIterator.Current) < 0))
            {
                onLeftOnly(sourceIterator.Current);
                sourceIterator.MoveNext();
            }

            // While RHS < LHS, the items in RHS aren't in LHS
            while (sourceIterator.HasCurrent && destinationIterator.HasCurrent && (comparer.Compare(sourceIterator.Current, destinationIterator.Current) > 0))
            {
                onRightOnly(destinationIterator.Current);
                destinationIterator.MoveNext();
            }

            // While LHS==RHS, the items are in both
            while (sourceIterator.HasCurrent && destinationIterator.HasCurrent && (comparer.Compare(sourceIterator.Current, destinationIterator.Current) == 0))
            {
                onBoth(sourceIterator.Current, destinationIterator.Current);
                sourceIterator.MoveNext();
                destinationIterator.MoveNext();
            }
        }

        // Mop up.
        while (sourceIterator.HasCurrent)
        {
            onLeftOnly(sourceIterator.Current);
            sourceIterator.MoveNext();
        }

        while (destinationIterator.HasCurrent)
        {
            onRightOnly(destinationIterator.Current);
            destinationIterator.MoveNext();
        }
    }
}

internal class EnumerableIterator<T>
{
    private readonly IEnumerator<T> _enumerator;

    public EnumerableIterator(IEnumerable<T> enumerable)
    {
        _enumerator = enumerable.GetEnumerator();
        MoveNext();
    }

    public bool HasCurrent { get; private set; }

    public T Current
    {
        get { return _enumerator.Current; }
    }

    public void MoveNext()
    {
        HasCurrent = _enumerator.MoveNext();
    }
}

Вы должны быть осторожны при изменении коллекций, перебирая их.

Если они не отсортированы, то сравнение каждого элемента в одном с каждым элементом в другом - это O (mn), что очень быстро причиняет боль.

Если вы можете скопировать значения ключей из каждой коллекции в Словарь или аналогичные (то есть коллекцию с приемлемой производительностью при запросе «присутствует ли X?»), То вы можете придумать что-то разумное.

Автор: Roger Lipscombe Размещён: 02.10.2008 09:43

0 плюса

6194 Репутация автора

Я знаю, что это старый пост, но вы должны проверить AutoMapper. Он будет делать именно то, что вы хотите, в очень гибкой и настраиваемой форме.

AutoMapper

Автор: rboarman Размещён: 04.06.2010 08:45

0 плюса

20 Репутация автора

У меня была та же проблема, и мое лучшее решение было следующее (адаптировано к вашему случаю), с загрузкой обоих списков:

  1. Для каждой учетной записи в L1 проверьте, существует ли она в L2:
    • Если найдено, обновите все значения из Учетной записи L1 на основе L2. Затем удалите учетную запись из L2.
    • Если не найден, пометьте Учетную запись L1 как удаленную или удалите ее из списка, это зависит от структуры вашей базы данных.
  2. Для каждой учетной записи, оставленной в L2, добавьте ее в L1.

Я рекомендую реализовать IEquatable<>интерфейс в своем классе Account (или просто переопределить Equals()метод), чтобы он всегда сравнивал идентификаторы методов, которые требуют сравнения между объектами:

public struct Account : IEquatable<Account>
{
    public int Id;
    public double Amount;

    public bool Equals(Account other)
    {
        if (other == null) return false;
        return (this.Id.Equals(other.Id));
    }
}

Алгоритм синхронизации будет выглядеть примерно так (убедитесь, что оба списка инициализированы, чтобы не возникало ошибок):

L1.ForEach (L1Account =>
{
    var L2Account = L2.Find(a => a.Id == L1Account.id);
    // If found, update values
    if (L2Account != null)
    {
        L1Account.Amount = L2Account.Amount;
        L2.Remove(L2Account);
    }
    // If not found, remove it
    else
    {
        L1.Remove(L1Account);
    }
}
// Add any remaining L2 Account to L1
L1.AddRange(L2);
Автор: Mateus W. Размещён: 14.02.2019 12:44
32x32