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: Sun, 19 Feb 2017 23:00:41 -0500 Organization: Aioe.org NNTP Server Lines: 43 Message-ID: References: NNTP-Posting-Host: PBuS014lhzVyHjLbXmo/ZQ.user.gioia.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit 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:36351 On 2/19/2017 5:31 PM, Robert Klemme wrote: > On 19.02.2017 23:18, Eric Sosman wrote: >> On 2/19/2017 5:13 PM, Arne Vajhøj wrote: >>> On 2/19/2017 2:02 PM, Robert Klemme wrote: > >>>> Even for ints the approach seems pretty wasteful, if I understood you >>>> correctly. >>> >>> I am not so sure about that. It is O(n) in number of intervals. >>> No sorting required. > > When I said "wasteful" I thought of the memory usage. But is it a problem? >> If I understand you correctly, the time should be O(n+m) >> for n intervals containing a total of m bytes. Memory use >> would be O(biggestOffset - smallestOffset). > > That is what I would assume, too. Runtime I would have said is O(n*m+o) > with n = number of intervals, m = average length of interval and o = > biggestOffset - smallestOffset (for the output generation). See my reply to Eric. I don't think two variable big O is standard. > It might > still work well if the range is not too big. Which is why I asked about the data size. > For the time being, I would stick with the sorting approach as this has > better predictable memory consumption. There memory usage depends on > the number of intervals input and not on the distribution of interval > ends. What I mean is, that for the bitset approach a single outlier is > sufficient to make memory consumption explode. If this data map can be in memory, then I would do an actual comparison to one of the better sorting approaches. Because of the different characteristics. Arne