Candidates for removal - Githubissues

kth-competitive-programming / kactl

KTH Algorithm Competition Template Library (... eller KTHs AC-tillverkande lapp)

2.6k stars 689 forks source link

Candidates for removal #116

Open Chillee opened 5 years ago

Chillee commented 5 years ago

Since with the new additions in PR we're running fairly close to the page limit, I thought it'd be a good idea to keep a running list of what might be removable.

[ ] SubMatrix.h (13 lines)- Pretty trivial to re-implement from scratch.
[ ] Matrix.h (26 line)- Also pretty trivial to re-implement. It isn't used elsewhere either.
[ ] FenwickTree.h (22 lines) - I personally find 1d fenwick trees to be nearly completely useless - especially since we have the bottom-up segtree that runs nearly as fast as the fenwick tree.
[ ] Bellman Ford (12 line)/Floyd Warshall (12 lines) - Also pretty trivial
[ ] techniques.txt :^)

simonlindholm commented 5 years ago

I personally find 1d fenwick trees to be nearly completely useless - especially since we have the bottom-up segtree that runs nearly as fast as the fenwick tree.

How large is the perf difference? Also, we should probably add some code to segtree in this case to support lower_bound.

Also, perhaps:

[ ] line-hull intersection
[ ] global min cut
[ ] TopoSort
[x] binomialModPrime should be just a description
[ ] HillClimbing
[ ] Polynomial

On the topic of shorting we could also decrease the font size for surrounding .tex code -- the algorithms are currently of rather smaller size than the math, while being used far more frequently.

General purpose numbers and Probability distributions don't really pull their weight. They could be made shorter by using tables, I guess.

Chillee commented 5 years ago

Well, nearly as fast is a bit of an exaggeration - it's a 55% difference.

simonlindholm commented 4 years ago

On the topic of shorting we could also decrease the font size for surrounding .tex code -- the algorithms are currently of rather smaller size than the math, while being used far more frequently.

Done in 3ad3b65505e1d1707a66255575757c2692149abd. (Won two whole columns; we're currently at 23.666 pages)

Chillee commented 4 years ago

Let's include some of the stuff we're not currently including then :)

Currently these are the files excluded:

./content/numerical/MatrixInverse-mod.h
./content/various/FastInput.h
./content/tex/preprocessor.py
./content/graph/Dinic.h
./content/graph/GomoryHu.h
./content/strings/Hashing-codeforces.h
./content/geometry/CirclePolygonIntersection.h
./content/geometry/PolygonUnion.h
./content/geometry/ManhattanMST.h
./content/geometry/LineProjectionReflection.h
./content/geometry/DelaunayTriangulation.h
./content/geometry/CircleLine.h

I would consider

./content/various/FastInput.h
./content/graph/GomoryHu.h
./content/geometry/CirclePolygonIntersection.h
./content/geometry/PolygonUnion.h
./content/geometry/ManhattanMST.h
./content/geometry/LineProjectionReflection.h
./content/geometry/CircleLine.h

simonlindholm commented 4 years ago

Added FastInput and GomoryHu, will look at the rest tomorrow.

simonlindholm commented 4 years ago

Added CirclePolygonIntersection.

LineProjectionReflection feels unnecessary since projection is pretty easy if you know your dot products: a + (p - a).dot(b - a)*(b - a)/(b - a).dist2()

Maybe we shouldn't be too greedy, could be confusing to remove things later, and I'm not sure how much the currently open PRs will eat.