Сортировка слов на месте

Question

Как вы сортируете диктовку на месте? У него нет такого метода сортировки, как list.sort?

d = {3: 'three', 1: 'one', 2: 'two'}
tmp = dict(sorted(d.items()))
d.clear()
d.update(tmp)

Хотите такой результат ^, но он должен быть правильным на месте, то есть без использования двойной памяти. И другие ссылки на тот же объект должны увидеть переупорядочение!

Answer 1

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

Изменение реализации диктов, которое приводит к диктовкам, сохраняющим порядок, в основном очень ограничено в способах манипулирования порядком он может поддерживать. Таблица dict ha sh хранит индексы в плотном массиве записей, и именно этот массив поддерживает порядок элементов dict.

Плотный массив не может быть произвольно переупорядочен без аннулирования таблицы ha sh. Даже удаление записи должно быть реализовано как оставление фиктивного маркера на его месте для целей разрешения коллизий, и это место записи не может быть повторно использовано без полной перестройки таблицы ha sh.

Даже если бы вам пришлось попробуйте выполнить какую-то неэффективную ручную сортировку, удаляя и заменяя записи, вы накапливаете фиктивные данные и запускаете перестроение таблицы ha sh, потребляя дополнительную память, которую вы не хотели использовать. Вот простая демонстрация:

import os

os.system(f'grep VmPeak /proc/{os.getpid()}/status')

x = dict.fromkeys(range(2**16))

os.system(f'grep VmPeak /proc/{os.getpid()}/status')

for i in range(2**16):
    if i == 21845:
        os.system(f'grep VmPeak /proc/{os.getpid()}/status')
    k = next(iter(x))
    x[k] = x.pop(k)
    if i == 21845:
        os.system(f'grep VmPeak /proc/{os.getpid()}/status')

os.system(f'grep VmPeak /proc/{os.getpid()}/status')

Вывод:

VmPeak:    15092 kB
VmPeak:    20224 kB
VmPeak:    20224 kB
VmPeak:    24832 kB
VmPeak:    24832 kB

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

Answer 2

Технически вы можете отсортировать ключи, а затем pop повторно вставить значения. Таким образом, другие ссылки на тот же объект также увидят изменение. Однако это не спасет вас от использования дополнительной памяти. видно из следующего примера:

In [1]: def inplace(d): 
   ...:     for key in sorted(d): 
   ...:         d[key] = d.pop(key) 
   ...:                                                                                       

In [2]: def create_new(d): 
   ...:     return dict(sorted(d.items())) 
   ...:                                                                                       

In [3]: import math                                                                           

In [4]: limit = (2/3) * 2**20                                                                

In [5]: load_factor_low = {i: i for i in range(math.ceil(limit) + 1)}                        

In [6]: load_factor_high = {i: i for i in range(math.floor(limit) - 1)}                      

In [7]: %timeit create_new(load_factor_low)                                                         
116 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [8]: %timeit inplace(load_factor_low)                                                     
104 ms ± 2.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [9]: %timeit create_new(load_factor_high)                                                        
89.8 ms ± 1.45 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [10]: %timeit inplace(load_factor_high)                                                    
128 ms ± 1.52 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)