LiamM32 / Eurovision_Condorcet

A program to count votes for the Eurovision Song Contest using a redesigned voting system.
1 stars 2 forks source link

Slow because of calls to Election::getResult() #5

Closed LiamM32 closed 1 year ago

LiamM32 commented 1 year ago

The version of this program in the master branch currently takes a long time because there are too many calls to Election::getResult(). It is in line 28 of EurovisionSchulze.php. $this->filteredPairwise[$country] = $contest->getResult(methodOptions: ['%tagFilter' => true, 'withTag' => true, 'tags' => $country])->pairwise; The most likely underlying problem is that this function does more than what is required during this loop. It doesn't only get one pairwise comparison, but all pairwise comparison using votes with the specified tag.

The faster branch has been made with a modified version of EurovisionSchulze.php. This one is currently much faster because it calls Election::getResult() fewer times; only once per voting country.

However, I put this in a new branch instead of the master because this method may no longer be optimal if Condorcet gets a new function for getting pairwise comparisons from a filtered set of votes.

julien-boudry commented 1 year ago

Merge your cache system, having a new version of the pairwise API can take time, and maybe not so efficient for your case because you need cache first. The new API will allow filtering pairwise with the tag (without the need for result computing), but will not provide the cache.

Two other little optimization strategies can help (choose one, not both):

  1. Could be to call getResult(method: 'Copeland', ...), because the default method is Schulze, but Copeland is a little bit faster.

  2. More ambitious and experimental (I didn't try), keep a cache system, but do like that:

    $filteredElection = clone $election;
    $filteredElection->removeVotesByTags(tags: $country, with: false);
    $pairwise = $filteredElection->getExplicitPairwise(); // Or work with the non-explicit pairwise, even faster and better, non-explicit use internal key instead of candidates names.

It must be better because internally, the compiler doesn't duplicate vote object memory, and votes are already parsed. And you don't need to compute the Result, but directly the pairwise.

LiamM32 commented 1 year ago

Are you saying that when I call $contest->getResult()->pairwise, I should use Copeland? Why would this make a difference? If this function only gets pairwise comparisons, not the final ranking, why would it be different for each voting method?

Or are you suggesting that I make the whole process Copeland instead of Schulze?

julien-boudry commented 1 year ago

It's just a little hacky optimization. Pairwise will be the same, but getResult do more than pairwise, including computing Schulze (by default) wich is slower than Copeland.

julien-boudry commented 1 year ago

The real solution, I agree : is to get filtered Pairwise without using getResult. But will take some time to do properly.

LiamM32 commented 1 year ago

So every time it runs the Schulze method, it runs the Schulze method multiple times within the Schulze method?

julien-boudry commented 1 year ago

Every time it runs your method, It runs many time Schulze method for nothing (because it's the filtered pairwise that you want).

julien-boudry commented 1 year ago

https://github.com/julien-boudry/Condorcet/pull/152