Хранить динамические массивы в хеш-таблице в Golang?
В Go люди используют «срезы» в качестве динамических массивов, поскольку размеры простых массивов должны быть известны во время компиляции.
Но хотя равенство концептуально просто для динамических массивов, Go не определяет его для срезов (поскольку срезы ведут себя по-разному в зависимости от других элементов базового массива). В результате фрагменты нельзя использовать в качестве ключей в map.
Поэтому в Go не существует простого способа хранения динамических массивов в хеш-таблице.
Как программисты Go обходят это ограничение? Пишут ли для этого люди свои собственные реализации хэш-таблиц?
@JimB Два динамических массива равны, если они имеют одинаковую длину и их элементы равны. Два среза равны, если они имеют одинаковую длину и емкость и их элементы равны. Если бы Go сделал любой выбор, это сработало бы для меня, но он решил не делать ни того, ни другого, и это утомительно обходить.
Почему бы не быть равными, если равны только длина и элементы, поскольку шаблоны распределения могут быть разными, но в результате получать одни и те же данные (именно так работает срезы.Равно)? Почему бы не быть равными, только если резервные массивы имеют один и тот же адрес? Равны ли указатели или на что они указывают? А как насчет кусочков кусочков? Независимо от того, как вы хотите его определить, это не особенность языка, и в тех редких случаях, когда вам нужен ключ карты, основанный на срезе, его нетрудно обойти.
Другая проблема с использованием среза в качестве ключа заключается в том, что срезы изменяемы.
@JimB Для динамических массивов легко определить равенство. Срезы пытаются быть одновременно двумя вещами: динамическими массивами и представлениями. Вот почему есть «выбор». Моя проблема в том, что они вообще не сделали никакого выбора. Re: указатели — это структурное и ссылочное равенство, и в некоторых языках они обрабатываются по-разному, например в семействе ML.
Массивы @MWB не являются изменяемыми как ключи, поскольку присвоение массива всегда является копией всего значения.
Технически срезы не являются динамическими массивами. Это представления массивов.
Вот не очень эффективный хак, который я написал, когда мне нужно было что-то вроде этого: github.com/bserdar/slicemap
Мой первый комментарий был неточным. Позвольте мне попробовать еще раз: другая проблема заключается в том, что резервный массив скопированного значения среза может быть изменен через исходное значение среза.
@BurakSerdar Интересный подход. Я думаю, он должен иметь достойную производительность для очень коротких клавиш.
Да, по сути, поиск по карте len(x) для каждого фрагмента ключа карты x, но при больших данных карты становятся маленькими, потому что пространство ключей сегментировано.
@BurakSerdar Интересно, можно ли добиться большего (работая с длинными клавишами) с помощью unsafe и reflect.
Интересно, является ли O(len(x)) естественным нижним пределом для этого подхода, независимо от используемого метода.
@BurakSerdar Хеш-таблица нужна O(len(key)) только для вычисления хеша или сравнения ключей во время поиска. Возможно, вы захотите описать свой подход в качестве ответа — его увидят больше людей.
Ответы 1
Фрагменты не разрешены в качестве ключей карты, чтобы предотвратить незначительные ошибки из-за изменения ключей после их размещения на карте. Срез — это представление массива, поэтому, если вы используете ключ среза для вставки значения на карту, а затем кто-то изменяет базовый массив, вставленное значение становится недоступным с использованием старого ключа. Массивы можно использовать в качестве ключей карты, поскольку при назначении массива его содержимое будет скопировано, и изменить существующий ключ карты невозможно.
Тем не менее, иногда необходимо использовать срезы в качестве ключей карты (т. е. писать кеш на основе среза значений), и вы можете взломать это, создав карту карт для каждого элемента в срезе. Это не работает со срезами более высокого порядка, но работает достаточно хорошо для срезов сопоставимых элементов (например, []string), содержащих относительно мало элементов. Реализация этой идеи здесь: https://github.com/bserdar/slicemap
Принимаю это на данный момент, поскольку это кажется лучшим предложением на данный момент. Мне любопытно, можно ли добиться большего с точки зрения производительности, используя unsafe и reflect.
Вам не нужно писать всю реализацию хеш-таблицы, вы просто определяете прокси-ключ для своего среза в зависимости от того, как вы хотите определить равенство. например для фрагмента байтов вы можете хешировать эти байты. Вы всегда можете сохранить фрагмент на карте. (если бы равенство было простым, оно было бы определено, но это не так — см. также FAQ: go.dev/doc/faq#map_keys)