Path: csiph.com!aioe.org!.POSTED!not-for-mail From: =?UTF-8?Q?Arne_Vajh=c3=b8j?= Newsgroups: comp.lang.java.programmer Subject: Re: Wanted: List of intervals Date: Thu, 16 Feb 2017 17:11:55 -0500 Organization: Aioe.org NNTP Server Lines: 30 Message-ID: References: NNTP-Posting-Host: PBuS014lhzVyHjLbXmo/ZQ.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.7.1 X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.lang.java.programmer:36311 On 2/16/2017 4:13 PM, Volker Borchert wrote: > Given: a file containing an unordered list of disjoint but possibly > adjacent [long lower, long upper) intervals. > Wanted: a list of such intervals, sorted by lower, with adjacent input > intervals concatenated > > The worst case input list size n is (current knowledge) a million. > > Currently, I just read them into an ArrayList, sort() it and finally > concatenate. ("Make it work _first_ before you make it work _fast_.") > Asymptotic time is dominated by sorting's O(n log n). > > Does anyone know of a suitable (i.e., asymptotic time O(n log n) > or better, but less than 2n references) data structure that merges > during insertion? Apache commons-collections TreeList is unordered > thus requires binary search at O(log^2 n) for insert, and standard > TreeSet seems to be expensive when looking for previous and next. > > BSD-ish license preferred, LGPL OK, commercial will be considered. > > If I can't find anything, I'll probably write a special mergesort > that does the concatenation during merge. Not optimal, but better > than nothing and easy enough. You say *long*. Does that mean that total range bytes can not be in memory? Arne