Today I was looking into an issue I was having regarding having to do many [up to thousands] of FindName checks in my WYSIWYG graphics editor. This is due to the fact that most [if not all] of my elements are named, and when adding a new palette item I need to check and make sure that the names of the new item do not conflict with any existing items on my canvas. I stress test using palette items that contain roughly 3k elements, all with their own names. In practice, this may never be the case, but I always like to stress the crap out of things to see where they can break down the line... and honestly I can see a user ending up with complex palette items that may contain many many elements.
Aaaaaaaaaaaaanyways. Before I was going through my new item and checking all names against the canvas [using FindName] that the item was to be placed in. I found when stress testing that this comparison could take a long long time.
The solution we came up with was to create a Dictionary of all names on the canvas and then do my checks against THAT [Dictionary.ContainsKey("nameOfItem")] instead of using FindName. I chose to use a Dictionary since it is implemented on a hash, whereas a List is not.
In my tests I found that the time to do my naming checks was cut roughly in half by doing this. Obviously more memory is required to house the Dictionary of names, but the time savings more then makes up for it in my case.
In summary - it may be quicker to generate a Dictionary of names and then check against that, instead of using FindName.
I haven't tested the single case [ie only doing ONE FindName], but when doing thousands and hundreds of thousands, my performance was doubled.
.
7 years ago
2 comments:
You might squeeze out a bit more speed if you use List< string > as a static collection of your "palette element"(class). Then you can use another static method which does a Linq query like so:
return myList.Any(o => o == myNewNameStringToCheck); //returns true if any found; false otherwise
:)
Hmm... I was under the impression that List still did searches in linear time... whereas a Dictionary uses an internal hash to improve on performance.
I actually ended up doing something a little different anyways. I ended up storing the base name along with the highest index of that base [ie. Group0 --> Group = base, 0 = instance] and then just going straight for the max instead of doing a trial and error. This reduced the number of comparisons I ended up doing by a silly amount... and made my naming checks on large elements go from 1.5 mins to below a second.
The problem I guess would be that there is the chance for the max instance to get very very high, and for many instance values to actually not be used [if something is named Group7, but Groups0-6 do not exist]... but the performance trade off makes this a very small issue to me.
Thank you for the tip though, I actually haven't used much LINQ in my travels so I forget it's there ^^
Post a Comment