From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id q1GCL95D026770 for ; Thu, 16 Feb 2012 13:21:09 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0DANPzPE8SB0QknGdsb2JhbABEsF8iAQEBAQEICwkJFCeBcgEBBAEnPhQFCwtGVwYTh3+wGIkHjF8DAwMCgzgnAgSDdASITp9v X-IronPort-AV: E=Sophos;i="4.73,428,1325458800"; d="scan'208";a="131633492" Received: from dmz-mailsec-scanner-7.mit.edu ([18.7.68.36]) by mail4-smtp-sop.national.inria.fr with ESMTP; 16 Feb 2012 13:21:03 +0100 X-AuditID: 12074424-b7fae6d000000906-5d-4f3cf4ae59a4 Received: from mailhub-auth-3.mit.edu ( [18.9.21.43]) by dmz-mailsec-scanner-7.mit.edu (Symantec Messaging Gateway) with SMTP id B7.D2.02310.EA4FC3F4; Thu, 16 Feb 2012 07:21:02 -0500 (EST) Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by mailhub-auth-3.mit.edu (8.13.8/8.9.2) with ESMTP id q1GCL0ud020396; Thu, 16 Feb 2012 07:21:00 -0500 Received: from localhost (CONTENTS-VNDER-PRESSVRE.MIT.EDU [18.9.64.11]) (authenticated bits=0) (User authenticated as jfc@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id q1GCKwnq010821; Thu, 16 Feb 2012 07:20:59 -0500 (EST) Message-Id: <201202161220.q1GCKwnq010821@outgoing.mit.edu> To: Goswin von Brederlow cc: Francois Berenger , caml-list@inria.fr In-reply-to: <87y5s3mb1z.fsf@frosties.localnet> References: <4F346DB9.2070303@riken.jp> <20120210182914.GA17498@annexia.org> <87wr7tb77z.fsf@frosties.localnet> <4F36AA45.1070502@colba.net> <4F38D455.1040204@irisa.fr> <4F3B0A46.3070105@riken.jp> <87mx8kruk1.fsf@frosties.localnet> <4F3C6AB4.6090100@riken.jp> <4F3C6D08.3020706@riken.jp> <87y5s3mb1z.fsf@frosties.localnet> Comments: In-reply-to Goswin von Brederlow message dated "Thu, 16 Feb 2012 09:34:16 +0100." X-Mailer: MH-E 8.2; nmh 1.3; GNU Emacs 23.1.1 Date: Thu, 16 Feb 2012 07:20:58 -0500 From: John Carr X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrGIsWRmVeSWpSXmKPExsUixCmqrbvui42/wbvdXBYH591htfi0YwOL xZwPtxgdmD0mvTjE4jFrd4LH7WfbWAKYo7hsUlJzMstSi/TtErgyzv3uZSmYxlHx6PsaxgbG BrYuRk4OCQETiUlL1kPZYhIX7oHYXBxCAvsYJY7uW8QO4WxglLj6bxcThNPAJDGlvZcVpIVX wEridvNNoBYODhEBHYm9vQIgYWYBW4nNPx8xgdjCQOEdK68ygticAvoS++7shxp6iEli97pO doiGYomV0/ezQpyhK/Fx0UywOIuAqsTf84fB4mwCshKP2rsYJzDyL2BkWMUom5JbpZubmJlT nJqsW5ycmJeXWqRrrpebWaKXmlK6iREUXOwuKjsYmw8pHWIU4GBU4uHlYLbxF2JNLCuuzD3E KMnBpCTKe+ATUIgvKT+lMiOxOCO+qDQntfgQowQHs5IIb9lHoBxvSmJlVWpRPkxKmoNFSZxX Q+udn5BAemJJanZqakFqEUxWhoNDSYL352egRsGi1PTUirTMnBKENBMHJ8hwHqDh/F9AhhcX JOYWZ6ZD5E8xKkqJ894GaRYASWSU5sH1wqL/FaM40CvCvC9BqniAiQOu+xXQYCagweYvrEAG lyQipKQaGIMnmWQIaymxfLgRUHTfQ1/pqkqQ/D1Nmd8eVam83io3OOZpVu57FbdWWuuGEe9f Z/ffy1tmrPL8bWTAVbby9LT163TnHHsRLZCq9UxPJn/eo8NcWyYs908PDKpnMDp2SD9+4oay 2GNu56vClud4/Y2Z+/1P+cm7MUGvuBytPh/J/3Rpy9cIMSWW4oxEQy3mouJEAK0CImnZAgAA Subject: Re: [Caml-list] Fwd: interval trees Goswin von Brederlow wrote: > Francois Berenger writes: > > > > let rec interval_tree intervals = > > match intervals with > > [] -> Empty > > | _ -> > > let x_mid = median intervals in > > let left, mid, right = partition intervals x_mid in > > let left_list = L.sort leftmost_bound_first mid in > > let right_list = L.sort rightmost_bound_first mid in > > Node (x_mid, > > left_list, right_list, > > interval_tree left, interval_tree right) > > > > I'm afraid my program could crash on a very long list of intervals. > > Each recursion halves the lists, right? That means you need a very very > very long list to exceed the recursion depth. How good is median selection? If it works like quicksort, approximating the median, typical stack depth is logarithmic and worst case stack depth is linear. If median selection is precise, creating a balanced tree, I wouldn't worry about stack depth.