6

I'm quite new to python, so I'm doing my usual of going through Project Euler to work out the logical kinks in my head.

Basically, I need the largest list size possible, ie range(1,n), without overflowing.

Any ideas?

2
  • 1
    I'm not totally sure what you're doing with range, but remember that for many Project Euler problems, brute-forcing will take an incredible amount of time and/or memory. This isn't to say that developing a brute-force method is always bad; on the contrary, you can test the same (shortened) inputs to that and an optimized routine you designed and make sure they give the same result. On the other hand, some of the problems are totally trivial because of Python's (or any other lang's) arbitrarily long integers (16, 20, 48, 97).
    – Nick T
    Jul 14, 2010 at 16:44
  • Just messing around with some map/reduce/filtering stuff. It worked, but I moved on to a more 'elegant' solution. I'm doing euler to learn the language because I'm terrible at just reading 'tutorials'
    – Bolster
    Jul 14, 2010 at 17:01

2 Answers 2

8

Look at get_len_of_range and get_len_of_range_longs in the builtin module source

Summary: You'll get an OverflowError if the list has more elements than can be fit into a signed long. On 32bit Python that's 2**31 - 1, and on 64 bit Python that's 2**63 - 1. Of course, you will get a MemoryError even for values just under that.

2
  • I thought that the sys.maxsize limit only applied to xrange, not to Python 2's range. Of course it's pretty academic unless you have a great deal of memory... Jul 14, 2010 at 16:00
  • Quick follow up question; any easy way to query python as to how much it can cope with at the minute?
    – Bolster
    Jul 14, 2010 at 16:18
0

The size of your lists is only limited by your memory. Note that, depending on your version of Python, range(1, 9999999999999999) needs only a few bytes of RAM since it always only creates a single element of the virtual list it returns.

If you want to instantiate the list, use list(range(1,n)) (this will copy the virtual list).

3
  • 1
    Are you assuming 3.x? On 2.x this is incorrect for the reason given in my own answer, and on 3.x it's still incorrect as long as you interpret "list" literally: list size is bound by ssize_t . Anyway, it's really silly to simply assume people are using 3.x . Jul 14, 2010 at 15:56
  • There is no doubt he's assuming 3.x; sys.getsizeof(range(1e8)) returns 400000036 on 2.6 (and takes a noticeable time to compute). The 3.x analogy would be sys.getsizeof(xrange(1e8)) that gives 20 and is instant.
    – Nick T
    Jul 14, 2010 at 16:49
  • 3
    Which part if "depending on your version of Python" didn't you understand? :-( Jul 15, 2010 at 10:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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