Должен ли я использовать два Hashmap для быстрого поиска на двух объектах вместо линейного поиска одного hashmap?

Question

У меня была проблема с собеседованием, когда меня попросили найти оптимизированное решение для поиска в двух экземплярах: номер студента и класс (только один на каждого учащегося).sn_to_class() должен вернуть класс для номера студента.Кроме того, class_sns() должен возвращать список номеров студентов для данного класса.

Моим первым решением было использование hashmap sn_to_class_map (число в качестве ключа и номер студента в качестве данных) и hashmap class_to_sns_map (класс какключ и номер студента в качестве данных).Таким образом, поиск будет свернут до O(1), но данные будут увеличены.

псевдокод:

sn_map = dict()
cl_map = dict()

fun addStudents(sn, cl):
    sn_map[sn] = cl
    cl_map[cl].add(sn)    # List

fun getStudents(cl)
    return cl_map[cl]

fun getClass(sn)
    return sn_map[sn]

Правильно ли мой подход?

Answer 1

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

В вашем случае вас попросили сделать «оптимизированное» решение, и вы столкнулись с таким компромиссом:

• Если вы сохраняете карту от номеров учеников до классов, то getClass и addStudents бывают быстрыми, и вы используете пространство только для этого одного представления данных, но getStudents медленнее, потому что это нужно прочитайте всю карту.
• Если вы сохраняете карту из классов в списки номеров учеников и не беспокоитесь о порядке номеров учеников в этих списках, тогда getStudents и addStudents быстрые, и вы используете пространство только для это одно представление данных, но getClass медленнее, потому что нужно прочитать всю карту.
• Если вы сохраняете карту от классов до отсортированных списков номеров учеников, то getStudents работает быстрее, getClass немного быстрее, чем с несортированными списками (необходимо проверить каждый класс в карта, но, по крайней мере, он может выполнять бинарный поиск в каждом списке), и вы используете пространство только для этого одного представления данных, но getClass все еще относительно медленный, если классы маленькие, а addStudents значительно медленнее потому что вставка ученика в список может занять много времени.
• Если вы сохраняете две карты, как вы предлагаете, то все операции выполняются довольно быстро, но теперь вам нужно место для обоих представлений данных.

Ваш вопрос: каков правильный компромисс? И мы не можем ответить на это за вас. Возможно, память очень ограничена, и одна операция вызывается очень редко, и только в не зависящих от времени контекстах, так что лучше делать эту операцию медленнее, чем тратить память; но, возможно, память не проблема, а скорость важна. В реальной программе я думаю, что , вероятно, будет гораздо больше, если вы будете заботиться о скорости, а не о разнице коэффициента использования памяти в два раза, поэтому предлагаемое вами решение с двумя картами, скорее всего, будет Лучший; но мы не можем знать.

Таким образом, в ситуации интервью, которую вы описываете, лучший подход - описать несколько вариантов, объяснить компромисс, объяснить, почему вы можете выбрать один или другой, и опционально объяснить, почему решение с двумя картами вероятно, будет лучшим в реальной программе - но эта последняя часть не самая важная часть ИМХО.