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 A87095D4 for ; Thu, 18 Mar 2021 12:50:12 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="scan'208,217";a="498669820" 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 13:50:08 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id B4DCCE0148; Thu, 18 Mar 2021 13:50:08 +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 55392E0131 for ; Thu, 18 Mar 2021 13:50:04 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=ivg@ieee.org; spf=Pass smtp.mailfrom=ivg@ieee.org; spf=None smtp.helo=postmaster@mail-ot1-f48.google.com IronPort-PHdr: =?us-ascii?q?A9a23=3AcMZdzxYCilfxuKS1ZTgWee7/LTHM0IqcDmYuwqp?= =?us-ascii?q?isKpHd+GZx7+nAna3zctkgFKBZ4jH8fUM07OQ7/mxHzVbv93a4TgrS99lb1c9k?= =?us-ascii?q?8IYnggtUoauKHbQC7rUVRE8B9lIT1R//nu2YgB/Ecf6YEDO8DXptWZBUhrwOhB?= =?us-ascii?q?oKevrB4Xck9q41/yo+53Ufg5EmCexbal9IRmrqQjdrNQajIVjJ6o+xBbEpmZDd?= =?us-ascii?q?vhLy29vOV+dhQv36N2q/J5k/SRQuvYh+NBFXK7nYak2TqFWASo/PWwt68LlqRf?= =?us-ascii?q?MTQ2U5nsBSWoWiQZHAxLE7B7hQJj8tDbxu/dn1ymbOc32Sq00WSin4qx2RhLkl?= =?us-ascii?q?DsLOjgk+2zRl8d+jr9UoAi5qhNwzY7bYoGbOvR9cK3AY90VWXFMUdxNWyFbGI6?= =?us-ascii?q?wc5cDAugHMO1Fr4f9vVwOrR6mCAevGuPg0DlIjWL30609z+QhFh/G0xAgH9IPr?= =?us-ascii?q?HTUt8j+OaATUeCrw6nF1jTDYO1I1jjj8oTIdQohof6VUL92bMHexlUhGRnfgVW?= =?us-ascii?q?MtYzqISmV1uIVvmab4OduW+KihnI7pw1soTWj2MYhh4jHiI8WyV3I6zt0zoYoK?= =?us-ascii?q?dC2VUJ2bsKpHYZeuS2GOYV7Q8MvTn90tSg6xbALv4OwcisSyJk/2RLTd/iKf5K?= =?us-ascii?q?L7x/jTuqdPyp0iG5/dL+whBu/91WrxPfmWcmuyllKqzJIktnSuXAJ0Bze8s2HR?= =?us-ascii?q?eF8/kelwDqP0BzT5vxdLUA6mqfWKIQtwrE3lpoUvkTDGjH5lF/qg6+Rc0Uo4um?= =?us-ascii?q?o6+L5bbX6vpKQKZN4hwXkPqktmsGzG/o0PhUSU2SB9umx16Xv/UjjT7VLiv02n?= =?us-ascii?q?LPZsJffJckDp665HQBV350i6xmhETipzs4UnX4dLFJKYB6HlZTmO0nSIPDkCve?= =?us-ascii?q?ym0ijny1ux/DCJ7HhBpTNLmPfkLr6ZrZ860tcyBIpwtxF5pJUDKsBIPPpVUPru?= =?us-ascii?q?tzYFExxDwvhwevuDpB435kVH2uLBq6eLIvTq16UoOw1cMeWY4pAmSj0LbAK4OL?= =?us-ascii?q?pk3Q5mEMGNf2ow5Q/aX21E7JhOUrPMimkucsIDWpf5ll2d+ftklDXCVZ7VzOJR?= =?us-ascii?q?6s5owoDJsemAIPELqioib2FmSCnR9hYOjAABVeLHnPlMY6DXqVUAAqiZ/R5mzl?= =?us-ascii?q?BboCPDpc73HmGtQL3xvxgNOWGokUwhdfYzNFwotbru1Q3/D1wAd6a1gmlTmx5k?= =?us-ascii?q?yUPXTBkhchC?= IronPort-HdrOrdr: =?us-ascii?q?A9a23=3AtZ4ltqMjk1TvI8BcT5f155DYdL4zR+YMi2QD?= =?us-ascii?q?/UoZc20tTuWzkceykPMHkSLlkTp5YgBZpfmsGomlBUnd+5l8/JULMd6ZNjXOlW?= =?us-ascii?q?O0IOhZnO7f6hL6HSmWzJ8+6Y5BdOxEBMT0HRxGi6/BkWqFOvIB5PXCz6yyn+fZ?= =?us-ascii?q?yB5WLD1CT6179Q92BkK6PyRNNW17LKE0Hpad+cZLzgDIER8qR/+2CXUfU+/Iq8?= =?us-ascii?q?ejrvLbSCQbDB0q4hTmt0LO1JfGFXGjr3EjegIK77Nn1WTeiQT26uGYrvmnxnbn?= =?us-ascii?q?u1P73tB5nt3uz9cGKe6trowuKjvqghu1f4gJYdC/lQFwjueo5lMn1OPJvg5lBc?= =?us-ascii?q?Ju8HncF1vbnTLdnzLt2jov9HPuoGX3vUfe?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0C2BAD+S1NgfzDSVdFaHgEBCxIMghIBg?= =?us-ascii?q?TsCgjc6MYRCgR6QLoo3hhSDbYY3gWgLAQMBDQUvBAEBhFACgXkCHQcBBDUFDQI?= =?us-ascii?q?QAQEFAQEBAgEDAwQBEwEBDQsLCCeFag1DARABgWMig2sBAQMBEhEEGQEBNwEEC?= =?us-ascii?q?wsEAQY3AgIiEgEFARwZCBMHhTAFIZ8FgQQ9iy5/M4MEAQEGhXyBPAkSgSUCAQG?= =?us-ascii?q?GewEBhkQmHIFKQoFHgjcuPoQHgQeCSYJggj0HRL18gw6cTCKkJ7dzECOBSYF5f?= =?us-ascii?q?Qg7MQaCMlAZDY4fiQOFYSgvOAIGAQkBAQMJhXmKPAEB?= X-IPAS-Result: =?us-ascii?q?A0C2BAD+S1NgfzDSVdFaHgEBCxIMghIBgTsCgjc6MYRCgR6?= =?us-ascii?q?QLoo3hhSDbYY3gWgLAQMBDQUvBAEBhFACgXkCHQcBBDUFDQIQAQEFAQEBAgEDA?= =?us-ascii?q?wQBEwEBDQsLCCeFag1DARABgWMig2sBAQMBEhEEGQEBNwEECwsEAQY3AgIiEgE?= =?us-ascii?q?FARwZCBMHhTAFIZ8FgQQ9iy5/M4MEAQEGhXyBPAkSgSUCAQGGewEBhkQmHIFKQ?= =?us-ascii?q?oFHgjcuPoQHgQeCSYJggj0HRL18gw6cTCKkJ7dzECOBSYF5fQg7MQaCMlAZDY4?= =?us-ascii?q?fiQOFYSgvOAIGAQkBAQMJhXmKPAEB?= X-IronPort-AV: E=Sophos;i="5.81,258,1610406000"; d="scan'208,217";a="376130396" X-MGA-submission: =?us-ascii?q?MDH7OQ89vk2uU6Z5ltT9v7mrcmYQa1hY/Cpj03?= =?us-ascii?q?QxAfDOFOCGySCs7ShlZX5bCnUu9DTCsHxlC0zx3SuxohzfDbvs6t5aUs?= =?us-ascii?q?4Ys9jErfBig5X6ZX1RFqnptnm0Y/hXvnVpukkSybNZN9wCoYEWNDmhPP?= =?us-ascii?q?bqtJ/H2k8lvYKfVYZL3b/0XQ=3D=3D?= Received: from mail-ot1-f48.google.com ([209.85.210.48]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES256-GCM-SHA384; 18 Mar 2021 13:49:18 +0100 Received: by mail-ot1-f48.google.com with SMTP id 31-20020a9d00220000b02901b64b9b50b1so5043693ota.9 for ; Thu, 18 Mar 2021 05:49:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ieee.org; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=QxoIGtWdrNhO/Br39vq/vkW+PlvhsX4etcMGMbvnxxU=; b=EG4SvRrBGw2w/yO4nbS+rNJhLI97X7hMX3ro8gPE/ASRXMY8lzNtXkGLaFY8gk1n2s KJWEBu6rL2uK2dCfsMe8jjTwDyyOZvSidYaQ0tLRJFMRX9UTrPZF/l80Dwmg63YfnCJr zHNKVc5ryjYVQxIxdW1IVOlKSg7dLijhW5kKM= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=QxoIGtWdrNhO/Br39vq/vkW+PlvhsX4etcMGMbvnxxU=; b=eTXF2onyEk3AD1K0ENtipxZI6hebWhoVJcK3YpoElVmgBa6o4vSlxVK4BQ96bGn6xA mRxtGJXwagRjbbclcJpNZahWsqiB3UPV+S2XtZQnWO7MxnZwDlYa4dAPSNWyxn7IPsCP q+ZlhQEXzGgCSzkcKDRzi/pwYDlEjv9v6CW1+PBfgm8DjxyriRjlJXzVu0Mmii3rLwY+ a0Gonmta/w/5lVejAEhGa3+2eRprUz3tsOAXwyiL8Nvilrm9BlC9++UEt27KUsWr73jh l1d08XstzzHBFjhXK5tlo3wpdsyX2dNZfHYnsBFHUDA5+P9y7LYp2IByOabc4tvK3lYz 9YuQ== X-Gm-Message-State: AOAM533eG+W30SF5uBzhdFVRwRn5J+bDB3BdDi6IMXogTCYvUByE+GBw Cnv1j8VIyrz2r5HpDzffpO1Y8+5fwuYNgWsxEPpT98I/LkVEDQ== X-Google-Smtp-Source: ABdhPJwvi3jWUHYb/mWusAzsKjX6pnD9iL4133+GBKazIuJosdDr0XV7P/hFhK2F3r5obSLcJOtmhE1KKb7qiHByDQ4= X-Received: by 2002:a9d:3a37:: with SMTP id j52mr7127260otc.328.1616071757304; Thu, 18 Mar 2021 05:49:17 -0700 (PDT) MIME-Version: 1.0 References: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> In-Reply-To: <3e61c49d-8b20-378b-0c24-75b8da14b4f7@alliot.org> From: Ivan Gotovchits Date: Thu, 18 Mar 2021 08:48:34 -0400 Message-ID: To: jean-marc.alliot@irit.fr Cc: caml-list Content-Type: multipart/alternative; boundary="00000000000006c11405bdcf07e7" Subject: Re: [Caml-list] Choosing a random element in a Map or a Set Reply-To: Ivan Gotovchits X-Loop: caml-list@inria.fr X-Sequence: 18434 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: --00000000000006c11405bdcf07e7 Content-Type: text/plain; charset="UTF-8" On Thu, Mar 18, 2021 at 5:41 AM wrote: > 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 > As a side note, in case if you decide to pursue this idea. You don't really need to take the code as you can implement your solution using the public interface. For that, you need only these two public functions: `find_first` and `split`. The `find_first` function will help us to extract the top element (`let top t = fst@@find_first (fun _ -> true) t`), and `let destruct t = split (top t) t` will return you the left and the right subtrees, and the top element. The `destruct` function will not allocate or rebalance any trees and conceptually will just return pointers to the corresponding subtrees. So it is O(1) both in space and time. --00000000000006c11405bdcf07e7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


=
On Thu, Mar 18, 2021 at 5:41 AM <<= a href=3D"mailto:jean-marc.alliot@irit.fr">jean-marc.alliot@irit.fr>= wrote:
Dear lis= t,

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

As a side note, in case if you decide to pur= sue this idea. You don't really need to take the code as you can implem= ent your solution using the public interface.
For that, you = need only these two public functions: `find_first` and `split`. The `find_f= irst` function will help us to extract the top element (`let top t =3D fst@= @find_first (fun _ -> true) t`),
and `let destruct t =3D split= (top t) t` will return you the left and the right subtrees, and the top el= ement.=C2=A0 The `destruct` function will not allocate or rebalance any tre= es and conceptually
will just return pointers to the correspondin= g subtrees. So it is O(1) both in space and time.
--00000000000006c11405bdcf07e7--