Вектор обнуляемых HashMaps в ржавчине
Мне очень сложно иметь дело с векторами HashMaps в ржавчине. Я хочу использовать векторы HashMaps в качестве реализации контейнера разреженных матриц в соответствии с ограничениями, которые я, надеюсь, смогу объяснить ниже.
Самое главное, я хочу свести к минимуму время доступа и модификации, включая амортизированные распределения. Затем я хочу максимально сократить использование памяти без увеличения времени доступа или, по крайней мере, незначительно.
О времени выполнения: я определенно буду много искать, поэтому мне нужно наилучшее возможное время доступа, которое будет дано вектором, а не HashMap<(INDEX, KEY), Value>, как указано в комментариях. Поправьте меня, если я ошибаюсь: хеширование и обработка коллизий определенно повлияют на производительность. Мой ключ представляет собой сложную структуру. Хотя я подумываю упростить его в перечислении для ключа, поэтому, возможно, в этом случае хэширование будет дешевле, но я не уверен, что это будет возможно.
О памяти: мне нужно избежать ненужных накладных расходов на память с пустым HashMap, для которого требуется 48 байтов в памяти. Мой вектор имеет размер порядка 100 миллионов, поэтому он может легко потреблять десятки ГБ. Чтобы выйти из этой расточительной ситуации, я решил использовать Option<Box>. Насколько я понимаю, мне требуется обнуляемость, и я не могу использовать Box напрямую в этом случае, потому что этот тип не допускает обнуляемости, следовательно, это заставит меня использовать пустой HashMap и зарезервировать 48 байтов где-то в памяти плюс дополнительные 8 байтов на элемент из-за сама коробка. С Option<Box> вариант None потребляет всего 8 байтов, что приводит к уменьшению памяти до 6 раз, если все элементы были пустыми хэш-картами.
Я очень открыт для альтернативных подходов к реализации разреженных матриц, которые удовлетворяют мои потребности, но в этом вопросе я хочу сосредоточиться на шаблонах ржавчины для эффективных с памятью представлений вектора хэш-карт, которые также избегают иметь дело с тем, что кажется мне излишне многословными цепочками Типы опций и указателей (Box/Rc и др.). Есть ли лучший подход для обработки векторов обнуляемых HashMaps в ржавчине?
@Stargateur добавил больше деталей
Я прочитал весь ваш вопрос и не понял, в чем проблема. Вам было сложно работать с Vec<Option<Box<HashMap<K, V>>>> или вы где-то застряли? (Если да, укажите где.) Или вы просто находите цепочку дженериков слишком уродливой и задаетесь вопросом, есть ли лучший способ? (Если это так, пожалуйста, не пугайтесь цепочки - просто прочитайте это как «вектор необязательного принадлежащего указателя на хэш-карту».) То, что вы описали, кажется мне совершенно разумным и идиоматичным. Rust предоставляет такие типы, как Option и Box, именно поэтому вы можете оптимизировать, как вы планируете сделать здесь. Действуй.
@user4815162342 user4815162342 да, действительно, я нахожу это многословным и шаблонным, и мне интересно, есть ли лучший способ (то есть вообще избегать цепочки) или мне просто нужно привыкнуть к этому :)
@Redirectk Я, наверное, повторяюсь в этот момент, но чтобы все было ясно на 100%, я думаю, вам следует привыкнуть к этому, и я даже не вижу, где находится шаблон. Альтернативой является переход на подход с одной хэш-картой, который кажется лучшим выбором для разреженного поиска и приведет к меньшему количеству распределений. В любом случае, если у вас есть конкретная проблема с чем-то необоснованно сложным или многословным, задайте более конкретный вопрос. В остальном, я думаю, это отличный способ изучить Rust (я предполагаю, что вы новичок в этом языке) — получайте удовольствие!
Я думаю, что @user4815162342 и @Ahmed Masud правы в том, что использование одного HashMap является правильным подходом, если только у вас нет каких-то действительно загадочных требований. Если вы действительно хотите использовать Vec<Option<Box<HashMap<K, V>>>, вы можете обернуть его в пользовательский тип и реализовать методы для этого типа, которые уменьшают многословность, например. fn insert(&mut self /* CustomType */, usize i, K k, V v) -> Option<V> { /* insert into position i of the Vec, creating a new HashMap if it is None */ }.
Ответы 1
Согласно документации Rust, создание пустого HashMap не приводит к выделению кучи. На самом деле контейнеры Rust в целом имеют такое поведение. Не нужно заворачивать HashMap в Option.
Тот факт, что обнуляемость должна быть явно выражена в Rust, заключается в том, чтобы гарантировать, что контракты API понятны как для автора библиотеки, так и для пользователя. Как и во всем, «бесплатных обедов не бывает», и для того, чтобы сделать это явным, может потребоваться несколько unwraps здесь и там.
Наконец, обратите внимание, что хотя HashMap не является Copy, но является Clone, если его ключи, значения и состояние равны Clone (фактически состояние по умолчанию — клонирование). Как указано в документации Rust, Clone «[d] отличается от Copy тем, что Copy является неявной и недорогой побитовой копией, в то время как Clone всегда является явным и может быть или не быть дорогим».
Для пустой HashMap по-прежнему требуется 48 байтов в соответствии с size_of, а для опции требуется только 8. Наличие миллионов пустых хэш-карт в векторе легко заставляет мою программу потреблять десятки ГБ.
@Redirectk Просто чтобы не запутать других читателей, вы, вероятно, очень свободно используете термин «опция» для обозначения Option<Box<HashMap<K, V>>> или аналогичной косвенности, потому что Option<HashMap<K, V>> требует точно такого же объема памяти. как HashMap<K, V>
@ cafce25 вы правы, но вы забыли опцию в типе XD
@cafce25 совершенно прав. Если бы вы хотели избежать 48 байтов, вы бы использовали Box. Это ортогонально тому, используете ли вы Option. Я понимаю путаницу, потому что большинство языков объединяют обнуляемость со стратегией распределения (например, Java).
@Redirectk, если вам нужны миллионы HashMaps в векторе, возможно, вам нужно переписать собственный контейнер. Например, рассматривали ли вы хэш-карту, имеющую форму HashMap<(INDEX, KEY), Value>, для замены всего вашего вектора хэш-карт, где INDEX — позиция в этом большом векторе, а KEY — локальный ключ хэш-карты? Когда вы начинаете сталкиваться с такими большими структурами, вам приходится создавать собственную структуру данных, чтобы оптимизировать ситуацию, потому что вы знаете о ней больше, чем общие реализации.
@ cafce25 Это справедливое замечание. Я уточню свой вопрос, что я имею в виду Option<Box<T>> или аналогичные цепочки типов/опций указателя.
@willtunnels Мне кажется, что для создания Box<HashMap<...>> по-прежнему требуется пустой HashMap в памяти? Плюс дополнительные 8 байт для самой коробки
@AhmedMasud Это действительная альтернатива. Я отредактировал свой вопрос, чтобы уточнить, что в моем случае время доступа действительно важно, и поиск карты, вероятно, будет слишком медленным. Я не запускал никаких тестов в этом случае, поэтому, пожалуйста, поправьте меня, если я ошибаюсь!
@Redirectk, только эталонный тест может дать вам окончательный ответ, но помните, что поиск HashMap - это O (1), поэтому поиск в одном унифицированном HashMap должен быть быстрее, чем поиск HashMap в Vec с последующим поиском ключа в этом меньшем HashMap. Конечно, это предполагает, что вам не нужно перебирать все элементы HashMap числа n.
@Redirectk Ах да, это очевидно правда.
Я ничего не понимаю в ваших жалобах. Было бы короче объяснить, что вы пытаетесь сделать, вместо того, чтобы говорить о решении, которое, по вашему мнению, вам нужно.