Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Uristides]

I just decided to read the C++17 new features.

Wait, what in the- I haven't even caught to speed with everything C++11 introduced yet, let alone C++14.
Fun fact: I just fit C++ standard release dates to a logarithmic model and it predicts by 2027 we'll be seeing new C++ standards yearly, by 2035 we can expect two standards a year and one standard per second by around 2228

[Reelya]

Yeah, except there was less pointer stuff going on with mine, because it generates a node<T> class at compile time for everything you try and put in there, so there is a family of node<T> classes directly storing a "T" in each one. They're not actually void* at all, and since all node<T>'s are children of "nodeBase", they're effectively interchangeable polymorphic objects.

And it automatically generates a Type<T> function for each type you try and store, the Type<T> returns a static char* string. Basically that string is generated at compile time, so effectively it generates const static type information that you can print out about your node<T> objects by directly reading the char* that each node<T> has. It doubles as a runtime-printable type string, and also you can say

if(type=Type<int>()) // do the int thing.

or "cout << type" which just prints "int". Which is all sorts of neat and no pointer unsafety since it's all statically typed at compile time yet acts like dynamic typing.

And if you didn't make a node<int>, but you call "if(type=Type<int>())" anyway, then the Type<int>() gets autogenerated at compile time, so you don't have to even worry about which types you specified to store or not, you can add or remove type checks in an ad-hoc manner. I'm actually wondering how std::any is going to measure up, the implementation I've got is actually pretty nice in a few ways.

[McTraveller]

...it's all statically typed at compile time yet acts like dynamic typing.

<voice-of-Victor>ABOMINATION!</voice-of-Victor>


(EDIT: actually, it's pretty neat, and a good exercise in templates and thinking about collections and typing.)

[alway]

Since I may have missed something while looking into its functionality:
Does anyone know if Visual Studio has a window that allows for copying a buffer of data from a file directly into a memory address at runtime from the debugger? And/or do the inverse of said process by copying an arbitrary buffer out to a file?

As far as I can tell, such a feature would be trivial via the EnvDTE interface* with a for loop around some ExecuteStatement calls; and would be just about the best thing to add to a debugger since breakpoints... and yet I can't seem to locate a built-in feature to do so. Am I just overlooking something?


*On a side note: EnvDTE is the system for Visual Studio automation, and lets you do every action you can do through the Visual Studio UI via code, among other things. It's pretty dang nifty and worth knowing about:
https://msdn.microsoft.com/en-us/library/envdte.aspx
https://msdn.microsoft.com/en-us/library/mt469259.aspx
https://msdn.microsoft.com/en-us/library/mt469181.aspx
https://msdn.microsoft.com/en-us/library/mt469169.aspx

[itisnotlogical]

I'm learning how to use an I2C sensor. The datasheet says I need to write a certain bit to a certain register to even turn the thing on, but I'm able to read data right away without any work besides typing bus.read_i2c_block_data().

It's awesome that I even have an opportunity to do this, but also very frustrating. All of the guides and documentation I've found seem to be written for those who already mostly know what they're doing.

[Reelya]

But the problem is that if you only send a void pointer then the receiving function has in fact no way of knowing what you sent to it. Let's consider the function you'd have to write:

void store(void *myThing) {}

How does "store" know what myThing really was? So you'd have to send it extra information:

void store(void *myThing, enum myType, enum mySize) {}

And that would ensure that you need a full catalogue of all possible types in your enum before you start using this, and you'd have to call it like this:

int whatToStore;

store((void *)whatToStore, typeInt, sizeof(int));

And to get around the need for doing this, you'd have to write a template function, which is exactly what I already did. And if you have a template function, there's no need to cast to void*.

As I noted, my mentioned design would require the calling code to know what you are pushing/retrieving, not the store/retrieve functions themselves (which would literally just care that they are void pointers and storing those in some sort of structure). It becomes the job of the programmer to hardcode those casts to the appropriate types based on the program flow. Of course that would also probably prevent you from doing true arbitrary willy-nilly pushes and pops from your data structure, but as mentioned there really isn't that much use for such a structure in the first place, as opposed to something with a regular order (say always pushing a person, then the object attacking them, then the attacking creature in that order, for example) which then means that on the other end you can just manually cast the first thing to person, the next one to the object, and the third to the creature. As I said, fragile and horribly unsafe, but it would work for the majority of use cases just fine (about which I am indeed interested as McTraveller is).

The problem is that if you serialize your void* storage you now can't get things out. Say it's float, double, float, int, but you're getting back just four void*. how do you determine the order they went in? If the client needs to keep a record of the order that everything went in, you've defeated the purpose of having a data store that can hold multiple types.

[Reelya]

There's was a stackoverflow question to optimized this code from a computation puzzle:

Code: [Select]

lli exchange(lli n)
{ 
    if(n<12) return n;
    else
    {
        lli sum=0;
        sum+=max(n/2,exchange(n/2));
        sum+=max(n/3,exchange(n/3));
        sum+=max(n/4,exchange(n/4));
        return sum;
    }
}
I worked out that you could unroll two levels of the recursion, combining like terms. The max function turned out to never be needed: Exchange n is always at least n. After that I unrolled three levels of recursion. Then i said fukkit and wrote a recursive function that outputs the unrolled function for n levels of recursion. The function it outputs is thousands of lines long, but it's really fast.

BTW here's the code for outputing the function to speed up the above:

Code: [Select]

std::vector<std::map<lli, lli>> map1;
map1.push_back(std::map<lli, lli>());
map1[0][2] = 1;
map1[0][3] = 1;
map1[0][4] = 1;
const int unrolled_levels = 20;
for (int level = 1; level < unrolled_levels; ++level)
{
map1.push_back(std::map<lli, lli>());
for (auto i = map1[level - 1].begin(); i != map1[level - 1].end(); ++i)
{
map1[level][(*i).first * 2] += map1[level - 1][(*i).first];
map1[level][(*i).first * 3] += map1[level - 1][(*i).first];
map1[level][(*i).first * 4] += map1[level - 1][(*i).first];
}
}

int level = unrolled_levels - 1;
std::cout << "\tlli exchange_opt(lli n) // unroll" << level << "\n\t{\n\n";
for (int inner_level = level; inner_level >= 0; --inner_level)
{
lli mult = 12;
std::cout << "\t\tif (n >= 12LL ";
for (auto i = 0; i < inner_level; ++i)
{
std::cout << " * 4LL";
mult *= 4LL;
}
std::cout << ") // " << (mult) << "\n\t\t{\n";
std::cout << "\t\t\tlli sum = 0;\n";

for (auto i = map1[inner_level].begin(); i != map1[inner_level].end(); ++i)
{
std::cout << "\t\t\tsum += exchange_opt(n/" << (*i).first << "LL)";
if ((*i).second > 1) std::cout << " * " << (*i).second << "LL";
std::cout << "; \n";
}
std::cout << "\t\t\treturn sum;\n";

std::cout << "\t\t}\n";
}
std::cout << "\t\treturn n;\n";
std::cout << "\n\t}\n\n";

Basically you run this, then cut and paste the output into your code, and it gives you a lot of speedup. For example if the original number is 1 million, you get 7000 times speedup, for 1 billion, you get 40000 times speed up. Just be aware: the optimized function is almost 2000 lines of code, and is optimized for long int numbers up to about 4 trillion. (I'm trying 1 trillion now, but I don't know if that would finish in a reasonable time).

[McTraveller]

There's was a stackoverflow question to optimized this code from a computation puzzle:

I'm too lazy to look it up - what is that function supposed to even do? Or is it just purely a "puzzle" problem?

I looked it up - the problem statement in http://stackoverflow.com/questions/43029024/reducing-the-time-complexity-of-the-code-below is actually kind of ambiguous if it's just the first statement; if you follow the example, then it matches...

[Reelya]

Yeah it's just for the idea of running a code generator to unroll a complex recursive function. get 40000x speed-ups.

EDIT:

discussing the benefits of using modulo vs bitmasks to clip numbers:

i % 2 gives you back 0 or 1, depending on odd or even. It uses a division and gives you back the remainder.

i & 1 also gives you back 0 or 1, depending on odd or even. It does a logical "AND" on each pair of bits in the left and right inputs, gives you back the results.

I was telling someone that it's better to use the latter than the former because the latter is much faster (a simple CPU bit operation) vs a full division calculation. The person scoffed "surely, such hand crafting is a load of shit. Super-duper compilers clearly optimize away any such small gain themselves".

Well think again. Compilers aren't God. They cannot know the designer's intent, they can only know what you ask for. In this case, it's missing that % and & produce the same output with some inputs, but different outputs with others:

-3 % 2 returns negative one.

-3 & 1 returns positive one.

So the compiler won't swap one for the other on the off-chance that what you wrote is what you wanted. But if you either never use negative numbers, or you don't want the sign to be retained (i.e. you only care about odd/even), then you can substitute "%(2^n)" for "&((2^n)-1)". It also runs a lot quicker. Changing 2 billion calls of %2 to &1 cut runtime from 55 seconds to 33 seconds on a "fully-optimized-for-speed" test program.

[Antsan]

I'm trying to write a kind of tonemapping algorithm that enhances local contrast in a given image without sacrificing image clarity. I already wrote a prototype that works quite well, but it's not as flexible as I want it to be and also quite costly in terms of time and space.

The idea is to collect the minimum and maximum intensities in range of a given pixel for multiple given ranges and then calculating the new value for that pixel by computing some value `min` out of the pooled minimum values, `max`out of the pooled maximum values and with original intensity for the pixel `v` via:

Code: [Select]

(v-min)/(max-min)For this I need an efficient pooling algorithm. I currently have this:

Code: [Select]

(defun sort-canal (canal predicate)
  (declare (type (array * 2)
                 canal)
           (type function predicate))
  (destructuring-bind (width height)
      (array-dimensions canal)
    (sort (loop :for x :from 0 :to (1- width)
             :append
             (loop :for y :from 0 :to (1- height)
                :collect
                `(,(aref canal x y)
                   ,x ,y)))
          predicate
          :key #'first)))

(defun pool-canal (canal predicate radius)
  (declare (type (array * 2)
                 canal)
           (type function predicate)
           (type (integer 1)
                 radius))
  (let* ((dim (array-dimensions canal))
         (sorted (sort-canal canal predicate))
         (to-do (fset:convert 'fset:set (mapcar #'first sorted)))
         (out (make-array dim
                          :element-type '(integer 0)
                          :initial-element 0)))
    (destructuring-bind (width height)
        dim
      (loop :for (intensity x y)
         :in sorted :do
         (loop :for out-x :from (max (- x radius)
                                     0)
            :to (min (+ x radius)
                     (1- width))
            :do
            (when (fset:empty? to-do)
              (return-from pool-canal
                out))
            (loop :for out-y :from (max (- y radius)
                                        0)
               :to (min (+ y radius)
                        (1- height))
               :do
               (when (fset:empty? to-do)
                 (return-from pool-canal
                   out))
               (when (fset:contains? to-do `(,out-x ,out-y))
                 (setf (aref out out-x out-y)
                       intensity
                       to-do
                       (fset:less to-do `(,out-x ,out-y))))))))))
The idea is to sort pixels by intensity into a list and then write their value into all the relevant pixels in the array holding the pooled values one by one.
First sorting the pixels into a list allows me to write to every pixel only once, but I'm still iterating over the whole rectangle of pixels which might be influenced by a given pixel for every one of those candidates, so basically for a given array with m pixels and a radius of n, time complexity is at O(m*nē). I think it should be possible to avoid iterating over pixels that already have been set, since it should be possible to just avoid the squares that already have been set, which should then make the algorithm O(m) instead, but I don't see how I could keep track of the rectangles already set nor how I could incorporate them into the boundaries for the loop variables.

[TheBiggerFish]

What language are you using?

[Gentlefish]

That looks like hell LISP.

[alway]

Hierarchical data structure like a quad tree might help; one for the min and one for the max. Mark nodes as complete, partial, or empty, depending on whether their children have been filled in. When a block has been filled entirely, you don't even bother traversing down deeper. Should be particularly effective for large radii, since that implies filling out (and thus ignoring) large areas of the tree sooner.

[Antsan]

I'm using Best Language, also known as Common Lisp.

Using a quadtree sounds really good. I'll try that. Thank you!
I think it's sufficient to mark a node as filled or not filled. I don't see how dealing with a partially filled node would be different from dealing with an empty node.

[McTraveller]

I'm trying to write a kind of tonemapping algorithm that enhances local contrast in a given image without sacrificing image clarity. I already wrote a prototype that works quite well, but it's not as flexible as I want it to be and also quite costly in terms of time and space.

The idea is to collect the minimum and maximum intensities in range of a given pixel for multiple given ranges and then calculating the new value for that pixel by computing some value `min` out of the pooled minimum values, `max`out of the pooled maximum values and with original intensity for the pixel `v` via:

Code: [Select]

(v-min)/(max-min)For this I need an efficient pooling algorithm. I currently have this:
:
The idea is to sort pixels by intensity into a list and then write their value into all the relevant pixels in the array holding the pooled values one by one.
First sorting the pixels into a list allows me to write to every pixel only once, but I'm still iterating over the whole rectangle of pixels which might be influenced by a given pixel for every one of those candidates, so basically for a given array with m pixels and a radius of n, time complexity is at O(m*nē). I think it should be possible to avoid iterating over pixels that already have been set, since it should be possible to just avoid the squares that already have been set, which should then make the algorithm O(m) instead, but I don't see how I could keep track of the rectangles already set nor how I could incorporate them into the boundaries for the loop variables.

Can you clarify what you mean by "multiple ranges"? I'm not sure what you mean there exactly, because if you are doing a min/max over any range, the greatest extent will win regardless of range...you might as well just compute over the largest range.  I'm also not quite sure what you mean by "pooled" values - is that the min/max store?  It's also very unclear as to what happens at the corners and edges of the image (since you can't get a meaningful area centered on a pixel in that situation).

If you are smart about your buffer management, I think you can get down to something that will be closer to O(m*n) for large images, and closer to O(m*n^2) for a small image.  Basically something like

• For the first (say top-left in this example) pixel in the image, scan the (largest) range (n x n pixels), but scan it by columns each n pixels high.
• Compute the min/max intensity for that range, then for each column, also store the min/max in that range *without* that column.
• Scan the next pixel to the right: you now only need to scan n pixels for the new column.
• Drop the leftmost column, so you have the min/max without it - then you just need to compare the min/max for the new column.
• Rinse and repeat.

This also avoids the expensive sorting operation.