Talk:Merge algorithm: Difference between revisions

Revision as of 16:05, 13 January 2008

Revision as of 02:43, 10 January 2009

Line 33:

Batch Processing

Batch processing occurs when files are processed off-line, i.e.
they are saved until some convenient time (e.g. at night) when the
computer system is not otherwise being used.

Updating files: the updates, i.e. the changed records, are "batched" together,
i.e. saved, and sorted into key order. Then the master file is read, one
record at a time, until a record with the same key as the first transaction is
found. This master file record is then updated and then the process is repeated.

The updating is done as follows:

* For magnetic tape. Put the updates in a separate file and merge the master
and the update to give a new master.

* For a disk, the easiest method is to associate a pointer with each record
leading to the next one (linked list). Individual records can be scrubbed
and replaced by reseting pointers.

In general, if only one master file is available, it is not altered, but a
new master is produced by merging.

Clearly in this context the new master file should not contain both the record from the old master file and the record from the update file, which would be the necessary consequence of interpreting "merge" as "produce multiset union".)

Line 51 ⟶ 60:

The kragen-hacks reference carries no weight in this case, because kragen-hacks is written by the same person who promulgated this questionable nomenclature in this Wikipedia article in the first place: me. If we decide to accept the term "merge" for this larger class of algorithms beyond just multiset union, it would have to be on the basis of documented terminology usage by people besides me. In my eyes, the fact that Knuth uses the term with a clearly more restricted meaning in mind creates a substantial burden of proof.

-- [[User:Kragen]]

-- KragenSitaker

== Minor change to python example ==