❔ Filtering out worse states from states array
I have a struct, for simplicity, let's call it State. State has many fields not related to each other. It also has a method IsWorse(State), which compares caller State to argument State and returns true if all caller State fields are worse or equal to argument State fields.
I want to quickly filter out states that are worse than any other states in the array, in other words, I want to filter out states that return true for method IsWorse at least once for any state in array.
I can already do this in O(n^2) time. I was thinking maybe there is a faster way.
14 Replies
I also use ArrayPool so 'filtering out' means just moving worse states to the back and reducing Length variable
you should post some code of what you're doing right now and what you want improved
the method I use now includes some other unimportant code, but here it is
public static int RemoveWorseStates_TwoPointers(CESPacked[] packedArray, ref int length)
{
int right = length - 1;
int removedCount = 0;
for (int i = 0; i < right; i++)
{
bool isWorse = false;
for (int j = i + 1; j <= right; j++)
{
if (packedArray[i].AllWorseOrEqual(packedArray[j]))
{
isWorse = true;
break;
}
}
if (isWorse)
{
CESPacked temp = packedArray[i];
packedArray[i] = packedArray[right];
packedArray[right] = temp;
right--;
removedCount++;
i--;
}
}
length -= removedCount;
int to = length + removedCount;
for (int i = length; i < to; i++)
{
if (!packedArray[i].IsDisposed)
{
packedArray[i].Dispose();
}
else
Debugger.Break();
}
return removedCount;
}
CESPacked is what State is in this code
and IsWorse is AllWorseOrEqualI want to quickly filter out states that are worse than any other states in the arraywhat does this mean? worse than what? do you just want to find the "best state" in the array?
there could technically be the best state, but if fields are different there won't be
state from array worse than any other state in the same array
what...?
i want to filter out states from array such as: if state from array is worse than any other state from the same array, it gets filtered out
i don't know what you don't understand
so you do just want to find the "best states"
that's it
technically yes, i want to find states, that are the best
can you show the code for
AllWorseOrEqual?public bool AllWorseOrEqual(CESPacked o)
{
return
Progress <= o.Progress &&
Quality <= o.Quality &&
CPRemaining <= o.CPRemaining &&
Durability <= o.Durability &&
AllBitFieldsWorseOrEqual(o);
}this honestly just feels like you should implement
IComparisonOperators and IEqualityOperatorsthat's a problem because imagine 2 states, with all fields set to 0.
first state has Progress of 100 and second state has Quality of 200.
I have to keep both states as none of them are worse than each other
and this baffles my mind on how to optimise it further.
One way i thought of was sorting array for each field and getting only 'best' states
Was this issue resolved? If so, run
/close - otherwise I will mark this as stale and this post will be archived until there is new activity.