Why my code consumes too much memory even after clearing list?

Question

So i'm trying to solve this problem and the question goes like this

Probably, You all Know About The Famous Japanese Cartoon Character Nobita and Shizuka. Nobita Shizuka are very Good friend. However , Shizuka Love a special kind of string Called Tokushuna.

A string T is called Tokushuna if

The length of the string is greater or equal then 3 (|T| ≥ 3 ) It start and end with a charecter ‘1’ (one) It contain (|T|-2) number of ‘0’ (zero) here |T| = length of string T . Example , 10001 ,101,10001 is Tokushuna string But 1100 ,1111, 0000 is not.

One Day Shizuka Give a problem to nobita and promise to go date with him if he is able to solve this problem. Shizuka give A string S and told to Count number of Tokushuna string can be found from all possible the substring of string S . Nobita wants to go to date with Shizuka But You Know , he is very weak in Math and counting and always get lowest marks in Math . And In this Time Doraemon is not present to help him .So he need your help to solve the problem .

Input First line of the input there is an integer T, the number of test cases. In each test case, you are given a binary string S consisting only 0 and 1.

Subtasks Subtask #1 (50 points) 1 ≤ T ≤ 100 1 ≤ |S| ≤ 100

Subtask #2 (50 points) 1 ≤ T ≤ 100 1 ≤ |S| ≤ 105

Output For each test case output a line Case X: Y where X is the case number and Y is the number of Tokushuna string can be found from all possible the substring of string S

Sample Input
3 10001 10101 1001001001 Output Case 1: 1 Case 2: 2 Case 3: 3

Look, in first case 10001 is itself is Tokushuna string. In second Case 2 Substring S[1-3] 101 and S[3-6] 101 Can be found which is Tokushuna string.

What I've done so far I've already solved the problem but the problem is it shows my code exceeds memory limit (512mb). I'm guessing it is because of the large input size. To solve that I've tried to clear the list which holds all the substring of one string after completing each operation. But this isn't helping.

My code

num = int(input())
num_list = []
for i in range(num):
  i = input()
  num_list.append(i)


def condition(a_list):
  case = 0
  case_no = 1
  sub = []
  for st in a_list:
    sub.append([st[i:j] for i in range(len(st)) for j in range(i + 1, len(st) + 1)])
    for i in sub:
        for item in i:
            if len(item) >= 3 and (item[0] == '1' and item[-1] == '1') and (len(item) - 2 == item.count('0')):
                case += 1

        print("Case {}: {}".format(case_no, case))
        case = 0
        case_no += 1
        sub.clear()

condition(num_list)

Is there any better approach to solve the memory consumption problem?

user_12497139 · Answer

Have you tried taking java heap dump and java thread dump? These will tell the memory leak and also the thread that is consuming memory.

Monty_Hindman_55857 · Answer

Your method of creating all possible substrings won't scale very well to larger problems. If the input string is length N, the number of substrings is N * (N + 1) / 2 -- in other words, the memory needed will grow roughly like N ** 2. That said, it is a bit puzzling to me why your code would exceed 512MB if the length of the input string is always less than 105.

In any case, there is no need to store all of those substrings in memory, because a Tokushuna string cannot contain other Tokushuna strings nested within it:

1       # Leading one.
0...    # Some zeros. Cannot be or contain a Tokushuna.
1       # Trailing one. Could also be the start of the next Tokushuna.

That means a single scan over the string should be sufficient to find them all. You could write your own algorithmic code to scan the characters and keep track of whether it finds a Tokushuna string. But that requires some tedious bookkeeping.

A better option is regex, which is very good at character-by-character analysis:

import sys
import re

# Usage: python foo.py 3 10001 10101 1001001001
cases = sys.argv[2:]

# Match a Tokushuna string without consuming the last '1', using a lookahead.
rgx = re.compile(r'10+(?=1)')

# Check the cases.
for i, c in enumerate(cases):
    matches = list(rgx.finditer(c))
    msg = 'Case {}: {}'.format(i + 1, len(matches))
    print(msg)

If you do not want to use regex, my first instinct would be to start the algorithm by finding the indexes of all of the ones: indexes = [j for j, c in enumerate(case) if c == '1']. Then pair those indexes up: zip(indexes, indexes[1:]). Then iterate over the pairs, checking whether the part in the middle is all zeros.

A small note regarding your current code:

# Rather than this,
sub = []
for st in a_list:
    sub.append([...])    # Incurs memory cost of the temporary list
                         # and a need to drill down to the inner list.
    ...
    sub.clear()          # Also requires a step that's easy to forget.

# just do this.
for st in a_list:
    sub = [...]
    ...

Why my code consumes too much memory even after clearing list?

2 Answers