Блог пользователя yermak0v

Бор и ассоциативный массив
Автор yermak0v, 12 лет назад, По-русски

Если в боре заменить буловское поле leaf на поле какого-то типа, то его можно вполне использовать как ассоциативный массив. Для этого тип ключа просто переведем в строку, и значение ячейки запишем в leaf соответствующего поля. Может ли из этого выйти ассоциативный массив? Если да, то это может быть вполне себе новая структура данных.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

http://en.wikipedia.org/wiki/Radix_tree

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Разве это то же? И в своем случае — я хочу полностью ассоциировать любой тип, с любим другим. Но все же минус в том что для некоторых типов надо писать самому ф-ю перевода в строку.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Может, вполне. Другое дело, что хэш-таблица будет работать, казалось бы, не медленнее.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Я не хочу выставлять этот алгоритм (хотя вряд ли его уже можно назвать алгоритмом) выше любого другого, я просто предложил то, что пришло мне в голову на днях.

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Я даже верю, что есть задачи, где это будет предпочтительнее чего-либо. Например, когда бор будет нужен еще и для чего-то другого.

      → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Зато такую структуру, в отличие от хеш-таблицы, можно сделать persistent. Подобная структура (radix-hash-tree) используется в стандартной библиотеке Scala для реализации immutable HashSet/HashMap

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Насколько я знаю, такой бор и используется всегда (вне олимпиад по программированию). Для примера: не так давно проходил день открытых дверей ABBYY, и там рассказывал товарищ, что они пользуют бор (точнее боры, 2 или 3) для разбора значения слова. Причем в листьях бора хранился не бул, а вся информация о соответствующем куске слова что мы знаем.

→ Ответить