Message-ID:

Remember: Silly is a state of Mind, Stupid is a way of Life. -- Dave Butler

devel / comp.lang.python / Re: Non-deterministic set ordering

Re: Non-deterministic set ordering

<mailman.423.1652672195.20749.python-list@python.org>

https://www.novabbs.com/devel/article-flat.php?id=18286&group=comp.lang.python#18286

copy link Newsgroups: comp.lang.python

Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!3.eu.feeder.erje.net!feeder.erje.net!news2.arglkargh.de!news.karotte.org!fu-berlin.de!uni-berlin.de!not-for-mail
From: pbr...@anode.ca (Paul Bryan)
Newsgroups: comp.lang.python
Subject: Re: Non-deterministic set ordering
Date: Sun, 15 May 2022 20:36:27 -0700
Lines: 56
Message-ID: <mailman.423.1652672195.20749.python-list@python.org>
References: <d93aad1d-8586-b844-d3de-fa9648535244@btinternet.com>
<CAGGBd_p3SqB-GRBW+DdTY6++DmJ2qHfJtQUK1u2Y18CG3nWuEA@mail.gmail.com>
<d26dd6fb-ff48-1269-6e2a-acd69e5fc3f6@btinternet.com>
<8c947b633c736874f99a09320d0b44c4af10d686.camel@anode.ca>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Trace: news.uni-berlin.de 5SvD9FEVxhcLwDSKCVSL4QHYgdOzR/bNJIFOkweQjS8Q==
Return-Path: <pbryan@anode.ca>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
Authentication-Results: mail.python.org; dkim=pass
reason="2048-bit key; unprotected key"
header.d=anode.ca header.i=@anode.ca header.b=DVQnD7ON;
dkim-adsp=pass; dkim-atps=neutral
X-Spam-Status: OK 0.020
X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; '2022': 0.05; 'sun,': 0.07;
'cc:addr:python-list': 0.09; 'dan': 0.09; 'identical': 0.09;
'order,': 0.09; '"real"': 0.16; 'assuming': 0.16;
'cc:name:python': 0.16; 'operations,': 0.16; 'order?': 0.16;
'received:10.202': 0.16; 'received:10.202.2': 0.16;
'received:10.202.2.163': 0.16; 'received:internal': 0.16;
'received:messagingengine.com': 0.16; 'tasks.': 0.16; 'wrote:':
0.16; 'python': 0.16; 'round': 0.19; 'cc:addr:python.org': 0.20;
'code': 0.23; 'list,': 0.24; 'cc:2**0': 0.25; 'anyone': 0.25;
'seems': 0.26; 'output': 0.28; 'email addr:python.org>': 0.28;
'header:User-Agent:1': 0.30; 'program': 0.31; '(as': 0.32;
'python-list': 0.32; "wouldn't": 0.32; 'but': 0.32; "i'm": 0.33;
'same': 0.34; 'header:In-Reply-To:1': 0.34; 'running': 0.34;
'subject:skip:d 10': 0.35; 'following': 0.35; 'received:66': 0.35;
'mon,': 0.36; 'thanks,': 0.36; 'developers': 0.39; 'use': 0.39;
'explain': 0.40; 'wishes': 0.40; 'something': 0.40; 'should':
0.40; 'best': 0.61; 'come': 0.62; 'your': 0.64; 'produce': 0.65;
'operations': 0.68; 'it:': 0.69; 'repeatedly': 0.69; 'within':
0.69; 'discover': 0.80; 'email name:<python-list': 0.84;
'ordering': 0.84; 'rob': 0.84; 'subject:Non': 0.84;
'\xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0': 0.84; 'shocked': 0.93
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=anode.ca; h=cc
:cc:content-type:date:date:from:from:in-reply-to:in-reply-to
:message-id:mime-version:references:reply-to:sender:subject
:subject:to:to; s=fm1; t=1652672189; x=1652758589; bh=K60QoIzSdY
hdANnhJcf0PuplwuW3z6uFlC8Ag5KcICw=; b=DVQnD7ONOUMbVMUCyjAEKdDJeh
EldnhK1q8yf+YasVrmifP3zNwSTr2lxN4tGtYyMG6THB6iY385KigarSeFkKRiQb
6f5+oZsEangIxSJ+S9QOAbSxq8VTZK3vMeLKH6To5j1JwLlv43jvBYwJ8iuPh7G3
iyI+Hp4BdGfnZsMBmWUNoBu/jbc6+nZFor2eZLmP7cqyzPsUcDIOpcIcaF1g64kw
uKxzguCD4U48kAQrlHlRx9PRe6ixcIxQ16QP/pQC/PZzNrZl55AcJBfktBEUwG7e
t71xvvZSEuftDKG2+foy3O9lc1R2blZNVUhX0VKfmxV/Ld5G7MxHGSdrHSAw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
messagingengine.com; h=cc:cc:content-type:date:date:from:from
:in-reply-to:in-reply-to:message-id:mime-version:references
:reply-to:sender:subject:subject:to:to:x-me-proxy:x-me-proxy
:x-me-sender:x-me-sender:x-sasl-enc; s=fm1; t=1652672189; x=
1652758589; bh=K60QoIzSdYhdANnhJcf0PuplwuW3z6uFlC8Ag5KcICw=; b=T
omfZiIMCCDiSwz7StHBrn/+eycUhSs+YONt8OTpDlitoraZP6vPOlwgFkHkbtZd+
jyfGpuvXpKanfhWBNUfKWfpcidxMb2mgslGsWQwq89J8zaj0ZAw38mu+HmPmNHG4
Ut5mFOargpJt65clVabwGuQA6TSGxkfux0D2BdHxmAQHij4P5adwJHYQ1JNsgHpx
+znv8ZXBS8N/kOvN5IWoedZ7iO7I7HX9nDiJZ2za+I8J8/MZEPJHfSvJzJGz1jgU
T9t1dIStWsn96GKmmvRxixaFJPg/svw0lIRIfAiFKKSOTgZQdzUu6nI8mxqixgFq
LJOC3PFaFj50Wz8/mFosA==
X-ME-Sender: <xms:vMaBYsZCcLF_bvvyMt_7ZHvk8OLEBf8TGSA7llv0zrjQX2CC6PvnqQ>
<xme:vMaBYnZuSPMq-I6Z7cxB0wDKShUg6K1mX-XBJIkoemf3w6v1IHDAFTC7djY5ViwtC
oBWgVFkli747Qp7zUE>
X-ME-Received: <xmr:vMaBYm9kPclKUyOVBAdPbqWIOS5OjBMLPAIksSbb3tDyekzV3Bzv8XBtBgbYuBMJFDVsrVRPGuijEaPepupT2kMQepiWSDKw56xUrg>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvfedrheeggdejhecutefuodetggdotefrodftvf
curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu
uegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenuc
fjughrpefkuffhvfevffgjfhgtfgggsegrtderredtreejnecuhfhrohhmpefrrghulhcu
uehrhigrnhcuoehpsghrhigrnhesrghnohguvgdrtggrqeenucggtffrrghtthgvrhhnpe
duvdetvefgffdvieeiheeffeettdejleeijeeihefgteekgfefueejgeffieekleenucff
ohhmrghinhepshhtrggtkhhovhgvrhhflhhofidrtghomhdpghhrrghnthhjvghnkhhsrd
gtohhmnecuvehluhhsthgvrhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhep
phgsrhihrghnsegrnhhouggvrdgtrg
X-ME-Proxy: <xmx:vMaBYmrplvQ1hErd9IZAL8B5hbGRG5Nx_eMR_6vecH37OX-sYRhkGA>
<xmx:vMaBYnpi8g93b71X9zHa5samu-SgIGbAtXayIVeTE-y1eK__a_MKTw>
<xmx:vMaBYkQmDKQSimxvAa03t7ysA5JuVViUGVjFV3eWZ7dAHvb6s55mAg>
<xmx:vcaBYgD4FfC3g69umSmnf7H3tyEpkMhmlAtRbqxk4Ea7ux0gmBntiA>
In-Reply-To: <d26dd6fb-ff48-1269-6e2a-acd69e5fc3f6@btinternet.com>
User-Agent: Evolution 3.44.1
X-Content-Filtered-By: Mailman/MimeDel 2.1.39
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.39
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: <https://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>
X-Mailman-Original-Message-ID: <8c947b633c736874f99a09320d0b44c4af10d686.camel@anode.ca>
X-Mailman-Original-References: <d93aad1d-8586-b844-d3de-fa9648535244@btinternet.com>
<CAGGBd_p3SqB-GRBW+DdTY6++DmJ2qHfJtQUK1u2Y18CG3nWuEA@mail.gmail.com>
<d26dd6fb-ff48-1269-6e2a-acd69e5fc3f6@btinternet.com>

by: Paul Bryan - Mon, 16 May 2022 03:36 UTC

This may explain it:
https://stackoverflow.com/questions/27522626/hash-function-in-python-3-3-returns-different-results-between-sessions

On Mon, 2022-05-16 at 04:20 +0100, Rob Cliffe via Python-list wrote:
>
>
> On 16/05/2022 04:13, Dan Stromberg wrote:
> >
> > On Sun, May 15, 2022 at 8:01 PM Rob Cliffe via Python-list
> > <python-list@python.org> wrote:
> >
> >     I was shocked to discover that when repeatedly running the
> > following
> >     program (condensed from a "real" program) under Python 3.8.3
> >
> >     for p in { ('x','y'), ('y','x') }:
> >          print(p)
> >
> >     the output was sometimes
> >
> >     ('y', 'x')
> >     ('x', 'y')
> >
> >     and sometimes
> >
> >     ('x', 'y')
> >     ('y', 'x')
> >
> >     Can anyone explain why running identical code should result in
> >     traversing a set in a different order?
> >
> >
> > Sets are defined as unordered so that they can be hashed internally
> > to
> > give O(1) operations for many tasks.
> >
> > It wouldn't be unreasonable for sets to use a fixed-by-arbitrary
> > ordering for a given group of set operations, but being
> > unpredictable
> > deters developers from mistakenly assuming they are ordered.
> >
> > If you need order, you should use a tuple, list, or something like
> > https://grantjenks.com/docs/sortedcontainers/sortedset.html
> Thanks, I can work round this behaviour.
> But I'm curious: where does the variability come from? Is it
> deliberate
> (as your answer seems to imply)? AFAIK the same code within the
> *same
> run* of a program does produce identical results.
> Best wishes
> Rob Cliffe

Subject	Author
Re: Non-deterministic set ordering	Paul Bryan