1
\$\begingroup\$

I'm looking for any possible improvements in terms of memory usage and speed, but really any advice is welcome.

Problem statement:

John has discovered various rocks. Each rock is composed of various elements, and each element is represented by a lower-case Latin letter from 'a' to 'z'. An element can be present multiple times in a rock. An element is called a gem-element if it occurs at least once in each of the rocks.

Given the list of rocks with their compositions, display the number of gem-elements that exist in those rocks.

Input Format

The first line consists of an integer, , the number of rocks. Each of the next lines contains a rock's composition. Each composition consists of lower-case letters of English alphabet.

Constraints Each composition consists of only lower-case Latin letters ('a'-'z'). length of each composition

Output Format

Print the number of gem-elements that are common in these rocks. If there are none, print 0.

My code: Essentially I build N lists of True or False values (since the number of times the same element appears doesn't matter), and at the end just "and" them two by two using reduce to end up with a final list of True values for the elements that were True in each rock, and then just sum up the True values.

import sys
from functools import reduce

# this is just to get test cases input
N = int(input())
strings = []
for i in range(N):
    strings.append(input())

# actual implementation starts here
lists = [[False] * 26 for i in range(N)]

for i in range(N):
    for c in strings[i]:
        # ord() gives the ASCII value of a character
        lists[i][ord(c) - ord('a')] = True

final_list = reduce(lambda x, y: [x[i] and y[i] for i in range(26)], lists)

print(reduce(lambda x, y: x + y, final_list))
\$\endgroup\$
5
\$\begingroup\$

There are several ways you can save memory, where you’re storing more information than you really need. In some cases, way more information than you need.

If you only save what you need, you’ll reduce memory and get a performance benefit to boot!

Memory improvement #1

These three lines are wasting memory:

strings = []
for i in range(N):
    strings.append(input())

You don’t actually need to gather up all the rocks into a list – you’re only ever looking at one at a time. Although in this case it’s unlikely to matter, creating a list when you don’t need one is a bad antipattern.

You can rewrite your code to make the strings list unnecessary, thus saving memory, like so:

lists = [[False] * 26 for i in range(N)]

for i in range(N):
    rock = input()
    for c in rock:
        # ord() gives the ASCII value of a character
        lists[i][ord(c) - ord('a')] = True

Note that this also only features one for loop of length N, which will likely have a (small) benefit to performance.

Memory improvement #2

The lists variable (that’s not a great name, btw) is a 26 x N-sized matrix. Again, this has the potential to get quite large if you have lots of rocks, or lots of different elements. And you’re storing more data than you need to – all we’re interested in is which elements were present in each rock. A simpler way to store that would be something like:

rock_elements = []

for _ in range(N):
    rock = input()
    rock_elements.append(set(rock))

final_list = reduce(lambda x, y: [i in x and i in y for i in range(26)], lists)

Now the rock_elements list only contains the set of elements in each rock. We’re not provisioning lots of unwanted memory for small rocks.

Memory improvement #3

We’re still storing more information than we need. For example, suppose the first rock omits a, and every other rock contains a. Remembering that those later rocks contain a is pointless, because we know that a isn’t a gem-element.

So an even more efficient solution would be to keep a set of possible gem-elements, and throw elements away whenever we find a rock that doesn’t contain them. Like so:

import string

gem_elements = set(string.ascii_lowercase)

for _ in range(N):
    rock = input()
    gem_elements = gem_elements & set(rock)

print(len(gem_elements))

Now our gem_elements set will never be larger than the number of possible elements, and we’re only storing the data for one rock at a time. Much better!

And as a nice side benefit, we’ve got rid of the two calls to reduce(), which are:

  • Generally not very Pythonic – idiomatic Python tends towards list comprehensions and similar rather than reduce() and map().
  • Moderately expensive – I think at least \$O(N)\$ in the number of rocks?
\$\endgroup\$
  • \$\begingroup\$ Thank you for taking the time to write this answer. Every improvement you mention is something i never really think about but that completely makes sense, so this is going to be very helpful going forward. \$\endgroup\$ – jeremy radcliff Jan 22 '17 at 23:17
  • \$\begingroup\$ Just a quick question: Is there any practical point to throwing the loop variable away (when you do for _ in range(N):) besides making it clear that you're not using it in the loop? \$\endgroup\$ – jeremy radcliff Jan 22 '17 at 23:23
  • 2
    \$\begingroup\$ @jeremyradcliff No, Python will allocate a variable just the same if you write for _ in iterable. It’s just a convenience to make the program more readable for future developers. \$\endgroup\$ – alexwlchan Jan 23 '17 at 6:35
  • \$\begingroup\$ Got it, thanks again for your detailed answer. \$\endgroup\$ – jeremy radcliff Jan 23 '17 at 17:08

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.