Как работает команда sort? (сортировка строк)

На самом деле это единственный раздел про unix на этом форуме

Модератор: /dev/random

Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Как работает команда sort?

Сообщение жучара »

Друзья! Файл src.txr
#
#4
+4
+

Shell

user@astra:~$ sort src.txt
#
+
#4
+4
user@astra:~$
Это всё, что угодно, но не лексикографический порядок.

++++++++++++++++++++++++++++++++++++++++++++++

И это ВЫРОЖДЕННЫЙ код и ВЫРОЖДЕННЫЙ исходник. Может показаться, что на выходе какой-никакой порядок (например, сперва строки группируются по длинам, а потом производится сортировка внутри каждой группы). Какое там! В реальном коде сортируются имена файлов, там путаница на выходе такая, что мама не горюй. Одна папка, потом другая папка, потом снова первая папка, да именно так. Функция sort бракованная или как? Спасибо, кто откликнется.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
olecya
Сообщения: 666
ОС: debian, fedora (i3-wm)

Re: Как работает команда sort?

Сообщение olecya »

Как на счет ответа в самой команде?

Код: Выделить всё

sort --debug file
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 19369
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Как работает команда sort?

Сообщение Bizdelnick »

Порядок сортировки зависит от локали. Если локаль юникодная, то см. https://www.unicode.org/reports/tr10/
env LC_COLLATE=C sort src.txt даст другой результат:

Код: Выделить всё

#
#4
+
+4
жучара писал(а):
03.12.2019 15:17
Одна папка, потом другая папка, потом снова первая папка,
Не верю. Показывайте.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Re: Как работает команда sort?

Сообщение жучара »

Bizdelnick писал:
03.12.2019 16:09
Не верю. Показывайте.
Папка foo суть корень дерева папок (содержит две папки # и +, а они тоже чего-то там содержат). Пустых папок нет. Все файлы нулевые. Латиница. ext4

Shell

user@astra:~$ find foo
foo
foo/#
foo/#/W
foo/#/W/o
foo/#/p
foo/#/a
foo/#/h
foo/#/as
foo/#/as/a
foo/#/D
foo/#/L
foo/#/L/a
foo/#/C
foo/#/C/o
foo/+
foo/+/ld
foo/+/K
foo/+/K/r
foo/+/Z
foo/+/Z/i
foo/+/3
foo/+/3/3
foo/+/G
foo/+/G/m
foo/+/r
foo/+/c
foo/+/c/c
foo/+/cr
foo/+/cr/p
foo/+/A
foo/+/A/A
foo/+/A/A/f
user@astra:~$
...А теперь сортирнём:

Shell

user@astra:~$ find foo | sort
foo
foo/#
foo/+
foo/+/3
foo/+/3/3
foo/#/a
foo/+/A
foo/+/A/A
foo/+/A/A/f
foo/#/as
foo/#/as/a
foo/+/c
foo/#/C
foo/+/c/c
foo/#/C/o
foo/+/cr
foo/+/cr/p
foo/#/D
foo/+/G
foo/+/G/m
foo/#/h
foo/+/K
foo/+/K/r
foo/#/L
foo/#/L/a
foo/+/ld
foo/#/p
foo/+/r
foo/#/W
foo/#/W/o
foo/+/Z
foo/+/Z/i
user@astra:~$
Ещё раз сортирнём и выведем только первые пять символов каждой строки для наглядности:

Shell

user@astra:~$ find foo | sort | cut -b1-6
foo
foo/#
foo/+
foo/+/
foo/+/
foo/#/
foo/+/
foo/+/
foo/+/
foo/#/
foo/#/
foo/+/
foo/#/
foo/+/
foo/#/
foo/+/
foo/+/
foo/#/
foo/+/
foo/+/
foo/#/
foo/+/
foo/+/
foo/#/
foo/#/
foo/+/
foo/#/
foo/+/
foo/#/
foo/#/
foo/+/
foo/+/
user@astra:~$
...так я и говорю, sort прыгает между папками, что вошь на гребешке. Ну и совсем красота, если выводить только файлы:

Shell

user@astra:~$ find foo -type f | sort | cut -b1-6
foo/+/
foo/#/
foo/+/
foo/#/
foo/+/
foo/#/
foo/+/
foo/#/
foo/+/
foo/#/
foo/+/
foo/#/
foo/+/
foo/#/
foo/+/
foo/#/
foo/+/
user@astra:~$
такие дела.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
olecya
Сообщения: 666
ОС: debian, fedora (i3-wm)

Re: Как работает команда sort?

Сообщение olecya »

Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Re: Как работает команда sort?

Сообщение жучара »

olecya писала:
03.12.2019 21:33
а это чего?

Shell

man sort
...
-V, --version-sort
natural sort of (version) numbers within text
натуральная сортировка чисел в тексте?
:wacko:
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 19369
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Как работает команда sort?

Сообщение Bizdelnick »

жучара писал(а):
03.12.2019 20:37
sort прыгает между папками, что вошь на гребешке
Ну так он ничего не знает про то, что / — это разделитель, и то, что он разделяет, надо сортировать по отдельности.
Почитайте всё-таки текст по приведённой мной выше ссылке. Там, среди прочего, говорится:
Collation order is not preserved under concatenation or substring operations, in general.
For example, the fact that x is less than y does not mean that x + z is less than y + z, because characters may form contractions across the substring or concatenation boundaries. In summary:
x < y does not imply that xz < yz
x < y does not imply that zx < zy
xz < yz does not imply that x < y
zx < zy does not imply that x < y
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
olecya
Сообщения: 666
ОС: debian, fedora (i3-wm)

Re: Как работает команда sort?

Сообщение olecya »

Вам такой нужен результат?

Shell

[nez@rox zhuchara]$ sort -V file
foo
foo/#
foo/#/C
foo/#/C/o
foo/#/D
foo/#/L
foo/#/L/a
foo/#/W
foo/#/W/o
foo/#/a
foo/#/as
foo/#/as/a
foo/#/h
foo/#/p
foo/+
foo/+/3
foo/+/3/3
foo/+/A
foo/+/A/A
foo/+/A/A/f
foo/+/G
foo/+/G/m
foo/+/K
foo/+/K/r
foo/+/Z
foo/+/Z/i
foo/+/c
foo/+/cr
foo/+/cr/p
foo/+/c/c
foo/+/ld
foo/+/r
команда sort по умолчанию учитывает только пробелы, буквы и цифры
с опцией -V вам будет доступна вся таблица менделеева
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Re: Как работает команда sort?

Сообщение жучара »

olecya писала:
03.12.2019 23:24
Вам такой нужен результат?

Shell

[nez@rox zhuchara]$ sort -V file
foo
foo/#
foo/#/C
foo/#/C/o
foo/#/D
foo/#/L
foo/#/L/a
foo/#/W
foo/#/W/o
foo/#/a
foo/#/as
foo/#/as/a
foo/#/h
foo/#/p
foo/+
foo/+/3
foo/+/3/3
foo/+/A
foo/+/A/A
foo/+/A/A/f
foo/+/G
foo/+/G/m
foo/+/K
foo/+/K/r
foo/+/Z
foo/+/Z/i
foo/+/c
foo/+/cr
foo/+/cr/p
foo/+/c/c
foo/+/ld
foo/+/r
команда sort по умолчанию учитывает только пробелы, буквы и цифры
с опцией -V вам будет доступна вся таблица менделеева
я вам благодарен, но я это хотел оставить на потом. Но раз такое дело, давайте с этим доразбираемся. Я правильно понял, что -V самый что ни на есть лексикографирческий порядок (что мне и надо)? Но я повторю. В man-e это должно как-то отразиться:

Shell

man sort
...
-V, --version-sort
natural sort of (version) numbers within text
натуральная сортировка чисел в тексте? На "сортирует в лексикографическом порядке" Это мало похоже. Скорее, подталкивает искать в тексте какие-то числа:
cafe3babe1hello2word
и их как-то сортировать.
cafe1babe2hello3word
И второе. Я пытался определить поведение команды sort по умолчанию. То есть если бы я прочёл, что команда sort по умолчанию действует ТАК-ТО эта тема была бы другой вплоть до полного отсутствия темы. Но я не прочёл потому, что в man sort не написано, как sort действует по умолчанию.
Write sorted concatenation of all FILE(s) to standard output.
А тогда:
olecya писала:
03.12.2019 23:24
команда sort по умолчанию учитывает только пробелы, буквы и цифры

откуда вы это знаете?
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5159
ОС: Gentoo

Re: Как работает команда sort?

Сообщение /dev/random »

жучара писал(а):
04.12.2019 17:40
Я правильно понял, что -V самый что ни на есть лексикографирческий порядок (что мне и надо)?
Нет.

По умолчанию используется лексикографический порядок. Вот только смысл термина "лексикографический порядок" зависит от локали. В юникодных локалях sort вкладывает в этот термин тот смысл, который требуется стандартом Unicode. К сожалению, это не тот смысл, который в него вкладываете вы.
Спасибо сказали:
Аватара пользователя
olecya
Сообщения: 666
ОС: debian, fedora (i3-wm)

Re: Как работает команда sort?

Сообщение olecya »

Код: Выделить всё

diff <(sort file) <(sort -d file)
Можете поэкспериментировать, вывести как я ваши пути в файл и например вместо решетки
в следующем пути поставить десять запятых или двадцать восклицательных знаков. Они все равно
будут выведены рядом

Код: Выделить всё

LESS=+/"-d," man sort
Есть нюансы с локалью но для общего понимания вполне подходит.
Добавлено (19:46):
Есть конечно различное поведение не очевидное с первого взгляда. Совсем недавно сама разбирала эффект

Код: Выделить всё

echo "azkpaxnz" | grep -o '\(.\).*\1'
Казалось бы жадность с "z.*z" должна победить, а на практике побеждает впереди стоящая "a"
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Re: Как работает команда sort?

Сообщение жучара »

/dev/random писал:
04.12.2019 18:27
К сожалению, это не тот смысл, который в него вкладываете вы.
и все добрые люди.

Код: Выделить всё

//foo.c
# include <stdio.h>
int main ()
{
	if (strcmp("#4", "+") < 0)
		printf ("#4 < +\n");
	return 0;
} 
Ниже как должен работать лексикографический порядок и как работает не пойми что.

Shell

user@astra:~$
user@astra:~$ gcc -o foo foo.c
user@astra:~$ ./foo
#4 < +
user@astra:~$ echo \#4 > bar
user@astra:~$ echo + >> bar
user@astra:~$ sort bar
+
#4
user@astra:~$
Раз уж разговор пошёл о терминах, то не поленюсь. Итак, сравниваем две строки посимвольно, пока не найдём разных символов. А тогда смотрим на код этих символов и та строка, код символа которой меньше и считается меньшей. Так, а если какая-нибудь строка закончится, а разных символов не будет найдено, то она считается меньше. Если две строки заканчиваются одновременно, то они равны. Я что-то сам придумал? Нет, взял из справочника по Си.

Тут, конечно, можно ещё оттачивать некоторые определения, но не заменить их на противоположные.

Другую сортировку, отличную от этой (ещё раз, взятой в справочнике по Си.) если и называть ТОЖЕ лексикографическим порядком, только другим, так это всё равно, что сказать: груша это тоже яблоко, только другое.

И да, все символы, с которыми до сих пор велась работа, соответствуют одним и тем же числам. Что в юникоде, что не в юникоде. Что в локали, что ещё где.

Вывод: sort по умолчанию что угодно, но не лексикографический порядок. Я бы с удовольствием послушал, как она сортирует по умолчанию. Если для этого придётся читать что-нибудь... Ну такое, что до весны мне с моим английским хватит, то очень грустно.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 19369
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Как работает команда sort?

Сообщение Bizdelnick »

жучара писал(а):
04.12.2019 20:09
не пойми что
Это не «не пойми что», а collation (фиг знает, как его по-русски).
жучара писал(а):
04.12.2019 20:09
Я бы с удовольствием послушал, как она сортирует по умолчанию. Если для этого придётся читать что-нибудь... Ну такое, что до весны мне с моим английским хватит, то очень грустно.
Поищите перевод, он наверняка есть.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5159
ОС: Gentoo

Re: Как работает команда sort?

Сообщение /dev/random »

жучара
То, что вы описываете, называется "бинарная сортировка". В юникодных же локалях используется алфавитная. Слова сортируются в алфавитном порядке в соответствии с алфавитами конкретных языков (даже если коды символов идут в другом порядке), а не-алфавитные символы принимаются во внимание в последнюю очередь. Загляните в любой словарь, посмотрите, как там отсортированы термины с пробелами, дефисами и другими символами внутри.
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Re: Как работает команда sort?

Сообщение жучара »

/dev/random писал:
04.12.2019 20:47
жучара
То, что вы описываете, называется "бинарная сортировка". В юникодных же локалях используется алфавитная. Слова сортируются в алфавитном порядке в соответствии с алфавитами конкретных языков (даже если коды символов идут в другом порядке), а не-алфавитные символы принимаются во внимание в последнюю очередь. Загляните в любой словарь, посмотрите, как там отсортированы термины с пробелами, дефисами и другими символами внутри.
вам виднее, оно, наверное, в самых пиковых случаях так, а в основном этак. Вот вспомнил, что я недавно читал про Grub
https://www.gnu.org/software/grub/manual/grub/grub.html
Там всё оглавление сплошь лексикографический порядок бинарная сортировка.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Re: Как работает команда sort?

Сообщение жучара »

Люди добрые, ну нельзя же писать это в манах

Shell

(1) If you use a non-POSIX locale (e.g., by setting `LC_ALL' to
`en_US'), then `sort' may produce output that is sorted differently
than you're accustomed to. In that case, set the `LC_ALL' environment
variable to `C'. Note that setting only `LC_COLLATE' has two problems.
First, it is ineffective if `LC_ALL' is also set. Second, it has
undefined behavior if `LC_CTYPE' (or `LANG', if `LC_CTYPE' is unset) is
set to an incompatible value. For example, you get undefined behavior
if `LC_CTYPE' is `ja_JP.PCK' but `LC_COLLATE' is `en_US.UTF-8'.
Note that setting only `LC_COLLATE' has two problems.
First, it is ineffective if `LC_ALL' is also set.
Переводим.
Заметим, что установка ТОЛЬКО ЛИШЬ (без всяких других опций) `LC_COLLATE' имеет две проблемы. Во -первых, оно неэффективно, если `LC_ALL` также установлено.
как такое вообще можно придумать, я не понимаю?
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5159
ОС: Gentoo

Re: Как работает команда sort?

Сообщение /dev/random »

жучара писал(а):
05.12.2019 01:09
как такое вообще можно придумать, я не понимаю?
В первом случае, "setting only LC_COLLATE" - имеется в виду установка прямо сейчас, специально для sort. Во втором случае, "if LC_ALL is also set" - имеется в виду если вы установили раньше, или кто-то установил за вас. Они не противоречат друг другу. Например, если вы используете sort в скрипте, и установили в этом скрипте только LC_COLLATE, без LC_ALL, то пользователь, запустивший ваш скрипт с собственным LC_ALL, сломает его. Как такое вообще можно не понять?
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Re: Как работает команда sort?

Сообщение жучара »

ТОЛЬКО ЛИШЬ (без всяких других опций) означает именно это. И не должно быть, что LC_ALL (ОКАЗЫВАЕТСЯ) тоже может быть установлено.

Это как сказать: если в комнате ТОЛЬКО ОДНА КОШКА, то это не значит, что кошка одна потому, что там может быть и вторая кошка. Шутим мы так, ага.

++++++++++++++++++++++++++++++++++++++++++++++++++

Но хрен с ним со всем. Дальше ещё хлеще.
Second, it has undefined behavior if `LC_CTYPE' (or `LANG', if `LC_CTYPE' is unset) is set to an incompatible value. For example, you get undefined behavior if `LC_CTYPE' is `ja_JP.PCK' but `LC_COLLATE' is `en_US.UTF-8'.
Переводим:
Во-вторых, оно имеет неопределённое поведение, если LC_CTYPE установлен в неподдерживаемое значение (чё в скобках опустим для простоты). Например, вы можете получить неопределённое поведение если `LC_CTYPE' есть `ja_JP.PCK', а `LC_COLLATE' есть `en_US.UTF-8'.
Допустим, что `ja_JP.PCK' и есть то самое неподдерживаемое значение. Но какого рожна в примере пишется `LC_COLLATE' есть `en_US.UTF-8', если мы выше допустили, что `LC_COLLATE' установлена в `C`?

Это как сказать: если у вас переменная `LC_COLLATE' установлена в `C`, то могут быть проблемы, если она установлена в `en_US.UTF-8'.:dash2:
Ужас.
Последний раз редактировалось жучара 05.12.2019 01:52, всего редактировалось 1 раз.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5159
ОС: Gentoo

Re: Как работает команда sort?

Сообщение /dev/random »

жучара писал(а):
05.12.2019 01:45
неподдерживаемое
Несовместимое, а не неподдерживаемое.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 19369
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Как работает команда sort?

Сообщение Bizdelnick »

жучара писал(а):
05.12.2019 01:45
ТОЛЬКО ЛИШЬ (без всяких других опций) означает именно это. И не должно быть, что LC_ALL (ОКАЗЫВАЕТСЯ) тоже может быть установлено.
Переменная окружения LC_ALL может быть установлена давно, а LC_COLLATE Вы устанавливаете прямо сейчас (о чём говорит использование present continuous, если что), тогда будет проблема. Ошибки в оригинале нет, есть только непонимание Вами языка.
жучара писал(а):
05.12.2019 01:45
Но какого рожна в примере пишется `LC_COLLATE' есть `en_US.UTF-8', если мы выше допустили, что `LC_COLLATE' установлена в `C`?
Это всего лишь пример. И никакого допущения относительно значения LC_COLLATE выше не было.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 772
ОС: астралинукс

Re: Как работает команда sort?

Сообщение жучара »

Bizdelnick писал:
05.12.2019 13:25
Это всего лишь пример. И никакого допущения относительно значения LC_COLLATE выше не было.
это ВТОРАЯ проблема. Описано, что в случае установления LC_COLLATE в "C" будут две проблемы. Вторая, к тому же, если LC_COLLATE будет "en_US.UTF-8"
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 19369
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Как работает команда sort?

Сообщение Bizdelnick »

жучара писал(а):
05.12.2019 15:56
Описано, что в случае установления LC_COLLATE в "C" будут две проблемы.
Написано:
жучара писал(а):
05.12.2019 01:09
Note that setting only `LC_COLLATE' has two problems.
Не уточняется, о каком именно значении речь. Из написанного выше, конечно, можно было бы предположить, что подразумевается именно локаль C, но детальное описание опровергает это предположение: речь о любом изменении LC_COLLATE.
В общем, не придирайтесь к мелочам.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали: