Может ли эта структура данных с несколькими деревьями обновляться в O (log (n)) вместо O (n)? - PullRequest
Новая
       34

Может ли эта структура данных с несколькими деревьями обновляться в O (log (n)) вместо O (n)?

0 голосов
/ 02 апреля 2020

Рассмотрим двунаправленную структуру данных с несколькими деревьями, которая связывает строки с массивами строк.

Свойство 1 : строка может принадлежать нулю или нескольким коллекциям S строк, т.е. belongsTo: string => Array<S<string>>.

Например, строки 'a', 'b', 'c', 'd' и 'x' могут быть связаны с коллекциями S(), S('a'), S('x'), S('a', 'b') и S('a', 'b', 'c'), так что каждое из следующих выражений возвращает true. 

belongsTo('a') // [S()]
belongsTo('x') // [S()]               both 'a' and 'x' belong to S()
belongsTo('b') // [S('a'), S('x')]    'b' belongs to both S('a') and S('x')
belongsTo('c') // [S('a', 'b')]
belongsTo('d') // [S('a', 'b', 'c')]

Обратите внимание, что строка может принадлежать многим коллекциям S и коллекции S может иметь несколько принадлежащих ему строк.

Свойство 1.1 : belongsTo игнорирует регистр и порядок: 

belongsTo('c') // S('a', 'b')
belongsTo('C') // S('a', 'b')

Свойство 1.2 : belongsTo is O(1)

Свойство 2 : contains возвращает массив строк, принадлежащих данной коллекции S: 

contains(S()) // ['a', 'x']
contains(S('a')) // ['b'])
contains(S('a', 'b')) // ['c'])
contains(S('a', 'b', 'c')) // ['d']
contains(S('x')) // ['b']

Свойство 2.1 : contains игнорирует регистр и порядок 

contains(S('a', 'b')) // ['c']
contains(S('A', 'B')) // ['c']
contains(S('b', 'a')) // ['c']

Свойство 2.2 : contains равно O(1)

Выше можно сделать просто с чем-то вроде следующего: 

const hashString = s => s.toLowerCase()
const hashArray = arr => sort(arr.map(hashString).concat()).join('_')

const stringIndex = {
  [hashString('a')]: [[]],
  [hashString('b')]: [['a'], ['x']],
  [hashString('c')]: [['a', 'b']],
  [hashString('d')]: [['a', 'b', 'c']],
  [hashString('x')]: [[]]
}

const sIndex = {
  [hashArray([])]: ['a', 'x'],
  [hashArray(['a'])]: ['b'],
  [hashArray(['a', 'b'])]: ['c'],
  [hashArray(['a', 'b', 'c'])]: ['d'],
  [hashArray(['x'])]: ['b']
}

// getters
const belongsTo = s => stringIndex[hashString(s)]
const contains = arr => sIndex[hashArray(arr)]

// others
const adjacent = (arr, s) => arr.concat(s)
const addTo = (arr, s) => { /* adds a string to a collection */ }
const update = (arr, old, new) { /* replace a string in a collection */ }

Вот обратная сторона. update(arr) (определено выше) занимает O(descendants(arr).length), где потомками являются все строки данной коллекции contains, а также все строки соседних коллекций contain и все строки соседних коллекций. смежные коллекции contain, эт c. (Смежность здесь похожа на концепцию детей, но это не дерево.)

Как только я пытаюсь абстрагировать строки в идентификаторы, я теряю функциональность хеширования, которая сохраняет свойства 1.1 и 1.2 (неупорядоченные и без учета регистра).

Есть ли способ сделать update в O(1) или O(log(n)) вместо O(descendants)?

...