Is there any standard way to sort a disk file?

Discussion in 'C++' started by Peter Olcott, Jul 19, 2006.

  1. Peter Olcott

    Peter Olcott Guest

    I have used the standard template library quite a bit, and std::sort has been
    very useful. Now I have reached the point where my memory requirements are
    exceeded. Is there some standard way to sort a binary file with a specifically
    defined structure?

    The only thing that I could think of would be to std::sort portions of this file
    in memory, and then later manually merge these sorted portions together using a
    home brewed merge sort . Does anyone have any better ideas?
    Peter Olcott, Jul 19, 2006
    #1
    1. Advertising

  2. * Peter Olcott:
    > [bad cross-posting]


    Please don't cross-post to [clc++] and Microsoft-specific groups.


    > I have used the standard template library quite a bit, and std::sort has been
    > very useful. Now I have reached the point where my memory requirements are
    > exceeded. Is there some standard way to sort a binary file with a specifically
    > defined structure?


    Yes, COBOL does that.

    That does not mean you should cross-post to [clc++] and [comp.lang.cobol].


    > The only thing that I could think of would be to std::sort portions of this file
    > in memory, and then later manually merge these sorted portions together using a
    > home brewed merge sort . Does anyone have any better ideas?


    Follow-ups set to the two Microsoft groups.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
    Alf P. Steinbach, Jul 19, 2006
    #2
    1. Advertising

  3. Peter Olcott schrieb:
    > I have used the standard template library quite a bit, and std::sort has been
    > very useful. Now I have reached the point where my memory requirements are
    > exceeded. Is there some standard way to sort a binary file with a specifically
    > defined structure?


    Load the key and some index as pair into memory and sort it by key.

    After that, you can build a new file from the old file in the right
    order using the index.

    --
    Thomas
    Thomas J. Gritzan, Jul 19, 2006
    #3
  4. On Wed, 19 Jul 2006 11:42:02 -0500, "Peter Olcott" <>
    wrote:
    >I have used the standard template library quite a bit, and std::sort has been
    >very useful. Now I have reached the point where my memory requirements are
    >exceeded. Is there some standard way to sort a binary file with a specifically
    >defined structure?


    http://www.informatik.hs-bremen.de/~brey/stlbe.html

    Chapter 10 'External sorting' may be helpful.

    Best wishes,
    Roland Pibinger
    Roland Pibinger, Jul 19, 2006
    #4
  5. Peter Olcott

    Peter Olcott Guest

    "Thomas J. Gritzan" <> wrote in message
    news:e9lou0$a0u$...
    > Peter Olcott schrieb:
    >> I have used the standard template library quite a bit, and std::sort has been
    >> very useful. Now I have reached the point where my memory requirements are
    >> exceeded. Is there some standard way to sort a binary file with a
    >> specifically
    >> defined structure?

    >
    > Load the key and some index as pair into memory and sort it by key.
    >
    > After that, you can build a new file from the old file in the right
    > order using the index.
    >
    > --
    > Thomas


    That won't work in my case because all the data is used as the key.
    Peter Olcott, Jul 19, 2006
    #5
  6. Peter Olcott

    Jerry Coffin Guest

    In article <rhtvg.272$5H.39@dukeread06>, says...
    > I have used the standard template library quite a bit, and std::sort has been
    > very useful. Now I have reached the point where my memory requirements are
    > exceeded. Is there some standard way to sort a binary file with a specifically
    > defined structure?
    >
    > The only thing that I could think of would be to std::sort portions of this file
    > in memory, and then later manually merge these sorted portions together using a
    > home brewed merge sort . Does anyone have any better ideas?


    Yup, that seems pretty much correct. A few points: first of all,
    std::merge may simplify writing the merge portion of the sort. It'll
    handle most of the details of an individual merge run, so from there
    it's mostly a matter of deciding what merge pattern you want.
    Traditionally, the polyphase merge was generally considered the best,
    but I can't say I've done any recent testing to see how well it does
    for hard-drive based sorting. My immediate reaction is that it'll
    probably do quite well, but may not improve efficiency enough to be
    worth the trouble.

    To create your sorted runs, you're probably better off using a
    priority_queue than reading data into something like a vector,
    sorting it, and then writing it out. In particular, a priority_queue
    will typically allow you to create longer runs in your initial sorted
    files -- as you write out each record, you can read in another from
    the original input. As long as it doesn't precede those that have
    already been written out, you can add it to the priority queue, and
    from there it'll end up in the same file. On average this can nearly
    double the length of the initial runs, which generally helps quite a
    bit.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
    Jerry Coffin, Jul 20, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jas Shultz
    Replies:
    0
    Views:
    936
    Jas Shultz
    Dec 3, 2003
  2. Replies:
    12
    Views:
    506
    santosh
    Nov 15, 2006
  3. Navin
    Replies:
    1
    Views:
    668
    Ken Schaefer
    Sep 9, 2003
  4. Juan Zanos
    Replies:
    5
    Views:
    134
    Matthew B.
    Nov 19, 2010
  5. Andries

    is there a way ..... any way

    Andries, Apr 26, 2004, in forum: Perl Misc
    Replies:
    27
    Views:
    235
    Robin
    Apr 27, 2004
Loading...

Share This Page