dwavesystems / dwave-greedy Goto Github PK

I'm seeing a performance regression in steepest descent in Ocean 4.1 vs Ocean 3.5. With Ocean 3.5, the sample code runs in about 2.4s, whereas with Ocean 4.1 it runs in about 3.9s. Is this expected? From what I can tell, they're both using the same version of greedy, so it seems surprising.

from time import perf_counter

import dimod
import greedy

bqm = dimod.generators.anti_crossing_clique(150)
sampler = greedy.SteepestDescentSolver()

def solve(bqm, sampler):
    results = sampler.sample(bqm, num_reads=50000)
    return results.first

tic = perf_counter()
first = solve(bqm, sampler)
toc = perf_counter()

print(toc-tic)

(Use of anti_crossing_clique as the test BQM is not significant, I just wanted something deterministic. I also saw similar differences with randomly generated BQM's.)

This is the same as dwavesystems/dimod#1169

Posting this more as an FYI than a request for help as it's not super high priority.

Logs: https://dev.azure.com/conda-forge/feedstock-builds/_build/results?buildId=504553&view=logs&jobId=517fe804-fa30-5dc2-1413-330699242c05&j=517fe804-fa30-5dc2-1413-330699242c05&t=c10fa5f2-fdf6-5338-3bdb-c4bea7c23412

I'm using greedy to post-process a sampleset. It would be great if when a sampleset is passed as initial_states, a copy of that same sampleset with greedy post-processing is returned.
The current behaviour makes a new sampleset, which doesn't keep the rest of metadata.

Desired use:

result = DWaveSampler().sample(bqm)
greedy_pp = greedy.SteepestDescentSolver().post_process(bqm, sampleset=result)

Ref: initial_states of SteepestDescentSolver.sample().

Keeping N samples in memory is expensive if we only want the k best ones!

Open question is the interface -- num_reads is synonymous with num_samples returned in sample set for all samplers in Ocean. Also, initial_states (even for random states) are expanded to num_reads input samples -- something we would also want to avoid in this case.

To retain compatible behavior with existing samplers, perhaps we could introduce a parameter like num_resample. Also, resample_reduce_method (min/max). And to support the k best samples use case, we'll need a parameter like num_samples.

So, something like:

ss = greedy.sample(bqm, num_reads=1, num_resample=1000, num_samples=3, resample_reduce_method='k-best')

Another take on this would be async sampler interface. In which case a caller would yield as many samples are needed, all with minimal memory overhead!