Каковы преимущества использования сортировки count в этом алгоритме?

segue_segway спросил: 13 июня 2018 в 05:26 в: python

Работа над следующим алгоритмом:

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

Авторитарное решение книги, из которой исходит проблема, говорит о создании двух хэшей - та, которая сопоставляет age = > количество вхождений этого возраста и другое, которое сопоставляет возраст со смещением в конечном массиве. Затем повторите эти два хэша и напишите значения с соответствующими смещениями в конечном массиве.

Код автора:

import collections 
Person = collections.namedtuple('Person', ('age', 'name'))def group_by_age(people):
  age_to_count = collections.counter([person.age for person in people])
  age_to_offset, offset = {}, 0   for age, count in age_to_count.items():
    age_to_offset[age] = offset 
    offset += count    while age_to_offset: 
    from_age = next(iter(age_to_offset))
    from_idx = age_to_offset[from_age]
    to_age = people[from_idx].age
    to_idx = age_to_offset[people[from_idx].age]
    people[from_idx], people[to_idx] = people[to_idx], people[from_idx]    age_to_count[to_age] -= 1    if age_to_count[to_age]:
      age_to_offset[to_age] = to_idx + 1 
    else:
      del age_to_offset[to_age]

Мне интересно, почему мы можем упростите вещи и просто создайте хэш с ключом = age и value = object. Затем просто перебирайте хеш-ключи и записывайте значения в массив. Если нужно сортировать выходные данные, можете сортировать хеш-ключи и вводить в хэш для ввода значений для ввода массива.

Вопрос 1: Почему автор пошел с менее интуитивным маршрутом?

Вопрос 2: Является ли мой код ниже (на основе авторского решения) хорошим? Этот код намного чище, поэтому возникает вопрос, почему автор не пошел с этим путем.

import collections 
Person = collections.namedtuple('Person', ('age', 'tuple'))def group_ages(people):
  age_to_count = collections.Counter([person.age for person in people])  age_to_offset, offset = {}, 0   for age, count in age_to_count.items():
    age_to_offset[age] = offset 
    offset += count    for old_index, person in enumerate(people):
    new_index = age_to_offset[person.age]
    people[old_index], people[new_index] = people[new_index], people[old_index]    age_to_count[person.age] -= 1    if age_to_count[person.age]:
      age_to_offset[person.age] += 1

1 ответ

data_garden Shantanu Agarwal ответил: 13 июня 2018 в 11:42

Правильно, что вы можете сортировать хеш keys и печатать их по порядку, но тогда как вы будете помнить keys.

Например, скажем, у вас есть 3 студента с возрастом 20,40 и 15. Теперь в hashmap, они будут похожи на h[20]="",h[40]="",h[15]="".

Но после их сортировки, как вы будете печатать значения из h. У вас не будет индексов сейчас. И если вы попытаетесь получить ключи от основного array, вы снова будете использовать для этого другой тип.

Дополнительное видео по вопросу: Каковы преимущества использования сортировки count в этом алгоритме?

Python - Работаем со списками ( Сортировка пузырьком)

3.Python для НЕ Начинающих - Сортировка Пузырьком / Bubble Sort

Как делать пирамидальную сортировку массива? - алгоритм "кучи" (heap sort algorithm)