sorting - Optimize algorithm: Update a collection by other collection with order C# -
problem: have collection need update other collection. length of them not equal , each item not same structure. both of them have identity field detect same.
i write generic algorithm use everywhere complexity o(m*n*3). main problem is: there better optimization algorithm? input must should generic ilist<t> , delegate reusable.
current approach:
source: data collection used display on gui.
target: data collection got remote server.
- remove old items source doesn't existed target via delegate comparer.
- add new items target source.
- reorder source target.
scenario usage: if have application display 1~2k row on list view. , have interval timer update list item (about 1 seconds). main point here application should smooth, doesn't flick , keep state of object: selected, change data... etc.
here source code:
using system; using system.collections.generic; using system.linq; namespace updatecollection { /// <summary> /// person dto (from other 3rd assembly) data remote server. /// </summary> public class persondto { public int id { get; set; } public string name { get; set; } public datetime birthday { get; set; } } /// <summary> /// person model used display on gui (our application). /// </summary> public class personmodel { public string identity { get; set; } public string displayname { get; set; } public int? age { get; set; } public bool selected { get; set; } public override string tostring() { return string.format("{0} {1} {2} {3}", identity, displayname, age, selected); } } static class program { /// <summary> /// encapsulates method has 2 parameters , not return value. /// </summary> /// <typeparam name="t1">the type of first parameter of method delegate encapsulates.this type parameter contravariant. is, can use either type specified or type less derived. more information covariance , contravariance, see covariance , contravariance in generics.</typeparam> /// <typeparam name="t2">the type of second parameter of method delegate encapsulates.</typeparam> /// <param name="arg1"></param> /// <param name="arg2"></param> public delegate void refaction<t1, in t2>(ref t1 arg1, t2 arg2); /// todo: complexity of algorithm is: o(m*n*3) need optimization. example: m*log2(n)+ m + n /// <summary> /// update source target. /// </summary> /// <typeparam name="tsourcetype"></typeparam> /// <typeparam name="ttargettype"></typeparam> /// <param name="source">source collection.</param> /// <param name="target">target collection.</param> /// <param name="compare">comparing method between source , target.</param> /// <param name="convert">convert method</param> /// <param name="update">update method</param> /// <param name="remove">remove method</param> public static void updateby<tsourcetype, ttargettype>( ilist<tsourcetype> source, ilist<ttargettype> target, func<tsourcetype, ttargettype, bool> compare, func<ttargettype, tsourcetype> convert, refaction<tsourcetype, ttargettype> update, func<tsourcetype, bool> remove = null) { if (source == null || target == null) return; if (convert == null) throw new aggregateexception("convert"); if (compare == null) throw new argumentnullexception("compare"); // remove item (var index = 0; index < source.count; ++index) { if (target.any(c => compare(source[index], c))) continue; var temp = source[index]; if (remove == null) source.removeat(index--); else if (remove(temp)) source.removeat(index--); } // add new item foreach (var t in target.where(t => !source.any(c => compare(c, t)))) { source.add(convert(t)); } // sort target (var index = 0; index < target.count; ++index) { (var pos = 0; pos < source.count; ++pos) { if (!compare(source[pos], target[index])) continue; var temp = source[pos]; if (update != null) update(ref temp, target[index]); source[pos] = temp; if (pos == index) continue; temp = source[pos]; source[pos] = source[index]; source[index] = temp; } } } public static ilist<personmodel> getfromuserinterface() { return new list<personmodel> { new personmodel {identity = "1", displayname = "a",}, new personmodel {identity = "2", displayname = "b", selected = true}, new personmodel {identity = "3", displayname = "c", selected = true}, new personmodel {identity = "4", displayname = "d"} }; } public static ilist<persondto> getfromremoteserver() { return new list<persondto> { new persondto {id = 6, name = "f", birthday = datetime.parse("1984-01-02")}, new persondto {id = 4, name = "d", birthday = datetime.parse("1986-01-12")}, new persondto {id = 3, name = "c", birthday = datetime.parse("1982-03-05")}, new persondto {id = 5, name = "e", birthday = datetime.parse("1984-05-22")}, new persondto {id = 1, name = "a", birthday = datetime.parse("1986-02-14")} }; } public static bool compare(personmodel source, persondto target) { return source.identity == target.id.tostring(); } public static personmodel convert(persondto target) { return new personmodel { identity = target.id.tostring(), age = target.birthday.year, displayname = target.name, }; } public static void update(ref personmodel source, persondto target) { source.age = target.birthday.year; source.displayname = target.name; } static void main(string[] args) { var source = getfromuserinterface(); var target = getfromremoteserver(); console.writeline("==> before update:\r\n"); foreach (var item in source) console.write("{0}\r\n\r\n", item); // todo: how optimize updateby algorithm better? source.updateby(target, compare, convert, update); console.writeline("==> after update:\r\n"); foreach (var item in source) console.write("{0}\r\n\r\n", item); console.readline(); } } }
you storing data in list; switching hash table structure give (roughly) constant time access members key. if ordering of data important, many languages have kind of ordered hash construct can use.
Comments
Post a Comment