Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin1!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed3a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.010 X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'subject:not': 0.03; 'tree': 0.05; 'subject:Python': 0.06; 'memory.': 0.07; 'exception,': 0.09; 'exception.': 0.09; 'overflow': 0.09; 'trees': 0.09; 'cc:addr:python-list': 0.11; '>>': 0.16; 'nodes': 0.16; 'exception': 0.16; 'sat,': 0.16; 'wrote:': 0.18; 'stack': 0.19; 'fit': 0.20; 'memory': 0.22; 'email addr:gmail.com>': 0.22; 'cc:addr:python.org': 0.22; 'balancing': 0.24; 'cc:2**0': 0.24; '>': 0.26; 'possibly': 0.26; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; 'message-id:@mail.gmail.com': 0.30; 'url:mailman': 0.30; 'getting': 0.31; 'branches': 0.31; 'quite': 0.32; 'url:python': 0.33; 'maybe': 0.34; "can't": 0.35; 'received:google.com': 0.35; 'really': 0.36; 'done': 0.36; 'url:listinfo': 0.36; 'url:org': 0.36; 'should': 0.36; 'christian': 0.38; 'skip:& 10': 0.38; 'url:mail': 0.40; 'easy': 0.60; 'ian': 0.60; 'hope': 0.61; 'helps': 0.61; 'balance': 0.61; 'entire': 0.61; "you're": 0.61; 'kind': 0.63; 'more': 0.64; 'dont': 0.67; '2015': 0.84; 'irrelevant': 0.84; 'optimisation': 0.84; 'to:none': 0.92 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type; bh=HfBvTxglYmgnOjAzXtTDWo5ZgK5hWx48fmjlD4XaOI4=; b=EMYqtWxoSlseLCWb+HuherYoPy16t+Jpen46Pb8vgLrK11TzBF2z9EQ1v1TZl09uTa dae7OvRrbB2SRyHlLsB4wUQ6q47lHT+w4hrANzDbmEqkjQX3Jiq4rkyxnja6WDVW8EOc Q6Cvv8vrkIboSt8lhQqhTFGfSdYNR2diG8h8cAmDWo+SYa2gqtnRHLq1KJuKSQq8fXxH zAIl/+mapiB30Wd1NmDAeCW8g9ozDjg6ajAHVyLmYva6AkU5rfzdA0/nKoatkIX0s9Ht h5IbGCGBxcJ3FLCb2/sF0gjgTgQQJgwIeO6bKdGsIXPx5QnJjCzga25TQw80tkHQyTe4 T5WA== MIME-Version: 1.0 X-Received: by 10.42.50.81 with SMTP id z17mr19842029icf.57.1430582004190; Sat, 02 May 2015 08:53:24 -0700 (PDT) In-Reply-To: References: <87mw1q9jqw.fsf@Equus.decebal.nl> <87383hj4zj.fsf@elektro.pacujo.net> <87d22lx38x.fsf@Equus.decebal.nl> <55432557$0$12994$c3e8da3$5496439d@news.astraweb.com> <87383fo062.fsf@Equus.decebal.nl> <87egmzl4yr.fsf@elektro.pacujo.net> <87a8xnl2r6.fsf@elektro.pacujo.net> <87383fkxy0.fsf@elektro.pacujo.net> Date: Sat, 2 May 2015 18:53:24 +0300 Subject: Re: Python is not bad ;-) From: Joonas Liik Cc: Python Content-Type: multipart/alternative; boundary=90e6ba2124d32e93e505151b54a2 X-Mailman-Approved-At: Sat, 02 May 2015 18:53:38 +0200 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.20+ Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 82 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1430585620 news.xs4all.nl 2918 [2001:888:2000:d::a6]:52864 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:89780 --90e6ba2124d32e93e505151b54a2 Content-Type: text/plain; charset=UTF-8 Balancing of trees is kind of irrelevant when "tree" means "search space" no? And you definitely dont need to keep the entire tree in memory at the same time. By cropping unsuitable branches early (and not keeping the entire tree in memory) it is quite easy to have more than 1000 of call stack and still have reasonable preformance. (some/many nodes have 0 or 1 children) Also should not-running-out-of-call-stack really be the main reason to balance trees? That sounds like an optimisation to me .. On 2 May 2015 at 18:45, Ian Kelly wrote: > On Sat, May 2, 2015 at 5:42 AM, Marko Rauhamaa wrote: > > Christian Gollwitzer : > > > >> That's why I still think it is a microoptimization, which helps only > >> in some specific cases. > > > > It isn't done for performance. It's done to avoid a stack overflow > > exception. > > If your tree is balanced, then the number of items you would need to > have to get a stack overflow exception would be approximately 2 ** > 1000, which you can't possibly hope to fit into memory. > > If your tree is unbalanced and you're getting a stack overflow > exception, then maybe you should think about balancing it. > -- > https://mail.python.org/mailman/listinfo/python-list > --90e6ba2124d32e93e505151b54a2 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Balancing of trees is kind of irrelevant when "tree&q= uot; means "search space" no?
And you definitely dont need to= keep the entire tree in memory at the same time.

By cropping u= nsuitable branches early (and not keeping the entire tree in memory)
<= div>it is quite easy to have more than 1000 of call stack and still have re= asonable
preformance. (some/many nodes have 0 or 1 children)

Also should not-running-out-of-call-stack really be th= e main reason to balance trees?
That sounds like an optimisation = to me ..

On 2 May 2015 at 18:45, Ian Kelly <ian.g.kelly@gmail.com&= gt; wrote:
On Sat= , May 2, 2015 at 5:42 AM, Marko Rauhamaa <marko@pacujo.net> wrote:
> Christian Gollwitzer <auriocus@g= mx.de>:
>
>> That's why I still think it is a microoptimization, which help= s only
>> in some specific cases.
>
> It isn't done for performance. It's done to avoid a stack over= flow
> exception.

If your tree is balanced, then the number of items you would need to=
have to get a stack overflow exception would be approximately 2 **
1000, which you can't possibly hope to fit into memory.

If your tree is unbalanced and you're getting a stack overflow
exception, then maybe you should think about balancing it.
--
https://mail.python.org/mailman/listinfo/python-list

--90e6ba2124d32e93e505151b54a2--