Sorting Large File (Code/Performance)

[Ira.Kovac]

Hello all,

I have an Unicode text file with 1.6 billon lines (~2GB) that I'd like
to sort based on first two characters.

I'd greatly appreciate if someone can post sample code that can help
me do this.

Also, any ideas on approximately how long is the sort process going to
take (XP, Dual Core 2.0GHz w/2GB RAM).

Cheers,

Ira

[Paul Rubin]

Ir*******@gmail.com writes:

I have an Unicode text file with 1.6 billon lines (~2GB) that I'd like
to sort based on first two characters.

I'd greatly appreciate if someone can post sample code that can help
me do this.

Use the unix sort command:

sort inputfile -o outputfile

I think there is a cygwin port.

Also, any ideas on approximately how long is the sort process going to
take (XP, Dual Core 2.0GHz w/2GB RAM).

Eh, unix sort would probably take a while, somewhere between 15
minutes and an hour. If you only have to do it once it's not worth
writing special purpose code. If you have to do it a lot, get some
more ram for that box, suck the file into memory and do a radix sort.

[John Nagle]

Ir*******@gmail.com wrote:

Hello all,

I have an Unicode text file with 1.6 billon lines (~2GB) that I'd like
to sort based on first two characters.

Given those numbers, the average number of characters per line is
less than 2. Please check.

John Nagle

[Ira.Kovac]

Thanks to all who replied. It's very appreciated.

Yes, I had to doublecheck line counts and the number of lines is ~16
million (insetead of stated 1.6B).

Also:

>What is a "Unicode text file"? How is it encoded: utf8, utf16, utf16le, utf16be, ??? If you don't know, do this:

The file is UTF-8

Do the first two characters always belong to the ASCII subset?

Yes, first two always belong to ASCII subset

What are you going to do with it after it's sorted?

I need to isolate all lines that start with two characters (zz to be
particular)

Here's a start: http://docs.python.org/lib/typesseq-mutable.html
Google "GnuWin32" and see if their sort does what you want.

Will do, thanks for the tip.

If you really have a 2GB file and only 2GB of RAM, I suggest that you don't hold your breath.

I am limited with resources. Unfortunately.

Cheers,

Ira

[Stefan Behnel]

Ir*******@gmail.com wrote:

>What are you going to do with it after it's sorted?

I need to isolate all lines that start with two characters (zz to be
particular)

"Isolate" as in "extract"? Remove the rest?

Then why don't you extract the lines first, without sorting the file? (or sort
it afterwards if you still need to). That would heavily cut down your memory
footprint.

Stefan

[Stefan Behnel]

Stefan Behnel wrote:

Ir*******@gmail.com wrote:

>>What are you going to do with it after it's sorted?

I need to isolate all lines that start with two characters (zz to be
particular)

"Isolate" as in "extract"? Remove the rest?

Then why don't you extract the lines first, without sorting the file? (or sort
it afterwards if you still need to). That would heavily cut down your memory
footprint.

Just for fun, this is what I meant:

for utf8_line in open(filename, 'rb'):
if utf8_line.startswith('zz'):
print utf8_line

Stefan

[John Machin]

On Jan 25, 8:26 am, [e-mail] wrote:

I need to isolate all lines that start with two characters (zz to be
particular)

What does "isolate" mean to you? What does this have to do with
sorting? What do you actually want to do with (a) the lines starting
with "zz" (b) the other lines? What percentage of the lines start with
"zz"?

When looking at the GnuWin32 collection:
(a) "Unicode" is not relevant to your sort problem.
(b) grab yourself a wc and a grep while you're there -- they will help
with "how many lines" and "what percentage of lines" questions.

[Martin Marcher]

On Thursday 24 January 2008 20:56 John Nagle wrote:

Ir*******@gmail.com wrote:

>Hello all,

I have an Unicode text file with 1.6 billon lines (~2GB) that I'd like
to sort based on first two characters.

Given those numbers, the average number of characters per line is
less than 2. Please check.

which would be true if 1.599.999.999 had 2 chars and the rest of the lines
just one :)

(but yes that would be an interesting question how to sort a 1 character
line based on the first 2 of that line)

martin

--
http://noneisyours.marcher.name
http://feeds.feedburner.com/NoneIsYours

You are not free to read this message,
by doing so, you have violated my licence
and are required to urinate publicly. Thank you.

[John Nagle]

Ir*******@gmail.com wrote:

Thanks to all who replied. It's very appreciated.

Yes, I had to double check line counts and the number of lines is ~16
million (instead of stated 1.6B).

OK, that's not bad at all.

You have a few options:

- Get enough memory to do the sort with an in-memory sort, like UNIX "sort"
or Python's "sort" function.
- Thrash; in-memory sorts do very badly with virtual memory, but eventually
they finish. Might take many hours.
- Get a serious disk-to-disk sort program. (See "http://www.ordinal.com/".
There's a free 30-day trial. It can probably sort your data
in about a minute.)
- Load the data into a database like MySQL and let it do the work.
This is slow if done wrong, but OK if done right.
- Write a distribution sort yourself. Fan out the incoming file into
one file for each first letter, sort each subfile, merge the
results.

With DRAM at $64 for 4GB, I'd suggest just getting more memory and using
a standard in-memory sort.

John Nagle

[Paul Rubin]

John Nagle <na***@animats.comwrites:

- Get enough memory to do the sort with an in-memory sort, like
UNIX "sort" or Python's "sort" function.

Unix sort does external sorting when needed.

[John Nagle]

Paul Rubin wrote:

John Nagle <na***@animats.comwrites:

> - Get enough memory to do the sort with an in-memory sort, like
UNIX "sort" or Python's "sort" function.

Unix sort does external sorting when needed.

Ah, someone finally put that in. Good. I hadn't looked at "sort"'s manual
page in many years.

John Nagle

[Paul Rubin]

John Nagle <na***@animats.comwrites:

Unix sort does external sorting when needed.

Ah, someone finally put that in. Good. I hadn't looked at
"sort"'s manual page in many years.

Huh? It has been like that from the beginning. It HAD to be. Unix
was originally written on a PDP-11. The GNU version has also always
been external.

[Albert van der Horst]

In article <b1**********************************@i7g2000prf.g ooglegroups.com>,
<Ir*******@gmail.comwrote:

>Thanks to all who replied. It's very appreciated.

Yes, I had to doublecheck line counts and the number of lines is ~16
million (insetead of stated 1.6B).

Also:

>>What is a "Unicode text file"? How is it encoded: utf8, utf16, utf16le, utf16be, ??? If you don't know, do this:

The file is UTF-8

>Do the first two characters always belong to the ASCII subset?

Yes, first two always belong to ASCII subset

>What are you going to do with it after it's sorted?

I need to isolate all lines that start with two characters (zz to be
particular)

Like in?
grep '^zz' longfile aapje

You will have a hard time to beat that with python, in every respect.

<SNIP>

>
Cheers,

Ira

Groetjes Albert

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- like all pyramid schemes -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst