Есть ли таблица приоритетов для канонического упорядочения сортировки?


26

This answer, в котором я писал о Operator Precedence Table, был неожиданно популярен.
Это заставило меня думать о подобных вещах, и мне интересно:

Существует ли «заказ таблица» для канонического порядка, используемого Sort и аналогичными функциями?
(Ordering, Order, OrderedQ)

Это достаточно легко проверить порядок различных выражений, но так же, как таблица старшинство содержит несколько сюрпризов даже для опытных пользователей, я задаюсь вопросом, если канонический порядок делает тоже? Кажется странным, если это не ясно изложено где-то, но я не помню, чтобы видел такой список.

Документация Order соблазнительно говорит:

Order использует канонический порядок, как описано в примечаниях для сортировки.

Однако документация Sort довольно простой, насколько я могу найти, говоря только:

  • Сортировка по умолчанию заказов целых, рациональных и приближенных действительных чисел их численных значений.
  • Сортирует сложные номера по их реальным частям, а в случае равенства - по абсолютным значениям их мнимых частей.
  • Сортировка символов символов по их именам и в случае связи по их контекстам.
  • Сортируйте обычно выражения заказов, сначала помещая короткие, а затем сначала сравнивая детали в глубину.
  • Сортировка обрабатывает полномочия и продукты специально, приказывая им соответствовать членам полинома.
  • Сортировка строк, как в словаре, с заглавными версиями букв, следующих за строчными буквами. Сначала сначала сортирует обычные буквы, затем по сценарию, готическому, двойному, греческому и иврите. Математические операторы появляются в порядке убывания приоритета.

Это описывает, как Sort рассматривает некоторые классы выражений, но не описывает относительного упорядочения этих классов или пытается каким-либо образом быть исчерпывающим.

  0

Одним из следствий канонического упорядочения является то, что, например, символы и строки не сортируются интуитивно. В каноническом порядке порядок равен '{a1, a10, a2, a9}', тогда как интуитивная сортировка дает '{a1, a2, a9, a10}'. Это удобно при сортировке файлов, например. 28 авг. 132013-08-28 12:56:13

+2

Кроме того, последний пункт является либо запутанным, либо совершенно неправильным: 'Sort @ {" a "," A "," á "," Á "}' дает '{" a "," á "," A "," Á "}', что, по-видимому, означает, что * Mathematica * не может отличить акцентированные символы (как это уже обсуждалось [здесь] (http://mathematica.stackexchange.com/q/3813/89)). 28 авг. 132013-08-28 12:58:57

  0

@ IstvánZachar да первая точка - типичная задача вычисления - интуитивная сортировка - более известная как естественный порядок, должна быть выполнена другим способом (см. Http://mathematica.stackexchange.com/questions/10619/sort-strings- по-природно-упорядоченности). Этот последний момент для акцентированного персонажа действительно является неожиданностью! 28 авг. 132013-08-28 14:03:48

5

Ahh хорошие вопросы весело. Во всяком случае, это не исчерпывающий ответ, а просто быстрый тест по основам:

list = {0.1, I, 2 + I, 0, 2 , 2 x, x, xxx, 2^x, x^2, x^x, x^ (2 x), X, xX, "y", "yy", "Y"}; 
Sort[list] 

{0, I, 0,1, 2, 2 + I, 2^х, "у", " Y», "уу", х, 2 х, х^2, х ^, х^(2 х), X, XX, XXX}

Единственное, что захватывает мое внимание, это мнимые числа - с мнимая часть, считающаяся значением больше нуля, но меньше любого положительного числа. Кроме этого, сначала появляются числовые значения, за которыми следуют строки, затем символы. Каждая секция заказана в соответствии с документацией Sort, упомянутой в сообщении.

+1

'Sort @ Transpose @ {list, Ordering @ Ordering @ list}' => {{0, 1}, {I, 2}, {0,1, 3}, {2, 4}, {2 + I, 5} , {«Y», 8}, {«yy», 9}, {x, 10}, {2 x, 11}, {x^2, 12}, {x^x, 13}, {x^(2 x), 14}, {X, 15}, {xX, 16}, {xxx, 17}} и, насколько я знаю, выполняется следующее (всегда?): '(Sort @ mylist) [[Ordering @ Ordering @ mylist]] == mylist' (см. [здесь] (http://stackoverflow.com/a/4547546/499167)). [+ 1, btw] 28 авг. 132013-08-28 15:37:52


4

Через несколько минут крайнего замешательства, я обнаружил, что Sort помещает все целые и рациональные числа перед всеми выражениями, квадратные корни, которые, в свою очередь, идут до того предопределенные константы, как $e$ и $pi$ :

OrderedQ[N[{-Sqrt[2], -1, 0, 1/2, 1, Sqrt[2], E, [Pi], Sqrt[15]}]] 
>> True 

Sort[{-Sqrt[2], -1, 0, 1/2, 1, Sqrt[2], E, [Pi], Sqrt[15]}] 
>> {-1, 0, 1/2, 1, -Sqrt[2], Sqrt[2], Sqrt[15], E, [Pi]} 
+6

Это, наверное, известная проблема, но именно эта проблема вдохновила мой вопрос, и я обескуражен тем, что четыре года спустя у нас все еще нет ответа. Это должна быть основополагающая информация о заказе в * Mathematica *, а не догадки. См. [(2729)] (https://mathematica.stackexchange.com/q/2729/121) и его [связанные вопросы] (https://mathematica.stackexchange.com/questions/linked/2729?lq=1) , 01 авг. 172017-08-01 09:51:35

  0

Константы - это действительно символы с чем-то вроде «NValues» на них, поэтому они согласуются с предоставленной спецификацией в 'Sort' docs. 01 авг. 172017-08-01 20:23:50


11

Итак, я думаю, что документы - это в основном ясно, если трудно представить. Вот мой вариант такой таблицы:

{ 
    "Numerics" -> 
     { 
     "Negative Integer" -> -1, 
     "Zero" -> 0, 
     "Positive Integer" -> 1, 
     "Negative Float" -> [email protected]\[Pi], 
     "Positive Float" -> [email protected]\[Pi], 
     "Symbolic Constant (Pi)" -> \[Pi], 
     "Symbolic Constant (E)" -> E, 
     "Imaginary (Zero Real Part)" -> I, 
     "Imaginary (Positive Real Part)" -> 1 + I, 
     "Imaginary (Negative Real Part)" -> -1 + I, 
     "Root" -> Sqrt[a], 
     "Cube Root" -> CubeRoot[a], 
     "Power" -> Power[a, 5], 
     "Subtract" -> a - b, 
     "Add" -> a + b, 
     "Divide" -> a/b, 
     "Multiply" -> a*b 
     }, 
    "Strings" -> 
     { 
     "Plus" -> "+", 
     "Minus" -> "-", 
     "Equals" -> "=", 
     "Divide" -> "\[Divide]", 
     "Slash" -> "/", 
     "Question" -> "?", 
     "Paren Left" -> "(", 
     "Paren Right" -> ")", 
     "Bracket Left" -> "[", 
     "Bracket Right" -> "]", 
     "Angle Left" -> "<", 
     "Angle Right" -> ">", 
     "Curly Left" -> "{", 
     "Curly Right" -> "}", 
     "Association Left" -> "\[LeftAssociation]", 
     "Association Right" -> "\[RightAssociation]", 
     "Number Char" -> "1", 
     "Lowercase ASCII Char" -> "a", 
     "Uppercase ASCII Char" -> "A", 
     "Lowercase Non-ASCII Char" -> "ü", 
     "Uppercase Non-ASCII Char" -> "Ü", 
     "Lowercase ASCII Word" -> "gunther", 
     "Uppercase ASCII Word" -> "Gunther", 
     "Lowercase Non-ASCII Word" -> "günther", 
     "Uppercase Non-ASCII Word" -> "Günther", 
     "Lowercase Script Char" -> "\[ScriptA]", 
     "Lowercase Greek Char" -> "\[Alpha]", 
     "Lowercase Gothic Char" -> "\[GothicA]", 
     "Hebrew Char" -> "\[Aleph]" 
     } 
    } // 
    Append[#, 
     With[{ 
     e = Expr[], 
     sa1 = SparseArray[{1, 2, 3}], 
     sa2 = SparseArray[{"a", "b", "c"}], 
     sa3 = SparseArray[Band[{1, 1}] -> {1, 2, 3, 1}], 
     sa4 = SparseArray[Band[{2, 2}] -> {1, 2, 3}] 
     }, 
     System'Private'SetNoEntry[e]; 
     "Expressions" -> 
     { 
     "Symbol" -> a, 
     "Basic" -> expr[], 
     "Call" -> expr @@ Map[[email protected]*[email protected]*Last]@#, 
     "List" -> Map[[email protected]*[email protected]*Last]@#, 
     "Association" -> [email protected][[email protected]*Last]@#, 
     "Association 1" -> <|"Association" -> 1, "b" -> -100|>, 
     "Association 2" -> <|"Sorts" -> 1, "b" -> -100|>, 
     "Association 3" -> <|"By" -> 1, "b" -> -100|>, 
     "Association 4" -> <|"Key" -> 1, "b" -> -100|>, 
     "Association 5" -> <|-100 -> 1, "b" -> -100|>, 
     "SparseArray 1" -> sa1, 
     "SparseArray 2" -> sa2, 
     "SparseArray 3" -> sa3, 
     "Sparse Array 4" -> sa4, 
     "SparseNotArray" -> SparseNotArray[{1, 2, 3}], 
     "NoEntryExpr" -> e 
     } 
     ] 
     ] & // 
    Map[ReplaceAll[Rule[k_, k2_ -> v_] :> {k, k2, v}]@*Thread] // 
    Apply[Join] /* SortBy[Last] // 
Grid[List @@@ #, 
    Dividers -> GrayLevel[.8], 
    Background -> {{GrayLevel[.95], GrayLevel[.95], None}, None}, 
    Alignment -> Left 
    ] & 

(пришлось нарезать таблицу пополам, чтобы загрузить его через Imgur)

table pt 1

table pt 2

Обратите внимание, что основные Числовые и строки довольно ясны из документов. Из выражений вытекают только настоящие странности.

Один случай, который не обрабатывается в документах, - Association, который, конечно же, имеет некоторые структурные причуды. Очевидно, что сортировка осуществляется по ключевым словам, а не по значению, и она сортирует между числами и строками.

Другая странность - CubeRoot. Я понятия не имею, что с этим. Может быть, такой стол должен существует, поэтому WRI поймает ошибки в корневом пространстве (я думаю, что это ошибка).

Отметьте, что SparseArray сортирует, как его содержимое, что неудивительно, учитывая, как это содержимое сохраняется, даже если этот контент не указан. Независимо от того, влияет ли это на производительность, это не то, что я тестировал.

Другое дело, что выражения System'Private'NoEntryQ не сортируются странно, кроме Association.

  0

+1 для первой попытки в этом Q & A создать таблицу. Спасибо. 03 авг. 172017-08-03 16:17:09

  0

@ Mr.Wizard, к сожалению, я уже понял, что этого не хватает. Я предполагаю что-то вроде 'SparseArray' и других конструкций типа NoEntry типа странно, возможно, даже больше, чем' Association'. После того, как я прочитал записную книжку «Внутри шаблона Matcher», я посмотрю на это и обновлю. 03 авг. 172017-08-03 16:28:43

  0

Я не думал, что это будет исчерпывающим, но я искренне благодарю за это, и я с нетерпением жду вашего обновления. :-) 03 авг. 172017-08-03 16:33:21

  0

@ Mr.Wizard просто проверил некоторые базовые типы «NoEntry». Кажется, они выглядят нормально, что приятно. Не так много сюрпризов скрывалось здесь, как я ожидал. 03 авг. 172017-08-03 19:09:28