last day (15 days later) » 

01:17
0
Q: C# - Remove N Elements and Shift L-N Remained Elements to Zero Index in List<T> of size L in a Fastest Way

Mr.AFI have a generic List<T>, This List After a while, overflows RAM and slow down performance of the program. The program works in a such way that last Elements of the List are fresh ones and last ones probably to be requested in program is much more. In order to prevent the program to overflow the ...

Dai
Dai
Removing elements from a List<T> is always going to be slow and many things can cause reallocations - but first-off, do you understand how List<T> works internally? What profiling have you done specifically and what makes you think "shifting" elements in a List<T> is a good idea?
Sounds like you want a circular buffer
Rav
Rav
The way lists work, they need to allocate more memory as they grow, you can try using a Queue to remove the items you don't need docs.microsoft.com/en-us/dotnet/api/…
@Dai good question, VS diagnostic tool shows RAM usage goes up and CPU as well
@Jason anything that is fast
@Rav I haven't used that so far , but looks good
Dai
Dai
Please explain what you mean by "overflows RAM" - how much memory is your process actually when your code runs? (Don't blindly trust the VS Diagnostic Tools window, it doesn't accurately (or rather: it doesn't fairly) report .NET memory usage, it only shows the total OS-allocated memory usage, which is very in .NET processes on multicore systems because the GC behaves differently and allocates huge multi-megabyte GC heaps for each hardware-thread)
01:17
@Rav it Removes and returns the object at the beginning of the Queue<T> but the requests might not at first element always
Could you try to use the LinkedList<T>? It has a linear time for insert and remove, but isn't indexed (no this[int index] property). It also has a memory overhead for each item, but there is no re-allocations.
@Dai actually I do print logs in console window as well , I do see lists become more and more fat. actually it's a part of online game engine . and requests make it fat
@Mr.AF the reason that I suggest a circular buffer / ring buffer is that by design it'll remove the older entries when you reach your desired size limit. I don't believe that there is a native implementation, but it's fairly simple to achieve en.m.wikipedia.org/wiki/Circular_buffer
@Jason I do agree but I did search it , C# has not natively implemented circular List
@Mr.AF how are the items in the list retrieved, by index?
01:17
An example of how your "requests" work might be useful.
@insane_developer most often , I do compare elements like Contains and Find a match
Another option is to use the Dictionary<TKey, TValue> if you have a unique key for each stored object. It also has a constant time for insert and remove and is indexed (by the key).
@Dmitry I do agree because of hash table for searching it's so fast but , I need define keys and change entire program structure.
@Mr.AF in a big list, as you said, this is very inefficient. Why not use a HashSet<T> instead where all access is O(1)?
@insane_developer if it's good why not, as I commented , any solution which is fast and is related to List of elements .
@Dmitry I think LinkedList<T> is practical and worth trying.
01:17
HashSet and dictionary are not going to preserve the priority that older items should be deleted first. If you want this out of the box, an option is to use Queue and do a size check before each insert and dequeue before enqueue if the limit is reached.
LInkedList<T> is not so good when the item you're looking for is not the head or the tail, then your search is linear.
@insane_developer if O(1) related to head and tail , then your right.
I've mistaken in my first comment - LinkedList<T> has a constant time for insert and remove. Sorry.
@Jason if that's the case, I'd go with a priority queue. .NET does not offer that out of the box, so it has to be implemented.
@insane_developer it's just first in first out priority. So a circular buffer fits best in my opinion, I'm just thinking of how to implement one with the structures .net has already with limited effort. In this case, a Queue with size checks on insert.
01:17
@Jason if you want to keep a fixed length, a circular array would be more efficient. All you have to do is keep track of where the tail is. If you know the tail, the head is the next index (when going back to 0). It's still inefficient when searching what's not at the end.
@insane_developer a circular buffer / circular array / ring buffer is what I was suggesting. Yes you will have to iterate to check for an item, but that was already the case in the question. When I think about the queue approach to implement a fixed length queue though, it's probably better to use a linked list, as queue will not allow iteration from the back of the structure.
@Jason I think the size of this list is what makes a linked list not the best option when the whole point is to reduce the size of memory being used, more so a doubly linked list (which you'd need in this case). An array with the same number of items will take considerably less space in memory.
@insane_developer, yes I agree. But the poster had stated that they want something out of the box. Perhaps an ordered Dictionary could be used here where on insert you check size and remove an item from index 0 if the size limit is met. docs.microsoft.com/en-us/dotnet/api/…

last day (15 days later) »