наука и жизнь

[juan_gandhi]

Scala:

  scala> List(Set(1,2)).flatten == List(Set(2,1)).flatten
res3: Boolean = false

Бля.

Comments

[nponeccop.livejournal.com]

> ne, zachem ispol'zujut Data.HashSet ?

Я не знаю, я не использую.

Реализации и интерфейсы существенно различные.

HashSet требует от элементов реализации Hashable.

Set требует реализации Ord.

Думаю, что проще в реализации и быстрее исполняется в конкретном случае - то и надо использовать.

[eacher.livejournal.com]

>> Я не знаю, я не использую.

hurraaa!!! a to ja dumal, chto ja odin takoj :)

spasibo za raz'jasnenija

[sassa-nf.livejournal.com]

дык, вроде ясно зачем.

Set имеет логарифмическую (от размера сета) стоимость для insert / delete / lookup. HashSet амортизирует эту стоимость за счёт O(1) операции хеширования (дальше логарифмическая стоимость поиска по меньшему субсету).

[nponeccop.livejournal.com]

Непонятно, насколько он амортизирует и амортизирует ли, т.к. IntMap - это не хеш-таблица, а bit trie, как я понял.

[sassa-nf.livejournal.com]

ха, я не посмотрел.

ну, тогда вычислить хеш один раз и сравнивать хеши просто, а сравнивать сложный объект каждый раз - не просто.

[sassa-nf.livejournal.com]

мммм... дык, HashSet тоже требует Ord.

А можно разложить по полочкам, почему пример с HashSet выдал False? Я сегодня с утра когда глядел, мне показалось, что весь сет бьётся на субсеты с помощью хеша, а субсет-то всё равно Set. Т.е. значения с одинаковым хешем всё равно должны оказаться упорядоченными в каждом субсете. Вот и не понятно, в чём прикол тогда.

[nponeccop.livejournal.com]

Это не ко мне. Меня всего лишь попросили найти коллизию и проверить с ней.

[sassa-nf.livejournal.com]

ну да, но теперь же это самое интересное :)

import qualified Data.IntMap as I
import qualified Data.Set as S
...
insert :: (Hashable a, Ord a) => a -> HashSet a -> HashSet a
insert a (HashSet s) = HashSet $
  I.insertWith (\_ -> S.insert a) (hash a) (S.singleton a) s

по ключу (hash a) нашли существующее значение и скомбинировали его с новым: (S.insert a). Поскольку S.insert==Set.insert, то должно быть отсортировано. quickcheck что, к разным типам привёл два списка?

[nponeccop.livejournal.com]

> quickcheck что, к разным типам привёл два списка?

Это исключено, т.к. (==) :: Eq a => a -> a -> Bool, а не (Eq a, Eq b) => a -> b -> Bool, т.е. сравнению требуется 2 одинаковых типа.

Вы на toList и fromList посмотрите. Как происходит вставка одного элемента - иррелевантно, т.к. пример её не использует.

[sassa-nf.livejournal.com]

ну, посмотрю. я думал, дложно было быть consistent с поэлементной вставкой.

[nponeccop.livejournal.com]

в документации порядок не гарантируется. Соответственно, и консистентность.

[sassa-nf.livejournal.com]

говорят, используется:

fromList :: (Hashable a, Ord a) => [a] -> HashSet a
fromList xs = foldl' (flip insert) empty xs


да, я понимаю насчёт Eq, но как ещё объяснить разницу. Если бы объекты были одинаковы, то insert выполнился бы одинаково.

Мне доустановить ещё чё-то там надо. А то бы просто глянуть на fromList одного и другого.