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 19F495D4 for ; Thu, 18 Mar 2021 09:41:50 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="scan'208";a="498613059" 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 10:41:44 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id C56CBE013D; Thu, 18 Mar 2021 10:41:44 +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 86241E0131 for ; Thu, 18 Mar 2021 10:41:37 +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=3A3Qz8ihTwsX8oRGxUugmMB2Qhr9psokWfAWYlgqE?= =?us-ascii?q?Pu/d1aq2muq7aFwnh351FslbFUM3h5u5ejKKO6ua8AD1GuM3f+yhbOLV3FDY9w?= =?us-ascii?q?f0MmAIhBMPXQWbaF9XNKxIAIcJZSVV+9Gu6O0UGUOz3ZlnVv2HgpWVKQka3OgV?= =?us-ascii?q?6PPn6FZDPhMqrye+y54fTYwJVjzahfL9+Nhq7oRjVu8UMnIdvJKc8xhTVrndVZ?= =?us-ascii?q?u9b2X5mKVWPkhjm+8y+5oRj8yNeu/Ig885PT6D3dLkmQLJbETorLXk76NXkuhf?= =?us-ascii?q?fQwSP4GAcUngNnRpTHwfF9hD6UYzvvSb8q+FwxTOVPczyTbAzRDSi86JmQwLmh?= =?us-ascii?q?SsbKzI09nzch8pth6xZvR2hvQRyzZDUbo+IN/RwcK3SctwGSmRORctRSy5MD5m?= =?us-ascii?q?gY4cTAecMP+BVpJT9qVsUqhu+ABGhBOHxxTBSgH/6xKg63P47EQ7axgAvBdYOs?= =?us-ascii?q?HDVrNXyKKcfSuG1zLPJzTXfdf9W1y395Y7VeR8uvf+CR6h/cdbNyUYxDQPFiE2?= =?us-ascii?q?dpIP5Mz6R2OoBrXaX4uhiWOyhi2Mrtxx8riWzy8kiloXEmIAYx1HL+yh43Yo4J?= =?us-ascii?q?9K2RUp5bNO5DZdcqz+XOoR5TM4kXmpmuz46x6UFtJKnZiQG1YorywTBZ/GIbYS?= =?us-ascii?q?E+A/vWeiMLTtgh39oeaiziwu2/EWk0OHxUtS43ExLoyZZlNTHq2oD2AbJ6sedT?= =?us-ascii?q?/tw5keh1iiL1wDU8uxEOkU0lbbDK5I72b4wk4YTsVzEHi/rhEX6lqiWdl8+9ei?= =?us-ascii?q?u5OTofK/qppGGN4NsiwH+NLohmtCnDOk7LgQCRXWX9fqm2LH98kD1Xq9GguA4n?= =?us-ascii?q?6XEqJzaIN4Upq+9Aw9byIYj7BO/Ai+k0NsGh3YHKktJeBedgIjzJ17COur3DfO?= =?us-ascii?q?7g1Stlzdr2+vLPrz7ApXMMnjPirnhfaxl505G1AUz1cxf545TCrwZPP38QErxt?= =?us-ascii?q?NjBAh89Mgy02PrnBc5m1oIeXGKPGrWWPLnTsV+O/OIvIvODaJUbuDbneLAZ4Kv?= =?us-ascii?q?lhHo93FscZrWB3J0NaXn+EO41DV+eZC/uj94HVGIDpAF4RejuiVqeeT9JZmr0U?= =?us-ascii?q?bhvtXkAFIu6ANKbFciWi7ub0XLjdrVmI1teA1XJKk/GMoCNWvMCciWXSudgiD0?= =?us-ascii?q?YE7a7GdRJ/SHrjxfzzv9cFsSR4jcR3briztlpoePJx0la3QwxNNyU1iS2d08xn?= =?us-ascii?q?m4MQFcex6VjuQpmz0ub1rVkxftCHNpc6rVHSFViXaM=3D?= IronPort-HdrOrdr: =?us-ascii?q?A9a23=3A69BQt6r/0GiC9DHlVCZbTY8aV5siL9V00zAX?= =?us-ascii?q?/kB9WHVpW+afkN2jm+le6AT9jywfVGpltdeLPqSBRn20z+8J3aA6O7C+UA76/F?= =?us-ascii?q?a5NY0K1/qZ/xTMOQ3bstRc26BpbrRkBLTLZmRSoM7m7GCDc+oI7d+C+KCup+vP?= =?us-ascii?q?i01sQwZjdr16425CYDqzPVZxQGB9dPkEPb+d/NcCmz27ZX8MZN+6DXVtZZmkm/?= =?us-ascii?q?TutLbLJSELHAQm7g7mt0LM1JffHwKD1hkTFxNjqI1NzUH/nwb05rquvpiAo3ew?= =?us-ascii?q?60bp441SiJ/dzLJ4da6xo/MYNyn2jUKQbJlhMofigBkOvOqt5Fw2+eOinz4cOa?= =?us-ascii?q?1Ih0/5TyWQqRvp1xKI6kdL11bSjXuRgX7uuojdZB9SMbsnuatpNj/Q608tp5VG?= =?us-ascii?q?3KhTwkKV3qAndC/orWDY79jMWwovrGqYyEBS6dI7vjh6WYsaZKQUl4AZ4Qd/AP?= =?us-ascii?q?47bVnH1Lw=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0B+DABZH1NghoPyDFBagQmBUoF0ggIBJ?= =?us-ascii?q?hKEc4kEiBiEMJZcE4FoCwEDAQ0yAgQBAYZMHgwFMQQNAhABAQUBAQECAQMDBAE?= =?us-ascii?q?TAQEBAQsLCwgphXWCOCKEFEJJAiYCbAgBAReCVYMMq3aBMokjgS6BDyuLH4Rxg?= =?us-ascii?q?TiCRoRzgQeCSYJgBII5S6EKnHIHgwucPAUHAx+UAJAnqwSMf4FuB4FwdEyCak8?= =?us-ascii?q?ZDY44jjBAAWkCBgoBAQMJfI85AQE?= X-IPAS-Result: =?us-ascii?q?A0B+DABZH1NghoPyDFBagQmBUoF0ggIBJhKEc4kEiBiEMJZ?= =?us-ascii?q?cE4FoCwEDAQ0yAgQBAYZMHgwFMQQNAhABAQUBAQECAQMDBAETAQEBAQsLCwgph?= =?us-ascii?q?XWCOCKEFEJJAiYCbAgBAReCVYMMq3aBMokjgS6BDyuLH4RxgTiCRoRzgQeCSYJ?= =?us-ascii?q?gBII5S6EKnHIHgwucPAUHAx+UAJAnqwSMf4FuB4FwdEyCak8ZDY44jjBAAWkCB?= =?us-ascii?q?goBAQMJfI85AQE?= X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="scan'208";a="376101367" X-MGA-submission: =?us-ascii?q?MDHbDm9iAAmyEMPs6FsejYGWOqr3yV2ELln6Qn?= =?us-ascii?q?OFDUUiFjW5aIyeVVUyv5QOZ3nYgXrXt18S9c6WVy9ex0z8ki0PgbmdpL?= =?us-ascii?q?z4ppewS9k8vZmKrshwgKKt9QpgBIUD56tYSoeXPO2yqLB/rAu0/97y7Z?= =?us-ascii?q?OLQoEw2Z0GYm5hles8Y7XDUQ=3D=3D?= Received: from smtp09.smtpout.orange.fr (HELO smtp.smtpout.orange.fr) ([80.12.242.131]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 18 Mar 2021 10:41:36 +0100 Received: from god3 ([86.199.91.60]) by mwinf5d85 with ME id hlhb2400U1J8B2m03lhbWC; Thu, 18 Mar 2021 10:41:36 +0100 X-ME-Helo: god3 X-ME-Date: Thu, 18 Mar 2021 10:41:36 +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 1lMp9r-0006Q7-FP for caml-list@inria.fr; Thu, 18 Mar 2021 10:41:35 +0100 To: caml-list@inria.fr From: jean-marc.alliot@irit.fr Message-ID: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> Date: Thu, 18 Mar 2021 10:44:39 +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 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Content-Language: fr Subject: [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: 18429 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: Dear list, I am trying to take a random element from a Map or a Set. Currently, I generate one random int between 1 et Card(map), and I iter until I reach this element. The solution is in O(n) which is not great... I was about to code the following solution: take the current Map code and add a function which follows the balanced binary tree from the root and takes randomly a left or right turn at each node until we reach a leaf (we only need to generate one random int and use its binary representation to choose the left or right direction at each node). This should be in O(log(n)) Before I start coding like an idiot: 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... Thanks Jean-Marc