想象一下以下类型：
public struct Account
{
public int Id;
public double Amount;
}
IList<Account>在 C# 2.0中同步两个的最佳算法是什么？（没有 linq）？
第一个列表（L1）是参考列表，第二个（L2）是根据第一个同步的：
Id 标识帐户。找到一个幼稚且有效的算法并不难，但我想知道是否有一个聪明的解决方案来处理这种情况而不会破坏可读性和性能。
编辑：
首先，我会摆脱可变结构。可变值类型从根本上来说是一件坏事。（与公共领域一样，IMO。）
可能值得构建一个字典，以便您可以轻松比较两个列表的内容。一旦你有了检查存在/不存在的简单方法，剩下的就应该很简单了。
老实说，听起来您基本上希望 L2 成为 L1 的完整副本...清除 L2 并调用 AddRange？还是说您在更改 L2 时还想采取其他行动？
如果您的两个列表已排序，那么您可以简单地串联浏览它们。这是一个 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 存在吗？”时具有可接受性能的集合），那么您可以想出一些合理的东西。
我遇到了同样的问题，我最好的解决方案是以下（适用于您的情况），同时加载了两个列表：
我建议在您的AccountIEquatable<>类中实现该接口（或仅覆盖该方法），以便它始终比较需要在对象之间进行比较的方法上的 ID：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);
除了 Jon Skeet 的评论之外，让您的 Account 结构成为一个类并覆盖 Equals() 和 GetHashCode() 方法以获得良好的相等性检查。
L2 = L1.clone()？
...但我猜你忘了提一些事情。
我知道这是一篇旧帖子，但您应该查看 AutoMapper。它将以一种非常灵活和可配置的方式完全满足您的需求。
我已经实现了两种算法，一种用于排序，一种用于顺序收集。两者都支持空值和重复值，并且以相同的方式工作：
它们产生CollectionModification<LeftItemType,RightItemType>类似于CollectionChangedEventArgs<T>( reference ) 的 return ，后者可用于同步集合。
关于收益率：
当使用一种或另一种算法将左侧项目（参考集合）与右侧项目进行比较时，您可以
CollectionModification在它们返回后立即应用返回的每个收益，但这可能导致“集合已修改”-异常（例如在使用List<T>.GetEnumerator) 时。为了防止这种情况，两种算法都可以使用可索引集合作为即将发生变异的参考集合。您只需使用YieldIteratorInfluencedReadOnlyListExtensionsYieldIteratorInfluencedReadOnlyList<ItemType>中的扩展方法将引用集合与 (abstract) 一起包装。:)
第一个算法适用于升序或降序列表并使用IComparer<T>.
/// <summary>
/// The algorithm creates modifications that can transform one collection into another collection.
/// The collection modifications may be used to transform <paramref name="leftItems"/>.
/// Assumes <paramref name="leftItems"/> and <paramref name="rightItems"/> to be sorted by that order you specify by <paramref name="collectionOrder"/>.
/// Duplications are allowed but take into account that duplications are yielded as they are appearing.
/// </summary>
/// <typeparam name="LeftItemType">The type of left items.</typeparam>
/// <typeparam name="RightItemType">The type of right items.</typeparam>
/// <typeparam name="ComparablePartType">The type of the comparable part of left item and right item.</typeparam>
/// <param name="leftItems">The collection you want to have transformed.</param>
/// <param name="getComparablePartOfLeftItem">The part of left item that is comparable with part of right item.</param>
/// <param name="rightItems">The collection in which <paramref name="leftItems"/> could be transformed.</param>
/// <param name="getComparablePartOfRightItem">The part of right item that is comparable with part of left item.</param>
/// <param name="collectionOrder">the presumed order of items to be used to determine <see cref="IComparer{T}.Compare(T, T)"/> argument assignment.</param>
/// <param name="comparer">The comparer to be used to compare comparable parts of left and right item.</param>
/// <param name="yieldCapabilities">The yieldCapabilities that regulates how <paramref name="leftItems"/> and <paramref name="rightItems"/> are synchronized.</param>
/// <returns>The collection modifications.</returns>
/// <exception cref="ArgumentNullException">Thrown when non-nullable arguments are null.</exception>
public static IEnumerable<CollectionModification<LeftItemType, RightItemType>> YieldCollectionModifications<LeftItemType, RightItemType, ComparablePartType>(
IEnumerable<LeftItemType> leftItems,
Func<LeftItemType, ComparablePartType> getComparablePartOfLeftItem,
IEnumerable<RightItemType> rightItems,
Func<RightItemType, ComparablePartType> getComparablePartOfRightItem,
SortedCollectionOrder collectionOrder,
IComparer<ComparablePartType> comparer,
CollectionModificationsYieldCapabilities yieldCapabilities)
Python 算法灵感来自：有序列表的两个实例的高效同步。
第二种算法适用于任何顺序并使用IEqualityComparer<T>.
/// <summary>
/// The algorithm creates modifications that can transform one collection into another collection.
/// The collection modifications may be used to transform <paramref name="leftItems"/>.
/// The more the collection is synchronized in an orderly way, the more efficient the algorithm is.
/// Duplications are allowed but take into account that duplications are yielded as they are appearing.
/// </summary>
/// <typeparam name="LeftItemType">The type of left items.</typeparam>
/// <typeparam name="RightItemType">The type of right items.</typeparam>
/// <typeparam name="ComparablePartType">The type of the comparable part of left item and right item.</typeparam>
/// <param name="leftItems">The collection you want to have transformed.</param>
/// <param name="getComparablePartOfLeftItem">The part of left item that is comparable with part of right item.</param>
/// <param name="rightItems">The collection in which <paramref name="leftItems"/> could be transformed.</param>
/// <param name="getComparablePartOfRightItem">The part of right item that is comparable with part of left item.</param>
/// <param name="equalityComparer">The equality comparer to be used to compare comparable parts.</param>
/// <param name="yieldCapabilities">The yield capabilities, e.g. only insert or only remove.</param>
/// <returns>The collection modifications.</returns>
/// <exception cref="ArgumentNullException">Thrown when non-nullable arguments are null.</exception>
public static IEnumerable<CollectionModification<LeftItemType, RightItemType>> YieldCollectionModifications<LeftItemType, RightItemType, ComparablePartType>(
IEnumerable<LeftItemType> leftItems,
Func<LeftItemType, ComparablePartType> getComparablePartOfLeftItem,
IEnumerable<RightItemType> rightItems,
Func<RightItemType, ComparablePartType> getComparablePartOfRightItem,
IEqualityComparer<ComparablePartType>? equalityComparer,
CollectionModificationsYieldCapabilities yieldCapabilities)
where ComparablePartType : notnull
需要以下框架之一
这两种算法都是使用自定义实现类型（IndexDirectory,NullableKeyDictionary等LinkedBucketList）创建的，所以我不能在这里简单地复制粘贴代码，所以我想参考我的以下包：
帐户：
public class Account
{
public Account(int id) =>
Id = id;
public int Id { get; }
public double Amount { get; }
}
以及以下集合项相等比较器类：
AccountEqualityComparer：
public class AccountEqualityComparer : EqualityComparer<Account>
{
public new static AccountEqualityComparer Default = new AccountEqualityComparer();
public override bool Equals([AllowNull] Account x, [AllowNull] Account y) =>
ReferenceEquals(x, y) || (!(x is null && y is null) && x.Id.Equals(y.Id));
public override int GetHashCode([DisallowNull] Account obj) =>
obj.Id;
}
AccountCollectionViewModel：
using Teronis.Collections.Algorithms.Modifications;
using Teronis.Collections.Synchronization;
using Teronis.Collections.Synchronization.Extensions;
using Teronis.Reflection;
public class AccountCollectionViewModel : SyncingCollectionViewModel<Account, Account>
{
public AccountCollectionViewModel()
: base(CollectionSynchronizationMethod.Sequential(AccountEqualityComparer.Default))
{
// In case of SyncingCollectionViewModel, we have to pass a synchronization method.
//
// Sequential means any order
//
}
protected override Account CreateSubItem(Account superItem) =>
superItem;
protected override void ApplyCollectionItemReplace(in ApplyingCollectionModificationBundle modificationBundle)
{
foreach (var (oldItem, newItem) in modificationBundle.OldSuperItemsNewSuperItemsModification.YieldTuplesForOldItemNewItemReplace())
{
// Implementation detail: update left public property values by right public property values.
TeronisReflectionUtils.UpdateEntityVariables(oldItem, newItem);
}
}
}
程序：
using System.Diagnostics;
using System.Linq;
class Program
{
static void Main()
{
// Arrange
var collection = new AccountCollectionViewModel();
var initialData = new Account[] {
new Account(5) { Amount = 0 },
new Account(7) { Amount = 0 },
new Account(3) { Amount = 0 }
};
var newData = new Account[] {
new Account(5) { Amount = 10 },
/* Account by ID 7 got removed .. */
/* but account by ID 8 is new. */
new Account(8) { Amount = 10 },
new Account(3) { Amount = 10 }
};
// Act
collection.SynchronizeCollection(initialData);
// Assert
Debug.Assert(collection.SubItems.ElementAt(1).Id == 7, "The account at index 1 has not the ID 7.");
Debug.Assert(collection.SubItems.All(x => x.Amount == 0), "Not all accounts have an amount of 0.");
// Act
collection.SynchronizeCollection(newData);
// Assert
Debug.Assert(collection.SubItems.ElementAt(1).Id == 8, "The account at index 1 has not the ID 8.");
Debug.Assert(collection.SubItems.All(x => x.Amount == 10), "Not all accounts have an amount of 10.");
;
}
}
你可以看到我使用了SyncingCollectionViewModel，一个非常“重”的类型。那是因为我还没有完成轻量级的SynchronizableCollection实现（添加、删除、替换等虚拟方法缺失）。