Path: csiph.com!feeder.erje.net!2.eu.feeder.erje.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Robert Klemme Newsgroups: comp.lang.java.programmer Subject: Re: Wanted: List of intervals Date: Thu, 16 Feb 2017 23:18:28 +0100 Lines: 44 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net NSZdnCxdEVixtIaAUnSmaAdXCVd+0f4nfdFqcanHkmjcsQeKc= Cancel-Lock: sha1:JtgsZhGeB6xhRfyxyYPJC1JU5dU= User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.7.0 In-Reply-To: Xref: csiph.com comp.lang.java.programmer:36312 On 16.02.2017 22:13, 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. By current hardware standards I would almost call that "tiny". > 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). Is it really a performance issue that you need to tweak this approach? Or is it more that you find the current approach ugly (which I could understand)? > 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. I think you will have to implement the merging yourself as this is not a generic operation (i.e. dependent on the data type, in your case a tuple). > 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. There are some binary search implementations available that you could put to use in http://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html Kind regards robert -- remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/