On Fri, Feb 18, 2005 at 03:21:10PM -0800, John Machin wrote: > Not robust in the face of input like: > [[1,1]] > or > [[1,2], [1,2]] > or > [[1,2], [2,1]] > or > [[1,2], [2,3], [3,1]]
oops, my bad.
>
> needs "if first == second: continue" here
>
> > if has_first and has_second:
>
> needs "if rev[first] == rev[second]: continue" here
an 'is' is enough, and better.
> > rev[first].extend(rev[second])
> > rev[second][:] = []
> > rev[second] = rev[first]
> > elif has_first:
> > rev[first].append(second)
> > rev[second] = rev[first]
> > elif has_second:
> > rev[second].append(first)
> > rev[first] = rev[second]
> > else:
> > copy = [first, second]
> > res.append(copy)
>
> My reaction to the "magic" by which res grows was "omigod that's the
> most horrible thing I've seen for quite a while" but there was worse to
> come :-)
what is magic about it? is it really that horrible?
> List appending is O(1) only in the amortised sense. Extending is not
> O(1) in any sense. Neither is the list comparison that is necessary for
> robustness (using your data structure, that is).
>
> You don't need to think. This problem has been extensively picked over
> by folk who are a lot smarter than us, starting from 30 years ago.
> Google for "disjoint set" and "union-find". One gets the impression
> that the best possible algorithm would be slightly *worse* than O(n).
Of course! I'd forgotten clean about union-find. And yes, it's
O(n*log(n)) union and find, and my implementation is O(n**2) for
union, O(1) for find; I'm pleased that, in spite of having forgotten
about union-find, I "reinvented" (heh) something that is better than
the "naive" implementation we saw in class.
Now I'm even more worried about your dismissal of this as magic and
horrible.
--
John Lenton ([EMAIL PROTECTED]) -- Random fortune:
Why don't you fix your little problem... and light this candle?
-- Alan Shepherd, the first man into space, Gemini program
signature.asc
Description: Digital signature
-- http://mail.python.org/mailman/listinfo/python-list
