Re: Fast NSArray compare
To summarise what was discussed, - I think the folder hierarchy problem is easily solvable as I always traverse from top of the tree. If an entry for one of the folders is found in my set I stop the traversal to lower leaves of the tree. - I would be using NSSet to store my “restrict list”. However I will be using file names instead of resource identifier object because I need to preserve this across reboots. However I could always extract the resource identifier object for these NSURL objects and do the comparison. There is always a possibility that one of the files stored in “restricted list” could be removed or changed automatically by user or program. If this happens, I am holding a useless value that is no longer present in file system. This is not a big issue as I see other than wasteful entry in the set. Upon application restart when reading from the file which stored the restricted list, I could do a file existence check for all entries in the restricted set. - I will be converting the NSSet to NSArray and save it in file. I read the array as NSSet when the application starts. Is there something else I am missing? Regards, Varun On 16/04/2014 4:17 am, "Gary L. Wade" wrote: >Also, if your folder hierarchy, traversal code, and checks can deal well >with it, you¹ll get better performance by short-circuiting based on upper >directory checks. > >For example, if you know you¹re in /Downloads, don¹t compare against >/Documents/AboutUs.pdf. Just use the /Documents set of file objects when >you¹re in /Documents. >-- >Gary L. Wade >http://www.garywade.com/ > > > > > >___ > >Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) > >Please do not post admin requests or moderator comments to the list. >Contact the moderators at cocoa-dev-admins(at)lists.apple.com > >Help/Unsubscribe/Update your Subscription: >https://lists.apple.com/mailman/options/cocoa-dev/varun.chandramohan%40won >tok.com > >This email sent to varun.chandramo...@wontok.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
On Apr 14, 2014, at 9:01 PM, Ken Thomases wrote: > You should obtain the resource identifier object of each URL using > -getResourceValue:forKey:error: with NSURLFileResourceIdentifierKey, then > compare those two objects using -isEqual:. One thing to watch out for, though: the object returned for NSURLFileResourceIdentifierKey returns YES for isEqual: if the two objects have the same inode. This means that if you have two files that are hard links of the same inode, it will report them as equal. If you want to check if two URLs point to the same catalog node rather than to the same inode, you'll need to do something else. Charles ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
Also, if your folder hierarchy, traversal code, and checks can deal well with it, you¹ll get better performance by short-circuiting based on upper directory checks. For example, if you know you¹re in /Downloads, don¹t compare against /Documents/AboutUs.pdf. Just use the /Documents set of file objects when you¹re in /Documents. -- Gary L. Wade http://www.garywade.com/ ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
On Apr 15, 2014, at 7:45 AM, Alex Zavatone wrote: > A good approach here would be to make a test case for NSArray and NSSet, a > known set of files and simply test now long each takes. In general I agree that it’s a good idea to test before optimizing. It’s common for people here to start obsessing over performance without even knowing whether the unoptimized code will take a measurable amount of time. But in this case, there are enough red flags (scanning the filesystem, which often contains millions of files, and doing string comparisons against thousands of patterns), and using an NSSet instead of an NSArray is such an easy change, that I consider it a no-brainer to go with NSSet. —Jens ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
Another wild thought, how about drop one layer lower to POSIX and use a little bit of OpenCL? For every directory with content paths C[0..i] and the list of restricted paths R[0..j] construct a matrix (using OpenCL) M[0..i, 0..j] where M[i, j]=strcmp(C[i], R[j]) (strcmp() itself can be OpenCL code as well, using bit wise XOR and NOT) and logic AND every element in every row (another OpenCL operation). This will spit out an array of booleans indicating whether the path in question should be skipped. Sent from my iPad > On Apr 15, 2014, at 8:02 AM, Varun Chandramohan > wrote: > > Hi All, > > I have a question about efficiency when trying to compare NSURL. The > requirement is quite simple. I try and iterate through a directory to all > subdirectories and files. While doing this walk-through, I need to check > against an array of NSURLs which are restricted files and folders. > This means if I find a match of file I am trying to access in the array then > I don't do any operations on that file and continue. > > Lets say I walkthrough 1000 files and folders, for each file/folder I need to > compare against this array list. This might be slow or inefficient. Is there > a faster way to do something like this? > > Secondly, I plan to store array of NSURL for restricted files and folders. > What is the best way to get partial compare? > > Eg: Entry in array : /XYZ/abc > This means I should not iterate into the abc folder. So any files > /XYZ/abc/1.c or /XYZ/abc/def/2.c should all be skipped. Whats the best way to > do partial NSURL compare? Or is it better I store it as NSString instead of > NSURL? > > Regards, > Varun > ___ > > Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) > > Please do not post admin requests or moderator comments to the list. > Contact the moderators at cocoa-dev-admins(at)lists.apple.com > > Help/Unsubscribe/Update your Subscription: > https://lists.apple.com/mailman/options/cocoa-dev/xcvista%40me.com > > This email sent to xcvi...@me.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
To keep your NSSet you can store it as an array. There are conversion methods like -[NSSet array] and +[NSSet setWithContentsOfArray:]. Also, you can try to determine if your code is running on SSD. SSD can be iterated in parallel and GCD will help a little when parallelizing the search. Sent from my iPad > On Apr 15, 2014, at 12:10 PM, Varun Chandramohan > wrote: > > Thanks Guys, > > Yes I was not planning to use -[NSURL isEqual:]. Interestingly, Graham¹s > suggestion was to use NSSet, I was thinking what if I want to keep this > persistent? I would be writing this set to a file? I have used NSArray > writeToFile before but I don¹t see that method for NSSet. Do I have to > convert it to NSArray and store? Am I missing something? > > I figured if I put resource identifier object into the NSMutableSet then > will I be able to write this into a file? I know it is possible if I store > it as NSString but might not allow id? > > Regards, > Varun > >> On 15/04/2014 12:01 pm, "Ken Thomases" wrote: >> >>> On Apr 14, 2014, at 7:02 PM, Varun Chandramohan wrote: >>> >>> I have a question about efficiency when trying to compare NSURL. The >>> requirement is quite simple. I try and iterate through a directory to >>> all subdirectories and files. While doing this walk-through, I need to >>> check against an array of NSURLs which are restricted files and folders. >>> This means if I find a match of file I am trying to access in the array >>> then I don't do any operations on that file and continue. >> >> You don't say how you're comparing URLs. Just in case, you should not >> use -[NSURL isEqual:] or any method which relies on string comparison. >> That can be confused by case differences, the presence of hard or >> symbolic links, and extraneous path elements (e.g. "foo/./bar" vs. >> "foo/bar"). >> >> You should obtain the resource identifier object of each URL using >> -getResourceValue:forKey:error: with NSURLFileResourceIdentifierKey, then >> compare those two objects using -isEqual:. >> >> If you take Graham's suggestion of using an NSSet or similar hash-based >> collection to test, then put the resource identifiers of the restricted >> files into the set and check a candidate URL's resource identifier >> against that set. >> >> For what it's worth, comparing resource identifiers may be faster than >> the string comparison otherwise inherent in -[NSURL isEqual:]. The >> identifier is likely to be a number or pair of numbers internally and so >> is quick to compare. That said, the improvement may be swamped by the >> cost of obtaining the resource identifier object. >> >> >>> Secondly, I plan to store array of NSURL for restricted files and >>> folders. What is the best way to get partial compare? >>> >>> Eg: Entry in array : /XYZ/abc >>> This means I should not iterate into the abc folder. So any files >>> /XYZ/abc/1.c or /XYZ/abc/def/2.c should all be skipped. Whats the best >>> way to do partial NSURL compare? Or is it better I store it as NSString >>> instead of NSURL? >> >> Don't try to do substring compares. Since you're iterating a directory >> hierarchy, you should simply not iterate a subdirectory if it matches. >> When using NSDirectoryEnumerator, that's easy to do: just call >> -skipDescendants. >> >> If you feel you must compare two URLs to see if one is contained in the >> other, you'll probably have to successively obtain the parent directory >> URL from the candidate URL using -getResourceValue:forKey:error: with >> NSURLParentDirectoryURLKey until you've reached the top of the hierarchy >> or you have matched one of your restricted file URLs. >> >> You _might_ want to optimize that by obtaining the >> NSURLVolumeIdentifierKey of each URL and then determining that one >> doesn't contain the other if the two URLs are for different volumes. >> Whether that's appropriate or not depends on whether you care about >> path-based containment or file-system-based containment. "/foo/bar/baz" >> may be on a different volume than "/foo" and you have to decide whether >> that means that it's not contained by "/foo". >> >> Regards, >> Ken > > > ___ > > Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) > > Please do not post admin requests or moderator comments to the list. > Contact the moderators at cocoa-dev-admins(at)lists.apple.com > > Help/Unsubscribe/Update your Subscription: > https://lists.apple.com/mailman/options/cocoa-dev/xcvista%40me.com > > This email sent to xcvi...@me.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
A good approach here would be to make a test case for NSArray and NSSet, a known set of files and simply test now long each takes. On Apr 14, 2014, at 8:59 PM, Graham Cox wrote: > > On 15 Apr 2014, at 10:02 am, Varun Chandramohan > wrote: > >> Lets say I walkthrough 1000 files and folders, for each file/folder I need >> to compare against this array list. This might be slow or inefficient. Is >> there a faster way to do something like this? > > > As a general principle, if you have to check whether one of a list of things > is part of another list of things, an array is the wrong container for the > job, because it amounts to a worst-case O(n^2) search. Instead, use a set or > hash table for the set of things that must be detected among the first list, > and it reduces to a worst-case O(n) operation. That said, if the number of > items in the second list is small, the performance may be acceptable, and > using a hash table might not speed it up noticeably - the time will be > dominated by the iteration through the larger list. > > --Graham > > > > ___ > > Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) > > Please do not post admin requests or moderator comments to the list. > Contact the moderators at cocoa-dev-admins(at)lists.apple.com > > Help/Unsubscribe/Update your Subscription: > https://lists.apple.com/mailman/options/cocoa-dev/zav%40mac.com > > This email sent to z...@mac.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
On Tue Apr 15 2014 12:41:50 GMT+1000 (PGT) Graham Cox wrote: On 15 Apr 2014, at 12:03 pm, John Brownie wrote: think you're an order of magnitude out. Searching an array is linear with the length of the array, O(n), whereas a set or hash should be close to constant, O(1), if there's not a big collision in the hashes. But the principle is correct, that you don't want to be searching arrays. Of course, if it's a sorted array, you can do it in O(log n) by binary searching. Right, but you're also iterating the first list, which is O(n), so for each item you have to linear search a second list, O(n) again, so it's O(n) x O(n), or O(n^2). If the second "list" is just a hash or set, that's O(1), so overall it's O(n) x O(1) or O(n). That is, I was discussing the overall performance, not just the lookup for membership. OK, I see your point. With two different lists, assuming the fixed list (n entries) is much smaller than the total list (m entries), you end up with O(mn), O(m), or O(m log n), which probably ends up as O(m) in the end, but the size of the multiplier will still bite. John -- John Brownie, john_brow...@sil.org or j.brow...@sil.org.pg Summer Institute of Linguistics | Mussau-Emira language, Mussau Is. Ukarumpa, Eastern Highlands Province | New Ireland Province Papua New Guinea | Papua New Guinea ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
On Apr 14, 2014, at 21:10 , Varun Chandramohan wrote: > I was thinking what if I want to keep this persistent? This doesn’t sound like such a good idea. There’s nothing to guarantee that your saved data will actually match the state of the file system the next time you read it back. In particular, the NSURL class reference says of ‘NSURLFileResourceIdentifierKey’: > The value of this identifier is not persistent across system restarts. However, it seems to me it’s a little worse than that. The file system can change behind your back at any time. Even resource identifiers you may have kept in memory while your app is running have the potential to become invalidated from one moment to the next. Since (it sounds from your earlier description), the way you *really* know which files/folders are restricted is by name (that is, essentially by path), you might be better off basing your comparisons on -[NSURL isEqual:] after all, or perhaps even comparisons of -[NSURL path]. Note that if the NSURLs you’re checking come from a directory enumerator, they will have a consistent structure (and the correct case). If you’re careful constructing your set of restricted URLs, there shouldn’t be a problem about doing the name-string-based comparison I’m suggesting. ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
Thanks Guys, Yes I was not planning to use -[NSURL isEqual:]. Interestingly, Graham¹s suggestion was to use NSSet, I was thinking what if I want to keep this persistent? I would be writing this set to a file? I have used NSArray writeToFile before but I don¹t see that method for NSSet. Do I have to convert it to NSArray and store? Am I missing something? I figured if I put resource identifier object into the NSMutableSet then will I be able to write this into a file? I know it is possible if I store it as NSString but might not allow id? Regards, Varun On 15/04/2014 12:01 pm, "Ken Thomases" wrote: >On Apr 14, 2014, at 7:02 PM, Varun Chandramohan wrote: > >> I have a question about efficiency when trying to compare NSURL. The >>requirement is quite simple. I try and iterate through a directory to >>all subdirectories and files. While doing this walk-through, I need to >>check against an array of NSURLs which are restricted files and folders. >> This means if I find a match of file I am trying to access in the array >>then I don't do any operations on that file and continue. > >You don't say how you're comparing URLs. Just in case, you should not >use -[NSURL isEqual:] or any method which relies on string comparison. >That can be confused by case differences, the presence of hard or >symbolic links, and extraneous path elements (e.g. "foo/./bar" vs. >"foo/bar"). > >You should obtain the resource identifier object of each URL using >-getResourceValue:forKey:error: with NSURLFileResourceIdentifierKey, then >compare those two objects using -isEqual:. > >If you take Graham's suggestion of using an NSSet or similar hash-based >collection to test, then put the resource identifiers of the restricted >files into the set and check a candidate URL's resource identifier >against that set. > >For what it's worth, comparing resource identifiers may be faster than >the string comparison otherwise inherent in -[NSURL isEqual:]. The >identifier is likely to be a number or pair of numbers internally and so >is quick to compare. That said, the improvement may be swamped by the >cost of obtaining the resource identifier object. > > >> Secondly, I plan to store array of NSURL for restricted files and >>folders. What is the best way to get partial compare? >> >> Eg: Entry in array : /XYZ/abc >> This means I should not iterate into the abc folder. So any files >>/XYZ/abc/1.c or /XYZ/abc/def/2.c should all be skipped. Whats the best >>way to do partial NSURL compare? Or is it better I store it as NSString >>instead of NSURL? > >Don't try to do substring compares. Since you're iterating a directory >hierarchy, you should simply not iterate a subdirectory if it matches. >When using NSDirectoryEnumerator, that's easy to do: just call >-skipDescendants. > >If you feel you must compare two URLs to see if one is contained in the >other, you'll probably have to successively obtain the parent directory >URL from the candidate URL using -getResourceValue:forKey:error: with >NSURLParentDirectoryURLKey until you've reached the top of the hierarchy >or you have matched one of your restricted file URLs. > >You _might_ want to optimize that by obtaining the >NSURLVolumeIdentifierKey of each URL and then determining that one >doesn't contain the other if the two URLs are for different volumes. >Whether that's appropriate or not depends on whether you care about >path-based containment or file-system-based containment. "/foo/bar/baz" >may be on a different volume than "/foo" and you have to decide whether >that means that it's not contained by "/foo". > >Regards, >Ken > ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
On 15 Apr 2014, at 12:03 pm, John Brownie wrote: > think you're an order of magnitude out. Searching an array is linear with > the length of the array, O(n), whereas a set or hash should be close to > constant, O(1), if there's not a big collision in the hashes. But the > principle is correct, that you don't want to be searching arrays. Of course, > if it's a sorted array, you can do it in O(log n) by binary searching. Right, but you're also iterating the first list, which is O(n), so for each item you have to linear search a second list, O(n) again, so it's O(n) x O(n), or O(n^2). If the second "list" is just a hash or set, that's O(1), so overall it's O(n) x O(1) or O(n). That is, I was discussing the overall performance, not just the lookup for membership. --Graham ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
Graham Cox wrote: As a general principle, if you have to check whether one of a list of things is part of another list of things, an array is the wrong container for the job, because it amounts to a worst-case O(n^2) search. Instead, use a set or hash table for the set of things that must be detected among the first list, and it reduces to a worst-case O(n) operation. That said, if the number of items in the second list is small, the performance may be acceptable, and using a hash table might not speed it up noticeably - the time will be dominated by the iteration through the larger list. I think you're an order of magnitude out. Searching an array is linear with the length of the array, O(n), whereas a set or hash should be close to constant, O(1), if there's not a big collision in the hashes. But the principle is correct, that you don't want to be searching arrays. Of course, if it's a sorted array, you can do it in O(log n) by binary searching. John -- John Brownie, john_brow...@sil.org or j.brow...@sil.org.pg Summer Institute of Linguistics | Mussau-Emira language, Mussau Is. Ukarumpa, Eastern Highlands Province | New Ireland Province Papua New Guinea | Papua New Guinea ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
On Apr 14, 2014, at 7:02 PM, Varun Chandramohan wrote: > I have a question about efficiency when trying to compare NSURL. The > requirement is quite simple. I try and iterate through a directory to all > subdirectories and files. While doing this walk-through, I need to check > against an array of NSURLs which are restricted files and folders. > This means if I find a match of file I am trying to access in the array then > I don't do any operations on that file and continue. You don't say how you're comparing URLs. Just in case, you should not use -[NSURL isEqual:] or any method which relies on string comparison. That can be confused by case differences, the presence of hard or symbolic links, and extraneous path elements (e.g. "foo/./bar" vs. "foo/bar"). You should obtain the resource identifier object of each URL using -getResourceValue:forKey:error: with NSURLFileResourceIdentifierKey, then compare those two objects using -isEqual:. If you take Graham's suggestion of using an NSSet or similar hash-based collection to test, then put the resource identifiers of the restricted files into the set and check a candidate URL's resource identifier against that set. For what it's worth, comparing resource identifiers may be faster than the string comparison otherwise inherent in -[NSURL isEqual:]. The identifier is likely to be a number or pair of numbers internally and so is quick to compare. That said, the improvement may be swamped by the cost of obtaining the resource identifier object. > Secondly, I plan to store array of NSURL for restricted files and folders. > What is the best way to get partial compare? > > Eg: Entry in array : /XYZ/abc > This means I should not iterate into the abc folder. So any files > /XYZ/abc/1.c or /XYZ/abc/def/2.c should all be skipped. Whats the best way to > do partial NSURL compare? Or is it better I store it as NSString instead of > NSURL? Don't try to do substring compares. Since you're iterating a directory hierarchy, you should simply not iterate a subdirectory if it matches. When using NSDirectoryEnumerator, that's easy to do: just call -skipDescendants. If you feel you must compare two URLs to see if one is contained in the other, you'll probably have to successively obtain the parent directory URL from the candidate URL using -getResourceValue:forKey:error: with NSURLParentDirectoryURLKey until you've reached the top of the hierarchy or you have matched one of your restricted file URLs. You _might_ want to optimize that by obtaining the NSURLVolumeIdentifierKey of each URL and then determining that one doesn't contain the other if the two URLs are for different volumes. Whether that's appropriate or not depends on whether you care about path-based containment or file-system-based containment. "/foo/bar/baz" may be on a different volume than "/foo" and you have to decide whether that means that it's not contained by "/foo". Regards, Ken ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Fast NSArray compare
On 15 Apr 2014, at 10:02 am, Varun Chandramohan wrote: > Lets say I walkthrough 1000 files and folders, for each file/folder I need to > compare against this array list. This might be slow or inefficient. Is there > a faster way to do something like this? As a general principle, if you have to check whether one of a list of things is part of another list of things, an array is the wrong container for the job, because it amounts to a worst-case O(n^2) search. Instead, use a set or hash table for the set of things that must be detected among the first list, and it reduces to a worst-case O(n) operation. That said, if the number of items in the second list is small, the performance may be acceptable, and using a hash table might not speed it up noticeably - the time will be dominated by the iteration through the larger list. --Graham ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Fast NSArray compare
Hi All, I have a question about efficiency when trying to compare NSURL. The requirement is quite simple. I try and iterate through a directory to all subdirectories and files. While doing this walk-through, I need to check against an array of NSURLs which are restricted files and folders. This means if I find a match of file I am trying to access in the array then I don't do any operations on that file and continue. Lets say I walkthrough 1000 files and folders, for each file/folder I need to compare against this array list. This might be slow or inefficient. Is there a faster way to do something like this? Secondly, I plan to store array of NSURL for restricted files and folders. What is the best way to get partial compare? Eg: Entry in array : /XYZ/abc This means I should not iterate into the abc folder. So any files /XYZ/abc/1.c or /XYZ/abc/def/2.c should all be skipped. Whats the best way to do partial NSURL compare? Or is it better I store it as NSString instead of NSURL? Regards, Varun ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: https://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
