Почему вы не можете использовать хеш-таблицы / словари в алгоритме сортировки?

Question

Когда вы используете алгоритм сортировки подсчета, вы создаете список и используете его индексы в качестве ключей при добавлении числа целочисленных вхождений в качестве значений в списке.Почему это не то же самое, что просто создать словарь с keys в качестве индекса и counts в качестве значений?Например:

hash_table = collections.Counter(numList) 

или

hash_table = {x:numList.count(x) for x in numList} 

Создав хеш-таблицу, вы просто скопируете число вхождений целых чисел в другой список.Хэш-таблицы / словари имеют O (1) раз поиска, так почему бы это не было предпочтительным, если вы просто ссылаетесь на пары ключ / значение?

Я включил алгоритм подсчета сортировки ниже для справки:

def counting_sort(the_list, max_value):
    # List of 0's at indices 0...max_value
    num_counts = [0] * (max_value + 1)

    # Populate num_counts
    for item in the_list:
        num_counts[item] += 1

    # Populate the final sorted list
    sorted_list = []

    # For each item in num_counts
    for item, count in enumerate(num_counts):

        # For the number of times the item occurs
        for _ in xrange(count):

            # Add it to the sorted list
            sorted_list.append(item)

    return sorted_list

Answer 1

Вы, конечно, можете сделать что-то подобное.Вопрос в том, стоит ли это делать.

Подсчет сортировки имеет время выполнения O (n + U), где n - количество элементов в массиве, а U - максимальное значение.Обратите внимание, что по мере того, как U становится все больше и больше, время выполнения этого алгоритма начинает заметно ухудшаться.Например, если U> n и я добавлю еще одну цифру к U (например, изменив ее с 1 000 000 до 10 000 000), время выполнения может увеличиться в десять раз.Это означает, что сортировка по счету начинает становиться непрактичной, когда U становится все больше и больше, и поэтому вы обычно запускаете сортировку по счету, когда U довольно мала.Если вы собираетесь запустить сортировку с небольшим значением U, то использование хеш-таблицы не обязательно стоит затрат.Хэширование элементов стоит больше циклов ЦП, чем просто поиск в стандартных массивах, а для небольших массивов потенциальная экономия памяти может не стоить дополнительного времени.И если вы используете очень большое значение U, вам лучше переключиться на сортировку по основанию, которая, по сути, представляет собой множество меньших проходов сортировки с очень маленьким значением U.

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

Но это больше аргументы реализации, чем что-либо еще.По сути, сортировка при подсчете сводится не столько к «использованию массива», сколько к «построению частотной гистограммы». Это просто тот случай, когда обычный старый массив обычно предпочтительнее хеш-таблицы при построении этой гистограммы.