Dave B wrote:
> On Sunday 4 May 2008 04:15, Dan Stromberg wrote:
>
>
>>On Sat, 03 May 2008 19:26:04 +0200, Dave B wrote:
>>
>>
>>>On Saturday 3 May 2008 18:51, Dan Stromberg wrote:
>>>
>>>
>>>>Isn't this what join(1) is for?
>>>
>>>AFAIK join operates on sorted files, which doesn't seem to be the case
>>>here.
>>
>>It seems to me either you accept the nlogn sort, or you end up with an
>>n^2 pair of nested loops, like what the OP had.
>
>
> Not if you use awk. With awk, you have a linear solution on the number of
> input records (assuming awk's hash lookups are efficient).

Are you sure awk use hash lookups? Occasionally done efficiency
analysis makes me suspect that a "standard" awk will use a tree
representation for associative arrays. The consequence would be
a O(N logN) complexity for accessing every element individually.

A full traversal, OTOH, could at least in theory be done in O(N),
even with a tree representation when additional measures would
be taken.

I'd be interested whether anyone knows about the implementation
of associative arrays in the various existing awks. (The POSIX
document seems not to specify any complexity requirements.)

Janis

> And, furthermore, I think it cannot be assumed that the files can be
> reordered at will.
>