New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Ranges with Infs on endpoints could be smarter ((0..Inf)[99999999999]) #5935
Comments
From @AlexDanielConsider this code: Result: In other words, we can calculate the value without turning the Range into a list. However: Code: Result: This can be easily solved. However, the question is what should be done with other cases (e.g. (-Inf..0)[*-5] and similar) |
From @smls`Range` does `Positional`: ➜ say Range.^roles' `Positional` is the "Role for objects which support indexing them using postcircumfix:«[ ]»" (https://docs.perl6.org/type/Positional.html). This suggests that `Range` should implement the `[ ]` subscript natively so that it can complete in O(1), rather than falling back to `.list.[ ]` which makes it O(n). So maybe this is more of a performance bug/oversight than an RFC?
I think all cases should give the same result that they do now. |
The RT System itself - Status changed from 'new' to 'open' |
From @zoffixznetOn Thu, 29 Dec 2016 13:49:40 -0800, smls75@gmail.com wrote:
It's a bit more involved than that due to floating point math and its host of issues creeping up in many of the cases. The fast range observed by OP is an Int range that doesn't suffer from those. For the rest of the range types, the current complexity for many cases is not 0(n), but 0(Inf), because it just infiniloops trying to get a .succ of an element, but precision isn't available for such a fine grain. For example, .elems on range (2e89..2e100) would return Inf if it could ever complete and all elements in that range are 2e89, never reaching the end point, because there's no precision available to store +1 increment. I created a branch to play around with this ticket, but I'm already hitting issues just trying to make .elems figure out the result fast. How many elements are in ranges (2e0..2e100), (2e20..2e100), (2e40..2e100), (2e60..2e100), (2e75..2e100), and (2e85..2e100)? The answer for all of them is 2e+100 elements because of lack of precision bits. How many elements there are in range 2.000_000_000_000_001e20..2.000_000_000_000_002e20? If we do the math in our heads, we get 100_000 elements, but thanks to floating point math precision, the actual answer is ONE element, and it's 2e+20. Note that this element is LOWER than the lowest end point of the range we used. Another example is (^2e20)[*-1]. The last element is 2e20, but the end point is excluded, so what do we return?; considering (2e20-1) is still 2e20. And it'd continue to give that number as value for the next 500000 elements or so (counting from end), until it'd switch to giving 1.99999999999999e+20 as the element for another half a million elements. And most of that range is in these chunks. So is a weird, chunked, unpredictable, and at-times absolutely wrong result better than correct but slow range, that at large enough values can be made to be non-increasing, infinite, and one that hangs when you attempt to fully reify it? I think Rats can be improved, so I'll still hack around on this ticket in that scope, but I'm not so sure the Num ranges should be changed. |
From 1parrota@gmail.com
"I'm sorry, Dave, I can't do that". In some cases, a refusal to |
Migrated from rt.perl.org#130437 (status was 'open')
Searchable as RT130437$
The text was updated successfully, but these errors were encountered: