Ask Your Question
1

Need help converting python code to sage compatible

asked 2019-07-02 12:58:33 +0100

abu safa gravatar image

updated 2019-08-26 21:16:59 +0100

FrédéricC gravatar image

I have a list of 262144 elements in a list created through "itertools.product". Now I have to loop over these elements and multiply it with all other elements, which is taking too much time. (I don't have any issue of memory / cpu)

elements = []
for e in itertools.product(range(4), repeat=9):
    elements.append(e)

for row in elements:
   for col in elements:
      do_calculations(row, col)

def do_calculations(ro, co):
    t = {}
    t[0] = [multiply(c=ro[0], r=co[0])]
    for i in range(1, len(ro)):
        _t = []
        for j in range(i+1):
            _t.append(multiply(c=ro[j], r=co[i-j]))
        t[i] = _t

        for vals in t.values():
            nx = len(vals)
            _co = ro[nx:]
            _ro = co[nx:]
            for k in range(len(_ro)):
                vals.append(multiply(c=_co[k], r=_ro[k]))

        _t = []
        for k in t.values():
            s = k[0]
            for j in range(1, len(k)):
                s = addition(c=s, r=k[j])
            _t.append(s)
    return _t

def addition(c, r) -> int:
    __a = [[0, 3, 1, 2],
           [3, 2, 0, 1],
           [0, 3, 2, 1],
           [1, 0, 2, 3]]

    return __a[c][r]


def multiply(c, r) -> int:
    __m = [[0, 0, 0, 0],
           [0, 1, 2, 3],
           [0, 3, 1, 2],
           [0, 2, 3, 1]]

    return __m[c][r]

it is taking too much time to process single col with rows.... can any one help me in this? regards

edit retag flag offensive close merge delete

Comments

Exactly what is the problem you're trying to solve? It could be there's already an efficient implementation for it. If nothing else, it looks like most of what you're doing could be done more efficiently using actual matrix objects and/or numpy arrays. But before offering a concrete solution it would help if you could tell us what the original problem is.

Iguananaut gravatar imageIguananaut ( 2019-07-02 14:17:48 +0100 )edit
1

You should first remove the functions addition and multiply. That is to say, define your matrices __a and __m inside the function do_calculations and replace the call addition(c=s, r=k[j]) by __a[s][k[j]] (and similarly with multiply).

vdelecroix gravatar imagevdelecroix ( 2019-07-02 14:50:47 +0100 )edit

i am not solving anything, but generating a result from elements. elements are in shape of list - tuple (000000000, 000000001, ........ 333333332, 333333333) i need to multiply each element with all elements to get the result for single element with respect to all elements. you can say, i am making a grid of element as row and columns and their results in do_calculations, i am solving an algebric like equation. I hope you understand what i am doing

abu safa gravatar imageabu safa ( 2019-07-02 19:50:34 +0100 )edit

is it possible to convert above code and use it in sage? does sage do iterations fast?

abu safa gravatar imageabu safa ( 2019-07-02 20:42:37 +0100 )edit

This question deserves a new tag, such as Nine-billion-names-of-god, but I don't know how to retag a question...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2019-07-04 09:09:22 +0100 )edit

1 Answer

Sort by » oldest newest most voted
2

answered 2019-07-04 09:03:27 +0100

Emmanuel Charpentier gravatar image

I do not understand what you're trying to accomplish (computing the nine billions names of God ?).

I note that you are doing nothing with the result of do_calculations : it's neither used (to what ends ?), printed (where ?) nor stored (where ?).

For argument's sake, let's have a look at the size of problem. your elements are all the nine-long lists whose elements belong to [0, 1, 2, 3]. There are 4^9=262144 of them. Your (potential) table of results has therefore (4^9)^2=68719476736 elements (about seventy billions).

How much time is necessary to compute one element ? Let's see : pick two elements at random and operate on them. Using your original definitions in a Python3-based Sage :

sage: A=tuple(r.sample([0, 1, 2, 3], 9, replace=True).sage())
sage: B=tuple(r.sample([0, 1, 2, 3], 9, replace=True).sage())
sage: time(do_calculations(A,B))
CPU times: user 1.21 ms, sys: 0 ns, total: 1.21 ms
Wall time: 1.22 ms
[0, 0, 0, 0, 0, 1, 1, 1, 0]

You would need about (((4^9)^2)*1.22e-3).n(digits=3)=8.38e7 seconds (i. about (((4^9)^2)*1.22e-3/(24*60*60*365.25)).n(digits=3)=2.66 years) to perform the computations.

Storing the result (using an efficient encoding, i. e. two bits per element) but no previsible gain from string compressin algorithm (since your computation doesn't seem to have any special properties), you would need about 17.5 GB of storage.

Therefore, absent any "interesting" properties of your addition and multiply functions, inducing "interesting" symmetries (i. e. a structure) on the set of your nine-letter words, the "brute-force" approach is doomed.

May I suggest that using (a part of) 2.66 years to study the possible algebraic properties of your elements and operations might be more fruitful ?

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2019-07-02 12:58:33 +0100

Seen: 828 times

Last updated: Jul 04 '19