Path: csiph.com!aioe.org!news.mixmin.net!news2.arglkargh.de!news.karotte.org!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: Sun, 19 Feb 2017 23:31:38 +0100 Lines: 38 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable X-Trace: individual.net 0gDSQ7GyngS74l6vTRtD3QLp4LGBi/Osp+GYk7WxlaskTyXas= Cancel-Lock: sha1:Gjxluw02pkKR2ri79Qoz4HBOHP4= 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:36349 On 19.02.2017 23:18, Eric Sosman wrote: > On 2/19/2017 5:13 PM, Arne Vajh=C3=B8j 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. > 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 =3D number of intervals, m =3D average length of interval and o =3D= =20 biggestOffset - smallestOffset (for the output generation). It might=20 still work well if the range is not too big. For the time being, I would stick with the sorting approach as this has=20 better predictable memory consumption. There memory usage depends on=20 the number of intervals input and not on the distribution of interval=20 ends. What I mean is, that for the bitset approach a single outlier is=20 sufficient to make memory consumption explode. Cheers robert --=20 remember.guy do |as, often| as.you_can - without end http://blog.rubybestpractices.com/