-
Notifications
You must be signed in to change notification settings - Fork 86
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Observable collection that keeps suitable items #46
Comments
Hi @xperiandri. You are right. 👍 We need a way to patch items like react does with its vdom. One way to do this is to use patch algorithm like the Levenstein distance (https://en.wikipedia.org/wiki/Levenshtein_distance). It has a O(m*n) complexity so it could have performance issue on large collection. I wrote a small extension method on ObservableCollection without much tests so it could contains bugs: public static class ObservableCollectionExtensions
{
public static void LevenshteinPatch<T>(this ObservableCollection<T> source, IList<T> target)
{
if(source.Count == 0 && target.Count != 0)
{
foreach(var item in target)
{
source.Add(item);
}
return;
}
if(target.Count == 0)
{
source.Clear();
return;
}
var matrix = BuildLevenshteinMatrix(source, target);
ApplyLevenshteinMatrix(source, target, matrix);
}
private static int[,] BuildLevenshteinMatrix<T>(ObservableCollection<T> source, IList<T> target)
{
var m = new int[source.Count + 1, target.Count + 1];
for (var i = 1; i < source.Count; i++)
{
m[i, 0] = i;
}
for (var j = 1; j < target.Count; j++)
{
m[0, j] = j;
}
for (var j = 1; j < target.Count + 1; j++)
{
for (var i = 1; i < source.Count + 1; i++)
{
var substitutionCost = Equals(source[i - 1], target[j - 1]) ? 0 : 1;
var deletion = m[i - 1, j] + 1;
var insertion = m[i, j - 1] + 1;
var substitution = m[i - 1, j - 1] + substitutionCost;
m[i, j] = Min(deletion, insertion, substitution);
}
}
return m;
}
private static void ApplyLevenshteinMatrix<T>(ObservableCollection<T> source, IList<T> target, int[,] matrix)
{
var i = source.Count;
var j = target.Count;
while (i > 0 && j > 0)
{
if (matrix[i - 1, j] < matrix[i, j])
{
i--;
source.RemoveAt(i);
}
else if (matrix[i, j - 1] < matrix[i, j])
{
j--;
source.Insert(i, target[j]);
}
else if (matrix[i - 1, j - 1] < matrix[i, j])
{
i--;
j--;
source[i] = target[j];
}
else
{
i--;
j--;
}
}
for (var k = 0; k < j; k++)
{
source.Insert(k, target[k]);
}
for (var k = 0; k < i; k++)
{
source.RemoveAt(0);
}
}
private static int Min(int a, int b, int c)
{
var min = a < b ? a : b;
return min < c ? min : c;
}
} A more efficient way to do it would be to extract a unique key for each item to reduce the complexity. React documentation explain it briefly : https://facebook.github.io/react/docs/reconciliation.html If you are interested in this, Inferno has a great algorithm to patch keyed children : I would be great if Redux shipped a custom INotifyCollectionChanged collection or an extension method on ObservableCollection to patch items. If someone is interested to make a PR, I would be glad to review it and merge it! |
Extension method will not be as efficient as custom collection, a collection can batch update as a batch update within args of a single time raised event. Maybe not single time but not as much as 4 times. I don't remember the args type implementation |
I don't really know what the issue is here, but it seems the core of it is that something akin to a ListView is fully re-rendered even though only part of a collection in the state has changed, because the state collection does not implement INotifyCollectionChanged (and, indeed, is not and should not be mutable). What about having a view model where you bind the control to to a local ObservableCollection that you update from the immutable collection in the state? Sorry if I totally missed the point here. |
When an
ItemsControl
derived control is bound to a collection it creates visuals to display such items.When you switch reference in
ItemsSource
to another one all that visuals are thrown away and new visuals are created.So this is not the best solution for performance reasons.
Hence in order to make this scenario performant required an implementation of
INotifyCollectionChanged
which can check which items were deleted, which changed, which added and fires appropriate events.The text was updated successfully, but these errors were encountered: