From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by c5ff346549e7 (Postfix) with ESMTP id C76245D4 for ; Thu, 18 Mar 2021 10:07:04 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="scan'208";a="498623613" Received: from prod-listesu18.inria.fr (HELO sympa.inria.fr) ([128.93.162.160]) by mail2-relais-roc.national.inria.fr with ESMTP; 18 Mar 2021 11:06:46 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id 47A0CE0163; Thu, 18 Mar 2021 11:06:46 +0100 (CET) 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 Reply-To: =?UTF-8?Q?Fran=c3=a7ois_Pottier?= X-Loop: caml-list@inria.fr X-Sequence: 18430 Errors-To: caml-list-owner@inria.fr Precedence: list Precedence: bulk Sender: caml-list-request@inria.fr X-no-archive: yes List-Id: List-Help: List-Subscribe: List-Unsubscribe: List-Post: List-Owner: List-Archive: Archived-At: 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/