Пушыстый (_winnie) wrote,
Пушыстый
_winnie

Category:

HashSet , детерминированный обход.

Я предпочел бы что бы HashSet и LinkedHashSet в Java назывались бы UnorderedHashSet и HashSet

HashSet -> UnorderedHashSet
LinkedHashSet -> HashSet

У первого при итерации обход элементов не определён, иногда рандомен от запуска к запуску программы, при добавлении элемента его переколбашивает. У второго порядок обхода такой же, в котором в него клали элементы.

На двух проектах где я был, это дефолтное именование таблиц приводило к потере времени из-за недетерминированного порядка обхода Set. ИМХО, человеческого времени из-за ребилдов и кофликтов в svn было потеряно больше, чем выигрыш от сэкономленных килобайтов. А пользователи потратили больше времени на скачку патчей для для игры из-за диффов или из-за багов на сервере. А чуваки которые оптимизируют память - они вообще с каждым битом бегают, думая как покруче упаковать в byte[], а не только выбирают правильные контейнеры. А тем кто не думает о выборе контейнера - лучше давать более безопасную реализацию с детерминированным обходом.

На всякий случай об этом трюке, который делает обход хеш-таблицах детерминированным (и проще в реализации): Пусть хеш-таблица реализована как массив, элементы которого - связные указателями списки элементов ("корзины"). Можно дополнительно "перевязать" указателями эти элементы корзин во второй связный список, общий на всю хеш-таблицу. И для итерации использовать именно этот список.

В питоне до Python 2.7 были только словари и множества с недетерминированным порядка обхода. В python 2.7 появился collections.OrderedDict. Имхо, лучше бы сделали что бы в хеш-таблицах всегда был определенный порядок обхода, что бы не было как здесь - http://avva.livejournal.com/2323823.html

PS. Есть ещё TreeSet (TreeMap), априори нельзя сказать какой лучше в смысле стабильности по сравнению с LinkedHashSet (LinkedHashMap). Сортированный TreeSet может "абсорбировать" дамаг от того, что откуда-то вывод уже пришёл в недетерминированном порядке ( напр. ответ от компьютеров кластера ). Но зато при кодогенрации расставляет поля в алфавитном порядке, который иногда противоестествен (типа (old_value, new_value) превращается в (new_value, old_value)).
Tags: java, soft-dev
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 31 comments