News for hackers. Stuff that matters.
Re:Decreasing Gitlab repo backup times from 48 hours to 41 m... by parthdesai on Friday June 06, 2025 @01:01PM (#44202848)
My rule of thumb for 80%-90% of the problems is, if you need complicated algorithm, it means your data model isn't right. Sure, you do need complicated algorithms for compilers, db internals, route planning et all, but all things considered, those are minority of the use cases.
Re:Decreasing Gitlab repo backup times from 48 hours to 41 m... by anttihaapala on Friday June 06, 2025 @02:53PM (#44203856)
This is not a complicated algorithm. A hash map (dictionary) or a hash set is how you would always do deduplication in Python, because it is easiest to write / least keystrokes anyway. That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.
Re:Decreasing Gitlab repo backup times from 48 hours to 41 m... by throwaway2037 on Friday June 06, 2025 @10:49PM (#44207019)

    > That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.
I am confused. There are plenty of open source, fast hash map impls in C.
Re:Decreasing Gitlab repo backup times from 48 hours to 41 m... by saagarjha on Saturday June 07, 2025 @07:06AM (#44208851)
Yes, the problem is getting them into your project.
Re:Decreasing Gitlab repo backup times from 48 hours to 41 m... by account42 on Tuesday June 10, 2025 @04:22AM (#44234063)
That's only a problem if you have never done any C development.
Re:Decreasing Gitlab repo backup times from 48 hours to 41 m... by paulddraper on Friday June 06, 2025 @04:08PM (#44204509)
This isn't knapsack. This is a dict lookup.
Re:Decreasing Gitlab repo backup times from 48 hours to 41 m... by LtWorf on Friday June 06, 2025 @09:14PM (#44206593)
I wrote a funny algorithm to group together words that end the same way to write them once in my binary wordlist file, since there is an array that points to the start character and a \0 to end the word. My initial solution was O(n²) but it was too slow on a real wordlist so I had to come up with something better. In the end I just sort the list with quicksort, but revert the order of the words and then the groupable ones end up nearby each other.