Re: Add(Merge) two vectors

> merge uses 1 ptr_incr_cmp, 1 val_cmp and 1 val_assignment per Min(N1,N2)
and
> a simple copy of the rest. This has to be seen against the execution of a
> lot of utlitiy functions and the usage of lower_/upper_bound(!) for
> inplace_merge.

lower_bound() and upper_bound() are not required for inplace_merge() if
enough memory is available.

For inplace _merge(), the standard says
>> Complexity: When enough additional memory is available, ( last - first) -
1 comparisons. If no
additional memory is available, an algorithm with complexity N log N (where
N is equal to last first)
may be used.
<<

and for merge(), the standard says
>> Complexity: At most ( last1 - first1) + ( last2 - first2) - 1
comparisons.
>>

If you substitute last1 == first2 in the above complexity formula, that
comes down to

>>
Complexity: At most ( last2 - first1) - 1 comparisons.
>>

which is exactly the same number of comparisons as inplace_merge(). So
inplace_merge() does exactly the same "1 ptr_incr_cmp, 1 val_cmp and 1
val_assignment per Min(N1,N2)" in these circumstances, no different.

inplace_merge() is more complicated as you have observed.
If a buffer of sufficent size is not available then the implementation
usually has to do rotations of ranges of elements using whatever size buffer
was acquired. And since most implementations do this recursively, the
innermost inplace_merge()'s will at some point be using the buffer so
perfomance degrades gracefully.

But in terms of implementation, you can be very efficient

Suppose the number of elements in the first range is M and the number of
elements in the second range is N.
1) If the last element of the first range is less than or equal to the first
element of the second range, you can return immediately, there is nothing to
do for inplace_merge(), everything is already merged.
2) Then do a compare to see if the bottom elements of the first range are
already in the correct position
3) Then do a compare to see if the top elements of the second range are
already in the correct position
4) Acquire a buffer that is of size min(M1, N1) where M1 <= M and N1 <= N
5) Depending on the size of buffer acquired, you are doing a merge
forward/backward of the copied smaller elements or a divide-and-conquer
approach using whatever you got and buffered rotations/merges

> This means the smaller N1 and N2 are, and the more [0..N1)
> and [0..N2) are fragmented, ie the smaller fragments of each list are to
put
> in "wholes" of the other (that means more often lower_/upper_bound will be
> called), the more inplace_merge is inefficient against merge.
>
> > Effectively you are simulating inplace_merge() by doing this.
>
> No, merge is straight forward in code execution and therefore most
efficient
> (no extra overhead, see above). Allocating memory (when not initializing!)
> is O(1), regardless of space needed.

I am not wholly talking about merge() at this point. I am contrasting

1. inplace_merge()

versus

2(i) merge()
2(ii) the 3rd vector where output goes from merge().

The overhead of 2(ii) cannot be ignored if the sole reason for creating the
3rd vector is just to hold the output of merge(). And if the output vector
is empty you will be using back_inserter() which means memory allocation (or
a reserve). I am claiming that 2(i)+ 2(ii) combined are the equivalent to 1.

Of course, if your application _demanded_ the existence of the 3rd vector in
its own right, then merge() is always right, the overhead of 2(ii) may
shrink to nothing as your application already needs this 3rd vector.

> You are definitely wrong, because lower_/upper_bound will be used in
> implementing inplace_merge. I saw boost graph lib uses sorting the input
> vectors to std::inplace_merge.

I don't think I am wrong.

Examine Microsoft/Dinkumware's header <algorithm> and find inplace_merge()
(Using VC7.1 here but I think the implementation is more or less the same
for VC6/VC7/VC8). You see it calling lower_bound()/upper_bound() IF AND
ONLY IF -- MEMORY IS AVAILABLE (pardon me for the uppercase -- just
emphasising the point)??? I don't.

Same also with STLPort. In _algo.c, the auxilary function __merge_adaptive()
does not call
lower_bound(), upper_bound(), __rotate_adaptive() if enough memory is
available.

With the memory available, inplace_merge() is the same as merge().

Cheers

Stephen Howe







.

Relevant Pages

  • [NT] Defeating Microsoft Windows XP SP2 Heap Protection and DEP Bypass
    ... The following security advisory is sent to the securiteam mailing list, and can be found at the SecuriTeam web site: http://www.securiteam.com ... and bypassing DEP (Data Execution Prevention). ... Buffer overrun attacks are among the most common mechanisms, or vectors, ... a long string to an input stream or control longer than the memory ...
    (Securiteam)
  • RE: Defeating Microsoft Windows XP SP2 Heap protection
    ... Fact is XP SP2 is still far less likely to be vulnerable to buffer overflow ... > than the memory buffer allocated to hold it. ... > the operating system is now more careful to reduce both stack and heap ... > Execution Protection ...
    (microsoft.public.windowsxp.general)
  • Re: Discovering variable types...
    ... >- but I suppose MS expect us to use wrappers ... memory allocations for your variables from disk as well. ... >They most certainly are of fixed size, changing the size of a String ... >>me to keep buffer size and current postion right in the memory block. ...
    (comp.lang.pascal.delphi.misc)
  • Re: Discovering variable types...
    ... >memory it points to is on the heap. ... sequentially reading data, if one is randomly reading records, then a ... >project is what's prompting me to improve disk access. ... from a memory buffer I can do it in about a second. ...
    (comp.lang.pascal.delphi.misc)
  • Re: Multicast Directshow Graph Bridging, COW Rustling, & the Use of Portable Holes in Cartoon Ph
    ... memory to share buffer pools across processes and works pretty well. ... You get two basic Direct Show filters, ... issue each GMF-source a virtual memory alias with COW ...
    (microsoft.public.win32.programmer.directx.video)