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 29EAE5D4 for ; Fri, 19 Mar 2021 01:32:37 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.81,259,1610406000"; d="scan'208";a="498775875" Received: from prod-listesu18.inria.fr (HELO sympa.inria.fr) ([128.93.162.160]) by mail2-relais-roc.national.inria.fr with ESMTP; 19 Mar 2021 02:32:34 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id A9402E02E8; Fri, 19 Mar 2021 02:32:34 +0100 (CET) Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 3F31EE02E4 for ; Fri, 19 Mar 2021 02:32:31 +0100 (CET) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=mlists@ligand.eu; spf=Pass smtp.mailfrom=mlists@ligand.eu; spf=None smtp.helo=postmaster@relay1-d.mail.gandi.net IronPort-PHdr: =?us-ascii?q?A9a23=3A9qjE1BI3Fj9YdAR1Z9mcuAJhWUAX047cDksu8pM?= =?us-ascii?q?izoh2WeGdxfzKAkXT6L1XgUPTWs2DsrQY0ruQ6vu/EjdYqb+681k6OKRWUBEEj?= =?us-ascii?q?chE1ycBO+WiTXPBEfjxciYhF95DXlI2t1uyMExSBdqsLwaK+i764jEdAAjwOhR?= =?us-ascii?q?oLerpBIHSk9631+ev8JHPfglEnjWwba52IRmssAncuMsbjYRsJ6ot1xDEvmZGd?= =?us-ascii?q?+NKyG1yOFmdhQz85sC+/J5i9yRfpfcs/NNeXKv5Yqo1U6VWACwpPG4p6sLrswL?= =?us-ascii?q?DTRaU6XsHTmoWiBtIDBPb4xz8Q5z8rzH1tut52CmdIM32UbU5Uims4qt3VBPlj?= =?us-ascii?q?joMOjgk+2/Vl8NwlrpWrx2vqRJ/3YDafYOaNPRwca3ectIVWWVPU91NVyFCAIO?= =?us-ascii?q?wc5cDAvADMOtesoLzp0EOrRy7BQS0BO3v0CVHhnnq0q090uQhChzN0RE+ENIUr?= =?us-ascii?q?nvUqtr1O7kIUeuoy6TIyDHDb/JN2Tfh84jFaRQhofCDXb1qd8re1FMjGB3Yjli?= =?us-ascii?q?Jr4HuIjya2PgXvWeB8+pgSfygi3QhqwxpvjSi2Nohh4fLi48b1F3J9jl1zJorK?= =?us-ascii?q?dClVEJ2fN6pHZVNuyyaNoZ7QcMsTW92tCs0xLMLupy2cSoWxZkmxhPRZPqKeJW?= =?us-ascii?q?G7BLkUeaeOzZ4hHR9dbKwmRm970ugyvbyVsmzylZKoTRKncfPtnAWzRDT7dKHS?= =?us-ascii?q?vRl8keg3zaPzQHT5fteLUA6j6rWLYMqzL0olpcLr0jPAy37lF/0gaOKbEko5+u?= =?us-ascii?q?l5ur9brn7opKROZd4hhziPqg0hMCzHfg0PhIQU2SH5OiwzqDv8En/Tb5XlPM5i?= =?us-ascii?q?LPZv4rfJckDpq62HQtV0oE75halETim1M4XnHkaIF5cZR2LlY3pNEvPIPD8F/u?= =?us-ascii?q?/jE6jkDF2yPDHJLHhBIvCLmTbnLfge7Zy9VJcxRItwdxC5Z9YELMMLO7pVkPst?= =?us-ascii?q?9HVAAU1PxGwzuvpENl905kRWWOLAq+XKqPStlqI6/oqI+mIZY8Voyr9K+M+6v7?= =?us-ascii?q?qjH85lkUSfa+00pcNdn+4A+xqI1+Fbnr0ntcBDWAKsxIiQ+PwjV2CVSdfZ3KzX?= =?us-ascii?q?6In+jE2E5mmDIfGRoC1mrONxia7HptMZmBHEF+AC3nod5/XE8sLPSmbJ8sklj0?= =?us-ascii?q?fSZCgTZUg3FegrlzU0b1ie8TO8ysTspP4nPJ4/eDVmhwovWhxC8WGz3qlS2B7l?= =?us-ascii?q?2UEATIrivMs6Xdhw0uOhPAry8dTEsZesqshejd/DobVyqlBM/63XwvAetmTT1P?= =?us-ascii?q?OatGnDjg3QpQ83o1XC25NXu66hxWG5BKERqcPntSjAJ07+6TQmXXsdZ4V40aD7?= =?us-ascii?q?7EoihwdeuUKNWCigcZX7QXXDp+Q1knfkq+rceIT1SjB9SGFwHbc5Cll?= IronPort-HdrOrdr: =?us-ascii?q?A9a23=3AQIvcjan9BubZpUowowW271BV5rPpDfP6iWdD?= =?us-ascii?q?5ilNYBxZY6Wkvui0lvUayhP4zB4NMUtQ7+yoEqPoewKeybde544NMbC+GCzvv2?= =?us-ascii?q?W1JI9vhLGSsQHIMSv46+JbyONcY7FzYeeAT2RSoOTbxE2DE9gmyMSa66zAv42w?= =?us-ascii?q?815BRRxnApsQkDtRJwqfElJ7XwVKQac+faD82uNqvCGnYm5SU8LTPAhBY8HtvN?= =?us-ascii?q?vO/aiWGiIuJxli0wWWiCPt1biSKWnl4j46UylThZ84+2nEjACR3NTtj9ifygXA?= =?us-ascii?q?k07e6o0+oqqh9vJnBNaQzugZQw+cxzqAQYR6Rvm6uiopydvfpmoCtdnXvlMbI8?= =?us-ascii?q?9o4WjQdW3dm2qs5yDE0Cwyr0Pk00OSm3H5ocf0LQhKR/ZpoaJ8Xl/n51E7vNd6?= =?us-ascii?q?uZg7rl6xk5ZMFxvPkGDcyrHzJm9Xv3OurXAvnOIVhXA3a/pVVJZroYYS/FxYHf?= =?us-ascii?q?47dUqQhOBXdpgWfbnhzc1bfl+AY3fSsnMH+q3QYl0IEhCKTlNqgL3Q7xFtgHt7?= =?us-ascii?q?w0EErfZv10soyZMnR5FIo8TCP6h4/Ys+PfM+UKQVPpZ6feKHTkfATRXwMW6ILT?= =?us-ascii?q?3cZek6EkOIirqy2rkz6e2wPLEJwpcphf36ISdlnF93WmarM9SH2Nlw7xjRXH/V?= =?us-ascii?q?Z0WZ9uhuo7lc/oD9SdPQQFq+YWFrt8Ohpv4YE4n/W/G+Uag6P9bTaU/nGYNExG?= =?us-ascii?q?TFKulvAEhbdMUUv9IyXBawrtnQKovs39arO8r7Ff7KCjYrWmT2Bz8/WlHISvlo?= =?us-ascii?q?3wSQQ3f9xDfVU32FQD2cwbtAVJLC9+xW7YQTOogkiHlwtX2JovuTITkHiKYxZ0?= =?us-ascii?q?cWGsKDroqL4VOu9WKN1XhgJwZGZ3wlh4nIYjd0pRQXKQfPe74FvNmTEFoiv0e6?= =?us-ascii?q?Gg=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0D9AQAX/lNghsG3RtlaHQEBAQEJARIBB?= =?us-ascii?q?QUBQIFQgyFWAQE4MQqEOIkEhwIBAQaBOwOBMYkJhhSMDAsBAwENLAgEAQGEUAK?= =?us-ascii?q?BeQIdBwEENBMCEAEBBQEBAQIBAwMEARMBAQEBDQkLCCmFaA2COCKDagEBAQMBI?= =?us-ascii?q?w8BBS0ZCwQHGAICJgICVxkIE4JVAYJhBSULqwJ3gTKKPgaBDyqKMYMSJhx9gQ6?= =?us-ascii?q?Dfi4+gkmCRIJJgmAEgjknJG0ICJMdjUmcHIMOiVKSdQkipDKgU5IJhTGBa4FpD?= =?us-ascii?q?AcfLiYSO4JpUBcCDY4qDgmFC4NWhVQyAQIvAjYCBgEJAQEDCY5sgQ8BAQ?= X-IPAS-Result: =?us-ascii?q?A0D9AQAX/lNghsG3RtlaHQEBAQEJARIBBQUBQIFQgyFWAQE?= =?us-ascii?q?4MQqEOIkEhwIBAQaBOwOBMYkJhhSMDAsBAwENLAgEAQGEUAKBeQIdBwEENBMCE?= =?us-ascii?q?AEBBQEBAQIBAwMEARMBAQEBDQkLCCmFaA2COCKDagEBAQMBIw8BBS0ZCwQHGAI?= =?us-ascii?q?CJgICVxkIE4JVAYJhBSULqwJ3gTKKPgaBDyqKMYMSJhx9gQ6Dfi4+gkmCRIJJg?= =?us-ascii?q?mAEgjknJG0ICJMdjUmcHIMOiVKSdQkipDKgU5IJhTGBa4FpDAcfLiYSO4JpUBc?= =?us-ascii?q?CDY4qDgmFC4NWhVQyAQIvAjYCBgEJAQEDCY5sgQ8BAQ?= X-IronPort-AV: E=Sophos;i="5.81,259,1610406000"; d="scan'208";a="498775854" X-MGA-submission: =?us-ascii?q?MDGY9mU6HlHt/v59BDBvYT/VhYoUq7ag4feSHW?= =?us-ascii?q?damLNpUeDNaOjZ7iaML+dCN24gp6iDYijlCiJlOqSnby91qg7FJacIqQ?= =?us-ascii?q?8deT4LSmzdYV7/9nYUKdQok4EQf8cbtrz+L7ICiC+xdWbGvHc+EGqbAG?= =?us-ascii?q?sUPuZcVP0WxL4oiMTNXl21fw=3D=3D?= Received: from relay1-d.mail.gandi.net ([217.70.183.193]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 19 Mar 2021 02:32:30 +0100 X-Originating-IP: 10.200.201.19 Received: from webmail.gandi.net (webmail19.sd4.0x35.net [10.200.201.19]) (Authenticated sender: mlists@ligand.eu) by relay1-d.mail.gandi.net (Postfix) with ESMTPA id 5E75E240005 for ; Fri, 19 Mar 2021 01:32:30 +0000 (UTC) MIME-Version: 1.0 Date: Fri, 19 Mar 2021 10:32:30 +0900 From: Francois Berenger To: caml-list@inria.fr In-Reply-To: References: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> User-Agent: Roundcube Webmail/1.4.11 Message-ID: X-Sender: mlists@ligand.eu Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Subject: Re: [Caml-list] Choosing a random element in a Map or a Set Reply-To: Francois Berenger X-Loop: caml-list@inria.fr X-Sequence: 18437 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: On 18/03/2021 20:10, Nicolas Barnier wrote: > 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: Just FTR, a skip list would allow all the set operations, plus an efficient random access operation and element rank. Pugh, William. (1990). A skip list cookbook. I am not aware of an OCaml implementation with all the interesting operations though. > 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