Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #36355

Re: Wanted: List of intervals

Show key headers only | View raw

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.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-16 21:13 +0000
  Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-16 17:11 -0500
    Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 02:49 +0000
      Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-16 22:32 -0500
        Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 07:28 +0000
        Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-19 20:02 +0100
          Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 17:13 -0500
            Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-19 17:18 -0500
              Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-19 23:31 +0100
                Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 23:00 -0500
                Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 23:09 -0500
              Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 22:52 -0500
                Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-20 07:47 -0500
                Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-02-20 13:30 +0000
                Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-20 08:51 -0500
  Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-16 23:18 +0100
    Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 02:54 +0000
  Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-16 23:58 +0000
    Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 03:30 +0000
      Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-17 12:10 +0000
        Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 08:06 +0000
          Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-18 13:18 +0000
            Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 19:58 +0000
              Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-18 20:45 +0000
              Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-19 10:57 -0500
                Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-02-19 17:36 +0000
  Re: Wanted: List of intervals a.laforgia@gmail.com - 2017-02-17 03:13 -0800
  Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-17 08:20 -0500
  Re: Wanted: List of intervals Roedy Green <inquiry@mindprod.com> - 2017-03-08 01:30 -0800
    Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-09 19:32 +0000
      Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-09 23:05 +0000
        Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-11 01:40 +0000
          Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-11 12:39 +0000
            Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-11 18:15 +0000
              Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-11 21:47 +0000

csiph-web