![]() ![]() Fetch the UUIDs I care about from the dbĭim rs as RecordSet = DB.selectQuery("select * from Exam")ĭim f as FolderItem = ()ĭim folders() as String = f.ItemNames() //uses Karen's code for VERY fast item name listing, as a String()ĭim foldersDict as new Dictionary //declare a new dictionary for my lookupįor i as integer = 0 to ubound(folders()) Here is some code to show you what I’m doing: I should note that only 1 dictionary is needed, not 2. Using a Dictionary instead of an array is VERY worth the overhead to set up the dictionary. My data set is roughly 3100 folderitem names, with maybe 1-10 or so not present in one of the arrays. I’m not sure that the overhead involved in creating 2 new dictionaries and populating them is low enough to still maintain a time savings with this approach. Now, if I was starting with 2 dictionaries in the first place, this is the clear winning approach. However, this forgets that in order to do this, I have to take the 2 arrays of String() that I already have, and loop through them BOTH to create 2 new dictionaries, then do the lookups by looping through one of the dictionaries to do the hasKey() against the other dictionary for each item in the first. Others have suggested using a dictionary for this test, as lookups are faster due to the inherent hash tables in Dictionaries for their keys. So that would yield O(n^(1/2 * m)), which is still not good. That will be on average 50%ish of the array (assuming nearly all the values are present in both arrays, as is the case with my data), or so my addled brain tells me. But I suspect that indexOf short circuits and returns a result as soon as it finds a matching value, so it only has to visit the elements in the array until it finds the match. Now, if the test must visit each item in array 2, then my runtime will be O(n^m), where n is the size of the first array, and m is the size of the second array. However, this ignores the cost of the specific test for each item. In my case, I test each item in only one of the arrays exactly one time, thus my runtime is O(n), where n is the number of items in one of the arrays. Course, like you, it’s been years since I’ve really concerned myself with this stuff… but as I recall, you figure your bound by calculating how many times you have to visit or test an item. ![]() ![]() I’m not sure I agree that my approach is much worse than O(n). ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |