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

Groups > comp.lang.java.programmer > #36310 > unrolled thread

Wanted: List of intervals

Back to article view | Back to comp.lang.java.programmer

Contents

  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

Page 1 of 2  [1] 2  Next page →

#36310 — Wanted: List of intervals

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.

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).

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.

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.

Why do I worry? Because some essential native libraries are 32-bit
only...

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [next] | [standalone]

#36311

On 2/16/2017 4:13 PM, 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.
>
> 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).
>
> 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.
>
> 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.

You say *long*. Does that mean that total range bytes can not be
in memory?

Arne

[toc] | [prev] | [next] | [standalone]

#36319

Arne Vajh??j wrote:
> On 2/16/2017 4:13 PM, 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.
> >
> > 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).
> >
> > 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.
> >
> > 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.
> 
> You say *long*. Does that mean that total range bytes can not be
> in memory?

I think you misunderstood, maybe I wasn't clear enough. I'll provide
a trivial example.

Given: a file reading
27 48
250 260
115 162
60 81
203 240
85 100
272 304
162 203
10 27
350 372
304 350

Wanted: an Iterable<long[2]> containing
10 48
60 81
85 100
115 240
250 260
272 373
Or: an array containing
10 48 60 81 85 100 115 240 250 260 272 373
Or: ...?

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [prev] | [next] | [standalone]

#36321

On 2/16/2017 9:49 PM, Volker Borchert wrote:
> Arne Vajh??j wrote:
>> On 2/16/2017 4:13 PM, 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.
>>>
>>> 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).
>>>
>>> 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.
>>>
>>> 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.
>>
>> You say *long*. Does that mean that total range bytes can not be
>> in memory?
>
> I think you misunderstood, maybe I wasn't clear enough. I'll provide
> a trivial example.
>
> Given: a file reading
> 27 48
> 250 260
> 115 162
> 60 81
> 203 240
> 85 100
> 272 304
> 162 203
> 10 27
> 350 372
> 304 350
>
> Wanted: an Iterable<long[2]> containing
> 10 48
> 60 81
> 85 100
> 115 240
> 250 260
> 272 373
> Or: an array containing
> 10 48 60 81 85 100 115 240 250 260 272 373
> Or: ...?

If that example is realistic then you can simply:
* allocate byte array of suitable length
* loop through intervals and mark corresponding bytes
* 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.

Arne

[toc] | [prev] | [next] | [standalone]

#36326

Arne Vajh??j wrote:

> If that example is realistic then you can simply:

Actually, the intervals are offset reanges for a file whose
total size may well exceed 4 GB.

I intentionally did not mention this to avoid pushing people's
thoughts into wrong directions.

I should have used larger numbers for the example, though.

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [prev] | [next] | [standalone]

#36345

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?

> * 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.

Kind regards

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

#36347

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.

Arne

[toc] | [prev] | [next] | [standalone]

#36348

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.  Memory use
would be O(biggestOffset - smallestOffset).

-- 
esosman@comcast-dot-net.invalid
Fourteen hundred thirty-one days to go.

[toc] | [prev] | [next] | [standalone]

#36349

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.

>     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).  It might 
still work well if the range is not too big.

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.

Cheers

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#36352

On 2/19/2017 11:00 PM, Arne Vajhøj wrote:
> On 2/19/2017 5:31 PM, Robert Klemme wrote:
>> 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.

If there is a valid assumption that large portions of the range
is not used then one could try a sparse list approach.

Instead of 30 bit indexed array then go for a 14 bit indexed
array of pointers to 16 bit indexed arrays that first get allocated
when needed.

But it did not sound from the original description that it would
be the case.

Arne

[toc] | [prev] | [next] | [standalone]

#36350

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.

Where the sorting solution is O(NlogN) and O(1).

>                                              Memory use
> would be O(biggestOffset - smallestOffset).

O(N) with some assumptions.

Arne

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

#36356

Eric Sosman <esosman@comcast-dot-net.invalid> wrote:
> (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.")

this O(listSize) is hardly relevant, if a sufficiently flexible
sparse-implementation is used, that allows you to skim over the
holes between entries at warp-speed.

[toc] | [prev] | [next] | [standalone]

#36359

On 2/20/2017 7:47 AM, Eric Sosman wrote:
> On 2/19/2017 10:52 PM, Arne Vajhøj wrote:
>> On 2/19/2017 5:18 PM, Eric Sosman wrote:
>>>     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.

I think that is what is typical done.

Big O is not a calculation formula but a description of characteristics.

>                                   (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.")

True.

That is O(N) in list size.

>> 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.

The hypothesis was O(N) in number of intervals with some assumptions.

If those assumptions are not met then I would expect it to be
less than O(N).

So that was a worst case assumption.

Arne

[toc] | [prev] | [next] | [standalone]

#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/

[toc] | [prev] | [next] | [standalone]

#36320

Robert Klemme wrote:
> >
> > 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

I'm aware of these. But they don't help much with either
ArrayList which doesn't "like" insertion other than at the end
LinkedList which doesn't "like" the random access.

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [prev] | [next] | [standalone]

#36315

On Thu, 16 Feb 2017 21:13:26 +0000, Volker Borchert wrote:

> 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).
>
Good KISS approach. 
I wonder about a couple of things you may be able to find out before 
going much further.

- how do you know that ArrayList.sort is O(log^2 n) when the method
  description doesn't say what algorithm is used?

  I've worked through the various sort algorithms in "Software Tools 
  in Pascal"(implemented in PL/9 and timed running on a 2MHz
  6809 box some time ago). The in-memory sorts ranged from Bubble Sort
  (n^2) to Quicksort (nlog n). However, I noticed during my tests that
  quicksort has an unspoken assumption that comparison is cheaper than
  exchanging misordered elements. As a result its blindingly fast if the
  key is an int but exchanges involve copying the elements. However, if
  comparisons are slow, e.g. lexigraphic comparison of multiple keys and
  misordered element exchanges are fast , e.g. swapping pointers to
  static elements, then the humble shell sort is quicker.

  In Java I'd hope that a decent compiler would swap references to
  misordered elements within the ArrayList to static elements in heap
  storage, so a comparison of ArrayList.sort() vs a quicksort algorithm
  could go either way.
 
- Just for giggles, have you tried replacing the ArrayList with a 
  self-ordering structure such as a TreeMap? 

  I know you thought about using a TtreeMap, but have you tried using
  one and timing it? Don't forget that large red/black trees are quite
  efficient at searching for a key because the search path is only 
  sqrt(n) deep, so just 23 comparisons are needed to find a key in a 
  tree containing 8 million items. You'd probably beat even that by
  walking the tree with two pointers and doing the concatenation as
  you read the data out of it. Its quite possible that this may be 
  the fastest solution for a large data set.

The sources I'd use to find sort algorithms with example implementations 
and performance analyses are "Algorithms" (Sedgewick), the aforementioned 
"Software Tools in Pascal" and "Algorithms + Data Structures = 
Programs" (Wirth) - all present their example implementations in Pascal, 
but that is easy to transcribe directly into Java.

Sedgewick's Algorithms is an excellent book that belongs in any serious 
programmer's library.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#36322

Martin Gregorie wrote:

> - how do you know that ArrayList.sort is O(log^2 n)

It's O(n log n), not O(log^2 n). 

>   when the method
>   description doesn't say what algorithm is used?

It's either mergesort or TimSort which should be better on arrays
containing "runs" of elements in either ascending or descending order.
Anyway, asymptotic worst case can't be much better.

> The in-memory sorts ranged from Bubble Sort
> (n^2) to Quicksort (nlog n).
 
Quicksort is O(n log n) only on average, worst case is O(n^2) e.g. for
input data that is sorted the wrong way. And it is not stable, but that
is not a problem in my case. On the other hand, it does not need extra
memory. So I might even consider it.

>   I know you thought about using a TreeMap, but have you tried using
>   one and timing it? Don't forget that large red/black trees are quite
>   efficient at searching for a key because the search path is only 
>   sqrt(n) deep, so just 23 comparisons are needed to find a key in a 
>   tree containing 8 million items.

Shouldn't that be log(n)? sqrt(8000000) is about 2800... 

>   You'd probably beat even that by
>   walking the tree with two pointers and doing the concatenation as
>   you read the data out of it. Its quite possible that this may be 
>   the fastest solution for a large data set.

Yes. This is one possible solution I've been thinking of. And since
I'm probably not the first one with this sort of problem, I hoped
someone else has published an implementation. A red/black tree is too
easy to get wrong for me being keen on doing it myself.

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [prev] | [next] | [standalone]

#36324

On Fri, 17 Feb 2017 03:30:13 +0000, Volker Borchert wrote:

> Shouldn't that be log(n)? sqrt(8000000) is about 2800...
>
Yes. Its been a while (1999): I translated the red-black tree code in 
Sedgewick's "Algorithms" into C and implemented it initially on an 
Alphaserver. It ran successfully pretty much straight away. There were 
about 100 million items in the tree. Keys were numeric strings averaging 
10 chars long and we were managing 25,000 - 30,000 lookups/sec. Misses 
were added to the tree as they ocurred.

This used my own code due to features of DEC Unix, which had a Mach-based 
micro-kernel. The library red-black tree code ran like a dog with a 
wooden leg, never exceeding around 1200 lookups/sec because it held the 
tree structure pointers, user data and key separately, so it needed 3 
mallocs for each node stored. The Mach kernel serialised user process 
memory management because there was only a single copy of the memory 
management code. So, I implemented my own memory management (grabbed a 
1MB chunk. Subsequent requests doubled in size until the chunks hit 
16MB), which gave us the speedup we needed by minimising memory 
management calls by a very large factor: evidently the default heap 
extension size was relatively small for this strategy to work as well as 
it did.
  
>>   You'd probably beat even that by walking the tree with two pointers
>>   and doing the concatenation as you read the data out of it. Its quite
>>   possible that this may be the fastest solution for a large data set.
> 
> Yes. This is one possible solution I've been thinking of. And since I'm
> probably not the first one with this sort of problem, I hoped someone
> else has published an implementation. A red/black tree is too easy to
> get wrong for me being keen on doing it myself.
>
No need of that: the TreeMap class is based on a red-black tree.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web