std::set, index of element. Related topic

H

Hicham Mouline

Please refer to my previous post for presentation of the problem.

My question now is re how to actually write the code for
Calculate ( CalcCode codes[], double results[], const CalcOperations&
operations, int thing)
{
}

In practice, I see the operations map having as many as 30 operations.
There are groups of 4/5 operations that are tightly related, and when
operations within these groups
are requested within the same call of Calculate(), there is a perf benefit
by not having duplicate
execution of bits of code.
The structure of Calculate() is like:
{

if (operations.isSet(OP1))
{
.. .... // do length operation 1
// fill in results and codes
}
if (operations.isSet(OP2)) // tightly related to OP1
{
if (!operations.isSet(OP1))
{
// do length operation 1
}
// otherwise, lengthy operation 1 done already in the step before, not do
it again
}

This pattern might involve more than 3 or 4 operations in the if tests.

Is there a more elegant, shorter code way of writing this, but just as
efficient?

regards,
 
M

Michael DOUBEZ

Hicham said:
Please refer to my previous post for presentation of the problem.

My question now is re how to actually write the code for
Calculate ( CalcCode codes[], double results[], const CalcOperations&
operations, int thing)
{
}

In practice, I see the operations map having as many as 30 operations.
There are groups of 4/5 operations that are tightly related, and when
operations within these groups
are requested within the same call of Calculate(), there is a perf benefit
by not having duplicate
execution of bits of code.
The structure of Calculate() is like:
{

if (operations.isSet(OP1))
{
.. .... // do length operation 1
// fill in results and codes
}
if (operations.isSet(OP2)) // tightly related to OP1
{
if (!operations.isSet(OP1))
{
// do length operation 1
}
// otherwise, lengthy operation 1 done already in the step before, not do
it again
}

This pattern might involve more than 3 or 4 operations in the if tests.

Is there a more elegant, shorter code way of writing this, but just as
efficient?

If I understand correctly, you have a set (std::set) of operations and
some operation might reuse a previous operation (or advance the
computation of one) and the operations are addressed by their index in
'operations'.

I assume those operations work on the same set of parameters otherwise,
their would be no benefit (i.e. no use in OP2 reusing OP1 if OP1 was
called with different parameters).

In brief, you want to achieve a form of memoization.

IMO working with indexes in a std::set is a no-go. One solution
is indeed an std::map since you can iterate on the existing elements
'operations' and change the associated value with the computation
result. In your previous post, you mentioned that you had a performance
issue. I believe its steemed from the usage you made rather than from
std::map because finding a element is a set is basically the same as
finding one in a map. You could try std::tr1::unordered_map but IMHO it
would not be faster with so few elements.

Another possibility is to compute the graph of the operations to launch;
it is useful if you want to check you have no dependency cycle. It will
save you numerous tedious if/else but you have to know the antecedents
of your operations.
 
H

Hicham Mouline

Michael DOUBEZ said:
Hicham said:
Please refer to my previous post for presentation of the problem.

My question now is re how to actually write the code for
Calculate ( CalcCode codes[], double results[], const CalcOperations&
operations, int thing)
{
}

In practice, I see the operations map having as many as 30 operations.
There are groups of 4/5 operations that are tightly related, and when
operations within these groups
are requested within the same call of Calculate(), there is a perf
benefit by not having duplicate
execution of bits of code.
The structure of Calculate() is like:
{

if (operations.isSet(OP1))
{
.. .... // do length operation 1
// fill in results and codes
}
if (operations.isSet(OP2)) // tightly related to OP1
{
if (!operations.isSet(OP1))
{
// do length operation 1
}
// otherwise, lengthy operation 1 done already in the step before, not
do it again
}

This pattern might involve more than 3 or 4 operations in the if tests.

Is there a more elegant, shorter code way of writing this, but just as
efficient?

If I understand correctly, you have a set (std::set) of operations and
some operation might reuse a previous operation (or advance the
computation of one) and the operations are addressed by their index in
'operations'.

I assume those operations work on the same set of parameters otherwise,
their would be no benefit (i.e. no use in OP2 reusing OP1 if OP1 was
called with different parameters).

In brief, you want to achieve a form of memoization.

IMO working with indexes in a std::set is a no-go. One solution
is indeed an std::map since you can iterate on the existing elements
'operations' and change the associated value with the computation result.
In your previous post, you mentioned that you had a performance issue. I
believe its steemed from the usage you made rather than from std::map
because finding a element is a set is basically the same as finding one in
a map. You could try std::tr1::unordered_map but IMHO it would not be
faster with so few elements.

Another possibility is to compute the graph of the operations to launch;
it is useful if you want to check you have no dependency cycle. It will
save you numerous tedious if/else but you have to know the antecedents of
your operations.

As you mention the word "graph" for which operations to calculate, and their
dependencies on each other, is this related to graph theory and boost::graph
at all?

for instance, if I have, OP1 depends on OP2 and OP3, while OP4 depends on
OP1,
and OP5 depends on OP4 (ps it's never circular), I assume you're suggesting
to draw a graph of
depencies, and find the graph with the minimum number of nodes?

Basically, if I get a request for operations={ OP1, OP4 } it should run the
code that does
{ OP2, OP3, OP1, OP4 } in this order, each one of them just once. In
particular,
while calculating OP4, we don't need to recalculate OP1 because OP1 was
already in the request map,
we should reuse the result...

Given that my request map is only known at runtime, i can't generate this at
compile-time obviously.

How do I do this memoization then?

regards,
 
M

Michael DOUBEZ

Hicham said:
Michael DOUBEZ said:
Hicham said:
Please refer to my previous post for presentation of the problem.

My question now is re how to actually write the code for
Calculate ( CalcCode codes[], double results[], const CalcOperations&
operations, int thing)
{
}

In practice, I see the operations map having as many as 30 operations.
There are groups of 4/5 operations that are tightly related, and when
operations within these groups
are requested within the same call of Calculate(), there is a perf
benefit by not having duplicate
execution of bits of code.
The structure of Calculate() is like:
{

if (operations.isSet(OP1))
{
.. .... // do length operation 1
// fill in results and codes
}
if (operations.isSet(OP2)) // tightly related to OP1
{
if (!operations.isSet(OP1))
{
// do length operation 1
}
// otherwise, lengthy operation 1 done already in the step before, not
do it again
}

This pattern might involve more than 3 or 4 operations in the if tests.

Is there a more elegant, shorter code way of writing this, but just as
efficient?
If I understand correctly, you have a set (std::set) of operations and
some operation might reuse a previous operation (or advance the
computation of one) and the operations are addressed by their index in
'operations'.

I assume those operations work on the same set of parameters otherwise,
their would be no benefit (i.e. no use in OP2 reusing OP1 if OP1 was
called with different parameters).

In brief, you want to achieve a form of memoization.
[snip]
Another possibility is to compute the graph of the operations to launch;
it is useful if you want to check you have no dependency cycle. It will
save you numerous tedious if/else but you have to know the antecedents of
your operations.

As you mention the word "graph" for which operations to calculate, and their
dependencies on each other, is this related to graph theory

Yes. You don't necessarily have to work explicitly with graphs but you
can deduce an ordering from dependency specs with graph theory.
Maintaining a dependency spec is not trivial so this may not be applicable.
and boost::graph
at all?

IMO you don't need Boost.Graph for a simple node ordering.

[snip]
Given that my request map is only known at runtime, i can't generate this at
compile-time obviously.

True. Everything depends on the visibility on the dependency you have at
run time and may be overkill compared to a simple compute as you need it
method.
How do I do this memoization then?

Memoization can be implemented in a per function basis. Each operation
stores the result of previous call related to given parameter (a cache
if you want). If you work in multi-threaded environment or if the cache
rotates too quickly, this may not be a good idea.


For a local reuse of previously computes value, you would have to be
able to relate local instance of computation. This means passing your
set to each operation and do the processing:

OP1::compute(param, ResultSet)
{
if (!ResultSet.isSet(OP1))
{
//compute OP1
ResultSet[OP1]=result;
}
return ResultSet[OP1];
}

And when you need the result of another value (in OP1 by example)
res2=OP2::compute(param,ResultSet);

The difference with your method is that the memoization is specified
locally to the operation and not as a pare-call basis. Note that this
cost an additional parameter.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top