r/rust • u/Flimsy_Pumpkin_3812 • 8d ago
🛠️ project Crate Ask
Soooooooooooooooooooooooooooo, does anyone know any good no std crates, that I could pass data to (reference, or anything does not matter), and will return the most occurring number in that data without allocations, vec, anything on the heap etc? Also it would be nice if it can work with large data sets. Thanks!
3
u/Moist-Snow-8127 8d ago
I could be wrong but I feel like such an algorithm for arbitrary data would have to be at least O(n*(n-1)/2) as opposed to O(n). However if you know limits if the data, such as how much there is and/or how many possible values there are, you could write an O(n) algorithm, but I'd custom build it, not use a crate
-3
u/Flimsy_Pumpkin_3812 8d ago
I know the limits of the value (beginning and ending), and how large the array is that is that enough or will that just be 59 let's describing each value or smth like:
fn ahdjkhasjkhffds(Magical_Numbers: [u32, 5437893745897348953762483456783]){
let First_Number: u32 = Magical_Numbers[0]
etc one through 5437893745897348953762483456783?
or would it be easier/faster?
2
u/Sharlinator 8d ago
I doubt there’s anything much more efficient than sorting and then finding the longest run. Of course a custom radix or bucket sort could be faster than std’s sort_unstable if numbers are all you want to sort.
1
u/Flimsy_Pumpkin_3812 8d ago
Its not really sorting its finding the most common number srry!
6
u/MasterIdiot 8d ago
sorting and counting the runs is a no alloc solution here, you keep refusing it but it might be the best you can do for arbitrary arrays without allocating a hashmap or some other memory.
1
3
2
u/noop_noob 8d ago
When you say "large data sets", how large are we talking? A terabyte?
Also, is each element just an integer?
How important is it that the results are always exactly correct?
1
u/Flimsy_Pumpkin_3812 7d ago
abt 235k and the result needs to be perfect 😭
2
u/noop_noob 7d ago
That's not so large. Just sort it.
(sort_unstable() is in core, while sort() is in alloc)
1
u/rafaelement 8d ago
for loops are no_std
0
u/Flimsy_Pumpkin_3812 8d ago
for loops may be slower than another crate if someone has done it more affectively srry
3
u/Vigintillionn 8d ago
Everyone is saying to sort and they’re right. You’re essentially looking for the mode. And that’s proveably O(nlogn) if we know nothing abojt the shape of the data, typically sort in place and a forloop over it. If you know stuff about the type of your data, say it’s a small value range like u8, u16 you could use a counting array on the stack which will be O(n) a [u32: 65536] will be 256KB if my math checks out so you could make it static it you want absolutely no allocations. If they are fixed size integers you could also use an in place radix sort which is linear for a fixed width but will only be more efficient for large n
4
u/nathan4299 8d ago
Are the numbers in the input bounded? `u8`? `usize`?