Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #85827

Re: python implementation of a new integer encoding algorithm.

Path csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!newsreader4.netcologne.de!news.netcologne.de!bcyclone01.am1.xlned.com!bcyclone01.am1.xlned.com!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path <davea@davea.name>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.026
X-Spam-Evidence '*H*': 0.95; '*S*': 0.00; 'algorithm': 0.04; 'value,': 0.04; 'encoding': 0.05; 'referring': 0.07; 'bits': 0.09; 'bytes,': 0.09; 'encode': 0.09; 'integers': 0.09; 'assumptions': 0.16; 'byte,': 0.16; 'values?': 0.16; 'zero,': 0.16; 'subject:python': 0.16; 'wrote:': 0.18; 'bit': 0.19; '>>>': 0.22; 'header:User-Agent:1': 0.23; 'byte': 0.24; 'bytes': 0.24; 'define': 0.26; 'second': 0.26; 'values': 0.27; 'header:In-Reply- To:1': 0.27; 'tried': 0.27; 'rest': 0.29; '[1]': 0.29; 'am,': 0.29; "i'm": 0.30; 'went': 0.31; 'apparently': 0.31; 'claiming': 0.31; 'constant': 0.31; 'subject:skip:i 10': 0.31; 'terms.': 0.31; 'values.': 0.31; 'not.': 0.33; 'third': 0.33; 'except': 0.35; 'beyond': 0.35; 'shows': 0.36; 'subject:new': 0.38; 'challenging': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'that,': 0.38; 'to:addr:python.org': 0.39; 'how': 0.40; 'dave': 0.60; 'new': 0.61; 'range': 0.61; 'first': 0.61; 'you.': 0.62; 'email addr:gmail.com': 0.63; 'decided': 0.64; 'provide': 0.64; 'charset:windows-1252': 0.65; 'sample': 0.67; 'between': 0.67; 'beat': 0.68; 'received:74.208': 0.68; 'million': 0.74; '100': 0.79; '2015': 0.84; 'yours': 0.88; 'average': 0.93
Date Wed, 18 Feb 2015 17:19:48 -0500
From Dave Angel <davea@davea.name>
User-Agent Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
MIME-Version 1.0
To python-list@python.org
Subject Re: python implementation of a new integer encoding algorithm.
References <e45a71b2-7ec0-4c7d-88ae-c48aebe154b7@googlegroups.com> <mailman.18784.1424182393.18130.python-list@python.org> <515047c1-a20d-430e-a029-1c2d77db2f1a@googlegroups.com> <mailman.18823.1424278025.18130.python-list@python.org> <2a717ffb-d61d-4407-9082-1c17cd7ee573@googlegroups.com>
In-Reply-To <2a717ffb-d61d-4407-9082-1c17cd7ee573@googlegroups.com>
Content-Type text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding 7bit
X-Provags-ID V02:K0:onNUMsNMx6dS8HUeGsI/uI9W5xbgFPmLHnSP/OeZy8n i5boxYKRzJQbwy0cPMrcTBeU7lDl5cQUGcdkAu37KAeyt5WD6g /780w/hwxsSvBx5eRs6BVTlCaGIKYiN7uMfkgMRlQfe/pvTcth vcftL1PKNV3AtbKzdK2dj22/iThBLv5DXZPQx/rTj9zjSZQSdP pnyBUX3E5W2Gpha8tg0iLnD03KzxyQ9txeQ0rQW52aRpf9ZiYD 2jmr0EcOBsEkGO/qOEGZ5EPxazCUlpqkbfIE0Oep0NZTu5BS5Y qIbYd6k3AzBNnuUJGNBU6Td2yZaUEGMWAfr2Fppw/aQHgsvOyB bMSBfg39q/cBQR7aJOU0=
X-UI-Out-Filterresults notjunk:1;
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.15
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.18839.1424298000.18130.python-list@python.org> (permalink)
Lines 48
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1424298001 news.xs4all.nl 2853 [2001:888:2000:d::a6]:42956
X-Complaints-To abuse@xs4all.nl
X-Received-Bytes 5342
X-Received-Body-CRC 2802915041
Xref csiph.com comp.lang.python:85827

Show key headers only | View raw

On 02/18/2015 02:55 PM, janhein.vanderburg@gmail.com wrote:
> Op woensdag 18 februari 2015 17:47:49 UTC+1 schreef Dave Angel:
>> On 02/18/2015 03:59 AM, janhein.vanderburg@gmail.com wrote:
>>
>>
>>> encoding individual integers optimally without any assumptions about their values.
>>>
>>
>> Contradiction in terms.
>>
>> --
>> DaveA
>
> Not.
> Jan-Hein.
>

Then you had better define your new word "optimal" to us.  I decided to 
try your algorithm for all the values between 0 and 999999.  One million 
values, and the 7bit encoding[1] beat yours for 950081 of them.  The 
rest were tied.  Yours never was shorter.

For a uniform distribution of those particular values, the average 
number of bytes used by yours was 3.933568 bytes, and by 7bit encoding 
was 2.983487

For the second and third million, yours are all 4 bytes, while 7bit uses 
3. Beyond 2097152, 7bit uses 4 bytes, same as you.  Between 16 and 17 
million, you average 4.156865, while 7bit is a constant 4.0.

After that, I started spot-checking.  I went up to 100 billion, and for 
none of those I tried did your algorithm take fewer bytes than 7bit.


So how is yours optimal?  Over what range of values?

I'm not necessarily doubting it, just challenging you to provide a data 
sample that actually shows it.  And of course, I'm not claiming that 
7bit is in any way optimal.  You cannot define optimal without first 
defining the distribution.

[1] by 7bit, I'm referring to the one apparently used in MIDI encoding, 
where 7 bits of each byte hold the value, and the 8th bit is zero, 
except for the last byte, where the 8th bit is one.  So 3 bytes can 
encode 21 bits, or up to 2**21 - 1.

-- 
DaveA

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-17 03:22 -0800
  Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 00:16 +1100
    Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 00:55 -0800
      Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 20:36 +1100
        Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 11:29 -0800
      Re: python implementation of a new integer encoding algorithm. Laura Creighton <lac@openend.se> - 2015-02-18 11:32 +0100
        Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 11:48 -0800
      People hated it for the same reasons I found them cool (was: python implementation of a new integer encoding algorithm.) Ben Finney <ben+python@benfinney.id.au> - 2015-02-18 21:57 +1100
  Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-17 09:12 -0500
    Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 00:59 -0800
      Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-18 11:46 -0500
        Re: python implementation of a new integer encoding algorithm. Grant Edwards <invalid@invalid.invalid> - 2015-02-18 17:30 +0000
          Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-18 18:12 +0000
        Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 11:55 -0800
          Re: python implementation of a new integer encoding algorithm. Marko Rauhamaa <marko@pacujo.net> - 2015-02-18 23:54 +0200
            Re: python implementation of a new integer encoding algorithm. Marko Rauhamaa <marko@pacujo.net> - 2015-02-19 00:08 +0200
            Re: python implementation of a new integer encoding algorithm. Grant Edwards <invalid@invalid.invalid> - 2015-02-18 22:58 +0000
          Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-18 17:19 -0500
            Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-19 07:45 -0800
              Re: python implementation of a new integer encoding algorithm. Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-19 11:04 -0700
              Re: python implementation of a new integer encoding algorithm. Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-19 11:16 -0700
              Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-19 13:24 -0500
              Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-20 05:34 +1100
              Re: python implementation of a new integer encoding algorithm. Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-19 11:32 -0700
              Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-19 13:41 -0500
              Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-19 13:46 -0500
              Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-20 05:49 +1100
      Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-18 17:00 +0000
  Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 01:34 +1100
    Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 01:04 -0800
      Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-18 08:54 -0500
        Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 11:52 -0800
      Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-19 01:16 +1100
  Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-17 09:50 -0500
  Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 01:58 +1100
  Re: python implementation of a new integer encoding algorithm. Dave Angel <davea@davea.name> - 2015-02-17 10:18 -0500
  Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-18 02:25 +1100
  Re: python implementation of a new integer encoding algorithm. Paul Rubin <no.email@nospam.invalid> - 2015-02-17 08:43 -0800
    Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-18 01:06 -0800
  Re: python implementation of a new integer encoding algorithm. Mario Figueiredo <marfig@gmail.com> - 2015-02-19 08:44 +0100
    Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-19 08:06 +0000
      Re: python implementation of a new integer encoding algorithm. Marko Rauhamaa <marko@pacujo.net> - 2015-02-19 10:36 +0200
        Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-19 09:33 +0000
        Re: python implementation of a new integer encoding algorithm. Terry Reedy <tjreedy@udel.edu> - 2015-02-19 14:50 -0500
          Re: python implementation of a new integer encoding algorithm. Marko Rauhamaa <marko@pacujo.net> - 2015-02-19 21:55 +0200
    Re: python implementation of a new integer encoding algorithm. Chris Angelico <rosuav@gmail.com> - 2015-02-19 19:36 +1100
    Re: python implementation of a new integer encoding algorithm. Mario Figueiredo <marfig@gmail.com> - 2015-02-19 10:42 +0100
    Re: python implementation of a new integer encoding algorithm. Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-19 10:28 +0000
    Re: python implementation of a new integer encoding algorithm. Mario Figueiredo <marfig@gmail.com> - 2015-02-19 14:27 +0100
  Re: python implementation of a new integer encoding algorithm. Jonas Wielicki <jonas@wielicki.name> - 2015-02-19 09:38 +0100
    Re: python implementation of a new integer encoding algorithm. janhein.vanderburg@gmail.com - 2015-02-19 07:58 -0800
  Re: python implementation of a new integer encoding algorithm. Denis McMahon <denismfmcmahon@gmail.com> - 2015-02-20 02:46 +0000
    Re: python implementation of a new integer encoding algorithm. wxjmfauth@gmail.com - 2015-02-20 00:58 -0800

csiph-web