Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: Wanted: List of intervals Date: Mon, 20 Feb 2017 07:47:50 -0500 Organization: A noiseless patient Spider Lines: 51 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 20 Feb 2017 12:46:00 -0000 (UTC) Injection-Info: mx02.eternal-september.org; posting-host="d107297532181dfe94e79c7c75bd43a4"; logging-data="32623"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/p6mbDwJma2cA0dgybNQQu" User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.7.1 In-Reply-To: Cancel-Lock: sha1:aUNB20doagEXEzM/x2BYggdu8fg= Xref: csiph.com comp.lang.java.programmer:36355 On 2/19/2017 10:52 PM, Arne Vajhøj wrote: > On 2/19/2017 5:18 PM, Eric Sosman wrote: >> On 2/19/2017 5:13 PM, Arne Vajhøj wrote: >>> On 2/19/2017 2:02 PM, Robert Klemme wrote: >>>> On 17.02.2017 04:32, Arne Vajhøj wrote: >>>> >>>>> If that example is realistic then you can simply: >>>>> * allocate byte array of suitable length >>>>> * loop through intervals and mark corresponding bytes >>>> >>>> What are "corresponding bytes"? Do you want to use the byte array as a >>>> bitset and mark all bits corresponding to values inside intervals? >>> >>> Yes. >>> >>>>> * loop through bytes and create new intervals >>>>> >>>>> But if the numbers really need to be long aka is greater >>>>> than MAX_INT, then that strategy does not work. >>>> >>>> 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. >> >> If I understand you correctly, the time should be O(n+m) >> for n intervals containing a total of m bytes. > > I would call that O(N) in number of intervals and O(N) > in interval length. I'm not sure why you would use the single symbol N to denote two entirely different quantities. (Also, as Robert Klemme pointed out, there's another component to the running time: The final scan takes O(listSize) time, independent of the number of intervals and the number of "marks.") > Where the sorting solution is O(NlogN) and O(1). > >> Memory use >> would be O(biggestOffset - smallestOffset). > > O(N) with some assumptions. It's the "some assumptions" that are at issue. If we had some ham we could have ham and eggs if we had some eggs. -- esosman@comcast-dot-net.invalid Fourteen hundred thirty days to go.