Speed up STV

[gabeschoenbach]

The bottleneck here is remove_cand(), which had been deepcopying the list of ballots. We switch to using the pickle module instead of deepcopy because it's quicker. For the future, if we can figure out a way to not copy all the ballots, that would speed things up even more.

[gabeschoenbach]

FYI, here was the pytest output when we don't copy ballots at all:

=================================================== test session starts ====================================================
platform darwin -- Python 3.9.16, pytest-7.4.0, pluggy-1.2.0
rootdir: /Users/gabe/Desktop/mggg/summer23/VoteKit
plugins: cov-4.1.0, anyio-3.7.0
collected 16 items                                                                                                         

tests/test_elections.py ......F...F.F...                                                                             [100%]

========================================================= FAILURES =========================================================
_______________________________________________ test_remove_cand_not_inplace _______________________________________________

    def test_remove_cand_not_inplace():
        remove = "a"
        ballots = test_profile.get_ballots()
        new_ballots = remove_cand(remove, ballots)
>       assert ballots != new_ballots
E       AssertionError: assert [Ballot(id=None, ranking=[{'b'}, {'c'}], weight=Fraction(2, 1), voters=None), Ballot(id=None, ranking=[{'c'}, {'b'}], ... weight=Fraction(1, 1), voters=None), Ballot(id=None, ranking=[{'b'}, {'e'}], weight=Fraction(1, 1), voters=None), ...] != [Ballot(id=None, ranking=[{'b'}, {'c'}], weight=Fraction(2, 1), voters=None), Ballot(id=None, ranking=[{'c'}, {'b'}], ... weight=Fraction(1, 1), voters=None), Ballot(id=None, ranking=[{'b'}, {'e'}], weight=Fraction(1, 1), voters=None), ...]

tests/test_elections.py:98: AssertionError
____________________________________________________ test_stv_winner_mn ____________________________________________________

    def test_stv_winner_mn():
        irv = STV(mn_profile, fractional_transfer, 3)
>       outcome = irv.run_election()

tests/test_elections.py:126: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
src/votekit/election_types.py:125: in run_election
    self.run_step()
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

self = <votekit.election_types.STV object at 0x11a55d520>

    def run_step(self) -> ElectionState:
        """
        Simulates one round an STV election
        """
        ##TODO:must change the way we pass winner_votes
        remaining: list[str] = self.election_state.remaining
        ballots: list[Ballot] = self.election_state.profile.get_ballots()
        fp_votes = compute_votes(remaining, ballots)  ##fp means first place
        elected = []
        eliminated = []

        # if number of remaining candidates equals number of remaining seats,
        # everyone is elected
        if len(remaining) == self.seats - len(self.election_state.get_all_winners()):
            elected = [cand for cand, votes in fp_votes]
            remaining = []
            ballots = []
            # TODO: sort remaining candidates by vote share

        # elect all candidates who crossed threshold
>       elif fp_votes[0].votes >= self.threshold:
E       IndexError: list index out of range

src/votekit/election_types.py:81: IndexError
______________________________________________ test_runstep_update_inplace_mn ______________________________________________

    def test_runstep_update_inplace_mn():
        irv = STV(mn_profile, fractional_transfer, 1)
>       out = irv.run_step()

tests/test_elections.py:139: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

self = <votekit.election_types.STV object at 0x11a5eaa00>

    def run_step(self) -> ElectionState:
        """
        Simulates one round an STV election
        """
        ##TODO:must change the way we pass winner_votes
        remaining: list[str] = self.election_state.remaining
        ballots: list[Ballot] = self.election_state.profile.get_ballots()
        fp_votes = compute_votes(remaining, ballots)  ##fp means first place
        elected = []
        eliminated = []

        # if number of remaining candidates equals number of remaining seats,
        # everyone is elected
        if len(remaining) == self.seats - len(self.election_state.get_all_winners()):
            elected = [cand for cand, votes in fp_votes]
            remaining = []
            ballots = []
            # TODO: sort remaining candidates by vote share

        # elect all candidates who crossed threshold
>       elif fp_votes[0].votes >= self.threshold:
E       IndexError: list index out of range

src/votekit/election_types.py:81: IndexError
================================================= short test summary info ==================================================
FAILED tests/test_elections.py::test_remove_cand_not_inplace - AssertionError: assert [Ballot(id=None, ranking=[{'b'}, {'c'}], weight=Fraction(2, 1), voters=None), Ballot(id=None, ra...
FAILED tests/test_elections.py::test_stv_winner_mn - IndexError: list index out of range
FAILED tests/test_elections.py::test_runstep_update_inplace_mn - IndexError: list index out of range
=============================================== 3 failed, 13 passed in 3.47s ===============================================