Продолжая тему Python in Golang, следующая интересная структура данных, в которую стоит погрузиться, - это Counter. В Python этот класс также входит в пакет collections и не требует пояснений. Учитывая итеративный ввод, он даст вам количество каждого элемента. Вы также можете получить N самых распространенных предметов. Я думал, что это будет довольно просто, и первая часть такова, однако получить первые N элементов немного сложнее. В Python класс Counter фактически наследуется от dict и предоставляет дополнительные функции.
Можно сказать в псевдокоде. При добавлении элемента в счетчик, если элемент находится в хэш-карте, увеличьте его счетчик, в противном случае установите его на 1. На самом деле это похоже на поведение defaultdict в Python, но это тема для другого дня. Теперь, когда мы хотим получить верхние N элементов, мы могли бы перебирать каждый элемент на нашей карте и проверять, есть ли верхние N элементов, но с учетом k в качестве длины нашей хэш-карты у нас будет O (k) временная сложность. Я думаю, мы можем добиться большего.
Есть действительно изящная структура данных, называемая куча, которая может помочь нам в решении этой проблемы. Подобно тому, как мы используем две разные структуры данных в примере OrderedDict, мы можем использовать здесь две структуры данных, чтобы уменьшить временную сложность.
У Golang есть куча пакетов, которые мы можем использовать для построения нашей собственной структуры данных. В нашем случае мы действительно можем следовать примеру очереди приоритетов в документации, однако наш приоритет - это количество раз, когда элемент появлялся в нашем счетчике. Конкретная куча Golang имеет сложность O (log (n)) как для Push, так и для Popping. (обратите внимание: в нашем примере выше, имея k в качестве длины нашей хэш-карты, O (log (k)) будет временной сложностью)
Теперь, когда мы используем кучу, мы можем получить лучшую временную сложность, и наш счетчик готов. В отличие от Python, мы не можем переопределить методы получения или установки карты для доступа к значениям. Вместо этого нам нужно создать наши собственные методы, которые обращаются к внутренней карте.
Довольно серьезная оговорка, которую я до сих пор не понял, - это как получить доступ к верхним N элементам в куче, не выскакивая, а затем повторно нажимая их. Благодаря этому наш метод MostCommon имеет временную сложность O (n log k), где n - количество элементов, которые мы извлекаем, а k - длина нашей кучи. Если бы мы могли снова отказаться от использования выталкивания и нажатия, этот метод был бы просто O (n). Поскольку мы сначала нажимаем, а потом снова нажимаем, я добавил мьютекс, чтобы сделать наш Counter потокобезопасным; без этого, если другой поток вызовет MostCommon в середине первого потока, он может вернуть неверные данные.
При работе с картами в нескольких потоках с несколькими авторами вам следует изучить структуру sync.Map, если вы не хотите управлять синхронизацией самостоятельно.
