From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id BE4D0E0131 for ; Thu, 18 Mar 2021 11:06:40 +0100 (CET) IronPort-HdrOrdr: =?us-ascii?q?A9a23=3AthjIXq6WMCUO0ZdJwwPXwHrXdLJzesId70hD?= =?us-ascii?q?6mlaTxtJfsuE0/2/hfhz73HJoRsyeFVlo9CPP6GcXWjRnKQe3aA9NaqvNTOLhE?= =?us-ascii?q?KGN4dnhLGD/xTEGzfistJbz7tqaaJkCNb9ZGIK6PrSxQmjDpIdx8Oa+7qjnufU?= =?us-ascii?q?wzNVSxt2ApsQiztRLia+PglISBJdBZw/faDw2uNiqyC7cXoaKuSXb0NrY8H5q9?= =?us-ascii?q?fGlI3rbHc9bnZN1CC0gSqs+PrGFXGjr3QjeghC3Ks49iz9mxH5j5/T1M2T8APW?= =?us-ascii?q?1GPY8v1t+efJ990rPr3vtuElbhHhkByhaogkZq2asFkO0YeS1Go=3D?= X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="scan'208";a="376105787" Received: from 91-175-127-215.subs.proxad.net (HELO MacBook-Pro-5.local) ([91.175.127.215]) by mail3-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 18 Mar 2021 11:06:40 +0100 To: jean-marc.alliot@irit.fr, caml-list@inria.fr References: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> From: =?UTF-8?Q?Fran=c3=a7ois_Pottier?= Message-ID: <368aa12e-e819-4049-7ec5-4a3479f77bbb@inria.fr> Date: Thu, 18 Mar 2021 11:06:39 +0100 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:68.0) Gecko/20100101 Thunderbird/68.12.1 MIME-Version: 1.0 In-Reply-To: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: fr Content-Transfer-Encoding: 8bit Subject: Re: [Caml-list] Choosing a random element in a Map or a Set Le 18/03/2021 à 10:44, jean-marc.alliot@irit.fr a écrit : > 1) Is there another, more intelligent, solution? > 2) Is my solution biased? I think it is not, as long as the tree is > properly balanced but... The tree is only approximately balanced, so this approach should be OK if you are willing to accept some bias, but it is not perfectly uniform. If it is important to obtain a uniform distribution, then I would suggest: 1- picking a random index in the interval [0, n); and 2- using a data structure that allows efficient indexing. Finger trees come to mind (see the papers by Hinze and Paterson and by Sozeau), but there are probably others. -- François Pottier francois.pottier@inria.fr http://cambium.inria.fr/~fpottier/