tmyklebu

6 ms·

1.
by tmyklebu 1y ago
Seems like the author is missing a trick? You can use a simple hash table without probing to classify each number as either (1) first instance of a number in the table, (2) known duplicate of a number in the table, or (3) didn't fit in
2.
by tmyklebu 1y ago
Well, modular multiplication is faster than modular inverse, both asymptotically for large moduli and practically for almost all moduli I can think of. (2, 3, and 4 being notable exceptions!) The article computes modular inverses of a_1, .
3.
by tmyklebu 1y ago
Yeah, that was just a search. There are 2^32 multipliers; call them m. For a bit in m*x to be useful, it must be zero for 16 symbols and one for 16 symbols. Call those bits "useful bits." Try every multiplier; for each multipli
4.
by tmyklebu 1y ago
Same idea, but without BMI2: unsigned h = (1264523 * x & 0x1020a01) * 134746240 >> 27; Alternatively: unsigned h = (1639879 * x & 0x1038040) * 67375104L >> 32 & 31; The multiplication by 67375104L can b
5.
by tmyklebu 1y ago
Two fast (today) instructions: unsigned h = _pext_u32(1264523 * x, 0x1020a01);
6.
by tmyklebu 1y ago
The second stage (on-site, ~20 competitors) is done like that. The first stage (this one, with ballpark 10000 competitors) is distributed and done in very heterogeneous environments, and it relies on local high school teachers taking time
7.
by tmyklebu 1y ago
This really is quite sad. The first stage of the CCC is written in pretty heterogeneous conditions. There are several thousand competitors across the world. Students use a language of their choice and their work is graded by their teacher
8.
by tmyklebu 2y ago
This was a popular topic in '80s linear programming books. Chvatal's "Linear programming," for instance, is carefully-written and devotes about 100 pages devoted to network simplex. Papadimitriou and Stieglitz's &
9.
by tmyklebu 2y ago
No cuts are necessary for minimum-weight bipartite matching as the constraint matrix is totally unimodular. Total unimodularity guarantees that any optimal basic solution is an integer solution. Moreover, well-known algorithms for linear p
10.
by tmyklebu 2y ago
There are theory papers on "buffer trees"---B-trees where each node is augmented with an O(B)-length array of pending updates and queries. I believe there were also some attempts at building SQL databases based on them. It sound
11.
by tmyklebu 2y ago
This is pretty persnickety and I imagine you're aware of this, but free is a weak symbol on Linux, so user code can replace it at whim. Your foo cannot be statically determined to be UB.
12.
by tmyklebu 2y ago
It does something unexpected if size is SIZE_T_MAX-1, too. And it's also undefined if input is null and size is zero, which seems more likely to surprise that function's author. This is because memcpy requires valid pointer argu
13.
by tmyklebu 2y ago
Compile time is another reason to prefer push_back, which is a function, to emplace_back, which is a function template.
14.
by tmyklebu 3y ago
First, what a great resource you've put together! You're presenting a lot of useful material clearly and concisely, together with the reasoning behind it. I wish I had this when I started doing performance work. > For a perfe
15.
by tmyklebu 3y ago
To try to argue it: Humanity does better when we don't marginalise people for dumb reasons such as membership in a visible minority group. Marginalising someone for a dumb reason is an individual decision, and it's a decision tha
16.
by tmyklebu 3y ago
Not research, but Jelani Nelson at Berkeley ran programmes in Ethiopia to expose schoolchildren to programming. (In case it needs to be said, Jelani is a top-shelf theoretical computer scientist.)
17.
by tmyklebu 3y ago
I wasn't around for too much of the 1980s, but I think there was a qualitatively similar hype cycle starting in the late 1970s. MINOS, CPLEX, XpressMP, OSL, KORBX, GAMS, AMPL, and many other optimisation packages came out of that perio
18.
by tmyklebu 5y ago
If you're just looking for hard-to-round inputs, you can also enumerate the double precision space completely with some cleverness and modest patience. Elkies [0] computes a piecewise linear approximation to his (number-theoretic) func
19.
by tmyklebu 5y ago
Nocedal and Wright is an excellent overview and a good starting point. Also consider: - R. Schneider, Convex bodies: the Brunn-Minkowski theory. The first two chapters are an excellent introduction to convex geometry (plus a little bit ex
20.
by tmyklebu 7y ago
What makes you think he misunderstood? What happens on fc30 when you 'yum install dstat' as he suggested? This webpage listing the contents of the fc30 pcp-system-tools package: https://fedora.pkgs.org/30/fe
21.
by tmyklebu 7y ago
Not exactly what you asked for, but C11 added this bit that was not there in C99: An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile obje
22.
by tmyklebu 8y ago
Threading was a structurally different change from fs operations and networking. You need the compiler to cooperate when you're writing to a location in one thread and reading it from another. You can either get there using hacks bui
23.
by tmyklebu 8y ago
> Example: Sockets should be IN. As above, vast numbers of programs want to use sockets and a standard approach would suit almost all of them perfectly well. I think the BSD socket library is that standard approach...
24.
by tmyklebu 8y ago
Just picking a couple quotes from the article: > Especially when you compare C++ to other languages, there’s a pretty strong argument to be made for a more inclusive and even all-encompassing standard library - look at the richness of th
25.
by tmyklebu 8y ago
There's more than enough neat stuff I don't know in there. Unfortunately it's tough to trust a source with so many errors in the stuff I do know. I wasn't aware of any CLT for iid random variables with infinite variance
26.
by tmyklebu 8y ago
This list is fun, but it's a little bit sloppy: - The central limit theorem relies on the mean and variance of your random variable existing; there are random variables for which mean and variance don't exist. - The definition of
27.
by tmyklebu 8y ago
> The converse is also true (and is much easier to prove, so we won’t be concerned with it): a diagonalizable matrix is always normal. It is actually more difficult to prove. [2, 1; 0, 1] is diagonalisable (via [1, -sqrt(2)/2; 0, s
28.
by tmyklebu 8y ago
It might be instructive for you to try solving the linear programs in netlib[0] with stochastic gradient descent. ;) The short version of the story is that different optimisation problems have different kinds of structure, and the user will
29.
by tmyklebu 8y ago
> What else are you going to do in C? But even most real world implementations of C have all sorts of structs and typedefs that you shouldn’t make any assumptions about and you should treat as an opaque type. Subtract two times? (BTW, s
30.
by tmyklebu 8y ago
> Even C has a bunch of functions to work with the date struct as an opaque type.... Yes, for conversion to/from time_t, formatting, and parsing. That's my point; you use the integral type whenever you don't care whether

More ›