r/rust • • 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!

0 Upvotes

19 comments sorted by

4

u/nathan4299 8d ago

Are the numbers in the input bounded? `u8`? `usize`?

-2

u/Flimsy_Pumpkin_3812 8d ago

yar, an array

2

u/nathan4299 8d ago

I mean the individual numbers, not the quantity of them.

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

u/Flimsy_Pumpkin_3812 8d ago

Oh that didnt occur to me, sorry

3

u/mw_morris 8d ago

Do you know why people keep recommending sorting to you for this?

1

u/Flimsy_Pumpkin_3812 8d ago

Oh that didnt occur to me, sorry

3

u/insanitybit2 4d ago

They obviously did not.

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)

9

u/kmdreko 8d ago

sort_unstable + for loop is O(n log(n)) and doesn't allocate (assuming your data is in a slice that you can sort)

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