in reply to Re^2: [OT] A measure of 'sortedness'?
in thread [OT] A measure of 'sortedness'?

I know you said "call them numbers", but if they really are bytes of disk I/O data, the one-byte value range restriction does leave open the possibility of a very small index -- you could mark the first occurrence of each value in each of the buffers during the sequential scans.

Other metadata could be computed as well, if they will be revisited frequently, like run-length of a particular value.

During the merge operation, you might be able to speed up merge point decisions into what's left of the etherical 10% side buffer based on knowing where to go to get the next chunk of data that needs resequencing.

In fact, a run-length table in lieu of actual data might buy you the space you need for a one-pass optimization. Forget saving index offset. Save the value and the number of them. (WARNING: Corner case where lots of length < sizeof(integer) runs causes the working buffer to actually be larger than the source buffers should be considered.). Then just overwrite the buffer with the resulting data.

This would, of course, be an application-specific solution and not a general case proof for all airless merges, but sometimes that's the call the Engineer has to make.

Okay, I'm done spamming you for the moment and heading home. This one sounds basic but fun; I'll be following this thread closely.

Replies are listed 'Best First'.
Re^4: [OT] A measure of 'sortedness'?
by BrowserUk (Patriarch) on Mar 18, 2015 at 23:53 UTC

    I think this has triggered a workable idea.

    Given a 2GB buffer of (minimum) 8-byte records = 268,435,456 records; using 1-bit per record requires 32MB. Well within my 10%.

    So, what can I record with 1-bit?

    My first though is that I can record whether this record is contiguous with the preceding one. Ie. Is is equal to it; or exactly one greater. In effect, contiguous runs of 1-bits become chunks of the buffer(s) that can be translocated to their final position en-masse.

    And (I think) by processing down those bitmaps in parallel (though not lock-step), and knowing the first value in each of the two buffers, it gives me a a straight forward map of how things have to be moved into their final positions.

    Does that convert the original O(N2) process into an O(2(or 3?)N) process?

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
    In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]

      Not sure -- it's been a long time since I've had anything detailed enough to warrant computational analysis of the execution cost (I miss the old days when I worked on fun stuff).

      A side trip, though, if a full run length index might have had value (does not look like it here), here's a Perlized representation. Some of the code is sloppy, but I didn't go home like I said I would so I optimized Wife-Deprivation Units at the cost of Code-I-Could-Be-Proud-Of Units.

      Okay, so here's a proof-of-concept. The assumption is that a Run-Length table will consume notably less space than the original data, such as might be true in a disk I/O operation. This is not a universally-applicable assumption but may yield thoughts toward optimization in your specific case.

      Read more... (3 kB)

      Results on my test run: 

      D:\PerlMonks>perl merge1.pl
Buffers:
     [AAAAAABBCCCDDDDEEEEE]
     [AAAABBBBBBCCCCCDDDDD]
Buffers:
     [AAAAAAAAAABBBBBBBBCC]
     [CCCCCCDDDDDDDDDEEEEE]

D:\PerlMonks>

      [download]

[reply]
[d/l]
[select]

        With a (typically) minimum keysize of 64-bits, whilst repeats are not impossible, they are unlikely.

        But also, the same problem is true of my "equal to or greater by one" runs; they simply won't happen often enough to be of value.

        What's needed are runs of adjacent values in one buffer that don't appear in the other buffer; and vice versa.

        That means tracking both buffers concurrently -- which as I indicated in the OP is quite possible -- but it requires significantly more code and comparisons. Sufficiently more that it probably doesn't save anything when doing the merge :(

        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
        In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]

In Section Seekers of Perl Wisdom