Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Peter Otten <__peter__@web.de>
Subject: Re: MemoryError in data conversion
Date: Mon, 14 Apr 2014 09:46:48 +0200
Organization: None
References: <lifelc$ccj$1@news.albasani.net>
Mime-Version: 1.0
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 7Bit
User-Agent: KNode/4.11.5
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.9239.1397461622.18130.python-list@python.org>
Lines: 90
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:70208

Mok-Kong Shen wrote:

> The code attached below produces in one of the two IMHO similar cases
> (excepting the sizes of the lists involved) MemoryError. Could experts
> kindly tell why that's so and whether there is any work-around feasible.

Here's a simpler way to reproduce the error:

>>> import ast
>>> def nested_list_literal(n):
...     return "[" * n + "42" + "]" * n
... 
>>> ast.literal_eval(nested_list_literal(98))
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[42]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
>>> ast.literal_eval(nested_list_literal(99))
s_push: parser stack overflow
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.3/ast.py", line 47, in literal_eval
    node_or_string = parse(node_or_string, mode='eval')
  File "/usr/lib/python3.3/ast.py", line 35, in parse
    return compile(source, filename, mode, PyCF_ONLY_AST)
MemoryError

You ran into a limitation of the compiler. For us to suggest a workaround 
you'd have to explain why you want to convert the list returned from 
buildhuffmantree() into python source code and back.

> Thanks in advances.
> 
> M. K. Shen
> 
> -----------------------------------------------------------------
> 
> import ast
> 
> def buildhuffmantree(slist,flist):
>    item=slist[:]
>    freq=flist[:]
>    while len(item)>2:
>      mn=min(freq)
>      id=freq.index(mn)
>      u=item[id]
>      del item[id]
>      del freq[id]
>      mn1=min(freq)
>      id=freq.index(mn1)
>      v=item[id]
>      del item[id]
>      del freq[id]
>      item.append([u,v])
>      freq.append(mn+mn1)
>    return(item)
> 
> def processing(slist,flist):
>    bintree=buildhuffmantree(slist,flist)
>    print(bintree)
>    byarray=bytearray(str(bintree),"latin-1")
>    bintree1=ast.literal_eval(byarray.decode("latin-1"))
>    print(bintree1)
>    print(bintree==bintree1)
> 
> slist1=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 'eof']
> 
> flist1=[18, 16, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, -1]
> 
> slist2=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
>          18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,
>          34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
>          50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65,
>          66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81,
>          82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97,
>          98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110,
>          111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123,
>          124, 125, 126, 127, 'eof']
> 
> flist2=[2, 2, 0, 2, 0, 0, 1, 2, 1, 0, 2, 0, 0, 1, 1, 0, 2, 0, 0, 0, 1,
>          0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0,
>          0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
>          0, 1, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,
>          0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0,
>          0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
>          0, 0, -1]
> 
> processing(slist1,flist1)  ### This works fine
> print()
> 
> processing(slist2,flist2)  ### This leads to MemoryError