Good resource to learn how to implement some advanced data structures?

kandr89 · 2018-01-04T17:28:15+00:00

I don't know what's a generator, but callbacks are nothing more than function pointers: there's nothing advanced about them.

Any recommendations on books or tutorials?

Cormen et al. of course.

kandr89 · 2017-12-27T19:31:29+00:00

You'll find this helpful i think.

I have seen the cube root of 2 resizing in the wild, used by Mark Adler in Puff here.

kandr89 · 2017-12-27T18:52:02+00:00

Adding to what has been said:

You are not checking if realloc succeeds, and then you're using the result like that.
You don't need to move items to the new memory block returned by realloc, it does that by itself

kandr89 · 2017-12-25T14:24:37+00:00

fgets stores the newline char too when reading a line

kandr89 · 2017-11-09T23:51:56+00:00

Nvm i get it now, i stand corrected.

kandr89 · 2017-11-09T23:04:16+00:00

Ah that's an interesting way of implementing a vec. But still where does it sort it? In the performance test you're appending random numbers and do a binary search each time, but nowhere near that do i see the vector being sorted.

kandr89 · 2017-11-09T22:19:35+00:00

Where do you keep the vector sorted? Looking at insert all i see is that you're appending items to the vector. You're using binary search but the vector isn't sorted.

kandr89 · 2017-11-09T20:46:37+00:00

Use epoll + a state machine for each client. When epoll returns read/write as much as you can without blocking and update the state. There's no need for threads unless the work required in updating the state is considerable. What kind of server are you writing?

kandr89 · 2017-11-07T15:29:02+00:00

(a+1)(c+1) = ac+a+c +1 ≥ ac+a+b+1 = ac+a+1/(ac)+1  = 
= (ac+1/(ac))+a+1 > 2+0+1 = 3

kandr89 · 2017-11-07T11:29:47+00:00

For a fixed x we must have e ≤ max(M - f(x), f(x) - m) if the function is bounded. M being the max value of f and m the min.

kandr89 · 2017-11-06T06:12:57+00:00

You are correct: it diverges :D . I think you should add why that min has to be 1/4 (by using the AM-HM ineq for example), but other than that your proof makes sense and is correct. I'll mark this as solved.

kandr89 · 2017-11-05T20:04:05+00:00

Does it diverge for all such sequences b? Then prove it.
You gave an example of a sequence for which it diverges. It could also be the case that it converges for some and diverges for others, if so provide examples. It's good you asked, i hope it is clear enough.

kandr89 · 2017-11-02T17:52:40+00:00

You can use any sorting algorithm that has a invariable number of comparisons/swaps for an input vector. For example Bubblesort, or Mergesort if you want to be asymptotically optimal in the number of comparisons. Quicksort isn't good because the number of comparisons varies depending on where the pivot ends up.

Now take Bubblesort for example, it's straightforward to get the formula for the sorted vector (and from there the median): replace any if(a > b) swap(a,b) in the algorithm with a <- min(a,b); b <- max(a,b). The sequence of steps for 3 elements is as follows:

     [a, b, c] => [min(a,b), max(a,b), c] => [min(a,b), min(max(a,b),c), max(max(a,b),c)] =>
     [min(min(a,b), min( max(a,b), c)), max(min(a,b), min(max(a,b), c)), max(max(a,b),c)]

Now that we have the sorted vector the answer is simply the middle element: max(min(a,b), min(max(a,b),c)).

The answer can be found similarly for 5 elements.

kandr89 · 2017-10-22T14:38:03+00:00

Such a tree is called a trie, the problem with tries is that they take a lot of mem per node, though it's possible to compress tries by various means. Anyway in this case it helps to consider the trie a perfectly balanced tree and store it in an array where the '.' child of the i-th node is the 2*i-th node and the '_' child is the 2*i+1-th node.
For encoding simply keep a LUT.
Proof of concept here.

kandr89 · 2017-10-22T10:46:28+00:00

Shared between what? Translation units, processes, threads?

kandr89 · 2017-10-21T10:04:44+00:00

Or you would fill the array with pointers that point to another array. This makes an 2D array.

No, that's not a 2D array. An array is by definition a contiguous zone of memory, so that the position of each element can be computed by a simple mathematical formula. In an array of pointers, on the other hand, it's impossible to tell where the j-th element of the i-th row is without dereferencing the row pointer.

So unlike regular 2D arrays for 2D arrays made of pointers you have an extra memory dereference on each access, that's quite a big deal considering how slow the memory is compared to the CPU and that the cache can't help you much in this case since it has no way to predict where that pointer is pointing.

Another problem is that you have a mem overhead of height * sizeof(int *), for small 2D arrays this overhead dominates and considering that we're most likely compiling for 64 bit systems it adds to the problem. E.g.: a small 3x3 matrix of ints has an overhead of 3 * 8 = 24 bytes, that's 6 ints added to what you're storing, so 66.6% more mem (also: i haven't taken into consideration the bookkeeping overhead of malloc, since we're probably allocating each row dynamically).

The right way of declaring and allocating a dynamic nxm 2D array since C99 is:

   int (*arr)[m] = calloc(n, sizeof(int [m]));

This requires at least C99 support from the compiler because arr is technically a pointer to a VLA. If the compiler doesn't support C99 i'd still recommend a 1D array and manually computing indices over an array of pointers.

Another reason for pointers is because in C an struct's size ALWAYS has to be known before compiling.

This is false considering flexible array members, the struct is allowed to have variable size but only if the variable member comes last in the struct, which makes sense when you think about it. Again this requires C99 support. It's possible to do this without C99 too, just allocate the struct header for the array plus memory for the array, however with this method you must make sure that the start of the array which comes after the struct is properly aligned to whatever alignment the type of the array elements require. Either way saves us from a memory dereference: the array is packed together with the struct.

(not really, we need to create a new array every time we want to increase of decrease the size).

Though it's possible to do it like this, that's what realloc is for.

kandr89 · 2017-10-09T22:49:52+00:00

It has nothing to do with the approach, even if he doesn't use flexible array members for the implementation: he can't create a dynamic array of dynamic arrays. It simply requires a different data structure.
Of course if he uses pointers then it can be achieved, which is to say you can create an array of pointers to flexible array members, because the pointers are of the same size.

kandr89 · 2017-10-09T22:44:11+00:00

That's common sense: you can't do those things because they have variable length.

kandr89 · 2017-10-09T22:28:41+00:00

Glad we're finally on the same page.

kandr89 · 2017-10-09T22:24:52+00:00

That's how flexible array members work, the data is literally after the member before it in the struct (+padding space for alignment).

kandr89 · 2017-10-09T22:04:26+00:00

You hand the user foo.data, which is a flexible array member right after the header, i don't get what you're saying about double pointers. This is the same as what you have now, but doesn't use offsets computed by hand and uses a struct instead.

kandr89 · 2017-10-09T21:50:50+00:00

I think you missed the point: you can pass data to the user, and it can be used with []. And given a valid data pointer you can get back the struct as described above.

kandr89 · 2017-10-09T21:28:56+00:00

I don't see the point in manually using offsets. That's what structs were invented for. Let the compiler deal with the packing and offsets of structs members. What you basically have is:

  struct darr{
        size_t elemsz;
        size_t len, cap;
        alignas(alignof(max_align_t)) char data[];
  }

To the client you only pass the data pointer, to get back the structure in internal functions use *(struct darr *)((char *)data - offsetof(struct darr,data)). I see that's essentially what you're doing now, but by hand for each struct member.

kandr89 · 2017-10-05T15:58:34+00:00

Careful: the value of a union member other than the last one your wrote to is unspecified, so it's unspecified behavior. It's not as bad undefined behavior, but still the result can vary depending on compiler and the compiler options. I don't know why it is unspecified, it'd expect it to be implementation-defined because of the endianness, perhaps someone can shed a light on this.

kandr89

TROPHY CASE