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?

Bolster
  • 7,460
  • 13
  • 61
  • 96
  • 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 '10 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 '10 at 17:01

2 Answers2

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.

Devin Jeanpierre
  • 92,913
  • 4
  • 55
  • 79
  • 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... – Scott Griffiths Jul 14 '10 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 '10 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).

Aaron Digulla
  • 321,842
  • 108
  • 597
  • 820
  • 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 . – Devin Jeanpierre Jul 14 '10 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 '10 at 16:49
  • 3
    Which part if "depending on your version of Python" didn't you understand? :-( – Aaron Digulla Jul 15 '10 at 10:15