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 DBB445D4 for ; Thu, 18 Mar 2021 14:21:03 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="asc'?scan'208";a="498697488" 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 15:21:00 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id AE2B7E0148; Thu, 18 Mar 2021 15:21:00 +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 26B7AE0131 for ; Thu, 18 Mar 2021 15:20:59 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=Neutral smtp.pra=simon.cruanes.2007@m4x.org; spf=Neutral smtp.mailfrom=simon.cruanes.2007@m4x.org; spf=None smtp.helo=postmaster@mout01.posteo.de IronPort-PHdr: =?us-ascii?q?A9a23=3Ammgvoxf3MVyJueFDqzBpZUUplGM+h9nLVj590bI?= =?us-ascii?q?XzolWe6HmxazJeXLljd1ThVPEFb/W9+hDw7KP9fy5CCpZusjK7itKWacPfidNs?= =?us-ascii?q?d8RkQ0kDZzNImzAB9muURYHGt9fXkRu5XCxPBsdMs//Y1rPvi/6tmZKSV3wOgV?= =?us-ascii?q?vO+v6BJPZgdip2OCu4Z3TZBhDiCagbb9oIxi6sAHcutMLjYZsK6s9xRrEr3VVc?= =?us-ascii?q?OlK2G1kIk6ekQzh7cmq5p5j9CpQu/Ml98FeVKjxYro1Q79FAjk4Km45/MLkuwX?= =?us-ascii?q?NQguJ/XscT34ZkgFUDAjf7RH1RYn+vy3nvedgwiaaPMn2TbcpWTS+6qpgVRHlh?= =?us-ascii?q?DsbOzM/7WrakdJ7gr5Frx29phx/24/Ub5+TNPpiZaPWYNcWSXNcUspNSyBNB4W?= =?us-ascii?q?xYIwSAeocJuZYt5fyqEcSrRWwAgmsAfngyj5OhnTr2aE33OAsHQTA0Qc9HdwBr?= =?us-ascii?q?W7Uoc37OqkST+670arGzTvMYPxKxDjy6pPFch89rfyWR798bdbdxVcpGgjYjlu?= =?us-ascii?q?Qs4vlPzaN2+oQsmib6u1gVeSygGM5sQFxvyKgxsEyhYnSm4kYzUvE9SR8wIYyI?= =?us-ascii?q?920UlJ0YcS5EJRKsSGVKZB2Ttk8T210pCo3yKYLuZu0cSkF0pgnwATfa/OefoW?= =?us-ascii?q?O/xnsW/qfLy1ii3J5ZLKwmQyy8U64x+D+S8S4zVJHozdYntfDtH0ByhPe5MebR?= =?us-ascii?q?vZj/kqv1zeC2xzS5+xKPUw5l6TVJZ48zrM0mJQdvlrOEzH4lknrkaObcFgv9Oa?= =?us-ascii?q?v6+TieLrmp5mcOpd7igH/LqQumtG/Dv8iPggPWGiW//m32r77/UDhXblHjf07n?= =?us-ascii?q?rPYvZ3YP8gWqK+0DxVI3oss9hqzFzSr3dACkXUaI19IeQiLg5b3N13SOvz0EPm?= =?us-ascii?q?yj0iqnTx23f7JJKfhDY/ILnXbkLfuY7J960lExQo2ytBf+o5UBq0cLP7pQk/xs?= =?us-ascii?q?8fYDgMnPAyz2eroFcty2psfWWKJHKCZLLvfvUKL6+8vOeWBZY0YtCzzJvUk/fL?= =?us-ascii?q?ikHA0lUIFcamsx5QXaXS4Hvp8I0WeZHrhmswBEWYPvgo5SuzmkkGNUSROZ3moW?= =?us-ascii?q?aIz+Co7BJi4AYvfWoyggqeM3CK0E5xZfGxGDUqMEXjwe4WeR/gMcD6SItNmkjE?= =?us-ascii?q?cSbeuUYoh1RW3uA/+yrpnNfbU9zYDtZPj0dh1//fcmQsz9TxyFcSd0nuCQ3t6n?= =?us-ascii?q?mMSFHcK2/VRu0V7RVCCyuBAhOBEFNFJr6dHSA48Ppnd1KpiDMzuWw/bVtaPUle?= =?us-ascii?q?vBNu8V2IfVNU0luQPZkF7U/64kxnF0jHiV6QUkruNQpcu76va0mO3fZ4llF7Di?= =?us-ascii?q?LlniEMpFJgcfVa6j7JyolCAT7XClF+UwuP3LMw07Gv27G6GiFG2kgRdWQ90X7/?= =?us-ascii?q?CWBg3YxfG69Pj6RGYJ5eeTI8/Ow4E8vasb6tHbtqBpVBBWeu7YZLGZHmtlmD2C?= =?us-ascii?q?RvantukXM/RY2wYmR7lJg0ciQl71XPaJU45HCjz+Qrj?= IronPort-HdrOrdr: =?us-ascii?q?A9a23=3AMX7aIqjyZ7hVmiUK0ZuBJFpk/3BQXjQji2hD?= =?us-ascii?q?6mlwRA09T+WznamV8sgz/xnylToXRTUMmcqYPrOBXHPb8vdOkO0sFJ2lWxTrv3?= =?us-ascii?q?btEZF64eLZsljdMgD36+I178pdWodkDtmYNzRHpOb8pDK1CtMxhOSAmZrY4tv2?= =?us-ascii?q?61dIYUVUZ7p77wF/YzzrcHFeYAVdH5I2GN69y6N8xwaIQngcYsSlCnRtZYGqzL?= =?us-ascii?q?f2vanrbhIcCxks5BPmt0LK1JfBDxOa0h0COgkv/Z4e9wH+/DDE2g=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AlAABbYVNgl40kQ7laGgEBAQEBAQEBA?= =?us-ascii?q?QEDAQEBARIBAQEBAgIBAQEBQIFQAoMfVwE4MY1GhlyBf4UTil+MAANUCwEDAQg?= =?us-ascii?q?FKggCBAEBhFACgXkCHQUGNRMCEAEBBQEBAQIBAwMEARMBAQEBAQEBAQkWBoYRD?= =?us-ascii?q?UMBEAGBYymDZAZlFBALRhBHBoMDAYMLAQqrUIE0iQuBNAoGgTkBgVKLcCaBBIE?= =?us-ascii?q?jg34uPoJgAgGHUwSCAoF9AoNKAQEBj3upOQEGAQGDBoEiiDCTMIMikE+QMaBTl?= =?us-ascii?q?zqBa4F8MxowQ4EegUtQGQ2OOIY6iBElATECATUCBgoBAQMJfBOBM405AQE?= X-IPAS-Result: =?us-ascii?q?A0AlAABbYVNgl40kQ7laGgEBAQEBAQEBAQEDAQEBARIBAQE?= =?us-ascii?q?BAgIBAQEBQIFQAoMfVwE4MY1GhlyBf4UTil+MAANUCwEDAQgFKggCBAEBhFACg?= =?us-ascii?q?XkCHQUGNRMCEAEBBQEBAQIBAwMEARMBAQEBAQEBAQkWBoYRDUMBEAGBYymDZAZ?= =?us-ascii?q?lFBALRhBHBoMDAYMLAQqrUIE0iQuBNAoGgTkBgVKLcCaBBIEjg34uPoJgAgGHU?= =?us-ascii?q?wSCAoF9AoNKAQEBj3upOQEGAQGDBoEiiDCTMIMikE+QMaBTlzqBa4F8MxowQ4E?= =?us-ascii?q?egUtQGQ2OOIY6iBElATECATUCBgoBAQMJfBOBM405AQE?= X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="asc'?scan'208";a="376144775" X-MGA-submission: =?us-ascii?q?MDE9pzr24oL8qfHncpEIjYLTRQQc5kKATAvd1n?= =?us-ascii?q?PuHEbMx55i+tQYbiUaAVpgtVCjRZtkOnJCzvmuHoC1FeclKIDsjHXSWu?= =?us-ascii?q?TYp+NIugnrOwKjmPCOn5RpJ55Du2X5b1Ok4xlS6hW1zh8rEa7YakekrT?= =?us-ascii?q?3qS/4Wp+YOShljsOPYBjKr5A=3D=3D?= Received: from mout01.posteo.de ([185.67.36.141]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 18 Mar 2021 15:20:58 +0100 Received: from submission (posteo.de [89.146.220.130]) by mout01.posteo.de (Postfix) with ESMTPS id 623B216005F for ; Thu, 18 Mar 2021 15:20:57 +0100 (CET) Received: from customer (localhost [127.0.0.1]) by submission (posteo.de) with ESMTPSA id 4F1Thm1jm5z9rxL; Thu, 18 Mar 2021 15:20:56 +0100 (CET) Date: Thu, 18 Mar 2021 10:20:54 -0400 From: Simon Cruanes To: =?utf-8?B?RnJhbsOnb2lz?= Pottier Cc: jean-marc.alliot@irit.fr, caml-list@inria.fr Message-ID: References: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> <368aa12e-e819-4049-7ec5-4a3479f77bbb@inria.fr> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="3bt9cd2LoxIx/6bt" Content-Disposition: inline In-Reply-To: <368aa12e-e819-4049-7ec5-4a3479f77bbb@inria.fr> Subject: Re: [Caml-list] Choosing a random element in a Map or a Set Reply-To: Simon Cruanes X-Loop: caml-list@inria.fr X-Sequence: 18435 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: --3bt9cd2LoxIx/6bt Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable 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/C= CWBTree/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-bal= anced trees" --=20 Simon Cruanes --3bt9cd2LoxIx/6bt Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEElJ/rh48GWcbX032NSsAdCEmqYrYFAmBTYcYACgkQSsAdCEmq Yra2kw//cdGJRqRyZOnC3ybcAhNMfQdA2TaKTFzRp8riVBp7np5exURNFFww3e0n /qdV1+6/ZRivy3/H8QZTmIrJSuyTUREhujPpE0Nx0xtpqzHNpZYkBf4S1Po6KiG6 doLegypd1J77BpVbOi5Sdb1s+i8L8D+yENjgmwCXAmYbnD0BRbSU2rGpmTNHsaSK OW0A2pUemW53zzzFfWQmpCMbMMqzpS0l1NfwGAOt/ChCTYwcrzKREZy4mqHcHTuO PZEvBme+6c1/BGpTGS0pEC4JYcrTrOryrbf57S3D+zW8FxSa3gW6gc1M+okUasDY erwlcW+jmbq+unCcDAYrIPeJa6MjEd9Z9XZrT1pEDwwAt68SlXLS3rtH/upDMI4A D5TZ6pn5xp0py4UZ2oYxq2tJc1Lnd+FTSPnsKhUB2XPildWqqyFlMV7+Rxk/HRkA /E4CM6AXy67IPQz6PPqMYuOr2h9OGAUiDLdJ+lITPAJe7sBCxOThJ8/eduyBGWma y3LED89yiBZoaNWA2xPRM4QFoqhEZpZRvT+gjBEGYUqMVPQQkbup/56Xrg5E0hil ChEmCv/qdVtH1hibAAyR2Yj8IftoR8ljJwLXi7LqvAevWuTqmZFzF05DKE75tX9X JqIvAZoGZC801Wjo9kv+gkBHRYRITNhc6QDt2MwRMK6vWhBvnn4= =ue3u -----END PGP SIGNATURE----- --3bt9cd2LoxIx/6bt--