Jump to content
Steve Maughan

Most efficient way to delete multiple items from a TList<T>...

Recommended Posts

I have quite a large list of 3000 objects stored in a TList<T>. I need to delete about half of them in a time-critical manner i.e. as fast as possible. I don't need to free the objects, just delete them from the list.

 

Two possible approaches come to mind. I could simply iterate through the list and repeatedly call List.Delete(index) for each item I'd like to remove. Another alternative would be to set the item to nil and then call List.Pack at the end. Is there any advantage in the second approach? Any other insights appreciated.

 

Steve  

Share this post


Link to post

May be rearrange items (move items to be kept to the beginning of the list) and then set Count to the number of items to be kept?

Share this post


Link to post
TList<T>.Pack( function (const L, R: T): Boolean
  begin
    Result := (L.Condition);
  end);

 

  • Like 1

Share this post


Link to post

I haven't done any benchmarks and don't know how much memory usage is a concern in your case- But I would assume that

  1. Creating a new list (you already know the capacity)
  2. Adding only the needed items
  3. Let your variable/field point to the new list

could be a valid option.

Share this post


Link to post
15 minutes ago, David Heffernan said:

What evidence do you have that this task is a bottleneck? 

In truth, little. It's just part of an optimization algorithm that needs to be as fast as possible. 

Share this post


Link to post

Measure, don't guess - basic rule of performance tuning

 

Linked list is a bad idea btw - if anyone thinks otherwise he needs to get an update on modern CPU architectures.

Edited by Stefan Glienke

Share this post


Link to post
1 hour ago, Anders Melander said:

Huh? You have heard of premature optimization haven't you?

Yes - I'm a total sucker for it. 

  • Like 1

Share this post


Link to post
31 minutes ago, Stefan Glienke said:

Measure, don't guess - basic rule of performance tuning

 

Linked list is a bad idea btw - if anyone thinks otherwise he needs to get an update on modern CPU architectures.

Hi Stefan - is it? I can't see why it would be a bad idea. Any links to enlighten me?

 

Steve

Share this post


Link to post
58 minutes ago, Stefan Glienke said:

Linked list is a bad idea btw

That's quite a unnuanced (is that a word?) statement.

Wouldn't you say it depends on the access and allocation pattern?

Edited by Anders Melander

Share this post


Link to post
5 minutes ago, Anders Melander said:

That's quite a unnuanced (is that a word?) statement.

Wouldn't you say it depends on the access and allocation pattern?

Of course but I am assuming that Steve is doing more with this list than just removing many items at once.

 

My personal experience with collections and a lot of material I read and watched is telling me that the chances are kinda slim that a linked list will perform better in the overall usecase.

 

Anyhow in the context of this question any discussion of this is moot and my first sentence in my first comment still stands. Anything else is a waste of time.

Edited by Stefan Glienke
  • Like 2

Share this post


Link to post
Guest

Linked lists has its merits, and sometimes it is the fastest way, i did an app where the job was to download hundreds of thousands or millions of data, all will be in list ( array in fact ) , then i will apply a filter or more to choose data from all this pile, here i switch to linked list where the data stored in this linked list is only the index in the original array and the next in LL, that way i can parse, manipulate and draw this specific selected data range in very fast way, here i would explain that in the same time when i built the LL, had a simple list of integers of the same size of original array with values either -1 or the index in the LL, now i can managed to go between them fast, i don't if this can be called a hybrid .

as for the benefits of List or array over linked list the first answer here https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java will explain this,

Share this post


Link to post
10 minutes ago, Kas Ob. said:

Very interesting. Thanks for the pointer.

One of the other answers explains it even better IMO and points to this gem: https://kjellkod.wordpress.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/

 

I guess I'll have to revisit some of my old code and redo the benchmarks.

Share this post


Link to post

We are all given a finite time here. Why would we spend it optimising something that wasn't a bottleneck. 

 

Imagine measuring, identifying the bottleneck, optimising, and the observing real discernible performance benefits? How great does that feel? 

 

Conversely, imagine expending time on work that yields no benefit. And worse, you likely end up with code that is harder to read and maintain. Usually this just results in bugs. Think of it, you spend valuable time making your program worse. You may as well just go to the pub and leave the code alone. You have a good time, and your program is better. Win win. 

Edited by David Heffernan
  • Like 7

Share this post


Link to post
4 hours ago, David Heffernan said:

You may as well just go to the pub and leave the code alone. You have a good time, and your program is better. Win win. 

Leave the pub once you reach the Ballmer Peak and then work on your program to make it even better :classic_biggrin:

  • Like 1
  • Haha 3

Share this post


Link to post

If the list is not sorted, probably the fastest option is to move items to be deleted to the end of the list by exchanging and then trim the list. This way only one memory reallocation happens. Depending on list length and available memory size, maybe creating a new list and copying only needed items to it would be quicker. Anyway, you really should benchmark this action first

Share this post


Link to post
23 minutes ago, Fr0sT.Brutal said:

If the list is not sorted, probably the fastest option is to move items to be deleted to the end of the list by exchanging and then trim the list. This way only one memory reallocation happens. Depending on list length and available memory size, maybe creating a new list and copying only needed items to it would be quicker. Anyway, you really should benchmark this action first

No, that is not fastest. It can be done with at most N item moves where N is the final coun of the list. 

Share this post


Link to post
7 minutes ago, David Heffernan said:

No, that is not fastest. It can be done with at most N item moves where N is the final coun of the list. 

It strongly depends on list size, number of items to delete and, of course, the <T> itself. If <T> is not a simple type, f.ex., a big record with lots of managed fields, assigning could take ages. However, on pretty large lists this could be the only acceptable option as internal array realloc would exhaust available memory.

Share this post


Link to post
1 hour ago, Fr0sT.Brutal said:

It strongly depends on list size, number of items to delete and, of course, the <T> itself. If <T> is not a simple type, f.ex., a big record with lots of managed fields, assigning could take ages. However, on pretty large lists this could be the only acceptable option as internal array realloc would exhaust available memory.

You don't understand. Moving an item to the end leads to all items between that point and the end being moved down.

 

It's perfectly possible to implement this without a realloc and without the dire performance traits of your chosen method. And if your array is huge and push the boundaries of available memory as you suggest, then your algorithm is unspeakably dire. 

Share this post


Link to post
1 hour ago, David Heffernan said:

You don't understand. Moving an item to the end leads to all items between that point and the end being moved down.

 

It's perfectly possible to implement this without a realloc and without the dire performance traits of your chosen method. And if your array is huge and push the boundaries of available memory as you suggest, then your algorithm is unspeakably dire. 

Why to move these items to the end? They can be ignored...
 

Next:=0;
for a:=0 to List.Count-1 do begin
 if List[a].Keep then begin
  List[Next]:=List[a];
  inc(Next);
 end;
end;
List.Count:=Next;

List<T>.Pack probably does (almost) the same, it just tries to move bigger amount of memory in one block.

Edited by Vandrovnik

Share this post


Link to post
4 hours ago, David Heffernan said:

You don't understand. Moving an item to the end leads to all items between that point and the end being moved down.

 

It's perfectly possible to implement this without a realloc and without the dire performance traits of your chosen method. And if your array is huge and push the boundaries of available memory as you suggest, then your algorithm is unspeakably dire. 

No, you don't understand 😉 I suggested to exchange them not move. Of course it only sounds simple, there will be many gotchas to avoid so if resources allow, copy is always the easiest option.

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×