0
\$\begingroup\$

The task is to store the newest ~100 numbers and calculate their sum.

I would like to optimize for time-performance.

Usage: In the context of sequence alignment, after creating a 2D scoring-matrix between 2 sequences, starting at the bottom right corner, I want to search for the optimal alignment path. Here I adapt previous alignment algorithms to search for the optimal alignment at a fixed alignment length. For this, the sum of the previous path isn't sufficient, but instead I want to save the values of the previous path into each cell.

storage = []
new_number = 1

def store_numbers(storage, new_number, storage_size = 100):
    storage.append(new_number)
    if len(storage)>storage_size:
        del storage[0]
    return storage, sum(storage)


#test
for x in range(100):
    print(store_numbers(storage, x, storage_size = 10)

Ideas: Avoid the function? Avoid append() - del() and instead overwrite? Instead of list use Numpy array or something else?

\$\endgroup\$
4
  • \$\begingroup\$ Can you add some details about what this function is used for(not what it does)? \$\endgroup\$ – schissmantics Jan 15 '20 at 13:13
  • 3
    \$\begingroup\$ post the actual context of calling store_numbers function (not fictitious printing) \$\endgroup\$ – RomanPerekhrest Jan 15 '20 at 13:17
  • \$\begingroup\$ Keep track of the sum incerementally. When adding item to the queue make addition to the sum. When a number Is being extracted from the queue subtract it from the sum. When consumer asks for sum return the accumulated value. \$\endgroup\$ – slepic Jan 16 '20 at 6:31
  • \$\begingroup\$ Is this your real code? What's the actual usage look like? You're missing a ) on your last line. \$\endgroup\$ – Mast Jan 16 '20 at 14:15
4
\$\begingroup\$

You could make your life way easier if you used the deque data structure.

from collections import deque

d = deque(maxlen=2)
d.append(1)
d.append(2)
d.append(3)

sum(d)  # gives 5, which is the sum of the last two inserted elements.

With this, you call the sum function only when you really need to, which will improve your performance if you don't need the sum every time (like when you're first populating the container).

Also, deque probably has faster length checking internally than using len onto a list.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks, that's a really handy solution! And it seems to run really fast! \$\endgroup\$ – KaPy3141 Jan 15 '20 at 13:36
0
\$\begingroup\$

I had a bit too much fun playing with this and came up with a circular list implementation with a running total that's not much of a win (or sometimes even slower) for smaller sizes but gets a lot faster as you scale up. The fun part was coming up with a nice framework for testing different implementations with different sizes (I used both your original implementation and Ignacio's deque as references) -- even if my implementation isn't useful for your case I hope it serves as a good example of test-driven development. :)

from abc import abstractmethod
from collections import deque
from time import time
from typing import Deque, Iterable, List, Tuple, Type

class NumberStorage:

    def __init__(self, storage_size: int) -> None:
        self._capacity = storage_size

    @abstractmethod
    def store(self, new_number: int) -> Tuple[Iterable[int], int]:
        """
        Stores the new number, dropping the oldest number if capacity is exceeded.
        Returns an iterable of all the stored numbers, and their sum.
        """
        pass

class NaiveStorage(NumberStorage):

    def __init__(self, storage_size: int) -> None:
        super().__init__(storage_size)
        self._storage: List[int] = []

    def store(self, new_number: int) -> Tuple[List[int], int]:
        self._storage.append(new_number)
        if len(self._storage) > self._capacity:
            del self._storage[0]
        return self._storage, sum(self._storage)

class DequeStorage(NumberStorage):

    def __init__(self, storage_size: int) -> None:
        super().__init__(storage_size)
        self._storage: Deque[int] = deque(maxlen=storage_size)

    def store(self, new_number: int) -> Tuple[Deque[int], int]:
        self._storage.append(new_number)
        return self._storage, sum(self._storage)

class CircularStorage(NumberStorage):

    def __init__(self, storage_size: int) -> None:
        super().__init__(storage_size)
        self._oldest = 0
        self._total = 0
        self._storage: List[int] = []

    def store(self, new_number: int) -> Tuple[List[int], int]:
        self._total += new_number
        if len(self._storage) < self._capacity:
            self._storage.append(new_number)
        else:
            self._total -= self._storage[self._oldest]
            self._storage[self._oldest] = new_number
            self._oldest += 1
            if self._oldest == self._capacity:
                self._oldest = 0
        return self._storage, self._total

def test_storage(
    storage_type: Type[NumberStorage], 
    capacity: int, 
    iterations: int, 
) -> None:
    start_time = time()
    storage = storage_type(capacity)
    for x in range(iterations):
        _, total = storage.store(x)
    print("{}\t(max={}, n={}) \tsum: {}\ttime : {}".format(
        storage_type.__name__,
        capacity,
        iterations,
        total,
        time() - start_time),
    )

for capacity, iterations in [(10**1, 10**2), (10**2, 10**4), (10**3, 10**6)]:
    for storage in (NaiveStorage, DequeStorage, CircularStorage):
        test_storage(storage, capacity, iterations)

My output is:

NaiveStorage    (max=10, n=100)         sum: 945        time : 0.0
DequeStorage    (max=10, n=100)         sum: 945        time : 0.0
CircularStorage (max=10, n=100)         sum: 945        time : 0.0
NaiveStorage    (max=100, n=10000)      sum: 994950     time : 0.014982223510742188
DequeStorage    (max=100, n=10000)      sum: 994950     time : 0.0159609317779541
CircularStorage (max=100, n=10000)      sum: 994950     time : 0.009946107864379883
NaiveStorage    (max=1000, n=1000000)   sum: 999499500  time : 12.579213619232178
DequeStorage    (max=1000, n=1000000)   sum: 999499500  time : 13.003407716751099
CircularStorage (max=1000, n=1000000)   sum: 999499500  time : 1.1614789962768555
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ – Toby Speight Jan 15 '20 at 18:02
  • 1
    \$\begingroup\$ As long as you are storing information (storage size) with the object, you could also store the "start" position. Then no size tests or Deque function calls are needed to save a new number; simply store it at position [start++%size]. \$\endgroup\$ – Ray Butterworth Jan 16 '20 at 1:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.