85

For example, files, in Python, are iterable - they iterate over the lines in the file. I want to count the number of lines.

One quick way is to do this:

lines = len(list(open(fname)))

However, this loads the whole file into memory (at once). This rather defeats the purpose of an iterator (which only needs to keep the current line in memory).

This doesn't work:

lines = len(line for line in open(fname))

as generators don't have a length.

Is there any way to do this short of defining a count function?

def count(i):
    c = 0
    for el in i: c += 1
    return c

To clarify, I understand that the whole file will have to be read! I just don't want it in memory all at once

3
  • to count the number of lines you will load the file in memory anyway!
    – hasen
    Dec 24, 2008 at 6:00
  • lists (all sequence types) are iterables as well. what you mean is "iterator"
    – user3850
    Dec 24, 2008 at 7:09
  • 4
    @hasen: yes, but not all at once.
    – Claudiu
    Dec 24, 2008 at 7:52

10 Answers 10

95

Short of iterating through the iterable and counting the number of iterations, no. That's what makes it an iterable and not a list. This isn't really even a python-specific problem. Look at the classic linked-list data structure. Finding the length is an O(n) operation that involves iterating the whole list to find the number of elements.

As mcrute mentioned above, you can probably reduce your function to:

def count_iterable(i):
    return sum(1 for e in i)

Of course, if you're defining your own iterable object you can always implement __len__ yourself and keep an element count somewhere.

6
  • this could be improved with an itertools.tee()
    – user3850
    Dec 25, 2008 at 20:16
  • 1
    @Matt Joiner: calling count_iterable consumes the iterator, so you wouldn't be able to do anything further with it. Copying the iterator with i, i2 = itertools.tee(i) beforehand would solve that problem, but it doesn't work within the function, because count_iterable can't change its argument as a side effect (but defining a function for a simple sum() strikes me as unnecessary anyway…). I think that was more or less my reasoning 2 years ago. Thinking about it further, I'd probably use .seek(0) instead (and rename the function, since it wouldn't work for arbitrary iterators anymore).
    – user3850
    Apr 18, 2011 at 23:50
  • 4
    strike itertools.tee. i always forget that it has to put the data from the original iterator somewhere, which goes directly against what the op wants.
    – user3850
    Apr 19, 2011 at 15:04
  • 2
    That's right. If you had to consume the whole iterable to get the count, you'd effectively be loading all the data in to tee's temporary storage until it was consumed by the other iterator. Apr 20, 2011 at 22:32
  • Excellent and concise solution, slightly improved by using a wildcard, as in sum(1 for _ in i). I only suggested this because PyCharm pointed out the unused loop variable. Thank you PyCharm! Dec 20, 2018 at 13:21
25

If you need a count of lines you can do this, I don't know of any better way to do it:

line_count = sum(1 for line in open("yourfile.txt"))
17

The cardinality package provides an efficient count() function and some related functions to count and check the size of any iterable: http://cardinality.readthedocs.org/

import cardinality

it = some_iterable(...)
print(cardinality.count(it))

Internally it uses enumerate() and collections.deque() to move all the actual looping and counting logic to the C level, resulting in a considerable speedup over for loops in Python.

12

I've used this redefinition for some time now:

def len(thingy):
    try:
        return thingy.__len__()
    except AttributeError:
        return sum(1 for item in iter(thingy))
5
  • 1
    It can never returns... See Triptych's example.
    – bortzmeyer
    Dec 24, 2008 at 8:39
  • 5
    "use with care" aka "we're all consenting adults", one of the tenets of Python. At least it was one, once. Nov 10, 2014 at 8:01
  • 2
    There is no reason to explicitly call __len__ or iter here; plain len(thingy) invokes __len__ in the standard way, and iterating over anything implicitly converts it to an iterator, so for item in iter(thingy) is just a slower, longer way to spell for item in thingy. Nov 8, 2018 at 15:18
  • 1
    @ShadowRanger: If you're redefining len, trying to call len will give you a bad time Dec 21, 2018 at 18:31
  • 1
    @Kundor: Hah! True. Missed that it was actually redefining len, not just providing a broader definition of it. Personally, I'd just make a backup copy of len so I have it available in the function, e.g. adding _len = len before the redefinition, then using _len inside the replacement function. I try to avoid manually calling special methods directly when possible (it's uglier, and at least pre-3.7, actually slower than calling the built-in because it must construct a bound method that len() avoids). Dec 21, 2018 at 19:07
11

It turns out there is an implemented solution for this common problem. Consider using the ilen() function from more_itertools.

more_itertools.ilen(iterable)

An example of printing a number of lines in a file (we use the with statement to safely handle closing files):

# Example
import more_itertools

with open("foo.py", "r+") as f:
    print(more_itertools.ilen(f))

# Output: 433

This example returns the same result as solutions presented earlier for totaling lines in a file:

# Equivalent code
with open("foo.py", "r+") as f:
    print(sum(1 for line in f))

# Output: 433
8

Absolutely not, for the simple reason that iterables are not guaranteed to be finite.

Consider this perfectly legal generator function:

def forever():
    while True:
        yield "I will run forever"

Attempting to calculate the length of this function with len([x for x in forever()]) will clearly not work.

As you noted, much of the purpose of iterators/generators is to be able to work on a large dataset without loading it all into memory. The fact that you can't get an immediate length should be considered a tradeoff.

7
  • 28
    It's also true for sum(), max() and min() but this aggregate functions take iterables.
    – ttepasse
    Dec 24, 2008 at 9:31
  • 12
    i downvoted this, mainly for the "absolutely," which is just not true. anything that implements __len__() has a length -- infinite, or not.
    – user3850
    Dec 24, 2008 at 11:04
  • 1
    @hop, the question is about iterables in the general case. iterables that implement len are a special case. Dec 24, 2008 at 14:50
  • 4
    @Triptych Yes, but as hop says, starting with "absolutely" implies universal applicability, including all special cases. Dec 25, 2008 at 12:50
  • 2
    Yes, if an infinite generator is given it will never terminate. But this does not mean that the idea is meaningless in all cases. A simple warning in the docstring that states this limitation would be sufficient for correct use. Apr 14, 2013 at 14:52
3

Because apparently the duplication wasn't noticed at the time, I'll post an extract from my answer to the duplicate here as well:

There is a way to perform meaningfully faster than sum(1 for i in it) when the iterable may be long (and not meaningfully slower when the iterable is short), while maintaining fixed memory overhead behavior (unlike len(list(it))) to avoid swap thrashing and reallocation overhead for larger inputs.

# On Python 2 only, get zip that lazily generates results instead of returning list
from future_builtins import zip

from collections import deque
from itertools import count

def ilen(it):
    # Make a stateful counting iterator
    cnt = count()
    # zip it with the input iterator, then drain until input exhausted at C level
    deque(zip(it, cnt), 0) # cnt must be second zip arg to avoid advancing too far
    # Since count 0 based, the next value is the count
    return next(cnt)

Like len(list(it)), ilen(it) performs the loop in C code on CPython (deque, count and zip are all implemented in C); avoiding byte code execution per loop is usually the key to performance in CPython.

Rather than repeat all the performance numbers here, I'll just point you to my answer with the full perf details.

1
  • In my testing (on Python 3.7.3, standard cpython interpreter), this is the fastest of all the methods which don't put the whole iterable in memory. Aug 19, 2019 at 17:28
1

For filtering, this variation can be used:

sum(is_good(item) for item in iterable)

which can be naturally read as "count good items" and is shorter and simpler (although perhaps less idiomatic) than:

sum(1 for item in iterable if is_good(item)))

Note: The fact that True evaluates to 1 in numeric contexts is specified in the docs (https://docs.python.org/3.6/library/stdtypes.html#boolean-values), so this coercion is not a hack (as opposed to some other languages like C/C++).

1
  • 1
    Note that, as an implementation detail on CPython, the latter is faster; the filtering in the genexpr reduces the number of (moderately expensive) transitions in and out of the generator, and sum is specifically optimized for int inputs (exact int; bool being a subclass doesn't count), so producing True forces it to take the slow (Python object) path, while producing 1 lets it use the fast (C long) path (until the sum exceeds the capacity of a C long anyway). Nov 8, 2018 at 15:38
0

We'll, if you think about it, how do you propose you find the number of lines in a file without reading the whole file for newlines? Sure, you can find the size of the file, and if you can gurantee that the length of a line is x, you can get the number of lines in a file. But unless you have some kind of constraint, I fail to see how this can work at all. Also, since iterables can be infinitely long...

1
  • 4
    i do want to read the whole file, i just don't want it in memory all at once
    – Claudiu
    Dec 24, 2008 at 7:53
-1

I did a test between the two common procedures in some code of mine, which finds how many graphs on n vertices there are, to see which method of counting elements of a generated list goes faster. Sage has a generator graphs(n) which generates all graphs on n vertices. I created two functions which obtain the length of a list obtained by an iterator in two different ways and timed each of them (averaging over 100 test runs) using the time.time() function. The functions were as follows:

def test_code_list(n):
    l = graphs(n)
    return len(list(l))

and

def test_code_sum(n):
    S = sum(1 for _ in graphs(n))
    return S

Now I time each method

import time

t0 = time.time()
for i in range(100):
    test_code_list(5)
t1 = time.time()

avg_time = (t1-t0)/10

print 'average list method time = %s' % avg_time


t0 = time.time()
for i in range(100):
    test_code_sum(5)
t1 = time.time()

avg_time = (t1-t0)/100

print "average sum method time = %s" % avg_time

average list method time = 0.0391882109642

average sum method time = 0.0418473792076

So computing the number of graphs on n=5 vertices this way, the list method is slightly faster (although 100 test runs isn't a great sample size). But when I increased the length of the list being computed by trying graphs on n=7 vertices (i.e. changing graphs(5) to graphs(7)), the result was this:

average list method time = 4.14753051996

average sum method time = 3.96504004002

In this case the sum method was slightly faster. All in all, the two methods are approximately the same speed but the difference MIGHT depend on the length of your list (it might also just be that I only averaged over 100 test runs, which isn't very high -- would have taken forever otherwise).

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.