Closed commander-trashdin closed 1 year ago
Hi. Any corrections or suggestions are welcome. When it comes to constant factors of performance, however, I'm not always striving for it. In many cases I focus on making it easy to read and modify my code in a contest.
(If I remember correctly, you suggested DP to reduce operations for matrix multiplication somewhere before. I like to read such tips or articles.)
Okay, several things.
1) Here is my (torn out of context) dfs macro (which performs non-recursive dfs. It also calls proper visitors (or so I hope). I am afraid it needs some rewriting before you could use it in your code, but maybe if you are interested, I can help with that. https://gist.github.com/thrashdin/b90abc53fc6890d4d5c78dab1df03b02
2) I suggested it here (https://github.com/numcl/numcl/issues/17#issuecomment-557381849) and I actually posted my code there (which works all but maybe a macro I wrote). People told me I need more like a compiler-macro for that, but I don't know how to make one. Again, if you are interested, maybe you can help me there). Also, there is ofc a wiki article on that. https://en.wikipedia.org/wiki/Matrix_chain_multiplication It mentions a faster algorithm -- pretty long one. Me and my friend are planning to implement it, both in C++ and CL. Asa it happens, I am willing to share the CL part)
3) Me and that friend I mentioned are actually planning to implement several high-level algorithms using CL, such as Mikkel Thorup algorithm (a faster Dijkstra). Willing to share them too.
4) I think your coding style is more advanced compared to mine => In many cases things I submit would need some corrections. Keep that in mind when you agree to deal with my stuff)
Thanks. All your work is interesting. If you write Thorup's algorithm, I will enjoy looking at your code. This repository is, however, aimed at competitive programming in the first place (though I also learn and write new algorithms never used in a competition, sometimes out of curiosity and sometimes out of necessity).
If I respond to a yes-no question, whether I accept other lisper's contribution or not, the answer is yes. However, for now I don't intend to make this repository a public project in the true meaning. Anyway, thank you for being interested in my work!
Well, yea, I mean, if I wasn't busy with all the other (mostly non Cl ;(( ) stuff, I should have made something like this myself by now. I actually attempted deque a year ago, but wasn't experienced enough.
Now, uhh, I got the idea about competetive programming, so.... Should I actually try to make some contributions (seems like yes?) and in what form -- a pull request? I take it as I can't just throw my gists in all directions)
Hey, we are bulding a certain library that might be nice for collection like yours. It's here https://github.com/commander-trashdin/cl-overload and the discussion is here https://github.com/markcox80/specialization-store
I was thinking about which functions should be included with your library in mind. So I would appreciate any suggestions if you have them. I think it can also be possible to make the way you generate your structures less...macro-based.
Hi. I won't be able to introduce such a dense abstraction layer for competitive programming (except for the possibility, major contest sites adopt a totally different judge system).
More importantly, however, I'm expecting great things from these kinds of attempt to fill in the missing piece of Common Lisp, parametric polymorphism. Keep it up.
Okay, Just for clarity though, the main goal of the project is to have 0-cost (in terms of runtime) abstraction. All of our specializations are carefully inlined and dispatched in such a way, that if you declare the types (which is about the same as just name functions according to the types) there will be exactly 0 performance costs.
No idea how to otherwise contact you, but here's an example of what I had in mind (I cannot do this atm, so I haven't finished the project, and this gist is merely a bad sketch, but it does convey the idea)
https://gist.github.com/commander-trashdin/e8582ba36b8d07f66a3646cf7bd7ad99
It (static dispatch) became half usable now (https://github.com/lisp-polymorph), and I intend to upgrade it more. At some point I'd like to take some of the basic structures you have here + finished red-black tree I once started. I hope I have your permission to take your impls? (I expect them to be performance oriented since, duh, competitive)l.
I saw it. Nice and laborious work, I think. Most code in this project is under public domain, so please feel free to reuse it.
Uh, sorry to bother you so much, but I suppose you aren't available for direct help (mostly with data structures implementation/review) right now or around now? I don't even know anybody else in the CL community who did as much as you in this area.
Hi. If your problem is deeply related to CL, I think you can ask it on reddit r/lisp, otherwise you can ask it on stackoverflow etc.. (Of course you can ask it here if you have a good reason to do so, but anyway I believe it's better to submit a question in an open forum first.)
You are good at writing data structures and thats what we also need for our polymorphism library.
Are you interested in them? I can dig up some code I was writing to check performance. Pretty sure for example I had a non recursive DFS, real quick, somewhere.