-3
\$\begingroup\$

Number can be very big.Script is taking number as a "number" list and crossing from 10-decimal based system to n-based system until list equals "5".I don't use letters like in 16-base system(hex).Example if result will be AB5 in hex list will be [10,11,5]. Some ideas how to optimize or/and change this to recursion?Any other hints/ideas for optimizing this code?

r=-1
number = [9,7,1,3,3,6,4,6,5,8,5,3,1]
l=len(number)
p=11
while (number[-1]!=5):
 i=1
 while(i<=l):
  #for x in reversed(xrange(1,i)):
  for x in xrange(i-1,0,-1):
   number[x]+=(number[x-1]*r)
   while(number[x]<0):
    number[x]+=p
    number[x-1]-=1
    if number[0]==0:
     #number.pop(0)
     del number[0]
     i-=1
     l-=1
  i+=1
#print p
 p+=2
 r=-2
print p-2

Algorithm in theory: From start we have some decimal number: 2507 . Base of decimal as everyone know is 10. list=[2, 5, 0, 7] :

    [2, 5, 0, 7]         # 2507 decimal(base 10)

        1.
        l[1]=l[1]+(diff_between_earlier_and_current_base*l[1-1]
        2.
        1.l[2]=l[2]+(diff_between_earlier_and_current_base*l[2-1]
        1.l[1]=l[1]+(diff_between_earlier_and_current_base*l[1-1]
        3.
        1.l[3]=l[3]+(diff_between_earlier_and_current_base*l[3-1]
        1.l[2]=l[2]+(diff_between_earlier_and_current_base*l[2-1]
        1.l[1]=l[1]+(diff_between_earlier_and_current_base*l[1-1]

if some element (while doing this) will be <0 we need to borrow from l[curent-1] until element<0 (if we doing subtraction below the line we are borrowing 10 but when we converting to 11 base we are borrowing 11 so when we have [2,-2] >> [1,9])

    Result in 11 base:
    [1, 9, 7, 10]

I think any way to optimize this is to write my code as recurrent function but i don't know how to do this.Anyone?

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Please add an explanation of what the purpose of this code is. \$\endgroup\$ – Adam Mar 29 '13 at 23:48
  • 2
    \$\begingroup\$ Because it is hard to write good answers without this information. Take a look at the about page: "Focus on questions about an actual problem you have faced. Include details about what you have tried and exactly what you are trying to do." I strongly recommend you follow these guidelines. \$\endgroup\$ – Adam Mar 29 '13 at 23:57
  • 3
    \$\begingroup\$ Can you please update your question to add a precise description of what you are trying to achieve because I'm not quite sure this is very clear now. \$\endgroup\$ – SylvainD Mar 30 '13 at 8:44
  • 4
    \$\begingroup\$ Here's your optimised version of the code : print 17. Please keep in mind that people who have commented here are people who would have been willing to help you if they could understand what you are trying to achieve. \$\endgroup\$ – SylvainD Mar 31 '13 at 0:34
  • 3
    \$\begingroup\$ Actually the site is for improving your code both with performance and style. The biggest problem with your code as it stands is that its inscrutable. It would help us suggest way to make it faster and easier to follow if you'd let us know what the fried monkey it's trying to accomplish. You don't have to tell us what the code is for, but you are much more likely to get help if you do. \$\endgroup\$ – Winston Ewert Apr 2 '13 at 14:29
3
\$\begingroup\$

From the explanation you provided, I think this does what you want to do :

def listToNumber(l,b):
        n=0
        for i in l:
                n = i+b*n
        return n

def numberToList(n,b):
        l=[]
        while n>0:
                l.append(n%b)
                n/=b
        return l[::-1]

l=[9,7,1,3,3,6,4,6,5,8,5,3,1]
base=10
n=listToNumber(l,base)
while numberToList(n,base)[-1] != 5:
        base+=1
print base

Tested on both [9,7,1,3,3,6,4,6,5,8,5,3,1] and [9,7,1,3,3,6,4,6,5,8,5,3,1]*10 , it seems like it returns the same thing but my implementation is much faster and much easier to understand.

A possible improvement would be :

def lastDigitInBase(n,b):
        return n%b

l=[9,7,1,3,3,6,4,6,5,8,5,3,1]*10
base=10
n=listToNumber(l,base)
while lastDigitInBase(n,base) != 5:
        base+=1
print base

On that final version and working with [9,7,1,3,3,6,4,6,5,8,5,3,1]*30, my code returns 13259 in 0.2 seconds while your implementation return the same result in more than 3 minutes and 16 seconds which is roughly 1000 times slower.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ok, but what happened to the stuff he was doing with r? That's the part that still confuses me. \$\endgroup\$ – Winston Ewert Apr 2 '13 at 22:15
  • \$\begingroup\$ I have no idea. My feeling is that the code was way too complicated for what it was trying to achieve. Once I understood the problem, I wrote this simple solution and it seems like it returns the same thing. \$\endgroup\$ – SylvainD Apr 2 '13 at 22:25
  • \$\begingroup\$ Nice.For different number with pypy: my: Initial run time: 1.15500020981 , yours: Initial run time: 0.999000072479 ,but can you write as recursive function without using ">>" , "/" or "%" ? That's the point. \$\endgroup\$ – prosze_wyjsc_z_kosmosu Apr 3 '13 at 0:40
  • \$\begingroup\$ r = previous_base - current_base. The initial step is base-10 -> base-11, hence -1; then base-11 to base-13 (11+2), hence -2. Why he's jumping by 2, I don't know. \$\endgroup\$ – Glenn Rogers Apr 3 '13 at 7:31
  • \$\begingroup\$ Do not think about it, it is intentionally.Base 10 > 11 > 13 > 15 > 17 > 19 > 21.Only odd. \$\endgroup\$ – prosze_wyjsc_z_kosmosu Apr 3 '13 at 11:06
2
\$\begingroup\$

I can't do much to help optimize this code as I don't know what its trying to do.

r=-1
number = [9,7,1,3,3,6,4,6,5,8,5,3,1]

I suggest presenting this as a function which takes number as a parameter. Code also runs faster in functions.

l=len(number)
p=11

Use names that mean things. Single letter variables names make your code hard to read

while (number[-1]!=5):

You don't need the parens.

 i=1
 while(i<=l):
  #for x in reversed(xrange(1,i)):

Delete dead code, don't comment it out

  for x in xrange(i-1,0,-1):
   number[x]+=(number[x-1]*r)

No need for parens, let your binary operates breath with some spaces

   while(number[x]<0):
    number[x]+=p
    number[x-1]-=1



    if number[0]==0:
     #number.pop(0)
     del number[0]
     i-=1
     l-=1

You don't actually gain much by deleting the empty places in the number. Your code will operate just the same if leave them with zeros. It'll simplify your code if you do that.

  i+=1
#print p
 p+=2
 r=-2

Rather then this, add a line

 r = 1 if p == 11 else 2

to the beginning of the loop. That way r is set in only one place

print p-2
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for suggestions.but my script is slower with they. \$\endgroup\$ – prosze_wyjsc_z_kosmosu Apr 2 '13 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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