From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 03EE37F02B for ; Thu, 5 Nov 2015 11:35:56 +0100 (CET) IronPort-PHdr: 9a23:UnZCJhGfjEqEI6sl64XZwZ1GYnF86YWxBRYc798ds5kLTJ74ps6wAkXT6L1XgUPTWs2DsrQf27eQ6PurADdIyK3CmU5BWaQEbwUCh8QSkl5oK+++Imq/EsTXaTcnFt9JTl5v8iLzG0FUHMHjew+a+SXqvnYsExnyfTB4Ov7yUtaLyZ/niqbpoNaKOE1hv3mUX/BbFF2OtwLft80b08NJC50a7V/3mEZOYPlc3mhyJFiezF7W78a0+4N/oWwL46pyv+YJa6jxfrw5QLpEF3xmdjltvIy4gyLeVhOC7WcwVWAfkxwAQ1SUrUKyYpCknDHzsOF62TLSF8DsQLY7VC7qu6lxQRnjjyYccTQ06mzRhcFqpKNduhOo4RJlld36eoaQYdRk/69cZ9IRDUBGQ9wZAyJbD4+xdYoESeAGIPxwq4D+rlEHq124CBX6V7Cn8SNBmnKjhf5y6O8mCwyTmVF5Eg== Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=frederic.bour@lakaban.net; spf=Pass smtp.mailfrom=frederic.bour@lakaban.net; spf=None smtp.helo=postmaster@mail.lakaban.net Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of frederic.bour@lakaban.net) identity=pra; client-ip=213.251.185.180; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="frederic.bour@lakaban.net"; x-sender="frederic.bour@lakaban.net"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of frederic.bour@lakaban.net designates 213.251.185.180 as permitted sender) identity=mailfrom; client-ip=213.251.185.180; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="frederic.bour@lakaban.net"; x-sender="frederic.bour@lakaban.net"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail.lakaban.net) identity=helo; client-ip=213.251.185.180; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="frederic.bour@lakaban.net"; x-sender="postmaster@mail.lakaban.net"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CtBAC0LztW/7S5+9VehA5vrjORMyGFcQKBcRABAQEBAQEBAYEJgi6CCAEBBCMdAQEjCQsBDwsEFA0dAgI8CRIGExKIBwMWCbAMcYRjAQWHQwOERgEBAQEGAQEBAQEBAQEVBhmEK4cOhQiCbYFEhhAMkDGFHYgGgiKaIBEnK4IEDR2BV3GFHwEBAQ X-IPAS-Result: A0CtBAC0LztW/7S5+9VehA5vrjORMyGFcQKBcRABAQEBAQEBAYEJgi6CCAEBBCMdAQEjCQsBDwsEFA0dAgI8CRIGExKIBwMWCbAMcYRjAQWHQwOERgEBAQEGAQEBAQEBAQEVBhmEK4cOhQiCbYFEhhAMkDGFHYgGgiKaIBEnK4IEDR2BV3GFHwEBAQ X-IronPort-AV: E=Sophos;i="5.20,247,1444687200"; d="scan'208";a="152738814" Received: from pepper.lakaban.net (HELO mail.lakaban.net) ([213.251.185.180]) by mail3-smtp-sop.national.inria.fr with ESMTP; 05 Nov 2015 11:35:55 +0100 Received: from pearl (unknown [88.200.78.209]) (Authenticated sender: defre@ygg-drasil.fr) by mail.lakaban.net (Postfix) with ESMTPSA id 50C834C93D5; Thu, 5 Nov 2015 10:32:50 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=lakaban.net; s=default; t=1446719570; bh=4R3cxK0/bmaSiy6HUOUsSkUY5n1HNk7XJZ88UxZ/XDw=; h=Date:From:Subject:To:Cc:In-Reply-To:References:From; b=aJKaMiH5yFOIzyD+dG92ng64sWFSM94te00iPgW+hJY9egJwxA3fkFMkIl7IIhm+O 9YsBqTQdA6fFisOwNBQiu+/amzk9Gl2XSqGyGBpXC916F1Xv1Kq1ta9yg7JcbLTwRg yvJYLqaLQMRUnchXL2wEruQTRRXyQhKcJPBL6beY= Date: Thu, 05 Nov 2015 11:34:34 +0100 From: =?iso-8859-1?b?RnLpZOlyaWM=?= Bour To: Francois Berenger Cc: OCaml List Message-Id: <1446719674.22101.0@mail.lakaban.net> In-Reply-To: <563A42E9.7010008@inria.fr> References: <563A42E9.7010008@inria.fr> X-Mailer: geary/0.10.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="=-B30wT091UItJg/1YimFJ" Subject: Re: [Caml-list] Do we have a B-tree implementation in ocaml? --=-B30wT091UItJg/1YimFJ Content-Type: text/plain; charset=utf-8; format=flowed If I understand well, you want an efficient rank function on a sequence, you are not particularly interested in B-trees. I have an implementation of balanced trees you might be interested into: https://github.com/def-lkb/grenier/blob/master/baltree/bt1.mli It is a binary tree with a smart constructor to ensure only balanced trees are built. Beside that, no other constraints are applied. In particular these are not search trees although those can easily be implemented on top. O(1) access to the size (number of items) is provided, and as such an O(log n) rank function. Performance is also quite competitive: although I did not push the code yet, I implemented Map and Set from the standard library using these trees. On a small set of benchmarks I ran, these were at worst 10% slower than the standard ones. On Wed, Nov 4, 2015 at 6:39 PM, Francois Berenger wrote: > Hello, > > I am looking for even a simple implementation with at > least the following operations: > > insert/add, remove, mem/contains and at_rank. > > The at_rank is especially important since it is inefficient > to implement it using fold in a set like the ones from the stdlib. > > Thanks a lot, > F. > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/arc/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs --=-B30wT091UItJg/1YimFJ Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable
If I understand well, you want an efficient rank function on a sequenc= e, you are not particularly interested in B-trees.

I have an implementation of balanced trees you might be interested into:


It is a binary tree with a = smart constructor to ensure only balanced trees are built.
Beside= that, no other constraints are applied. In particular these are not search= trees although those can easily be implemented on top.

O(1) access to the size (number of items) is provided, and as such an= O(log n) rank function.

Performance is also quite= competitive: although I did not push the code yet, I implemented Map and S= et from the standard library using these trees. On a small set of benchmark= s I ran, these were at worst 10% slower than the standard ones.
<= br>

On Wed, Nov 4, 2015 at 6:39 PM, Francois Berenger <francois= .berenger@inria.fr> wrote:
Hello, I am looking for even a simple implementation with at least the following operations: insert/add, remove, mem/contains and at_rank. The at_rank is especially important since it is inefficient to implement it using fold in a set like the ones from the stdlib. Thanks a lot, F.
--=20
Caml-list mailing list. Subscription management and archives: https://sympa.inria.= fr/sympa/arc/caml-list Beginner's list: = http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inr= ia.fr/bin/caml-bugs
= --=-B30wT091UItJg/1YimFJ--