On Aug 4, 3:14 pm, Robert Miller <r...@rlmiller.org> wrote: > If Python jumped off a cliff... Then Sage might as well :-). Or be reimplemented in CL.
> So then you would rather have Sage sets give an error rather than sort > in a list? I can't imagine why this is a good thing. You seem to be > ignoring the sorted() function altogether, rather than admitting it > can ever be useful. I think it will be confusing if Sage sets and python sets behave differently in that respect. That said, your choice is consistent with how python lists are compared, so as an attempt at total ordering of sets it's probably the best one. > I think that this is entirely too pedantic for the problem at hand. I > would like to pick an arbitrary, consistent ordering and stick with > it, to make the user's life easier, and the developer's. Which was my suggestion: Order the vertices by the order in which they are added. That is a well-defined, consistent choice that does not require a non-existing total ordering. Forcing people to be explicit about their choices often seems pedantic, until one encounters a situation where the choice unexpectedly makes a difference. > > Don't rely on sorting, but use other methods for getting consistent > > orderings and efficient membership tests. > > Such as? "order of introduction" and hashing. > > sage: f = PolynomialRing(ComplexNumbers(100),"x").random_polynomial() > > sage: L = f.roots() > > sage: sorted(L, key = lambda v: [v[0].abs(),v[0].arg()]) > > It is very difficult to define such a sort (which is consistent) on > arbitrary objects coming in without becoming *very* inefficient. But that's why you're explicit about your choice of "key": You only have to come up with a method that is consistent for your one example, so that the doctest does the right thing. > not trying to demand that all Sage objects always define a total > ordering, I'm just suggesting that since there is an inconsistent > definition of < for Sage sets, and since they get used frequently as > vertices, that we define a total ordering. You yourself admitted that > you can't think of a natural mathematical meaning for < for arbitrary > sets... I think you are patching things the wrong way around: We find that graphs assume the existence of a total ordering on their vertex set, but that such an ordering need not be implemented. The more natural way to solve the problem is by looking why graphs make that assumption and if they have to. Not by trying to endow everything with a total ordering. In terms of cost, I think your solution will be more expensive as well. Consider the lookup of a set V in a sorted list L of sets. This will cost log(len(L)) set comparisons. For each comparison V < W you incur len(V)*log(len(V))+len(W)*log(len(W) in sorting and then another O(len(V)) for finding the smallest element not in both V and W. So, assuming all sets in L have about the same cardinality as V, we get a complexity of O(len(L)*len(V)*log(len(V))) Compare this to a lookup of a set V in an indexed set L of sets. Computing the hash of V might take some time; O(len(V)) probably. But the elements of L should have their hashes already computed and cached (that would make sense for something like a frozen set). Then you just have a quick hash table locator, followed by a very small number of set comparisons (provided a decent hashing strategy is used). So this is O(C*len(V)) where C is the number of sets in a hash bin. The "O(1)" theory assumes hash computation is cheap (hence our "len(V)") and requires that C is independent of len(L), but I'm not sure this is feasible in practice. I think this example makes me even more convinced that vertices should be looked up via hashing and not via sorted lists and hence strengthens my opinion that "universal total ordering" is a bad thing, inviting bad programming style. But then again, I'm not volunteering to implement the required changes. I think we've had a very healthy discussion and seen some good arguments on either sides. Now it's up to the painter to choose the colour of the shed. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
