I'm looking for ways to have str representations of ranges of integers without allocating. My current best attempt is to manually match on each value:
match i
{
0 => "0",
1 => "1",
2 => "2",
...
n => "n"
}
which works, but has the obvious problem of not scaling. I've tried to automate this with macros, but i couldn't get it to work with declarative macros and procedural macros seemed too involved for me.
If you think about this for a second, doing this for u32 requires you to have ~4 billion statically allocated strings up to 10 bytes in length. Arguably you could overlap and share prefixes, but that is only likely to save you around 10%, so you're looking down the barrel of 40 GB here.
Obviously that's not tenable.
Instead if by "not allocating" you simply mean "not requiring a heap allocation" you could instead write into a buffer/small string type that can hold up to 10 bytes and be dereferenced to &str, but even that's pretty pointless since what you nearly certainly want to do with this string is print or otherwise format it, and that's directly supported by the integer itself using Display.
You don't have to write that yourself:
I don't need the entire value space. Currently, I only need from 0 to around 4000, which, if my math is correct, should only require about 15k.
Don't use macros, write a const function that computes the array and store it in a static variable.
Nonetheless, format_into() gives you the whole range without using any additional memory. Its only problem is it's not const yet. Is it really important for you for some reason to have the numerals hard-coded in the executable as static strings?
if the static storage is not a problem for your use case, you can just generate the lookup table in a build script.
I had preferred statics because I'm also doing a fair amount of cross-thread communication and I didn't want the additional lifetime considerations or dealing with Arcs
why you send the string representations cross threads? why not just send the integer values and format the number in each thread?
I wonder if you really need all these strings, or could simply have
const DIGITS: &str = "0123456789";
and cherry-pick substrings from it, but it depends on your needs.
I mean
use std::io::{Write, stdout};
const DIGITS: &str = "0123456789";
fn main() {
let mut num = 1234;
let mut divisor = 1u32;
while num / divisor >= 10 {
divisor *= 10;
}
while divisor > 0 {
let i = (num / divisor) as usize;
let c = &DIGITS[i..i + 1];
stdout().lock().write(c.as_bytes()).unwrap();
num %= divisor;
divisor /= 10;
}
}
``You've just reinvented Display (though locking per character, which is odd)
I used stdout just to illustrate the idea:) My point was to store a small static string of all possible digits, and cherry-pick them.
You don't need to store a precomputed string of all possible digits to be able to trivially turn a number 0..=9 into a digit. b'0' + x (or b'0' | x) will do it.
Even better, thsnks!. So, the question is why does topic starter need 4K strings?
PS: or it also could be..
let start = '0' as u8;
let i = (num / divisor) as u8;
let c = (start + i) as char;
Because they do not want an owned buffer but a &'static str.
If you want a buffer, you can use Display or recently format_into() like said above.
(Not a serious suggestion.)
The repeating pattern of the decimal representation of 1/10_000_000_019 contains every zero-padded ten-digit number at least once, so you "only" need ~10G (at the cost of non-constant lookup).
Or for (all) four-digit numbers, analogously store 1/10_007's pattern in ~10K.[1]
Edit: made an unsafe free version âŠī¸
Every so often I am told about some maths fact that I can only assume someone went to prison for discovering
on my guts, the denominator is 10^n + prime so I don't think that much brute force was involved
Yeah there's going to be some pigeon hole principle or something. It's just that it's one of the specific types of maths that my brain fits into a "wanting to know this is a sign of a diseased mind" bucket for some reason. It's like an Ignobel prize but for the Fields medal.
Isn't this the problem of superpermutations, which has a lower bound of n! + (n-1)! + (n-2)! + n-3 as proven by the famous 4chan post (/sci/ - Science & Math - #3751105)? In the case of n=10, the lower bound should be around 4 million. I don't know how to find the index into this array tho.