Should using a property, regardless of whether it is stored or computed, indicate O(1) access? If not, why?
- Propose it
- Don’t propose it
Thank you for your insight.
Should using a property, regardless of whether it is stored or computed, indicate O(1) access? If not, why?
Thank you for your insight.
14 Comments
Our guidelines are something like: A property is just that which does not require input, to be known. It is also not a verb; a function which takes no parameters must be a verb, unless it cannot be due to the current lack of generic computed properties.
It’s the job of an IDE to denote algorithmic complexity; it’s probably best displayed via an overlay that is triggered with a trackpad gesture. Tying algorithmic complexity into whether something takes parameters is the wrong way to go about things; it’s a poor attempt to convey meaning.
C0deH4cker writes: “I’d say it can be more only if it’s memoized so subsequent lookups are O(1) (and maybe O(log n) is okay too)”
http://twitter.com/C0deH4cker/status/693625832082907136
Properties should not have special requirements like that, it is premature optimization that will cause all sorts of horrible cashing, and more than a few race conditions. The team instead should learn how to profile code and fix the properties which are expensive with site specific memorization
No. Big O notation only counts the units of work. It doesn’t relay any information about the nature of that unit of work. A property that sleeps for a month and then returns the literal 5 is still order 1.
No. IMO, the name matters more than whether or not there is a set of empty parenthesis after the word. Here’s the most extreme example I can think of on the spur of the moment: a “factor” property that would return the factors of a number. It could be very expensive for the product of two large primes.
I agree with Jessy, here, and I think the real argument can be seen by considering the lazy modifier on stored properties. Since a lazy stored property isn’t created until needed, an initial access will incur whatever cost has been deferred. This rule would require that any property with a larger than O(1) creation complexity would have to be pre-calculated and stored, because without repeated retrievals per-instance, the cost payed would always be the unamortized. Amortization ceases to be compelling when you consider memoization, since degenerate access patterns (access, invalidate, access, invalidate, access…) would repeatedly incur the unamortized cost – exactly the same failure mode as the single-access case.
These may seem pedantic, but they are serious flaws when you want to enable a mental shorthand for algorithmic complexity which doesn’t take into account actual usage. Consider, too, the implications for protocol conformance. Since objects could be protocol-typed, individual annotation is not guaranteed to be available to programmers, so while a rule of this sort could improve some predictability, it’d be at the cost of protocol flexibility – and so, I’d expect protocols to switch entirely to function interfaces expecting protocol behaviors. This would be the loss of the attribute/action distinction.
My opinion: regardless of whether the property’s operation is complex or not, linear or logarithmic, any SPECIAL, unexpected behaviour should be clearly marked, both as part of the property’s name, and documentation. Too many developers seem scared of verbose naming or commentary, because it’s uncool or because their second-year lecturer or random Stack Overflow contributor told them (erroneously) that the fewer comments, the better.
The most important thing is that the property name and description convey USEFUL INFORMATION to the user, in a way that reduces mental work.
Thus it’s not that important to me that a property implies O(1) complexity. After all, for some times of objects (e.g. a JSON parser), it may well be that I fully expect the job to be complex and time consuming.
No. O-notation is only useful for comparsions, it doesn’t tell you if something is fast. For persistent objects, property access may incur network or disk activity, which is slow. I prefer caching to be explicit, so if I see a property I don’t assume I can reasonably read it in a loop. Which may be what you’re really asking.
I don’t see a value of constraining of how properties can be used. With constant time you couldn’t even look up a value in the dictionary, which could be a pretty normal use case for a computed property.
No. It’s pay me now our pay me later. If there was a requirement like that, the work would get done at some other time, regardless of whether the property might ever be evaluated. The beauty of swift’s properties is you can have the concise style and doing whatever work only when needed. Hopefully efficiently – same as if you were calling a method named getSomething.
My opinion: regardless of whether it is a property or function, if it’s stored or computed, some type of official support for big O notation would be nice. This might even allow for some automatic complexity inference (a stored property is always O(1), a function that calls something O(n) is not…)
I don’t think it should be mandatory in any way (otherwise we damage the language’s accessibility.)
No. A sum of an integer list could be implemented O(n) or O(1). Either implementation could be a better one for different uses. The interface should not be different depending on implementation! This is what documentation is for.
Unless the compiler can guarantee O(1) time for properties (I doubt it can), then we must always assume slower access. Use a struct if you want O(1) access time.
Is the poll closed? I voted, but it didn’t increment the vote count.