Re: iPhone: validate a NSString for US zipcode
Paul Bruneau mailto:paul_brun...@special-lite.com wrote (Thursday, January 7, 2010 11:00 AM -0500): To help make this thread more Cocoa-y, I would like to ask: Do the NSSet and NSArray methods like -containsObject perform in a fashion comparable to a home-rolled binary search? I greatly prefer to use the Cocoa stuff rather than try to remember/learn how to properly code such things. NSSet (and NSDictionary) use hash tables to organize and look up their objects/keys. Look up and insertion times are nearly linear--assuming a well distributed hash function--regardless of collection size. NSArray does not impose an order on its contents. While arrays can be sorted--and as others have pointed out, there are binary search functions in Core Foundation--NSArray never assumes that its contents are ordered and searches are always preformed using a sequential, brute force, comparison of objects. It's easy to demonstrate all of this by setting a breakpoint in the -hash and -isEqual: methods of the objects added to a collection. For ZIP code membership, an NSIndexSet makes a lot more sense. -- James Bucanek ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
I'm a little unclear what you are asking, but I'll tell what I know. You just want to know if a 5 digit zip code is a valid one? Or do you want to compare it to the list of valid city names that are assigned to it? (yes it can be more than one, ugh) They are (from a non-USPS point of view) arbitrarily assigned by the post office and there are currently 42,305 or so assigned (out of a theoretical maximum of 100,000 of course) So assuming you just want to know if it's a valid zip (and don't care about if they got the city right), the only way to validate it solely from within your app as a valid zip code would be to have a list of them in your app. You could load them from a plist or straight text I guess into an NSArray or NSSet and then check to see if the zip is valid as needed. You can get the list from a third party service like http://www.zipcodeworld.com/ or maybe from some free source. The value of this might be questionable, since a zip code with a typo still has roughly a 50% chance of being a valid one. Plus the USPS is always adding new ones, so will you risk telling your user that his zip code doesn't exist when he is standing in it? So I guess the answer is there is no Cocoa technology that can help with this--unless you are asking something completely different, in which case let's all have a good chuckle at my poor comprehension skills :) On Jan 7, 2010, at 11:11 AM, Eric E. Dolecki wrote: I've been googling but haven't seen yet how to best validate a 5-digit zipcode for use in the US (without using a webservice). I have the NSString, I just need to validate it. I know zero RegExp, is there a formatter I can use? ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
I don't care about the city, just that the zip code will work. On an iPhone testing against an array of 42,305 values... could that be pretty quick? Seems like a large set to go through looking. I'm sending the value to a webservice to return weather data. On Thu, Jan 7, 2010 at 11:45 AM, Paul Bruneau paul_brun...@special-lite.com wrote: I'm a little unclear what you are asking, but I'll tell what I know. You just want to know if a 5 digit zip code is a valid one? Or do you want to compare it to the list of valid city names that are assigned to it? (yes it can be more than one, ugh) They are (from a non-USPS point of view) arbitrarily assigned by the post office and there are currently 42,305 or so assigned (out of a theoretical maximum of 100,000 of course) So assuming you just want to know if it's a valid zip (and don't care about if they got the city right), the only way to validate it solely from within your app as a valid zip code would be to have a list of them in your app. You could load them from a plist or straight text I guess into an NSArray or NSSet and then check to see if the zip is valid as needed. You can get the list from a third party service like http://www.zipcodeworld.com/ or maybe from some free source. The value of this might be questionable, since a zip code with a typo still has roughly a 50% chance of being a valid one. Plus the USPS is always adding new ones, so will you risk telling your user that his zip code doesn't exist when he is standing in it? So I guess the answer is there is no Cocoa technology that can help with this--unless you are asking something completely different, in which case let's all have a good chuckle at my poor comprehension skills :) On Jan 7, 2010, at 11:11 AM, Eric E. Dolecki wrote: I've been googling but haven't seen yet how to best validate a 5-digit zipcode for use in the US (without using a webservice). I have the NSString, I just need to validate it. I know zero RegExp, is there a formatter I can use? -- http://ericd.net Interactive design and development ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
Eric E. Dolecki wrote: I don't care about the city, just that the zip code will work. On an iPhone testing against an array of 42,305 values... could that be pretty quick? Seems like a large set to go through looking. I'm sending the value to a webservice to return weather data. Use an array of bits, not numeric values. Each bit position is numbered (indexed) by zip-code. The bit is 0 if its zip-code is invalid, 1 if valid. Time to validate any given zip-code is constant: a couple of shifts and ANDs. Total data size: 100,000 bits, which is 12.5 KB. -- GG ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
On Thu, Jan 7, 2010 at 11:53 AM, Eric E. Dolecki edole...@gmail.com wrote: I don't care about the city, just that the zip code will work. On an iPhone testing against an array of 42,305 values... could that be pretty quick? Seems like a large set to go through looking. I'm sending the value to a webservice to return weather data. Doesn't the service return an error if you give it an invalid zip code? You could simply check for that. Doing so would avoid having to do the check on the phone, and also having to update your app whenever zip codes change. sherm-- -- Cocoa programming in Perl: http://www.camelbones.org ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
On 7 Jan 2010, at 16:11, Eric E. Dolecki wrote: I've been googling but haven't seen yet how to best validate a 5-digit zipcode for use in the US (without using a webservice). I have the NSString, I just need to validate it. I know zero RegExp, is there a formatter I can use? It might be better *not* to try to validate it at all. That way you'll have zero work to do to make your application accept data for non-U.S. addresses, some of which (Canada and the United Kingdom being two good examples) use alphanumeric postal codes *with spaces*, or (in some European countries) a five-digit code with an optional alpha prefix indicating country. Also, if the webservice you are using doesn't support anything other than U.S. zip codes right now, it might gain support later on, so the appropriate place to do any validation is in that webservice. Just my 2 cents as a non-U.S. citizen... Kind regards, Alastair. -- http://alastairs-place.net ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
On Jan 7, 2010, at 8:53 AM, Eric E. Dolecki wrote: I don't care about the city, just that the zip code will work. On an iPhone testing against an array of 42,305 values... could that be pretty quick? Seems like a large set to go through looking. I'm sending the value to a webservice to return weather data. Given that you would likely want to do this test with a binary search I don't see any reason why it should be slow (effectively you can do the entire search with about 17*k compares). The bigger concern with validation would be in having the complete list of zip codes to validate against. It might make more sense to see if your weather service can fast fail on an invalid zip code, since they will likely maintain a valid zip code list, and if you do it yourself you would want to maintain the same one they do. -- David Duncan Apple DTS Animation and Printing ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
On Jan 7, 2010, at 9:53 AM, Eric E. Dolecki wrote: I don't care about the city, just that the zip code will work. On an iPhone testing against an array of 42,305 values... could that be pretty quick? Seems like a large set to go through looking. I'm sending the value to a webservice to return weather data. What do you mean, will work? That the weather service will accept it? Does the service respond that the zip code isn't usable, for whatever reason? Otherwise, searching 42k+ will be very quick if you put it into a sqllite database. But then you will have to maintain the database, continually update it, and possibly correct it. My 2¢ Keary Suska Esoteritech, Inc. Demystifying technology for your home or business ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
On Jan 7, 2010, at 8:53 AM, Eric E. Dolecki wrote: I don't care about the city, just that the zip code will work. On an iPhone testing against an array of 42,305 values... could that be pretty quick? Seems like a large set to go through looking. I'm sending the value to a webservice to return weather data. Time to read about Binary Search --- for a list that size you can find (or not) a match in just 16 comparisons . . . Cheers, . . . . . . . .Henry On Thu, Jan 7, 2010 at 11:45 AM, Paul Bruneau paul_brun...@special-lite.com wrote: I'm a little unclear what you are asking, but I'll tell what I know. You just want to know if a 5 digit zip code is a valid one? Or do you want to compare it to the list of valid city names that are assigned to it? (yes it can be more than one, ugh) They are (from a non-USPS point of view) arbitrarily assigned by the post office and there are currently 42,305 or so assigned (out of a theoretical maximum of 100,000 of course) So assuming you just want to know if it's a valid zip (and don't care about if they got the city right), the only way to validate it solely from within your app as a valid zip code would be to have a list of them in your app. You could load them from a plist or straight text I guess into an NSArray or NSSet and then check to see if the zip is valid as needed. You can get the list from a third party service like http://www.zipcodeworld.com/ or maybe from some free source. The value of this might be questionable, since a zip code with a typo still has roughly a 50% chance of being a valid one. Plus the USPS is always adding new ones, so will you risk telling your user that his zip code doesn't exist when he is standing in it? So I guess the answer is there is no Cocoa technology that can help with this--unless you are asking something completely different, in which case let's all have a good chuckle at my poor comprehension skills :) On Jan 7, 2010, at 11:11 AM, Eric E. Dolecki wrote: I've been googling but haven't seen yet how to best validate a 5-digit zipcode for use in the US (without using a webservice). I have the NSString, I just need to validate it. I know zero RegExp, is there a formatter I can use? = iPhone App Development and Developer Education . . . Visit www.nonatomic-retain.com Mac OSX Application Development, Plus a Great Deal More . . . Visit www.trilithon.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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
On Jan 7, 2010, at 12:29 PM, David Duncan wrote: Given that you would likely want to do this test with a binary search I don't see any reason why it should be slow (effectively you can do the entire search with about 17*k compares). To help make this thread more Cocoa-y, I would like to ask: Do the NSSet and NSArray methods like -containsObject perform in a fashion comparable to a home-rolled binary search? I greatly prefer to use the Cocoa stuff rather than try to remember/learn how to properly code such things. Plus, the theory of premature-optimazation-is-bad would say just use the Cocoa stuff and only if performance is proven to be a problem, then look at optimizing, wouldn't it? ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
The webservice reports a city not found error - to which I can default to a known zipcode instead. On Thu, Jan 7, 2010 at 12:32 PM, Henry McGilton (Boulevardier) appledevelo...@trilithon.com wrote: On Jan 7, 2010, at 8:53 AM, Eric E. Dolecki wrote: I don't care about the city, just that the zip code will work. On an iPhone testing against an array of 42,305 values... could that be pretty quick? Seems like a large set to go through looking. I'm sending the value to a webservice to return weather data. Time to read about Binary Search --- for a list that size you can find (or not) a match in just 16 comparisons . . . Cheers, . . . . . . . .Henry On Thu, Jan 7, 2010 at 11:45 AM, Paul Bruneau paul_brun...@special-lite.com wrote: I'm a little unclear what you are asking, but I'll tell what I know. You just want to know if a 5 digit zip code is a valid one? Or do you want to compare it to the list of valid city names that are assigned to it? (yes it can be more than one, ugh) They are (from a non-USPS point of view) arbitrarily assigned by the post office and there are currently 42,305 or so assigned (out of a theoretical maximum of 100,000 of course) So assuming you just want to know if it's a valid zip (and don't care about if they got the city right), the only way to validate it solely from within your app as a valid zip code would be to have a list of them in your app. You could load them from a plist or straight text I guess into an NSArray or NSSet and then check to see if the zip is valid as needed. You can get the list from a third party service like http://www.zipcodeworld.com/ or maybe from some free source. The value of this might be questionable, since a zip code with a typo still has roughly a 50% chance of being a valid one. Plus the USPS is always adding new ones, so will you risk telling your user that his zip code doesn't exist when he is standing in it? So I guess the answer is there is no Cocoa technology that can help with this--unless you are asking something completely different, in which case let's all have a good chuckle at my poor comprehension skills :) On Jan 7, 2010, at 11:11 AM, Eric E. Dolecki wrote: I've been googling but haven't seen yet how to best validate a 5-digit zipcode for use in the US (without using a webservice). I have the NSString, I just need to validate it. I know zero RegExp, is there a formatter I can use? = iPhone App Development and Developer Education . . . Visit www.nonatomic-retain.com Mac OSX Application Development, Plus a Great Deal More . . . Visit www.trilithon.com http://www.nonatomic-retain.com/ -- http://ericd.net Interactive design and development ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
As others have pointed out, letting the service do the validation takes the onus off of your app to keep itself up-to-date. If you get an error, though, I would let the user know that the zip code is invalid and give them an opportunity to fix it or choose a different one. The user shouldn't be bothered very often since running into an invalid zip code should only happen when it's being entered initially or if for some reason it later disappears. On Jan 7, 2010, at 10:07 AM, Eric E. Dolecki wrote: The webservice reports a city not found error - to which I can default to a known zipcode instead. On Thu, Jan 7, 2010 at 12:32 PM, Henry McGilton (Boulevardier) appledevelo...@trilithon.com wrote: On Jan 7, 2010, at 8:53 AM, Eric E. Dolecki wrote: I don't care about the city, just that the zip code will work. On an iPhone testing against an array of 42,305 values... could that be pretty quick? Seems like a large set to go through looking. I'm sending the value to a webservice to return weather data. Time to read about Binary Search --- for a list that size you can find (or not) a match in just 16 comparisons . . . Cheers, . . . . . . . .Henry On Thu, Jan 7, 2010 at 11:45 AM, paul_brun...@special-lite.com wrote: I'm a little unclear what you are asking, but I'll tell what I know. You just want to know if a 5 digit zip code is a valid one? Or do you want to compare it to the list of valid city names that are assigned to it? (yes it can be more than one, ugh) They are (from a non-USPS point of view) arbitrarily assigned by the post office and there are currently 42,305 or so assigned (out of a theoretical maximum of 100,000 of course) So assuming you just want to know if it's a valid zip (and don't care about if they got the city right), the only way to validate it solely from within your app as a valid zip code would be to have a list of them in your app. You could load them from a plist or straight text I guess into an NSArray or NSSet and then check to see if the zip is valid as needed. You can get the list from a third party service like http://www.zipcodeworld.com/ or maybe from some free source. The value of this might be questionable, since a zip code with a typo still has roughly a 50% chance of being a valid one. Plus the USPS is always adding new ones, so will you risk telling your user that his zip code doesn't exist when he is standing in it? So I guess the answer is there is no Cocoa technology that can help with this--unless you are asking something completely different, in which case let's all have a good chuckle at my poor comprehension skills :) On Jan 7, 2010, at 11:11 AM, Eric E. Dolecki wrote: I've been googling but haven't seen yet how to best validate a 5- digit zipcode for use in the US (without using a webservice). I have the NSString, I just need to validate it. I know zero RegExp, is there a formatter I can use? ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
As someone who lives in a zip code that was added in 2004, yet STILL shows up as invalid in countless databases, I can't stress this point enough. Do not maintain data yourself that someone else has a reason/motivation and the resources to maintain. Just send it to the service, and catch the fail. Really. Please. From: Keary Suska cocoa-...@esoteritech.com What do you mean, will work? That the weather service will accept it? Does the service respond that the zip code isn't usable, for whatever reason? Otherwise, searching 42k+ will be very quick if you put it into a sqllite database. But then you will have to maintain the database, continually update it, and possibly correct it. ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
I've been googling but haven't seen yet how to best validate a 5-digit zipcode for use in the US (without using a webservice). I have the NSString, I just need to validate it. I know zero RegExp, is there a formatter I can use? I actually ran into a similar issue with one of my programs (Weather Vane) early on when it only supported US zip codes. I decided to use a free SOAP service to validate the zip code since it removed that as a maintenance burden. You've received a lot replies with the same suggestion, but unfortunately I can't find that service anymore. Everything else out there seems fee based. Maybe someone out there can point you to a free service. Maybe this question was already asked in one of the earlier replies, but I'll ask anyway: What does your application do? Why do YOU need to validate the zip? I use accuweather for my forecasts. If my app sends an invalid zip code, the query fails; that's my validation. ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
On Jan 7, 2010, at 10:00 AM, Paul Bruneau wrote: To help make this thread more Cocoa-y, I would like to ask: Do the NSSet and NSArray methods like -containsObject perform in a fashion comparable to a home-rolled binary search? I greatly prefer to use the Cocoa stuff rather than try to remember/learn how to properly code such things. Since NSArray is unordered I would not expect its containsObject to do better than O(n). If NSSet is an ordered container, it should be able to do O(lg n). I don't believe we give any guarantees as to performance of these methods however, but a simple implementation of either data structure would likely give you these performance characteristics. Plus, the theory of premature-optimazation-is-bad would say just use the Cocoa stuff and only if performance is proven to be a problem, then look at optimizing, wouldn't it? The theory of premature optimization would say that implementing an NSArray clone is a waste of time when you have an NSArray implementation in hand and no evidence that your clone would grant a performance improvement. But premature optimization is not a reason to avoid improving an algorithm by using NSSet instead of NSArray when the algorithm is clearly designed to be implemented with a set. That said, there may be many other reasons not to do so, such as being able to show that such a change would cause worse performance problems elsewhere, or showing that such a change has a poor cost:benefit ratio. In terms of the original question, validating the ZIP code before submitting to the service could be a form of premature optimization. Since the service has to validate the ZIP code in order to do real work, unless you could prove that doing so was a performance win, you should not do it in the name of performance. But there may be other reasons to do so, although from some of the other responses to this thread, it would seem that there are just as many other reasons not to :). -- David Duncan Apple DTS Animation and Printing ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
I am using the Yahoo! weather service. If I send it a zipcode that doesn't resolve to a city location, it does return a chunk of error XML - so I am using that as my validation now. I put up an alert notifying that the supplied zipcode doesn't work so another can be tried. It's not as nice as supplying a city name and choosing from a list of matches, but it works well enough I guess. I thought about using another service to validate a zipcode before sending it - but since I get the error supplied to me I can skip that extra step. I appreciate all of the feedback I've gotten on this - it's been very helpful. On Thu, Jan 7, 2010 at 4:24 PM, Lorenzo Thurman lorenzo7...@gmail.comwrote: I've been googling but haven't seen yet how to best validate a 5-digit zipcode for use in the US (without using a webservice). I have the NSString, I just need to validate it. I know zero RegExp, is there a formatter I can use? I actually ran into a similar issue with one of my programs (Weather Vane) early on when it only supported US zip codes. I decided to use a free SOAP service to validate the zip code since it removed that as a maintenance burden. You've received a lot replies with the same suggestion, but unfortunately I can't find that service anymore. Everything else out there seems fee based. Maybe someone out there can point you to a free service. Maybe this question was already asked in one of the earlier replies, but I'll ask anyway: What does your application do? Why do YOU need to validate the zip? I use accuweather for my forecasts. If my app sends an invalid zip code, the query fails; that's my validation. -- http://ericd.net Interactive design and development ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
That's backwards. NSArray is ordered; NSSet is not. Dave On Jan 7, 2010, at 2:44 PM, David Duncan wrote: Since NSArray is unordered I would not expect its containsObject to do better than O(n). If NSSet is an ordered container, it should be able to do O(lg n). smime.p7s Description: S/MIME cryptographic signature ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
On 1/7/10 1:44 PM, David Duncan said: To help make this thread more Cocoa-y, I would like to ask: Do the NSSet and NSArray methods like -containsObject perform in a fashion comparable to a home-rolled binary search? I greatly prefer to use the Cocoa stuff rather than try to remember/learn how to properly code such things. Since NSArray is unordered I would not expect its containsObject to do better than O(n). If NSSet is an ordered container, it should be able to do O(lg n). I don't believe we give any guarantees as to performance of these methods however, but a simple implementation of either data structure would likely give you these performance characteristics. CFArray.h does discuss performance. And there exists a CFArrayBSearchValues(). -- Sean McBride, B. Eng s...@rogue-research.com Rogue Researchwww.rogue-research.com Mac Software Developer Montréal, Québec, Canada ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
Well, depends on what you mean by ordered. NSArray retains insertion order. NSSet does not. But NSSet may be sorting things on insertion (like you'd get with a binary tree structure), while NSArray cannot assume any particular order. So from the NSArray implementor's standpoint, the array is unordered. -BJ On Thu, Jan 7, 2010 at 2:52 PM, Dave DeLong davedel...@me.com wrote: That's backwards. NSArray is ordered; NSSet is not. Dave On Jan 7, 2010, at 2:44 PM, David Duncan wrote: Since NSArray is unordered I would not expect its containsObject to do better than O(n). If NSSet is an ordered container, it should be able to do O(lg n). ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/bjhomer%40gmail.com This email sent to bjho...@gmail.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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
I can say I meant it in the way that BJ describes. However, the Cocoa documentation does describe them in the way that Dave states, so consider my sense on this particular point reversed :). On Jan 7, 2010, at 2:17 PM, BJ Homer wrote: Well, depends on what you mean by ordered. NSArray retains insertion order. NSSet does not. But NSSet may be sorting things on insertion (like you'd get with a binary tree structure), while NSArray cannot assume any particular order. So from the NSArray implementor's standpoint, the array is unordered. On Thu, Jan 7, 2010 at 2:52 PM, Dave DeLong davedel...@me.com wrote: That's backwards. NSArray is ordered; NSSet is not. On Jan 7, 2010, at 2:44 PM, David Duncan wrote: Since NSArray is unordered I would not expect its containsObject to do better than O(n). If NSSet is an ordered container, it should be able to do O(lg n). -- David Duncan Apple DTS Animation and Printing ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: iPhone: validate a NSString for US zipcode
In my testing NSDictionary's objectForKey: is extremely fast, with NSSet's member: coming in second and everything else trailing waayyy back. I was using simple immutable keys and complex, mutable objects, which may have affected the results. YMMV. So if you make a dictionary where the ZIPs are keys, with whatever you want as the objects, then your validity search consists of objectForKey: followed by a nil check on the result. If you make the result useful (perhaps the city,state?), even better. I have used NSDictionaries with over a million keys and never saw a performance hit worth worrying about. (NOT TESTED ON iPHONE, HOWEVER) Note that if you use immutable NSStrings for your keys, and use the same string for the object and the key, only one instance of the key will be created, making the overhead of this seemingly wasteful strategy very small. (This is because although NSDictionary copies its keys, -copy on an immutable object is just a retain). To help make this thread more Cocoa-y, I would like to ask: Do the NSSet and NSArray methods like -containsObject perform in a fashion comparable to a home-rolled binary search? I greatly prefer to use the Cocoa stuff rather than try to remember/learn how to properly code such things. ___ 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: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com