From: Rob Biedenharn Date: 2012-11-13T08:08:14+09:00 Subject: Re: Efficient way for comparing records between 2 large files (16 million records) --Apple-Mail=_A0D8A737-37A0-4A45-A10B-D3D451D2E538 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=iso-8859-1 On Nov 12, 2012, at 5:21 PM, Ruby Student wrote: > Team, >=20 > I have two large files, about 16 million records each. > The files are sorted. > The first 13 characters are used as a key. > We get an updated file every week. > We also keep the previous week file. >=20 > I need to compare the keys from the new file to the keys on the file = from last week. If the rest of the records are the same, then I do = nothing. If the keys matches but the rest of the records are different, = I then have an update and I will output that record to a new file. > I was wondering if there is an efficient way to do this in Ruby. = Either any built-in method or an efficient algorithm which I can = implement. >=20 > Thank you >=20 >=20 > --=20 > Ruby Student You can get quite efficient using the important fact that the files are = already sorted by your key value. Your problem is a slight variation on the merge phase of an External = Sort http://en.wikipedia.org/wiki/External_sorting Let's name the two files P (as in "previous") and N (as in "new"). At each step, you have the next record from P and from N. One of three things will be true: 1) the keys match Compare the rest of the records and a) write the update if different b) do nothing if all are the same read the next P and the next N 2) Pkey < Nkey Pkey was missing from N Delete the record P (update to nothing?) if deletions can happen read the next P (only; use the same N for the next iteration) 3) Pkey > Nkey Nkey was missing from P Insert a new record N read the next N (only; use the same P for the next iteration) If the end of file is reached for only one of the files, treat the key = as always greater than the other from the not-yet-at-end file. When both ends-of-file have been reached, you are done. Close the files. Of course, this depends on being able to read the files one record at a = time (or having a buffer to do so). Since it seems like these might be = line-oriented files, I suspect you're OK here. -Rob= --Apple-Mail=_A0D8A737-37A0-4A45-A10B-D3D451D2E538 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=iso-8859-1
Team,

I have two large files, about 16 million = records each.
The files are sorted.
The first 13 characters are = used as a key.
We get an updated file every week.
We also keep the = previous week file.

I need to compare the keys from the new file to the keys on the file = from last week. If the rest of the records are the same, then I do = nothing. If the keys matches but the rest of the records are different, = I then have an update and I will output that record to a new file.
I was wondering if there is an efficient way to do this in Ruby. Either = any built-in method or an efficient algorithm which I can = implement.

Thank you


--
Ruby = Student

You can get quite efficient using the = important fact that the files are already sorted by your key = value.

Your problem is a slight variation on = the merge phase of an External Sort
http://en.wikipedia= .org/wiki/External_sorting

Let's name the = two files P (as in "previous") and N (as in = "new").

At each step, you have the next record = from P and from N.

One of three things will be = true:

1) the keys match
Compare = the rest of the records and
a) write the update = if different
b) do nothing if all are = the same
read the next P and the next = N

2) Pkey < Nkey
Pkey was = missing from N
Delete the record P (update to = nothing?) if deletions can happen
read the next P (only; use the = same N for the next iteration)

3) Pkey > = Nkey
= Nkey was missing from P
Insert a new record = N
= read the next N (only; use the same P for the next = iteration)

If the end of file is reached for = only one of the files, treat the key as always greater than the other = from the not-yet-at-end file.

When both = ends-of-file have been reached, you are = done.

Close the = files.

Of course, this depends on being able to = read the files one record at a time (or having a buffer to do so). Since = it seems like these might be line-oriented files, I suspect you're OK = here.

-Rob
= --Apple-Mail=_A0D8A737-37A0-4A45-A10B-D3D451D2E538--