For example, in Java, we have code like this
Int n = 1234567
for (int i = 2; i * i < n; i++) { do something }
The purpose of i*i here is to avoid sqrt(), which seems a costy call
and in Swift, we can write like
for i in 2...n where i * i < n { }
I want to ask, does Swift compiler optimize this for loop pattern, if it first finds i * i >= n, Swift will abandon the rest of the iterations? So the total iteration count is much smaller than 2...n
They're not equivalent. The Java code is much closer to:
for i in 2... {
guard i*i < n else {
break
}
// do stuff
}
while the Swift code is much closer to:
for (int i = 2; i < n; i++) {
if (i * i < n) continue;
// do stuff
}
Well, I don't know exactly if the compiler can do what you're asking. The compiler is much smarter than me already. I just want to point out that the two codes are much more different semantically.
haha, then maybe someone could help answering. Yes I know the difference, that's why I want to know if Swift has additional process to handle such cases
The compiler doesn’t know if the where clause’s predicate will be true for elements at the start, the middle, the end, or some interweaved pattern (w.g. Evens and odds). It’s not smart enough to know which sections of the collection are safe to skip over,
What you’re looking for here is a prefix, and hey, and the standard library has a method just for this!
for i in (2...n).prefix(while: { $0 * $0 < n }) { ... }
Of course, this just for illustration, typically you would just make the upper bound of your range be sqrt(n)
I do doubt it, it requires proof that i^2 is monotonic, which is hard to come by for generic optimization.
If you want to break upon first encounter, it'd be easier to tell the compiler, rather than just hope that it can figure it out.
Thanks @AlexanderM !
The context is I'm in a "performance matter" hackthon-like event,
The reason is it is said sqrt() call is kind of costy comaring to using i * i as a condition.
the problem using "prefix" is it is O(n) operation, which I'm kind of unwilling to use.
what @Lantua mentioned above looks like I should go with, but anyway, thanks for pointing out
prefix should be O(k) where k is the output side for most collections (excluding Lazy collection family), which is the same for traversing k elements. It is fine to use on 2....
In fact, Swift compiler is quite aggressive on combining Collection APIs, so you'll likely get the optimal or near optimal code (You should still benchmark it though it that's what matter).
Note that this is different from your where case. Since the semantic of where is to loop until the end, while prefix bails out, even in an unoptimized code.
got you, thank you!
actually,
this is the doc I have for ClosedRange:
Returns a subsequence containing the initial elements until predicate returns false and skipping the remaining elements.
func prefix(while predicate: (Bound) throws -> Bool) rethrows -> Slice<ClosedRange<Bound>>
Available when Bound conforms to Strideable and Bound.Stride conforms to SignedInteger .
predicate
A closure that takes an element of the sequence as its argument and returns true if the element should be included or false if it should be excluded. Once the predicate returns false it will not be called again.
Complexity: O( n ), where n is the length of the collection.
@Lantua what you said is O(k) is perhaps
func prefix(_ maxLength: Int) -> Slice<ClosedRange<Bound>>
Whether we hit the ceiling O(n) depends on the usage too. Since we know we're using i * i < n and not arbitrary predicate, the prefix will just loop through the indices sqrt(n) times.
Swift does still have a while statement, if you want to guarantee minimum overhead.
Of course it’s O(n). The prefix can either be empty, or the full collection, or some middle ground. The condition check in the Java example is also O(n), you just don’t recognize it as such because it’s sneakily embedded in a loop, and not a named construct like a method.
Are you sure about this? The square root could be computed just once, whereas the square of the current index would need to be computed on each iteration.