• MinekPo1 [She/Her]@lemmygrad.ml
    link
    fedilink
    arrow-up
    1
    ·
    4 months ago

    you forgot about updating the hashes of items after items which were modified , so while it could be slightly faster than O((n!×n)²) , not by much as my data shows .

    in other words , every time you update the first hash you also need to update all the hashes after it , etcetera

    so the complexity is O(n×n + n×(n-1)×(n-1)+…+n!×1) , though I dont know how to simplify that

    • magic_lobster_party@kbin.run
      link
      fedilink
      arrow-up
      2
      ·
      edit-2
      4 months ago

      My implementation: https://pastebin.com/3PskMZqz

      Results at bottom of file.

      I’m taking into account that when I update a hash, all the hashes to the right of it should also be updated.

      Number of hashes is about 2.71828 x n! as predicted. The time seems to be proportional to n! as well (n = 12 is about 12 times slower than n = 11, which in turn is about 11 times slower than n = 10).

      Interestingly this program turned out to be a fun and inefficient way of calculating the digits of e.

      • MinekPo1 [She/Her]@lemmygrad.ml
        link
        fedilink
        English
        arrow-up
        2
        ·
        4 months ago

        Agh I made a mistake in my code:

        if (recalc || numbers[i] != (hashstate[i] & 0xffffffff)) {
        	hashstate[i] = hasher.hash(((uint64_t)p << 32) | numbers[i]);
        }
        

        Since I decided to pack the hashes and previous number values into a single array and then forgot to actually properly format the values, the hash counts generated by my code were nonsense. Not sure why I did that honestly.

        Also, my data analysis was trash, since even with the correct data, which as you noted is in a lineal correlation with n!, my reasoning suggests that its growing faster than it is.

        Here is a plot of the incorrect ratios compared to the correct ones, which is the proper analysis and also clearly shows something is wrong.

        Desmos graph showing two data sets, one growing linearly labeled incorrect and one converging to e labeled #hashes

        Anyway, and this is totally unrelated to me losing an internet argument and not coping well with that, I optimized my solution a lot and turns out its actually faster to only preform the check you are doing once or twice and narrow it down from there. The checks I’m doing are for the last two elements and the midpoint (though I tried moving that about with seemingly no effect ???) with the end check going to a branch without a loop. I’m not exactly sure why, despite the hour or two I spent profiling, though my guess is that it has something to do with caching?

        Also FYI I compared performance with -O3 and after modifying your implementation to use sdbm and to actually use the previous hash instead of the previous value (plus misc changes, see patch).