[Stream] Is Rust the Future of Competitive Programming?

16 месяцев назад, # ^ |

tbh I think this is matter of habit more than anything. Of course you probably would be slower first month after switch, but benefits of having language that does not try to kill you on every corner outweights time spent to learn it

→ Ответить

16 месяцев назад, # ^ |

+16

I don't think writing lots of code fast is really important. It saves little time. I think problems of C++ eat much more time on average.

→ Ответить

16 месяцев назад, # ^ |

+31

Can you elaborate which problems do you mean? I definitely know a few aspects where Rust is better than C++, but I don't see how they are really applicable for CP, especially, having in mind that a huge part of even high-rated community prefers printf over debugger in all cases and text editors over IDEs.

Don't get me wrong, I like to upsolve problems on Rust, but on more important contests I still stick to C++, because with enough discipline you can write C++ code as you do it in Rust (i.e. always having either one mutable reference or any number of immutable, etc.), but when you need to do something tricky to make your life a little bit easier, you almost always can do that in C++ and in Rust it is often not as easy.

One of such things is that in C++ you can wrap any short, but complex piece of code into a lambda and then use it, but Rust has some obstacles on this path. For example, if you are writing some dp, you may want to write a lambda "please, make sure that this state is computed", but it is impossible in Rust, because it captures dp as mutable. Obviously, you can make a function and pass everything to it, but then it probably would not be short anymore (e.g. if you need to compute sum of products of values from three different dp's as in problem F from the last contest). I also have similar issues when I need to compute a lot of simple things in dfs. Mutable y-combinator is easy in C++, but I simply don't know how to do it in Rust. Another problem is that C++ templates are superior, so for metaprogramming in Rust you have to go to macros earlier and macros code is undebuggable.

for in Rust is much nicer, though

→ Ответить

16 месяцев назад, # ^ |

+28

Recursive lambda in Rust

Yes, it is formally undefined behavior, but I use it extensively and had not had any problems yet

→ Ответить

16 месяцев назад, # ^ |

+11

Well, it definitely is a solution, and it is cool that it exists and works, but the fact that it looks messy even to C++ standards just drains all the happiness

But, honestly, I was wondering if it is doable in safe Rust without unreasonable overhead

→ Ответить

Spheniscine

16 месяцев назад, # ^ |

← Rev. 4 →

"Recursive closures" are definitely possible in safe Rust, here's an example: https://pastebin.com/QJ7bJbu5 (snipped from my submission to an AtCoder problem: https://atcoder.jp/contests/abc231/submissions/27948026)

I do admit it can be a tad unwieldy to code on-the-fly though (hence why for most DFS problems, I simply continued using the iterative DFS tricks I picked up from Kotlin to prevent StackOverflowException), but I haven't yet learned how to do a similar thing in C++, so I can't compare.

→ Ответить

16 месяцев назад, # ^ |

pastebin is somehow down for me, so I read the AtCoder submission, and, as far as I understood, you use RefCell to deal with mutability. Although, it is not too much, it is still unreasonable overhead I mentioned.

In C++ and for immutable case in Rust you can simply write y-combinator and it will be fine. You can find an implementation for Rust here, for example.

The example does not reflect it, but you can use it like this

let mut gr = vec![vec![]; n];

for i in 1..gr.len() {
    gr[i / 2].push(i);
}

let gr = gr;

let dfs = |dfs: &dyn Fn(usize) -> usize, v: usize| {
    let mut ans = 1;

    for &i in &gr[v] {
        ans += dfs(i);
    }

    ans
};

let dfs = y(dfs);

println!("dfs({}) = {}", 0, dfs(0));

Similar code for C++ works both for mutable and immutable case because C++ does not care, but in Rust replacing Fn with FnMut does not seem at least straightforward (you can read this as "I failed to do that"). Your code overcomes these problems with RefCell that does all the checks in runtime which is probably still fine, but still carries some overhead with the sole purpose of shutting the compiler up.

→ Ответить

Spheniscine

16 месяцев назад, # ^ |

Oh thanks, I didn't know about Y-combinator, that makes things much cleaner (well, except for the need for either RefCell or pointer-hacks, but it shouldn't be too much of a problem for the majority of the problems I'd use it for)

Not sure I have the ability to actually understand it, but at least it's pretty copy-pastable

→ Ответить

16 месяцев назад, # ^ |

What do you mean by "look messy"? Because usage site is not really messy, and why do you care about messiness of your library code during contest? And I do not think there's any real performance overhead

→ Ответить

16 месяцев назад, # ^ |

Usage and performance are great, I agree. I meant the implementation. It has unsafe, UB, macros and some boilerplate all in one place. I don't use prewritten code during a contest except for short (about 70 lines long) template for reading input and multitests, so at the end of the day, I indeed write my library code. It makes a lot of sense when you are mostly competing under ICPC rules, although, now I probably can start building a library.

In general, I don't mind the complexity of the solution. I even don't really mind unsafe, but I don't see any fundamental reasons for its necessity in this case. However, when you have to put up with UB, with things that completely avoidable in C++, like macros killing all the assistance from your IDE and boilerplate, and also with unsafe as the cherry on top of that in return for checks for rare occasions that you messed your references up, it kills all the fun of using Rust.

→ Ответить

16 месяцев назад, # ^ |

It is necessary here because we need to pass lambda as argument at the same time as we invoke it, hence we have more than 1 mutable reference (which is theoretically UB)

As for other things — macros is not that black of a box for clion now, and c++ templates have same problem. Also we are not only talking about memory safety as applied to CP — amount of sugar that rust gives that is very relevant to CP is staggering

→ Ответить

16 месяцев назад, # ^ |

Yes, I agree that this exact solution would not work. However, in fact, what we are trying to achieve is to create an anonymous object that has references to whatever we want to capture and also is able to call itself. Again, I see no fundamental reasons for it to be impossible for mutable references.

Maybe I missed some specific extension for CLion that helps with macros specifically, but currently the way I write macros when I need them looks like

Implement needed functionality for some particular case.
Wrap into macros and generalize using search and replace.
Fix errors that you can't even locate.
Cry if you need to add something later.

C++ template are much more debuggable in that sense. At least, you can read compiler errors and understand them. Errors even in normal Rust are sometimes misleading, but with macros it gets even worse. In general, I believe that in terms of debuggability Rust generics $$$\gg$$$ C++ templates $$$\gg$$$ Rust macros $$$\gg$$$ C++ defines. But in C++ you can do everything you need using only templates, while in Rust you have to occasionally use macros.

And yes, I agree that whenever you don't need anything too complex, using Rust is much more comfortable, except for a few very annoying things like using only usize and not isize for indexing, but, even to this day, C++ offers considerably more capabilities

→ Ответить

16 месяцев назад, # ^ |

They've added recursive expand which makes stuff way easier to write. But thing is I never needed to write something like that during the contest, and time is not that much of constraint when writing library. I'm not sure if rust or c++ better to use without library, but I do not have this alternative, I have libraries in both of them

→ Ответить

16 месяцев назад, # |

+16

January 21st is Saturday though

→ Ответить

16 месяцев назад, # ^ |

Thanks! I am bad at math. Fixed.

→ Ответить

oversolver

16 месяцев назад, # |

← Rev. 2 →

+80

Rust is getting increasingly more popular on CodeForces

13 people in #844, 6 in #843 — the same as 7 months ago...

→ Ответить

16 месяцев назад, # ^ |

I mean the bigger scale picture. Compared to 5 years ago. And I did not look at the statistics, but just submissions of people I befriend on codeforces.

→ Ответить

Golovanov399

16 месяцев назад, # |

← Rev. 2 →

Well, I had a hard time reading input in Rust without having a prewritten scanner. If the contest doesn't go well, I suggest you to do first several projecteuler.net problems (the rules of PE allow streaming and spoiling first 100 problems wherever you want); or maybe even start the stream earlier and practice them prior to the codeforces contest, as it seems more logical to do it in this order (basic stuff first, reading input second).

I am not a rustacean and speak from the position of somebody who also tried to take a glance at Rust in the recent past.

→ Ответить

16 месяцев назад, # ^ |

Great suggestion. Will probably do that. Thanks!

→ Ответить