Как list.sort (key = list.count) работает в Python 3.x?

Question

Я хотел бы отсортировать числовой список по частотам элементов. (Я нашел несколько способов сделать это.)

В ходе исследования я попробовал следующий пример.

Вопрос: Как работает list.sort (key = list.count)? Можно ли использовать list.count () во время list.sort ()?

Я читал, что ключевая функция оценивается для каждого элемента списка перед сортировкой, и эти значения используются для сравнений во время sort.

Кроме того, я где-то читал, что во время sort () список как бы заблокирован. (извините, я не могу найти ссылку сейчас - я прочитал довольно много блогов и руководств по этому топу c за последние несколько часов, включая Python документацию и инструкции по сортировке)

Это пример

### Python 3.7 ###

data = [22, 11, 33, 99, 88, 77, 22, 44, 55, 44, 66, 22]

# sort by value
data.sort()
print(data)
>>> [11, 22, 22, 22, 33, 44, 44, 55, 66, 77, 88, 99]

# sort by frequency, i.e. list.count()
data.sort(key=data.count)
print(data)
>>> [11, 22, 22, 22, 33, 44, 44, 55, 66, 77, 88, 99]
# expected >>> [11, 33, 55, 66, 77, 88, 99, 44, 44, 22, 22, 22]
# but no change, the value-sorted list is printed

# or
data.sort(key=lambda e: data.count(e))
print(data)
>>> [11, 22, 22, 22, 33, 44, 44, 55, 66, 77, 88, 99]
# expected >>> [11, 33, 55, 66, 77, 88, 99, 44, 44, 22, 22, 22]
# but no change, the value-sorted list is printed

примечание: сообщение об ошибке отсутствует.

В качестве дополнения я хотел бы отметить, что следующее работает должным образом:

max(data, key=data.count)

И, конечно же, это также дает ожидаемый результат

print(sorted(data, key=data.count))
>>> [11, 33, 55, 66, 77, 88, 99, 44, 44, 22, 22, 22]

По документации sorted () и sort () должны возвращать тот же результат, не так ли?

Спасибо за ваше понимание!

РЕДАКТИРОВАТЬ:

По документации - как я понял:

1. sort () принимает ключевую функцию и подает ключевую - функция с отдельными элементами списка

   -> вычисленные результаты - это количество вхождений каждого элемента (результаты эквивалентных элементов с одинаковым вычисленным результатом, поскольку их частота в списке одинакова)

   : У меня нет опыта для такой глубокой отладки в Python

   : сам data.count () возвращает соответствующий список проверенных мной частот

2. сохраняет / кэширует вычисленные результаты

   : это основа его эффективности

3. использует кешированные результаты вычислений (!) Для определения порядка исходного списка

   -> наименее частые элементы находятся в начале списка, а чаще всего у него обратно

   !!! этого не происходит ...

4. сохраняет список в новом порядке на месте

   !!! ... ИЛИ этого не происходит.

Кроме того, насколько я понял (хотя и не уверен), где-то во время этого процесса sort () 'блокирует' исходный список от других использование / доступ (и где-то снимает блокировку - в объяснении было что-то о многопоточных приложениях, насколько я помню).

ВАЖНО:

Я не ищу решения или кода чтобы отсортировать список - я был бы признателен за объяснение того, что происходит:

• Почему результатом является фактический возвращенный список, а не мои ожидания?

• Для сравнения, почему sorted () работает должным образом?

Answer 1

Это интересный вопрос, у меня нет полного ответа, так как он находится где-то здесь в исходном коде: https://github.com/python/cpython/blob/master/Objects/listobject.c

Однако вы можете иметь часть ответ, используя следующую функцию в качестве ключа:

def count(e):
   print(data)
   return data.count(e)

Если вы сделаете это, вы увидите, что он печатает только «[]». Это означает, что каким-то образом во время процесса сортировки на месте, вероятно, во избежание путаницы со списком, ваш список теперь указывает на пустой список (даже если сама ссылка, данные, не изменилась). Таким образом, data.count (e) всегда равен 0, и ваш список остается неизменным.

Таким образом, единственный способ использовать ваш список во время процесса сортировки на месте - это скопировать список, вы можете сделать, например, :

data.sort(key=data.copy().count)

Я добавлю, что это не сильно увеличивает стоимость всего процесса копирования списка, поскольку строка выше уже O (n² log (n)). В самом деле, это очень плохая идея - вызывать счетчик для каждого элемента списка. Эффективный способ O (n log (n)) сделать это:

nb_occ={}
for x in data:
    nb_occ[x]=nb_occ.get(x,0)+1
data.sort(key=nb_occ.__getitem__)

EDIT: см. Ответ juanpa.arrivillaga, это поведение фактически задокументировано в документации метода сортировки.

Answer 2

Хорошо, согласно документации :

CPython детали реализации: Пока список сортируется, эффект попытки изменения или даже осмотреть, список не определен. Реализация C Python делает список пустым на время и вызывает ValueError, если обнаруживает, что список был изменен во время сортировки.

Если выделена жирным шрифтом часть, то data.count вернет 0 для любого элемента, и сортировка не изменит порядок списка.

Answer 3

data = [22, 11, 33, 99, 88, 77, 22, 44, 55, 44, 66, 22]
data.sort()
a,s,z,p=[],[],[],{}
for i in data:
    if i not in s:
        s.append(i)
        t=data.count(i)
        a.append(t)
for i in range(len(a)):
    p[s[i]]=a[i]
for u,m in sorted(p.items(),key=lambda x: x[1]):
    z.append(u)
print(z)