But I'm trying to implement a "python sudoku resolver" in different languages, to compare "run times" only. (to resolve 100 easy sudoku grids)
I've made some good version for mojo, C, java, nodejs, nim .. and got great results
I used chatgpt 3.5 to convert the java version to rust .... (the c version was created in the same manner)
it worked OOTB ... but the result seems very very slow ...
Is there any rust expert which could help me to find what is wrong ?!
all codes are here (see makefile to run tests)
It can't be slower than py3 or java ... no ?!
Perhaps GPT doesn't reach to do the better optim ?!
The Rust version is doing a lot of linear scans like g.chars().skip(y * 9).take(9).collect(). These are necessary because of how &str and String work in Rust, but those datatypes are really unsuited for this application. &[u8] and Vec<u8> would at least let you direct-index, even if not necessarily the most idiomatic solution.
Yeah. On the one hand, it's impressive it translated the code at all. On the other hand, it clearly has no idea what it's doing.
Plus, all those compound iterators being glued together, then collected into a new allocation, only to be pulled back apart... probably much less of an issue than the repeated linear scans, but still unpleasant.
--release is a cargo flag. Most people will assume your code is part of a Cargo project.
Yeah. On the one hand, it's impressive it translated the code at all.
yes ! bard never reach to make a working solution ootb.... but gpt3.5 is magic !
Plus, all those compound iterators being glued together, then collected into a new allocation, only to be pulled back apart... probably much less of an issue than the repeated linear scans, but still unpleasant.
Yes, but it's the same constraints for all the implementations ...
But the rust version is very slow ;-(
Of course, with Vec<u8> & co ... it could be a lot faster ! ( like this mojo version, which uses vectors, is incredibly fast ... compared to barebone/C version).
I spent a little bit of time and wrote a more idiomatic Rust implementation of your algorithm. No idea how it compares to the others, and I haven't checked its output for correctness beyond seeing that the first example leaves no empty values.
In C a string is just a sequence of null-terminated bytes and you just treat it as such, which is fine because you know it will just store ascii characters.
In Javascript instead a string stores a UTF-16 encoded string and you treat it as a collection of 16 bit code units. But Javascript also has byte arrays, so why didn't you use them if you used a byte array in C?
In Rust a string is stored as UTF-8, and .chars() gives you an iterator over Unicode code points. This makes sense if you're working for text, where it usually makes no sense getting the nth character (also, what do you consider as a character? There are probably more possible answers than you might think). Again, you could just treat the string as a sequence of bytes (which they are, you can use .as_bytes() if you want) like you did in C.
In the end there's no such thing as "same constraints". Every language has been written with different expectations for what the user will do, and will be optimized accordingly. So yes, Rust is slow if you use it in a way that it wasn't designed for. You can still make it fast by doing those optimizations yourself, but here you're explicitly restricting yourself to not do them. Other languages will do some optimizations automatically, at the expense of other optimizations, usecases or sometimes correctness, but this is not reflected in your example.
IMO it would be more reasonable to replicate the same algorithm, but in a way that's more idiomatic for each language.
By choosing the most constrained digit each iteration, the runtime drops to 18ms total for the first hundred test samples. That's a major algorithmic change, though, so it's probably not a fair comparison with the others.
finally I've take your first version, as reference.
(on my computer, it takes 16s for the 100 first grids!)
I will study your optimized version ... and will probaly adapt your constraint (choosing the most constrained digit each iteration) to all other versions ... (but need to adapt the py one first)
And run it with the 1000 first grids !
Thanks a lot for ur work !!!
Your optimized version takes 280ms on my computer for the 1st 100 ... it's amazing !
this constraint is a game changer !
