Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Ian Kelly Newsgroups: comp.lang.python Subject: Re: How to waste computer memory? Date: Fri, 18 Mar 2016 07:57:57 -0600 Lines: 49 Message-ID: References: <265377f4-741d-4aa2-9338-239f56f8bc57@googlegroups.com> <56ebea83$0$1599$c3e8da3$5496439d@news.astraweb.com> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Trace: news.uni-berlin.de 3YDk4dGR7ywB/3ioR/lKEApk16aPqzGlP8hDU4E1a1XQ== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'received:209.85.223': 0.03; 'position,': 0.04; 'imply': 0.07; 'indexing': 0.07; 'utf-8': 0.07; 'width': 0.07; 'subject:How': 0.09; 'bytes,': 0.09; 'indexes': 0.09; 'non-ascii': 0.09; 'themselves,': 0.09; 'yeah,': 0.09; 'index': 0.13; '(assuming': 0.16; '2016': 0.16; '255': 0.16; 'locating': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'string:': 0.16; 'wrote:': 0.16; 'memory': 0.17; 'string': 0.17; 'byte': 0.18; 'bytes': 0.18; 'have:': 0.18; 'instance,': 0.18; 'string,': 0.18; '(in': 0.18; 'am,': 0.23; 'header:In-Reply-To:1': 0.24; "doesn't": 0.26; 'chris': 0.26; 'point.': 0.27; 'points': 0.27; 'fri,': 0.27; 'message-id:@mail.gmail.com': 0.27; 'grouping': 0.29; 'table,': 0.29; 'array': 0.29; 'character': 0.29; '(including': 0.30; 'that.': 0.30; 'code': 0.30; 'point': 0.33; 'consist': 0.33; "d'aprano": 0.33; 'point,': 0.33; 'steven': 0.33; '(for': 0.34; 'add': 0.34; 'received:google.com': 0.35; 'could': 0.35; '8bit%:86': 0.35; 'skip:e 40': 0.35; 'supports': 0.35; 'but': 0.36; 'too': 0.36; 'instead': 0.36; 'received:209.85': 0.36; 'to:addr:python-list': 0.36; 'subject:?': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'received:209': 0.38; 'to:addr:python.org': 0.40; 'still': 0.40; 'some': 0.40; 'your': 0.60; 'total': 0.62; 'more': 0.63; 'mar': 0.65; 'series': 0.65; 'store,': 0.66; 'worth': 0.67; 'characters.)': 0.84; 'rue': 0.84; 'to:name:python': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-transfer-encoding; bh=isda00/o1ofzYQz+CrAiLV38NzG8uCc09tec1FGjviE=; b=DPEFt6zYSM55yT1A6gVgWpCyd6G7zJrVsyZsBsDka+A3lJaE38eDmsXfrPyVqWRRNg EyczHUzdHvB2WO0KUwLJL3+Z2l7jKhAXvBubHO8wFc7AhBv4unYyABvGTM2ZW4/iwg/A quIoCv4ckjyTvBFexJxuDZI35cGZNZ9X7a7cpS+3JvLbUg409PGSc9wfhWhgzdsOrN1G Xand8i5RSMYt6ZSI8ssH9bdAL3LkW7wZqxTMbK7WOCduk6nkBTcGb3Gx8DMmgWLp0YMa jhOlCj4My7QBDDKuwLEtZP8obWgIbLzBrpIHOnfVWBuRrwksrNfmJqL/i25nvFYv+Gg1 rCbg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:content-transfer-encoding; bh=isda00/o1ofzYQz+CrAiLV38NzG8uCc09tec1FGjviE=; b=WXWCOLqXZLB5r/h9hIyKm/tGONEQ2+D+vOzQe472xuA2fYI/rPjeBo6d/PbO2cZQTV IHvVTdJLYkbv0/dQcFz46+vQgEYE/B409dk5fSBo1KvemoKkMDeosAjK5nXy3E65J8Z4 hcCx6J5s0BHDCf9B8xdbKh3L/AgLo0OZaHa0cEsjNYOJVm7itaN8GjWJ3Glf5yVJ9w4h dfzqprZCAIOC9eJuEzcThewxi3kBrGZJ1YorA7cQhIz9zPKp6yG2Ojw4cJRiVgyA5Z/P qrumiqRFFHiyAU0Kp7q9WvcFg3SiM7d4Z+hYA1HOh9ebGJejT/2VwEyRvWpLkXTCs4a7 2cMg== X-Gm-Message-State: AD7BkJLIwNQLThBmMf06ut/bPB3qT/JoKWHgSw3qe0nQJGTlQgOhWQFD5leWSeU7WDgjzElr53jnCxY3JeWWeQ== X-Received: by 10.107.19.140 with SMTP id 12mr17838005iot.11.1458309517318; Fri, 18 Mar 2016 06:58:37 -0700 (PDT) In-Reply-To: X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Xref: csiph.com comp.lang.python:105213 On Fri, Mar 18, 2016 at 6:37 AM, Chris Angelico wrote: > On Fri, Mar 18, 2016 at 10:46 PM, Steven D'Aprano w= rote: >> Technically, UTF-8 doesn't *necessarily* imply indexing is O(n). For >> instance, your UTF-8 string might consist of an array of bytes containin= g >> the string, plus an array of indexes to the start of each code point. Fo= r >> example, the string: >> >> =E2=80=9Cabc=CF=80=C3=9F=D0=8A=E2=80=A2=F0=92=80=81=E2=80=9D >> >> (including the quote marks) is 10 code points in length and 22 bytes as >> UTF-8. Grouping the (hex) bytes for each code point, we have: >> >> e2809c 61 62 63 cf80 c39f d08a e280a2 f0928081 e2809d >> >> so we could get a O(1) UTF-8 string by recording the bytes (in hex) plus= the >> indexes (in decimal) in which each code point starts: >> >> e2809c616263cf80c39fd08ae280a2f0928081e2809d >> >> 0 3 4 5 6 8 10 12 15 19 >> >> but (assuming each index needs 2 bytes, which supports strings up to 655= 35 >> characters in length), that's actually LESS memory efficient than UTF-32= : >> 42 bytes versus 40. > > A lot of strings will have no more than 255 non-ASCII characters in > them. (For example, all strings which no more than 255 total > characters.) You could store, instead of the indexes themselves, a > series of one-byte offsets: > > e2809c616263cf80c39fd08ae280a2f0928081e2809d > 0 2 2 2 2 3 4 5 7 10 > > Locating a byte based on its character position is still O(1); you > look up that position in the offset table, add that to your original > character position, and you have the byte location. For strings with > too many non-ASCII codepoints, you'd need some other representation, > but at that point, it might be worth just switching to UTF-32. So this uses approximately twice as much memory as the FSR and still requires switching on some form of character width in the implementation? Yeah, I don't think the RUE is going to go for that. 8-)