Optimizing search in listview
I have a simple linear search implemented in a listview with about 5000 items.
LISTDATA * CTestView::FindItem(ST_TIME time)
{
CListCtrl& ctlList = GetListCtrl();
int count = ctlList.GetItemCount();
LISTDATA * pItem = 0;
for (int i = 0; i < count; i++)
{
pItem = (LISTDATA *) ctlList.GetItemData(i);
if (pItem->time == time)
return pItem;
}
return 0; // not found zero
}
This is quite slow and shows up as it is called repeatedly in a function. Can I make this search faster?
[621 byte] By [
zspirit] at [2007-11-20 11:58:37]
# 1 Re: Optimizing search in listview
If you items are ordered by time, then you could perform a binary search directly on the list. Or if not, maybe you could keep your items (or atleast the <time, location> value pair) in a seperate data structure, and perform a binary search that structure to get the items location.
- petter
# 2 Re: Optimizing search in listview
...Can I make this search faster?I really like Petter's second suggestion - to keep a separate time-to-item map. Two comments:
1. Is your time value unique? Your function will find first match only.
2. Does your list change? I mean - could it be resorted? Are new items inserted? Updated? If yes - you might need to rebuild your external map after each change.
Another suggestion - since your search is based on Item's data, you could try CListCtrl::FindItem() function with LVFI_PARAM flag. I doubt it will be much faster that your own loop, but it's worth a try. Also, you don't have to debug / maintain that function ;)
# 3 Re: Optimizing search in listview
Thanks for the suggestions, I think map is a good idea. But now that this function itself can not speed up much, I have an alternate way to rework the logic of the caller function and avoid using the above function. Sorted list is not possible.
# 4 Re: Optimizing search in listview
If you store your data in your own datastructures then maybe using the listview in Virtual mode is more recommended to avoid storing the data in your structure and in the listview.
Marc G at 2007-11-11 4:04:58 >
# 5 Re: Optimizing search in listview
If you store your data in your own datastructures then maybe using the listview in Virtual mode is more recommended to avoid storing the data in your structure and in the listview.
Can you say a bit more about virtual mode? I am using OnGetdispinfo() so displaying from the same structure. What exactly is virtual mode of listview? thanks.
# 6 Re: Optimizing search in listview
Well my effort has reached a stall. All the rows were corresponding to all the records in the file in sequence. When I save I need to match all rows to the records and save its data correctly. So I realized I dont' need the Find() function because there is already 1-1 correspondance..it tried that that and it worked very fast!
But than I stumble on a feature in which any rows can be hidden from the list (so it is temperarily deleted). Now this breaks the 1-1 correspondence and say if you delete now 2, the new row 2 will respond to record 2 in the file which is incorrect. So now I know why the Find() function is important. Maybe I still can use some variation of my 1-1 correspondance..any suggestions with this info? Probably I have to get to CMap otherwise.
# 7 Re: Optimizing search in listview
Maybe I still can use some variation of my 1-1 correspondance..any suggestions with this info?You could try setting item's data to an index of the corresponding record instead of the pointer. This adds a level of indirection, but eliminates the need to update the relationship between item number and record number.
