Merged.

I didn't expect huge savings in typical configurations. Unless you have a huge
number of PDBs, one int per variable or one bit per operator of the task won't
matter all that much. It will be important when we have lots of tiny patterns,
though, and this is a case that may well arise with our new PDB work.

I'm fine with merging.

Experiments show little difference between the old and new versions. Some gapdb
runs have different number of expansions which is probably caused by the bugfix
in mean calculation. There is a positive overall trend for expansions (gapdb),
time and memory but the effect is minimal. This is somewhat unexpected: I was
hoping to see larger memory savings in ipdb runs that are dominated by
hillclimbing. Could be that the default config creates fewer and larger PDBs
than the config I tested with before (msg3756) so the overhead is less
noticeable. Anyway, I think we should merge this. What do you think?

http://ai.cs.unibas.ch/_tmp_files/pommeren/issue488-base-issue488-v1-compare.html

Everything looks fine.

> Is this intended?

No, this is a bug.

Ok, I implemented this using std::binary_search, since we know that the pattern
is sorted, so its only logarithmic in the pattern size. I removed the data of
point 1) and fixed the comments. For the average h value, I only fixed the
comments: empty patterns already lead to one abstract state with heuristic value
0 so the method already returned 0 for empty patterns.

The comment also says that
  "dead-ends are ignored (they neither increase the sum of all h-values nor the
   number of entries for the mean value calculation"
Which sounds to me like a PDB {s1 -> inf, s2 -> 10} should have an average value
of 10 whereas the code calculates 10/num_states = 5. Is this intended?

The code is uploaded at
https://bitbucket.org/flogo/downward-issues-issue488/pull-request/1/issue488/diff
Silvan, can you do a review?

On the other hand... something that scales linearly in the pattern size is
perhaps a bit special because we *know* pattern size is never going to be more
than logarithmic in our memory size, and generally logarithmic sins in algorithm
complexity are forgivable if we're not looking at a typical bottleneck (which is
clearly the case here). So I think I'd be fine with the approach you suggested.
It has the nice advantage of simplicity.

I'm generally not a fan of algorithms with worse big-O performance than what is
easily available with other algorithms, so if that's the price of not computing
the information in batch, I'd rather not. (I have network problems today so
can't check this out, but I don't think vectors have a count method, as it
cannot be efficiently implemented.)

It would be possible to compute this efficiently without computing it in batch
if we maintain a hash_set of vector<bool> for the pattern variables, but of
course this again entails a memory cost.

How about a method like "is_operator_relevant(const Operator &)" instead of
computing a vector and then iterating over it. I did not look at all details
yet, but it seems to me we can just check if any effect of the operator affects
a variable in the pattern. Since out patterns are smallish, a for loop over the
effects with calls to pattern.count() should be fast enough.

Regarding 1), we should definitely get rid of data that we don't need.

Regarding 2), I'd prefer the least complex suggestion in terms of maintenance,
data integrity etc., which I think means adding a flag to turn storage on/off
isn't the most preferred solution. From the way this is currently used, I'd
suggest simply adding a method that computes this information on demand and
returns a vector of relevant operators. Rather than returning a vector<bool>, it
would be preferable to return a vector of indices. The method should be called
something like "compute_..." rather than "get_..." to make clear it requires
substantial computation rather than just returning a stored attribute.

Once we do this, I think we can also get rid of "op_no" attributes in various
places, and build_abstract_operator could perhaps be passed an operator rather
than an operator number.

Looking over the class, I also found two small things that we might fix at the
same time:

- I don't think it makes sense to report the average h value for an empty
pattern as infinity. It should be 0. Are we supporting empty patterns properly
everywhere?

- The comments in the header file are very nice, but they should be rewrapped to
our usual line length.

To get a sense of this, I ran a memory profile on an airport task and got 15.6
MB for variable_to_index, 2.3 MB for distances, 1.2 MB for relevant_operators.

The PDB heuristic keeps two large objects around that we could avoid. In particular:

1) variable_to_index
   Vector<int> with one entry for each variable in the original task.
   This is only used during initialization.

2) relevant_operators
   Vector<bool> with one entry for each operator in the original task.
   This is only used by zero-one pdbs and the pho heuristic (which is not merged
yet).

I suggest to change 1) into a local variable passed around as a parameter. For
2) I suggest either turning storage on/off with a parameter or calculating it on
demand by iterating over all operators and pattern variables.