Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#25774 closed enhancement (duplicate)

nondeterministic sorting

Reported by: guenterrote Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: cython Keywords: sorting of tuples and lists
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by guenterrote)

While looking for an bug in my program, I noted that the built-in "list.sort" function behaves erratically. Here is an example which carries out the same operation twice.

lu = [(((2, 3, 5, 6, 8), (2, 3, 8)), [1, 0, 1, 0, 0]), (((2, 3, 5, 6, 8), (2,
8)), [1, 0, 0, 1, 0]), (((2, 3, 5, 6, 8), (8,)), [1, 0, 0, 0, 1]), (((2,
3, 6, 8), (2, 3, 8)), [0, 1, 1, 0, 0]), (((2, 3, 6, 8), (2, 8)), [0, 1,
0, 1, 0]), (((2, 3, 6, 8), (8,)), [0, 1, 0, 0, 1]), ((2, 3, 8), [0, 0,
2, 0, 0]), ((2, 8), [0, 0, 0, 2, 0]), ((8,), [0, 0, 0, 0, 2])]

pulist = lu[-3:]
for i in lu[:-3]:
    pulist.append(i)
pulist.sort()

print "pulist sorted\n",pulist

lu = [(((2, 3, 5, 6, 8), (2, 3, 8)), [1, 0, 1, 0, 0]), (((2, 3, 5, 6, 8), (2,
8)), [1, 0, 0, 1, 0]), (((2, 3, 5, 6, 8), (8,)), [1, 0, 0, 0, 1]), (((2,
3, 6, 8), (2, 3, 8)), [0, 1, 1, 0, 0]), (((2, 3, 6, 8), (2, 8)), [0, 1,
0, 1, 0]), (((2, 3, 6, 8), (8,)), [0, 1, 0, 0, 1]), ((2, 3, 8), [0, 0,
2, 0, 0]), ((2, 8), [0, 0, 0, 2, 0]), ((8,), [0, 0, 0, 0, 2])]

pulist = lu[-3:]
for i in lu[:-3]:
    pulist.append(i)
pulist.sort()

print "pulist sorted again\n",pulist

If I open a new worksheet and enter the above in a block, the result comes out as follows.

pulist sorted
[((2, 3, 8), [0, 0, 2, 0, 0]), ((2, 8), [0, 0, 0, 2, 0]), ((8,), [0, 0,
0, 0, 2]), (((2, 3, 5, 6, 8), (2, 3, 8)), [1, 0, 1, 0, 0]), (((2, 3, 5,
6, 8), (2, 8)), [1, 0, 0, 1, 0]), (((2, 3, 5, 6, 8), (8,)), [1, 0, 0, 0,
1]), (((2, 3, 6, 8), (2, 3, 8)), [0, 1, 1, 0, 0]), (((2, 3, 6, 8), (2,
8)), [0, 1, 0, 1, 0]), (((2, 3, 6, 8), (8,)), [0, 1, 0, 0, 1])]
pulist sorted again
[(((2, 3, 5, 6, 8), (2, 3, 8)), [1, 0, 1, 0, 0]), (((2, 3, 5, 6, 8), (2,
8)), [1, 0, 0, 1, 0]), (((2, 3, 5, 6, 8), (8,)), [1, 0, 0, 0, 1]), (((2,
3, 6, 8), (2, 3, 8)), [0, 1, 1, 0, 0]), (((2, 3, 6, 8), (2, 8)), [0, 1,
0, 1, 0]), (((2, 3, 6, 8), (8,)), [0, 1, 0, 0, 1]), ((2, 3, 8), [0, 0,
2, 0, 0]), ((2, 8), [0, 0, 0, 2, 0]), ((8,), [0, 0, 0, 0, 2])]

However, it is not deterministic. If I hit "evaluate" repeatedly, it gives sometimes the same result for the two repetitions. When I run it in python2, or when I run sage from a script, the (correct) result is the first one.

The python2 specification says:

Objects of different types, except different numeric types and different string types, ... are ordered consistently but arbitrarily (so that sorting a heterogeneous array yields a consistent result).

CPython implementation detail: Objects of different types except numbers are ordered by their type names; ...

For me it was important to have *any* ordering whatever, but it should be ordered consistently. This error might be very annoying. (As a workaround, I will convert the "tuples" etc. to strings.)

(python3 does not allow comparison between an integer and a tuple).

I am attaching the notebook. I am using The Sage Notebook, Version 8.3.beta5. With Version 7.4, the problem does not seem to occur.

Attachments (1)

weird-sort.sws (765 bytes) - added by guenterrote 3 years ago.
saved worksheet

Download all attachments as: .zip

Change History (7)

Changed 3 years ago by guenterrote

saved worksheet

comment:1 Changed 3 years ago by guenterrote

  • Description modified (diff)

comment:2 Changed 3 years ago by guenterrote

  • Description modified (diff)

comment:3 Changed 3 years ago by jdemeyer

  • Milestone changed from sage-8.3 to sage-duplicate/invalid/wontfix
  • Resolution set to wontfix
  • Status changed from new to closed

This is not a bug.

You're trying to compare numbers and tuples. Effectively something like 1 < (2,3). In Python 3, this is actually an error. Sage makes no guarantees about this kind of sorting. If you really want to apply the Python 2 convention that you quoted, you should use Python integers instead of Sage integers.

comment:4 follow-up: Changed 3 years ago by guenterrote

If sage make no guarantees it would be much better to disable the comparison operations for sage-integers when the result makes no sense. rather than let unwary users run into a trap. (The _le_ etc. methods would have to be adapted so that they raise an exception, like in python3.)

Is it documented somewhere that sage makes no guarantees about this kind of sorting? sage.rings.integer.Integer? The Python2 convention that I cited would imply that even sage-integers should be "ordered consistently but arbitrarily" when compared to other objects.

(Let me explain the background. In my application, I generated some object (a polyhedral subdivision) whose vertices are naturally described by some combinatorial "code" (tuples of various nesting depth). I needed to process the vertices in SOME consistent order, no matter which. (in order to obtain matching triangulations on he boundaries between different cells). The permissive comparison conventions of python2 were very handy for this purpose. I trusted my results for some time, until some more elaborate tests revealed that the objects that I was creating were malformed.)

comment:5 Changed 3 years ago by guenterrote

  • Milestone changed from sage-duplicate/invalid/wontfix to sage-8.3
  • Priority changed from critical to major
  • Type changed from defect to enhancement

comment:6 in reply to: ↑ 4 Changed 3 years ago by jdemeyer

  • Milestone changed from sage-8.3 to sage-duplicate/invalid/wontfix
  • Resolution changed from wontfix to duplicate

Replying to guenterrote:

If sage make no guarantees it would be much better to disable the comparison operations for sage-integers when the result makes no sense.

Indeed. That's the goal of #22029.

Note: See TracTickets for help on using tickets.