thelema314

vor 4 Jahrendiscuss

I have to note ocaml-bitmatch/bitstring. Example code: https://bitstring.software/documentation/#matching-bitstring...

This was extremely convenient for me in the past.

thelema314

vor 9 Jahrendiscuss

TL;DR: use probabilistic logging (x% chance of logging, with x chosen by dev for each log statement) instead of importance levels (ERROR, WARN, INFO, etc) to keep common events from flooding log files. Is that it?

edit: misclick

thelema314

vor 9 Jahrendiscuss

This is correct; OCaml integers are tagged with their LSB being 1 to indicate they're not a pointer. This means that the integer n is stored as 2n+1, and adding 1 requires modifying the stored value by 2.

thelema314

vor 10 Jahrendiscuss

> When using a signed integer variable to represent an index, there is an entire range of negative numbers that are not useful at all. Let's make use of them, then.

If you have "local variable" with more bits than log(# elements to be sorted), then yes, this trick works, but with sufficient extra bits, you can pack multiple indexes into a single variable by shifting and 'or'ing.

An even sneakier way of hiding this extra bit is to use the program counter to store it:

  a:
    int i = 0
    FOR (; i < # elems-1; ++i)
         IF pair(i, i+1) is out of order
             swap pair; goto b
    RETURN
  b:
    FOR (; i < # elems-1; ++i)
         IF pair(i, i+1) is out of order
             swap pair
    GOTO a

If the program is running the "b" loop, some pair has been swapped, so when it finishes the loop, it knows to re-run the "a" loop. If the program completes the "a" loop, it knows no pair was swapped, and can finish.

Edit: formatting

thelema314

vor 10 Jahrendiscuss

I kind of wish this article had gotten into some details of how various compilers implement std::function; while it was nice to see some details of clang++'s 32-byte size of all std::function to remove the need for dynamic memory for many function objects, I'm still wishing I had more details on efficiency/cost of using std::function vs. plain lambdas or function pointers or other solutions.

thelema314

vor 10 Jahrendiscuss

To depend on compiler flags, I do this:

## compiler_flags file keeps a copy of the compile flags $(builddir)/compiler_flags: force mkdir -p $(builddir) echo '$(CPPFLAGS) $(CFLAGS)' | cmp -s - $@ || echo '$(CPPFLAGS) $(CFLAGS)' > $@

##rebuild all objects if compile flags change $(LIBOBJECTS) $(RTLLIBOBJECTS) $(OPTLIBOBJECTS) $(TESTOBJECTS) $(builddir)/init_qt_workdir: $(builddir)/compiler_flags

I"m pretty happy with the results.

thelema314

vor 11 Jahrendiscuss

The most succinct informal description I have for NP-complete problems is lack of optimal substructure; that is, given a solution to part of the problem, it's possible for that to not help at all for solving the whole problem.

For Traveling Salesman, this means that given the best tour for an N-city graph, the best tour for the same graph augmented by a single vertex could be entirely different.

thelema314

vor 11 Jahrendiscuss

> Given any two cities, a and b out of N, we do not know which one is visited first in the shortest path, and we certainly don't know what a's successor will be in the solution. Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.

Usually, the problem is simplified to a threshold test, like: Does this tour have path length < X? These kind of problems are equivalently difficult to produce solutions for in the general case, but are straightforward to verify.

thelema314

vor 11 Jahrendiscuss

I found the redundancy of having the same number stored on both also unnecessary, and a scheme that just reorganized where the bracelets are seems better. The "friendship" component of having identical bracelets is lost, but information density is certainly improved. Instead of considering this as one's complement, just give the right bracelet sum to one person and all the rest of the bracelets to the other.

comments