-
-
Notifications
You must be signed in to change notification settings - Fork 1.6k
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
Adds digits method to the Int type #5598
Conversation
Hey @FrankKair, thanks for participating in making Crystal better! Besides the general question, the implementation using |
Personally, I've used Aside from performance issues, there are some differences with Ruby's
|
(First of all, thank you for the comments!) Hey @straight-shoota, thanks for pointing that out, I probably should've been a little more specific and explain why I think it's a nice addition to the standard library. So, as @woodruffw just said, it's interesting for checksum, digits manipulation and some algorithms (and exercises/coding challenges, why not). I thought it was so nice when Ruby implemented this method that I wanted Crystal to have it too. Otherwise, people would have to type And, as you just said, this is rather inefficient. So maybe that's a good thing, instead of letting people write inefficient code (as I just did), we could provide them a clean, performant API to work with. |
I was trying to think of a better idea for this method and I've come across this Haskell implementation: digs :: Integral x => x -> [x]
digs 0 = []
digs x = digs (x `div` 10) ++ [x `mod` 10] And I also saw the Elixir implementation: def digits(integer, base \\ 10)
when is_integer(integer) and is_integer(base) and base >= 2 do
do_digits(integer, base, [])
end
defp do_digits(integer, base, acc) when abs(integer) < base, do: [integer | acc]
defp do_digits(integer, base, acc),
do: do_digits(div(integer, base), base, [rem(integer, base) | acc]) This kind of approach would be more efficient, I suppose. @woodruffw I also think that the normal order makes more sense, because it's what most people expect. |
What about this? def digits
quotient = self.abs / 10
remainder = self.abs % 10
if quotient == 0
return [remainder]
end
digits(quotient) << remainder
end I'm using CPU wise, I tested the method with |
That implementation looks like a solid improvement to me. You might want to compare it to an iterative version, though -- my suspicion is that LLVM can optimize a |
Hello! Thank you for your interest and contribution to Crystal!. If the reason to bring this to Crystal is because Ruby has it, then the implementation needs to be as close as possible to the original implementation. This means that Also, as pointed out:
Doing a quick benchmark: require "benchmark"
struct Int
def digits
self.to_s.gsub('-', "").each_char.map(&.to_i).to_a
end
end
Benchmark.ips do |x|
x.report "123.digits (PR)" { 123.digits }
x.report "-123.digits (PR)" { -123.digits }
end Results in the following:
163 bytes allocated per operation. Worse case scenario, dealing with negative values, results in 289 bytes. There are other differences:
A possible alternate implementation might look like this: struct Int
def alt_digits(base = 10)
arr = [] of typeof(self)
num = self
while num != 0
arr << num.remainder(base).abs
num = num.tdiv(base)
end
arr
end
end Which shows the following on the benchmarks:
Faster iterations and less allocations. However, the naive implementation shown above doesn't deal with negative numbers, so that requires to be addressed if the objective is provide an implementation that is similar to Ruby (and if that is desired). Cheers. |
Hi, @luislavena, thank you for the in-depth feedback! I do believe that Having said that, I think that the method should return the numbers in order, because it's more natural. It's not intuitive to ask for digits and receive them from lsd to msd. At least for me 😅 The first implementation with Here is my benchmark: require "benchmark"
Benchmark.ips do |x|
x.report "digits_1" { 12312312312312312312.digits_1 }
x.report "digits_2" { 12312312312312312312.digits_2 }
x.report "digits_3" { 12312312312312312312.digits_3 }
end
struct Int
def digits_1
self.abs.to_s.each_char.map(&.to_i).to_a
end
def digits_2
quotient = self.abs.tdiv(10)
remainder = self.abs.remainder(10)
if quotient == 0
return [remainder]
end
quotient.digits_2 << remainder
end
def digits_3(base = 10)
arr = [] of typeof(self)
num = self
while num != 0
arr << num.remainder(base).abs
num = num.tdiv(base)
end
arr
end
end
At least for me, I do prefer to return the digits in order, so I tried adding
That way, the numbers changed a bit. What do you guys think should be the proper behaviour and which implementation should remain? |
How is this useful for checksums and check-digits? Besides, if those two (pretty rare) usecases are the only usecases is it worth having in the stdlib? I can't say i've ever wanted a method like this. |
It's pretty useful, at least in my experience. One of the common check-digit strategies is "perform function f on every kth digit and function g on every other digit, sum the results, and compare to the last digit," and a Of course, like you said, that's not a common use case. It's also (now that I think about it) a bit of an abuse of the On an unrelated note, if this gets added, I'm in agreement with @FrankKair that MSD order is preferable (and thereby break with Ruby's behavior in that aspect). |
All of the use cases you mention don't need to allocate memory. Just keep diving by ten and you get the digits. If no one can provide a real (as in "here's a real project I used it in") I don't think this should be go in the std. |
At the end of the day, you're still allocating an array for this method which makes calculating a checksum suboptimal. Perhaps it'd be better to put these checksum calculations inside the shards that require them. If we accept this though, it should accept a base. |
I refactored the code to this, following @RX14's idea of accepting a base: def digits(base = 10)
quotient = self.abs.tdiv(base)
remainder = self.abs.remainder(base)
if quotient == 0
return [remainder]
end
quotient.digits << remainder
end This is my first PR in a programming language, and even if it doesn't get added to the std lib, I'm quite grateful and I've learned a lot. It was very nice interacting with much more knowledgeable people, receiving feedback and discussing aspects that I didn't even consider in the first place. Well, I still think it's nice and useful (and of course it would be awesome to contribute to the project!), but ultimately this is up to you all. Cheers! 💎 |
Actually calling def digits_3(base = 10)
arr = [] of typeof(self)
num = self
while num != 0
arr << num.remainder(base).abs
num = num.tdiv(base)
end
arr.reverse!
arr
end This leads to:
I can go one step further by pre-allocating the array capacity to the right size before everything to avoid dynamic resizing: def digits_4(base = 10)
arr = Array(typeof(self)).new(Math.log10(self).ceil.to_i)
num = self
while num != 0
arr << num.remainder(base).abs
num = num.tdiv(base)
end
arr.reverse!
arr
end Benchmark:
About the topic of whether or not it should be accepted into the standard library, I also question where should method could be useful outside some code golf scenario. And if it is indeed useful, its probably better to have an |
@FrankKair If you like to proceed contributing to the language, you might take a look at issues suited for newcomers. |
Think that way, code golfing such as Project Euler is nice to provide comparison and benchmarks between languages. That was my first contact with Crystal, because I wanted to see how faster it could be than the other languages I used so far (such as Ruby, Python, Swift, Elixir...). I have a friend who also had his first contact with the language by trying to test its raw power. I may be wrong, but I don't think most people start experimenting with a language trying to build web frameworks or complicated CLIs, but rather trying to compare its features with other languages previously used. So I still think it's a good thing to have a nice performant digits method on the std lib, such as this one because then people wouldn't have the bad idea I had in the beginning of this pull request (using On the Elixir digits pull request, the author of the PR said: "While this is a pretty basic function, the way that 9/10 programmers tend to implement it is very inefficient and error prone, and it is in common usage. Thus, I would suggest that having a proper and efficient implementation in the standard lib is desirable." And then someone else said: "I like this! Having used the (non-standard) Haskell library Data.Digits for different tasks both yesterday and today, I can really see the benefit." Not only that, but some languages implemented this method in a questionable way, such as Ruby. The So yeah, I still think it's a nice addition to the std lib. |
I guess we can add this, it does no harm. It needs to be documented, and digits should probably always be an Int32 array. Plus we need to think about what to do with negative numbers. |
Why not
From my understanding |
@asterite The method is always returning "From my understanding -123 is still composed of the same digits as 123" |
Digits only go from 0 to 9. Int32 is the most common int type. Digits are unrelated to the number. At least that's my thinking. For example, multiply all digits then multiply by some other number, with Int8 chance of overflow. But maybe returning the same type is ok. I wish we had a universal integer number type, it's so messy with so many integer types. |
@FrankKair LGTM |
I still don't see much use in this method, if two other people want to approve it go ahead but I won't. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Not a member, but I'm 👍 on adding a digits
method 😄
Edit: Reiterating my desire for this in 2019.
Two approvals, that's nice! 😊
This pull request is open for over a year now, so I deleted my repo, thinking that it wouldn't go anywhere. Will GitHub be able to merge it or should I fork the repo again? 😅 |
It's only one approval from a core member, and as far as I see it, most others are rather skeptical of this. I don't see this as a useful addition and thus won't approve it. In any case, this needs a rebase to be merged. It might work if you simply restore your fork and the branch. |
Closing this in favour of #8554 Thank you anyways, @FrankKair ❤️ |
Thank you very much @straight-shoota, feeling like a visionary now 😅 |
Hi, this is my first pull request for a programming language.
I implemented the
digits
method for theInt
type, like Ruby did in its 2.4 release.