Databases
StackOverflow2013
Postsdbo
POHow to make this code handle big inputs more efficiently?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to make this code handle big inputs more efficiently?
    primarykey
    data
    text
    <p>Hey. I know this is not a 'refactor my code' site but I made this little piece of code which works perfectly fine with moderately sized input but it's problematic with string of size, say, over 2000.</p> <p>What it does - it takes a string of numbers as a parameter, and it returns the number of ways it can be interpreted as a string of letters, where each letter in the English alphabet is assigned a numeric value according to its lexical position: A -> 1, B-> 2, Z-> 26 etc.</p> <p>Since some letters are represented as two numbers the suffix tree is not unique so there can be multiple interpretations. For example '111' could be both 'AAA', 'KA' and 'AK'.</p> <p>This is my code. It's fairly readable and straightforward but it's problematic because:</p> <ol> <li>It has to copy part of the string every time to call it as argument to the recursive part.</li> <li>It has to store huge strings in the cache so it's very expensive, memory-wise.</li> <li>... it's recursive.</li> </ol> <p>Help much appreciated :)</p> <pre><code>cache = dict() def alpha_code(numbers): """ Returns the number of ways a string of numbers can be interpreted as an alphabetic sequence. """ global cache if numbers in cache: return cache[numbers] ## check the basic cases if numbers.startswith('0'): return 0 if len(numbers) &lt;= 1: return 1 ## dynamic programming part ## obviously we can treat the first (non-zero) ## digit as a single letter and continue - ## '342...' -&gt; C + '42...' total = alpha_code(numbers[1:]) ## the first two digits make for a legal letter ## iff this condition holds ## '2511...' -&gt; Y + '11...' ## '3711...' -&gt; illegal if numbers[:2] &lt;= '26': total += alpha_code(numbers[2:]) cache[numbers] = total return total </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USooboo
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to make this code handle big inputs more efficiently?
      1. USkurczak
      1. VTFavorite
    2. VO
      singulars
      1. POHow to make this code handle big inputs more efficiently?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIf you want it to perform well, don't make it recursive.
      singulars
      1. POHow to make this code handle big inputs more efficiently?
      1. USNoon Silk
    2. COI don't know how to make it non recursive
      singulars
      1. POHow to make this code handle big inputs more efficiently?
      1. USooboo
    3. CORecursion does not make it slow. The numbers[2:] makes it slow. But I don't think you can reduce the algorithm to any O() less than O(n^2).
      singulars
      1. POHow to make this code handle big inputs more efficiently?
      1. USjmucchiello
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload