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 ESMTPS id E50715D4 for ; Thu, 18 Mar 2021 17:03:52 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.81,259,1610406000"; d="scan'208";a="498739084" 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 18:03:50 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id 49ADEE0131; Thu, 18 Mar 2021 18:03:50 +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 80E21E0131 for ; Thu, 18 Mar 2021 18:03:44 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=jean-marc.alliot@irit.fr; spf=SoftFail smtp.mailfrom=jean-marc.alliot@irit.fr; spf=None smtp.helo=postmaster@smtp.smtpout.orange.fr IronPort-PHdr: =?us-ascii?q?A9a23=3A1PjvQxEnNf74tDlkdawTuJ1Gf3xLhN3EVjU92t8?= =?us-ascii?q?ck7tLN56b1NHcBiT32/xhgRfzUJnB7Loc0qyK6vGmADdeqsff+Fk5M7V0Hycfj?= =?us-ascii?q?ssXmwFySOWkMmbcaMDQUiohAc5ZX0Vk9XzoeWJcGcL5ekGA6ibqtW1aFRrwLxd?= =?us-ascii?q?6KfroEYDOkcu3y/qy+5rOaAlUmTaxe7x/IAiyoAnLq8Ubj4pvJqk1xxbIv3BFZ?= =?us-ascii?q?/lYyWR0KFyJgh3y/N2w/Jlt8yRRv/Iu6ctNWrjkcqo7ULJVEi0oP3g668P3uxb?= =?us-ascii?q?DSxCP5mYHXWUNjhVIGQnF4wrkUZr3ryD3q/By2CiePc3xULA0RTGv5LplRRP0l?= =?us-ascii?q?CsKMSMy/XrJgcJskq1UvBOhpwR+w4HKZoGVKOF+db7Zcd8DWGZNQtpdWylHD4y?= =?us-ascii?q?7coUPEvEBPf5GoIbhu1sAoxy+BQy2C+PuzD9Dm3v60KI+3ugkFwzNwQ4uEM8Us?= =?us-ascii?q?HnMsdv7KqkSX+C2wqfGwzrMYPFZ1ivy5oXTbhAsouuBUa5sfcffy0QiER7OgFW?= =?us-ascii?q?KqYziOjOYzuYNvHaB4OpmTO6vjnQoqxttrTS13Mgsjo3JhoMSylDY7ih5wZw1J?= =?us-ascii?q?dykSEJhb96kCp1dvDyVOIVqWM0tWX1ouDokxb0cv562ZCsHxIo6yhDfa/KJc4i?= =?us-ascii?q?F7xLgWeuMLzp2i3Jrdr27ihi8/kauyuPxW8e33VtFsCdIlsXAu3MO2hDP68WLV?= =?us-ascii?q?udw8Emn1D2S2Q7T7eRELlo1lardM5Mhzb8wloYTsUTeBSD6gkT2jKiQe045+ea?= =?us-ascii?q?o8/zqb7b6qpOGKoN4lBvyProhl8ChG+g0LwYDU3SD9em/1bDv51D1TbFOg/Esl?= =?us-ascii?q?qTVrYrWKMUHqqO/HgRbyJws6wylADejyNkYnWcILFZCeB+flIjpPk3OIOjiAfe?= =?us-ascii?q?khlSsjC9rx/fbPr39GJnNKWLDn63nfbZy9UFQ0gQzzcpH65JVDLEOPu7zV1fyu?= =?us-ascii?q?dDEFBM1LhK4z/z5BNhyyI8SQ3+DD6GFPK/KtF+H/OMvI+2CZI8Pvzb9LuAo5/z?= =?us-ascii?q?wgnAjn18RZKyp0oENaH+kBPhpOUGZYX7tgtcGDWcHpQs+TPbriF2eSzJTaWyyU?= =?us-ascii?q?7om5j4nEIKmEZvDRoe1jbOdxii7G5lWanlCClCNCnfoa56JW+wMaSKXOs9uiCY?= =?us-ascii?q?IVbmnS4871BGhrhX2y7R9LrmcxipNjpPm0949zPfOnBc/7nQgFMWY1GfLRHtpl?= =?us-ascii?q?2UFXHlshPggiUkh2hGEy6cux7RTHNlXovdISRsSNJjGzuU8BcqhdBjGe4KLRV+?= =?us-ascii?q?gB9CvGzp3R9Y1wtgSS0dnGsnkgAqQjGKRH7YJmunTV9QP+aXG0i20ep8V40aD7?= =?us-ascii?q?7EoihwdeuUKLXev7oZ+7QnPQYDTwR3xv5bvTrwV2Wv2zEnGzWeKuylwSwtsSeP?= =?us-ascii?q?eWGwHYVbK69Pj70XNQvmgE+Z/WiNxjPWaI64PUeXHyFBPRfPtItPbC0qwgWasQ?= =?us-ascii?q?xiSlOjkUQ=3D=3D?= IronPort-HdrOrdr: =?us-ascii?q?A9a23=3Aha9oR6u2PDajbsXtKAgrsw847skD79V00zAX?= =?us-ascii?q?/kB9WHVpW+aT/vrDoN0w0xjohDENHFQpnt6dMKeNKEmskqJdy48XILukQU3aqH?= =?us-ascii?q?KlRbsSibfK7jX8F0TFltJ1+rxnd8FFZuHYLV8/tsri5Rn9LtBI+qjjzImNpcPz?= =?us-ascii?q?i0hgVhtrbaYI1XYaNi++HldtTAdLQboVfaD82uN9qzCteWsaY62AbxFvY8H5q9?= =?us-ascii?q?LGj57gaxIdbiRJ1CC1kTiq5LTmeiLz4j4iVVp0rIsKzXLIiEjQ6KmlrpiAu3zh?= =?us-ascii?q?61M=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BgEACghlNgf4LyDFBaHQEBAQEJARIBB?= =?us-ascii?q?QUBQIFQAoMfVwEmEjGEQogmXogZCCWEBpZcgSQDVAsBAwENBQIjCAIEAQGEUAK?= =?us-ascii?q?Beh4MBTMCDQIQAQEFAQEBAgEDAwQBEwEBDQsLCCeFag2COCmDZAYjDwEyJAkCG?= =?us-ascii?q?gImAgJXBgEMCAEBEIJcAYMLC49WnAGBMokagSgGgQ8qAYlQgU+CI4JNgTgMgjo?= =?us-ascii?q?uPoJgAgGEc4JgBIFULoF9AoFEgTOQUak6B4xZknIFBwMflAeQK5R7i1iKOogXh?= =?us-ascii?q?GmCAoFldEyCaVAZDZRyh3ZAATECATUCBgEJAQEDCXyOfwEB?= X-IPAS-Result: =?us-ascii?q?A0BgEACghlNgf4LyDFBaHQEBAQEJARIBBQUBQIFQAoMfVwE?= =?us-ascii?q?mEjGEQogmXogZCCWEBpZcgSQDVAsBAwENBQIjCAIEAQGEUAKBeh4MBTMCDQIQA?= =?us-ascii?q?QEFAQEBAgEDAwQBEwEBDQsLCCeFag2COCmDZAYjDwEyJAkCGgImAgJXBgEMCAE?= =?us-ascii?q?BEIJcAYMLC49WnAGBMokagSgGgQ8qAYlQgU+CI4JNgTgMgjouPoJgAgGEc4JgB?= =?us-ascii?q?IFULoF9AoFEgTOQUak6B4xZknIFBwMflAeQK5R7i1iKOogXhGmCAoFldEyCaVA?= =?us-ascii?q?ZDZRyh3ZAATECATUCBgEJAQEDCXyOfwEB?= X-IronPort-AV: E=Sophos;i="5.81,259,1610406000"; d="scan'208";a="376167489" X-MGA-submission: =?us-ascii?q?MDFD02lDEAotnACl5sIf8WICec+Le0AE0eWgxO?= =?us-ascii?q?BI73yYcpkfS9E8oA2GZQb7Fs2z1DsoBRkxThhw+0yD+1733N7K4Sszqg?= =?us-ascii?q?x49NF/H9kr2H0QJ7xfq0g2xNgxCvWYJgmSE3PXltSL8OccnlhQ3guFqc?= =?us-ascii?q?//bbAfPn3OlTT86VpmVgDI6g=3D=3D?= Received: from smtp08.smtpout.orange.fr (HELO smtp.smtpout.orange.fr) ([80.12.242.130]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 18 Mar 2021 18:03:43 +0100 Received: from god3 ([86.199.91.60]) by mwinf5d88 with ME id ht3i2400V1J8B2m03t3inC; Thu, 18 Mar 2021 18:03:43 +0100 X-ME-Helo: god3 X-ME-Date: Thu, 18 Mar 2021 18:03:43 +0100 X-ME-IP: 86.199.91.60 Received: from [10.31.1.2] by god3 with esmtp (Exim 4.90_1) (envelope-from ) id 1lMw3h-0007Kn-UF; Thu, 18 Mar 2021 18:03:41 +0100 To: Simon Cruanes , caml-list@inria.fr References: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> <368aa12e-e819-4049-7ec5-4a3479f77bbb@inria.fr> From: jean-marc.alliot@irit.fr Message-ID: Date: Thu, 18 Mar 2021 18:06:44 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.8.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Content-Language: fr Subject: Re: [Caml-list] Choosing a random element in a Map or a Set Reply-To: jean-marc.alliot@irit.fr X-Loop: caml-list@inria.fr X-Sequence: 18436 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: Thanks Simon. This works beautifully and without having to write a single additional line of code. A few modifications were enough. That's the advantage of getting old: 30 years ago I would have jumped on my keyboard, now I realize that somebody smarter than me has probably already solved the problem, and I just ask and wait...  😁 Also thanks to all the other people who have answered my request. It's a pleasure, and an honor, to be still part of this community. Le 18/03/2021 à 15:20, Simon Cruanes a écrit : > There are some balanced trees with a weight attached to each node. > I have an implementation in containers-data > [signature](https://c-cube.github.io/ocaml-containers/3.2/containers-data/CCWBTree/module-type-S/index.html) . > > There is a random_choose function that does the traversal and exploits > the weight to pick left/right for each node. > > I implemented this years ago but the comments say: > > Most of this comes from "implementing sets efficiently in a functional language", Stephen Adams. > The coefficients 5/2, 3/2 for balancing come from "balancing weight-balanced trees" >