用于在C#2.0中同步两个IList的最佳算法
想象一下以下类型:
public struct Account { public int Id; public double Amount; }
在C#2.0中同步两个IList
的最佳算法是什么? (没有linq)?
第一个列表(L1)是引用列表,第二个列表(L2)是根据第一个列表同步的列表:
- 必须从L2中删除L2中不再存在的L2中的所有帐户
- 必须更新L1中仍存在于L1中的所有帐户(金额属性)
- 所有在L1中但尚未在L2中的帐户必须添加到L2
ID标识帐户。 找到一个天真的工作算法并不难,但我想知道是否有一个智能解决方案来处理这种情况而不会破坏可读性和性能。
编辑 :
- 帐户类型无关紧要,可以是类,具有属性,平等成员等。
- L1和L2未排序
- L2项目不能被L1项目替换,必须更新(逐个字段,属性按属性)
首先,我要摆脱可变结构。 可变值类型是一个根本不好的事情。 (正如公共领域,IMO。)
这可能值得建立一个词典,以便您可以轻松地比较两个列表的内容。 一旦你有了检查是否存在的简单方法,其余的应该是直截了当的。
说实话,听起来你基本上希望L2成为L1的完整副本……清除L2并且只需调用AddRange? 或者你是否也希望在改变L2时采取其他行动?
如果您的两个列表已排序,那么您可以简单地逐步浏览它们。 这是O(m + n)操作。 以下代码可以提供帮助:
class Program { static void Main() { List left = new List { "Alice", "Charles", "Derek" }; List right = new List { "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(IEnumerable source, IEnumerable destination, IComparer comparer, Action onLeftOnly, Action onRightOnly, Action onBoth) { EnumerableIterator sourceIterator = new EnumerableIterator (source); EnumerableIterator destinationIterator = new EnumerableIterator (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 { private readonly IEnumerator _enumerator; public EnumerableIterator(IEnumerable 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是否存在?”时具有可接受性能的集合),那么您可以想出一些合理的东西。
除了Jon Skeet的评论之外,还要将您的Account结构化为一个类,并重写Equals()和GetHashCode()方法以获得良好的相等性检查。
L2 = L1.clone()?
……但我猜你忘了提一些东西。
我知道这是一个旧post,但你应该查看AutoMapper。 它将以非常灵活和可配置的方式完成您想要的任务。
AutoMapper
- asp.net Base-64字符串中的字符无效
- IDisisposable应该级联应用吗?
- 是什么原因导致System.Drawing.Printing.PrinterSettings.InstalledPrinters抛出Win32Exception“RPC服务器不可用”?
- 使用BeginXXX重写套接字和流代码到XXXAsync
- 如何避免System.Runtime.InteropServices.COMException?
- 如何在代码中设置ServiceHostingEnvironment.AspNetCompatibilityEnabled = true(不在配置中).NET / C#
- 禁用特定函数或代码块的编译器优化(C#)
- 从所有网络适配器发送广播消息
- 使用Walker的Alias方法进行加权随机选择