X-FeedAbuse: http://nntpfeed.proxad.net/abuse.pl feeded by 195.154.70.45
Path: csiph.com!usenet.pasdenom.info!nntpfeed.proxad.net!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <rosuav@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.006
X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'languages.': 0.04; 'subject:Python': 0.06; 'element': 0.07; 'list?': 0.07; 'string': 0.09; 'abstraction': 0.09; 'high-level': 0.09; 'okay': 0.09; 'subject:skip:c 10': 0.09; 'cc:addr:python-list': 0.11; 'language,': 0.12; '"it\'s': 0.16; 'complexity,': 0.16; 'determines': 0.16; 'docs.': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'iterating': 0.16; 'subject: \n ': 0.16; 'subject:between': 0.16; 'subject:programming': 0.16; 'subscripting': 0.16; 'wrote:': 0.18; 'discussion': 0.18; 'wed,': 0.18; 'stefan': 0.19; 'cc:addr:python.org': 0.22; 'specifies': 0.24; 'unicode': 0.24; 'java': 0.24; 'cc:2**0': 0.24; 'header:In- Reply-To:1': 0.27; 'am,': 0.29; 'array': 0.29; 'character': 0.29; 'characters': 0.30; 'message-id:@mail.gmail.com': 0.30; '13,': 0.31; 'container': 0.31; 'operations.': 0.31; 'subject:that': 0.31; 'writes:': 0.31; 'quite': 0.32; 'basic': 0.35; 'operations': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'ram': 0.36; 'yield': 0.36; 'subject:?': 0.36; 'example,': 0.37; 'level': 0.37; 'performance': 0.37; 'sometimes': 0.38; 'even': 0.60; 'skip:\xc2 10': 0.60; 'length': 0.61; 'simple': 0.61; 'back': 0.62; 'act': 0.63; 'high': 0.63; 'such': 0.63; 'become': 0.64; 'linked': 0.65; '8bit%:31': 0.68; 'detail.': 0.68; 'overall': 0.69; '2015': 0.84; 'c++:': 0.84; 'complexity': 0.84; 'python-dev': 0.84; 'subject: *': 0.84; 'subject:Good': 0.91; '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:content-transfer-encoding; bh=PQ/KjaZUvbKWvR+tBVjWENz82T6q2cR/nFmxBDdj0Nk=; b=xbVqP2Ny1W7828gJb87jU66RWlGMyBIaCwim2IpAGcWZCw3VT+ST0XkH4bTe4rZcGD xvAL5L5i7Ke86W9qCrUTBw1Uzx0NJeos7LbRUX2Ed6EPJlyQkfCtcICGB+P8/zvvLfZa bHIs6hqdxezTPRZIOgVW3bLr4TC+EYi6GqN0Tq6zovjtFZA2jLm2vegRDXL1B6WsVCv9 22DdjqGAjp6xbZwNtD2nOkWmK6AugbWqDdJD3+Vj5dGq6+H3XMkww9b3bL2KyniV4KYe 5cZhJ2Nma7oi6c2G+WQepD0TnA7wxEP49kpPwnihCXOcAZdZTm/DpZjtg9AQQaK/Bc0n oLyA==
MIME-Version: 1.0
X-Received: by 10.43.39.1 with SMTP id tk1mr2689165icb.26.1431451589690; Tue, 12 May 2015 10:26:29 -0700 (PDT)
In-Reply-To: <complexity-20150512191339@ram.dialup.fu-berlin.de>
References: <02dba7aa-8466-4937-a8d8-82ffd03e5568@googlegroups.com> <87wq0gyvyr.fsf@elektro.pacujo.net> <mailman.333.1431308306.12865.python-list@python.org> <ed1b5d2c-7d29-4102-b310-ee544cf033a3@googlegroups.com> <55515f9d$0$12987$c3e8da3$5496439d@news.astraweb.com> <569169cf-d232-48c0-bd49-91090e9c0ddb@googlegroups.com> <mitbph$2sq$3@dont-email.me> <complexity-20150512191339@ram.dialup.fu-berlin.de>
Date: Wed, 13 May 2015 03:26:29 +1000
Subject: Re: Instead of deciding between Python or Lisp for a programming intro course...What about an intro course that uses *BOTH*? Good idea?
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.20+
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.406.1431451597.12865.python-list@python.org>
Lines: 34
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1431451597 news.xs4all.nl 2956 [2001:888:2000:d::a6]:38114
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:90470

On Wed, May 13, 2015 at 3:15 AM, Stefan Ram <ram@zedat.fu-berlin.de> wrote:
> Rob Gaddi <rgaddi@technologyhighland.invalid> writes:
>>Is that a true array or a linked list?  "It's a high level language,
>>that's just an implementation detail." Yes, but it's an implementation
>>detail that determines whether even the simple act of looking up element
>>n is O(1) or O(n).
>
>   The complexity is given in the documentation of high-level languages.
>
>   For example, from the documentation of the Java standard library:
>
>       =C2=BBThis implementation provides constant-time performance
>       for the basic operations (get and put),=C2=AB (java.util.HashMap)
>
>   C++:
>
>       Section 23.2.1 specifies the complexity, such as =C2=BBcompile time=
=C2=AB,
>       =C2=BBconstant=C2=AB, =C2=BBlinear=C2=AB for container operations.
>
>   But the abstraction mechanisms (templates, polymorphism)
>   often allow one to change the implementation quite easily.

It isn't always given in the docs. Sometimes it's not even a promise;
back when MicroPython was debating the implementation of Unicode
strings, there was a lengthy discussion on python-dev about whether
it's okay for string subscripting to be O(n) instead of O(1), and the
final decision was that yes, that's an implementation detail. (UTF-8
internal string representation, so iterating over a string would still
yield characters in overall O(n), but iterating up to the string's
length and subscripting for each character would become O(n*n) on
uPy.)

ChrisA