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 51CCE5D4 for ; Thu, 18 Mar 2021 11:10:21 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="scan'208";a="498644980" 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 12:10:17 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id 2B1A8E6083; Thu, 18 Mar 2021 12:10:16 +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 E455EE0131 for ; Thu, 18 Mar 2021 12:10:12 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=barnier@recherche.enac.fr; spf=SoftFail smtp.mailfrom=barnier@recherche.enac.fr; spf=None smtp.helo=postmaster@smtp5-g21.free.fr IronPort-PHdr: =?us-ascii?q?A9a23=3AkaunGhMXsk6qJbyP4tAl6nZ/ChdPi93PFj5Q0YI?= =?us-ascii?q?ujvd0So/mwa6KFHLW6fgltlLVR4KTs6sC17OH9fm7BydauN6oizMrSNR0TRgLi?= =?us-ascii?q?MEbzUQLIfWuLgnFFsPsdDEwB89YVVVorDmROElRH9viNRWJ+iXhpTEdFQ/iOgV?= =?us-ascii?q?rO+/7BpDdj9it1+C15pbffxhEiCCybL9vKBi6txjdu8cXjIdtNKo91wbCr2dVd?= =?us-ascii?q?ehR2W5mP0+YkQzm5se38p5j8iBQtOwk+sVdT6j0fLk2QKJBAjg+PG87+MPktR/?= =?us-ascii?q?YTQuS/XQcSXkZkgBJAwfe8h73WIr6vzbguep83CmaOtD2TawxVD+/4apnVAPkh?= =?us-ascii?q?SEaPDM/7WrZiNF/jLhDrRy8uRJ/zY7aboKbOvVwcazSf88VS2VaU8ZNVCFMGJ+?= =?us-ascii?q?wY5cBAucDO+tTsonzp0EJrRu7HQSiHOLvxSNPhn/yx6I6yPkqHBzc0ww6GdIOs?= =?us-ascii?q?WrbrM/oP6oVSu+61rPIzTPCb/xIwzfw85LIfQ49rvGMQ71wa9beyUkxGA/fkFq?= =?us-ascii?q?Qr5bqMC+P2uQDqWiW9uxtXv+ghGA7sQ9+uCSvxtsyhYnTgIIY0k7J+Cp6zYs3O?= =?us-ascii?q?NC0VFB3bNGkHpVQqSyXOJV6Tt4hTmxrvCs3y70LtJy4cSYEy5kpxwPSZfOJfYW?= =?us-ascii?q?L/B/vSfqcLDZ+iXl4dry/gBOy/lKhyu36TsS030hFoTRGktnXuHAN0AbT6seZR?= =?us-ascii?q?fRj/UehwiyD1wfJ6uFLOUw0lKzbK4QgwrEqjJYTv17DEynrk0v1lK+bblso9vW?= =?us-ascii?q?25+j9fLnrpIWQOoBqhg3kMqkigs+yDfoiPgUPX2WX4/qw2KPg8EHjQrhHjPs7m?= =?us-ascii?q?bTDvp/AP8QUvKu5DhdV0ok97xa/CC+r0M8dnXkbNFJIeAuLj4f3N13TOvz4A+2?= =?us-ascii?q?/jEqynztxyfDGJKXtApTLLnfdjLfsZahx51NCxAYp09xS5YhYB74fLP7pWkL9r?= =?us-ascii?q?NnYAQU4MwywzebnEtJ91oYGVG2UGKCZKqXSsV6W6eI1OOSMfpEatyr9K/c7/f7?= =?us-ascii?q?hkX85lkEHcaa325sYcmy3Eu5oI0WDeXbsmMsOEX8WvgoiS+znkEGNXiRWZ3a2R?= =?us-ascii?q?q484jA7CJm6DYrYXYCsgLmB3D+hEZFMZ2BGDEqMEXbyeImeVfcMcnHaHsg0mTU?= =?us-ascii?q?BUf2lSpQ9/RCorg7zjbR9fcTO/ShNk5Po09x8/KX5nAs09DFuR5CX2nuLTmxut?= =?us-ascii?q?nkFTD87xqt/rApwzF6Il6Zi1a8LXedP7u9EB19pfaXXyPZ3XoiacjKERc+ATRO?= =?us-ascii?q?devvjGSs4JvorztQOblx2G9jkgxbK1GykGe1N/5S7Qacs+6eZ5EDfYsN0ynLIz?= =?us-ascii?q?q4k53E8T8BPOHethqM5+g7aDMjHiRfC/46aMJ8E1SuIz1+tiGqDuEYweBV1Tb2?= =?us-ascii?q?YGH9FPw3Yt9n0oE3YHefGNA=3D=3D?= IronPort-HdrOrdr: =?us-ascii?q?A9a23=3Am1sKta7Xx+m/adYCAwPXwDvXdLJzesId70hD?= =?us-ascii?q?6mlaTxtJfsuE0/20lPMA2hPuzBoXUncsmdePUZPwOE/035hz/IUXIPOeTBDr0V?= =?us-ascii?q?HIEKhO5ZbvqgeQfRHW2fVa0c5bHpRWLP3VIRxEgd3h4A++euxP/PCi/LqzjenT?= =?us-ascii?q?i1dhJDsaDJ1I1AtyBgaFHkAefmAvbvAEPaCB7clKrSfIQxsqR/m8b0NoY8Hz4/?= =?us-ascii?q?fRkpWjTRkYbiRGmWr+70LMmdrHLyQ=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0CTAgBuNFNghwUqG9RaHAMDBxYEBEKBU?= =?us-ascii?q?IMhVzkxhEKRHAglnFoLAQMBDSwIBAEBhFACgXkCHQwFLxMCEAEBBQEBAQIBAwM?= =?us-ascii?q?EARMBAQEBCw0JCCmFaA2COCKDawYjDwEFLSQLGgImAgJXEwYCAQEXglUBgwsLq?= =?us-ascii?q?22BMoVYhHMGgQ8qjUMmHIIMgTgMA4I3Lj6CSYJFgkmCYASCOSckbQgIvH+BZ4E?= =?us-ascii?q?ngzmGGZJuBQoflACQJ6BNlzaBa4FnDAczGggfETuCaVAZDY4qDgmFC4NWhUZAM?= =?us-ascii?q?gI2AgYBCQEBAwmQNQEB?= X-IPAS-Result: =?us-ascii?q?A0CTAgBuNFNghwUqG9RaHAMDBxYEBEKBUIMhVzkxhEKRHAg?= =?us-ascii?q?lnFoLAQMBDSwIBAEBhFACgXkCHQwFLxMCEAEBBQEBAQIBAwMEARMBAQEBCw0JC?= =?us-ascii?q?CmFaA2COCKDawYjDwEFLSQLGgImAgJXEwYCAQEXglUBgwsLq22BMoVYhHMGgQ8?= =?us-ascii?q?qjUMmHIIMgTgMA4I3Lj6CSYJFgkmCYASCOSckbQgIvH+BZ4EngzmGGZJuBQofl?= =?us-ascii?q?ACQJ6BNlzaBa4FnDAczGggfETuCaVAZDY4qDgmFC4NWhUZAMgI2AgYBCQEBAwm?= =?us-ascii?q?QNQEB?= X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="scan'208";a="376116705" X-MGA-submission: =?us-ascii?q?MDGR1y7fDgF9sl8gfkORs2lwVgT24M9Su8Z35X?= =?us-ascii?q?VQnvo3IQ8frNJXxVENr9xyIcF55lWvce/39U9MC11EAlsRkHH0GWJXuh?= =?us-ascii?q?U6WLHk3rYnxCF9liBs3549LNDP9ZC0EACH00Bth3FxCQ9tASlL+ZXShF?= =?us-ascii?q?5GoKMuYmUf94SWdl/pOt9gGA=3D=3D?= Received: from smtp5-g21.free.fr ([212.27.42.5]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 18 Mar 2021 12:10:11 +0100 Received: from [192.168.1.106] (unknown [82.65.228.77]) by smtp5-g21.free.fr (Postfix) with ESMTP id 66F475FFA9 for ; Thu, 18 Mar 2021 12:10:11 +0100 (CET) To: caml-list@inria.fr References: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> From: Nicolas Barnier Message-ID: Date: Thu, 18 Mar 2021 12:10:11 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.7.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-Transfer-Encoding: 8bit Content-Language: en-US Subject: Re: [Caml-list] Choosing a random element in a Map or a Set Reply-To: Nicolas Barnier X-Loop: caml-list@inria.fr X-Sequence: 18431 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: Hi Jean-Marc, Le 18/03/2021 à 10:44, jean-marc.alliot@irit.fr a écrit : > 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? If using a Map or a Set is not compulsory, you can design a data structure supporting insert, delete, search and random element in constant amortized time with an extensible array and a hash-table as explained here: https://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time/ I don't know if there are any good implementation of (Python-like) extensible arrays in a widespread OCaml library, but François Pottier published one as part of another superb data structure (union-find): https://gitlab.inria.fr/fpottier/unionfind/-/blob/master/src/StoreVector.ml You may want to adjust the ratio (2 here) by which the array is resized when necessary. Hope this helps, -- Nicolas