I need to create a sorted and filtered list from an unsorted Dictionary of objects.
I tried maintaining a sorted dictionary however this proved impractical as these objects contain attributes which constantly updated by external processes.
The current solution requires two full passes over the dictionary - first a filter, secondly a sort. I feel there should be a way to combine these steps to avoid looping over the entire collection twice.
I'm trying to combine the first and second passes shown below into a single iteration over the dictionary if possible.
Speed is important here so I doubt I can use Linq.
//SETUP//
//class stub
public class myObject{
public int ID;
public float sortAttribute;
public bool filterAttribute;
}
//unsorted dictionary
Dictionary<int, myObject> myDictionary = new Dictionary<int, myObject>();
//sorting method
public int sortMethod(myObject o1, myObject o2)
{
if (o1.sortAttribute < o2.sortAttribute)
{
return -1;
} else {
return 1;
}
}
//CURRENT PROCESS//
//create empty list
List<myObject> sortedList = new List<myObject>();
//first pass - populate list from dictionary - filtering on the way
foreach (KeyValuePair<int, myObject> entry in myDictionary){
if (entry.Value.filterAttribute){
sortedList.Add(entry.Value)
}
}
//2nd pass - sort the populated list
sortedList.Sort(sortMethod);
CodePudding user response：
Here you have a data structure based on sorted dictionary that is always sorted by SortAttribute then by Id, no matter if data is changed outside because it reacts properly to changes on the data.
Insertion, modification and removal of an item is O(log(n)).
Disclaimer: It's not thread safe
namespace SortedDataStructureApp
{
public class ValueChangedEventArgs<T> : EventArgs
{
public T? PreviousValue { get; private set; }
public T? CurrentValue { get; private set; }
public ValueChangedEventArgs(T previousValue, T currentValue)
{
this.PreviousValue = previousValue;
this.CurrentValue = currentValue;
}
}
public class MyObject
{
public event EventHandler<ValueChangedEventArgs<int>>? IdChanged;
public event EventHandler<ValueChangedEventArgs<float>>? SortAttributeChanged;
public event EventHandler<ValueChangedEventArgs<bool>>? FilterAttributeChanged;
private int _id;
public int Id
{
get
{
return _id;
}
set
{
if (value == _id) return;
var previousValue = _id;
_id = value;
IdChanged?.Invoke(this, new ValueChangedEventArgs<int>(previousValue, value));
}
}
private float _sortAttribute;
public float SortAttribute
{
get
{
return _sortAttribute;
}
set
{
if (value == _sortAttribute) return;
var previousValue = _sortAttribute;
_sortAttribute = value;
SortAttributeChanged?.Invoke(this, new ValueChangedEventArgs<float>(previousValue, value));
}
}
private bool _filterAttribute;
public bool FilterAttribute
{
get
{
return _filterAttribute;
}
set
{
if (value == _filterAttribute) return;
var previousValue = _filterAttribute;
_filterAttribute = value;
FilterAttributeChanged?.Invoke(this, new ValueChangedEventArgs<bool>(previousValue, value));
}
}
}
internal class SortedDataStructure
{
private Dictionary<int, MyObject> unsortedDictionary = new Dictionary<int, MyObject>();
private SortedDictionary<float, SortedDictionary<int, MyObject>> sortedDictionary = new SortedDictionary<float, SortedDictionary<int, MyObject>>();
private EventHandler<ValueChangedEventArgs<int>> idChangedHandler;
private EventHandler<ValueChangedEventArgs<float>> sortAttributeChangedHandler;
private EventHandler<ValueChangedEventArgs<bool>> filterAttributeChangedHandler;
public SortedDataStructure()
{
idChangedHandler = new EventHandler<ValueChangedEventArgs<int>>(IdChanged);
sortAttributeChangedHandler = new EventHandler<ValueChangedEventArgs<float>>(SortAttributeChanged);
filterAttributeChangedHandler = new EventHandler<ValueChangedEventArgs<bool>>(FilterAttributeChanged);
}
private void IdChanged(object? sender, ValueChangedEventArgs<int> e)
{
if (sender == null) throw new ArgumentNullException(nameof(sender));
var obj = (MyObject)sender;
Remove(e.PreviousValue);
Add(obj);
}
private void SortAttributeChanged(object? sender, ValueChangedEventArgs<float> e)
{
if (sender == null) throw new ArgumentNullException(nameof(sender));
var obj = (MyObject)sender;
if (obj.FilterAttribute)
{
RemoveFromSortedDictionary(e.PreviousValue, obj.Id);
AddToSortedDictionary(obj);
}
}
private void FilterAttributeChanged(object? sender, ValueChangedEventArgs<bool> e)
{
if (sender == null) throw new ArgumentNullException(nameof(sender));
var obj = (MyObject)sender;
if (e.CurrentValue == true)
{
AddToSortedDictionary(obj);
}
else
{
RemoveFromSortedDictionary(obj.SortAttribute, obj.Id);
}
}
public void Add(MyObject obj)
{
if (obj == null) throw new ArgumentNullException(nameof(obj));
unsortedDictionary.Add(obj.Id, obj);
if (obj.FilterAttribute)
{
AddToSortedDictionary(obj);
}
obj.FilterAttributeChanged = this.filterAttributeChangedHandler;
obj.IdChanged = this.idChangedHandler;
obj.SortAttributeChanged = this.sortAttributeChangedHandler;
}
private void RemoveFromSortedDictionary(float sortAttribute, int id)
{
if (sortedDictionary.TryGetValue(sortAttribute, out var subDictionary) == false)
{
throw new InvalidOperationException($"Sorted structure is corrupted. Could not find sortAttribute: {sortAttribute}");
}
if (subDictionary.Remove(id) == false)
{
throw new InvalidOperationException($"Sorted structure is corrupted. Could not find id {id} in subdictionary");
}
}
private void AddToSortedDictionary(MyObject obj)
{
if (sortedDictionary.TryGetValue(obj.SortAttribute, out var subDictionary) == false)
{
subDictionary = new SortedDictionary<int, MyObject>();
sortedDictionary.Add(obj.SortAttribute, subDictionary);
}
subDictionary.Add(obj.Id, obj);
}
public bool Remove(int id)
{
if (unsortedDictionary.Remove(id, out var obj) == false)
{
return false;
}
if (obj.FilterAttribute)
{
RemoveFromSortedDictionary(obj.SortAttribute, id);
}
obj.FilterAttributeChanged -= this.filterAttributeChangedHandler;
obj.IdChanged -= this.idChangedHandler;
obj.SortAttributeChanged -= this.sortAttributeChangedHandler;
return true;
}
public IEnumerable<MyObject> GetSortedValues()
{
return this.sortedDictionary.Values.SelectMany(x => x.Values);
}
public MyObject GetById(int id)
{
return unsortedDictionary[id];
}
public bool ContainsKey(int id)
{
return unsortedDictionary.ContainsKey(id);
}
public bool TryGetValue(int id, out MyObject? obj)
{
return unsortedDictionary.TryGetValue(id, out obj);
}
}
}
Code to show how it works:
using SortedDataStructureApp;
var obj1 = new MyObject
{
Id = 1,
SortAttribute = 1,
FilterAttribute = true
};
var obj2 = new MyObject
{
Id = 2,
SortAttribute = 1,
FilterAttribute = true
};
var data = new SortedDataStructure();
data.Add(obj1);
data.Add(obj2);
// It shows 1, 2. Both have the same sort attribute but Id = 1 comes before Id = 2
foreach (var obj in data.GetSortedValues())
{
Console.WriteLine(obj.Id);
}
obj1.Id = 3;
Console.WriteLine();
// It shows 2, 3
foreach (var obj in data.GetSortedValues())
{
Console.WriteLine(obj.Id);
}
obj1.SortAttribute = 0.5f;
Console.WriteLine();
// obj1.SortAttribute < obj2.SortAttribute, so it shows 3, 2
foreach (var obj in data.GetSortedValues())
{
Console.WriteLine(obj.Id);
}
obj2.FilterAttribute = false;
Console.WriteLine();
// obj2 doesn't appear
foreach (var obj in data.GetSortedValues())
{
Console.WriteLine(obj.Id);
}
obj2.FilterAttribute = true;
obj1.FilterAttribute = false;
// now only obj2 is shown
Console.WriteLine();
foreach (var obj in data.GetSortedValues())
{
Console.WriteLine(obj.Id);
}
CodePudding user response：
As you do not specify exactly how big your dictionary is I will list 2 answers here and a suggestion, one for when your dictionary is big and one for when your dictionary is small (enough).
Lets start with the big dictionary. You can achieve this in multiple ways but I would try to use an O(n log n) method and not a O(n^2) as you mentioned that speed is of the essence. I would try to create a favourable merge sort step when you are creating your filtered list. Every filtered two elements can be sorted when you add them to your new list. Then you can skip the first step of merge sort and immediately begin sorting 4 elements. This however will almost be as fast as your current implementation as you only skip one step of merge sort and you will have to create your own version of merge sort that does not start with 2 elements.
For the small (enough) dictionary you can use a faster sorting algorithm. You could use a version of counting sort to create a filter and sorting algorithm that can sort your dictionary in O(n). You will need to study your data for this algorithm though to see how you are going to split your data into the different counting sort buckets E.G. if all your numbers are between 0 and 1 you can create 1000 buckets and select a bucket by multiplying the float by 1000. Do note that the buckets might have to be sorted as well if multiple elements are in them (if your data is split well these can be very fast as not a lot of numbers will be in the same bucket).
Personally I would suggest trying out option 2 and seeing if that gives you a good enough performance gain and if it does not require too many buckets. If you would require too many buckets or the performance is just not what you wanted you can always do option 1 afterwards.
CodePudding user response：
This method refers to the implementation of .net SortedList.
myObjectComparerClass myObjectComparer = new ();
foreach (KeyValuePair<int, myObject> entry in myDictionary){
if (entry.Value.filterAttribute){
int i = sortedList.BinarySearch(entry.Value, myObjectComparer);
if (i < 0)
sortedList.Insert(~i, entry.Value);
}
}
public class myObjectComparerClass : IComparer<myObject>
{
public int Compare(myObject o1, myObject o2)
{
if (o1.sortAttribute < o2.sortAttribute)
{
return -1;
} else {
return 1;
}
}
}