Неизменяемые структуры данных являются горячей темой в наши дни. Действительно, кажется, что они решают фундаментальную проблему, присутствующую во всех деструктивно обновленных структурах данных: либо вы должны синхронизировать все обращения к состоянию структуры данных, либо вы рискуете, что один поток увидит какое-то несовместимое состояние, в то время как другой выполняет некоторое обновление , Таким образом, нет общего состояния — нет проблем: просто сгенерируйте новую коллекцию и атомарно установите для нее общую переменную, используя некоторую инструкцию CAS (сравнение и замена), присутствующую почти во всех современных процессорах. Но подождите, мне нужно скопировать всю коллекцию при добавлении одного элемента? Нет, спасибо:)
К счастью, эта проблема уже давно решена. Решение приходит в форме совместного использования данных: вам не нужно копировать все для создания новой коллекции, большая часть данных будет передана старой. Звучит загадочно? Продолжайте читать, и я покажу вам, как это можно кодировать в статическом Groovy.
Коллекция, которую я выбрал, — это знакомая хэш-карта, которую, вероятно, знает каждый, кто кодирует Java. Реализация также не является чем-то новым, на самом деле это происходит из Clojure, где неизменяемые структуры данных называются постоянными и используются довольно интенсивно. Но вам не нужно изучать Clojure, чтобы пользоваться эффективными неизменяемыми структурами данных, статичными Groovy на помощь.
Итак, для начала, основная идея совместного использования состоит в представлении всего в виде дерева (точнее, Три, но мы не специалисты по компьютерам, верно? ? Это позволяет выполнять добавления и удаления, используя только логарифм размера структуры данных. генерировать новый. Как хэш-карту можно рассматривать как дерево? Просто разделив 32-битный хэш на группы по 5 бит, которые соответствуют уровням дерева. Это дает нам 6 уровней, поэтому высота дерева составляет не более 6, в то время как мы можем сохранять до 2 30 объектов на карте, если мы храним реальные объекты только на листьях, которых должно быть более чем достаточно.
Так что теперь к коду.
@Typed
abstract class FHashMap<K, V> implements Iterable<Map.Entry<K,V>> {
final V getAt(K key) { getAt(key, key.hashCode()) }
final FHashMap<K, V> put(K key, V value) {
update(0, key, key.hashCode(), value)
}
final FHashMap<K, V> remove(K key) {
remove(key, key.hashCode())
}
protected abstract V getAt(K key, int hash)
protected abstract FHashMap<K,V> update(int shift, K key, int hash, V value)
protected abstract FHashMap<K,V> remove(K key, int hash)
}
Довольно просто, не правда ли? Мы предоставляем операции получения, добавления и удаления карт. Я покажу просто добавить операцию, другие придерживаются аналогичных идей.
Начнем с пустого дерева:
class EmptyNode extends FHashMap<K,V> {
FHashMap<K,V> update(int shift, K key, int hash, V value) { new LeafNode(hash, key, value) }
}
Опять же, ничего особенного: при добавлении в пустое дерево мы создаем дерево, состоящее только из одного листового узла. Далее давайте представим базовый класс для всех листьев в дереве, где мы будем хранить привязки ключ / значение:
abstract class SingleNode extends FHashMap<K,V> {
final int hash
BitmappedNode bitmap(int shift, int hash, K key, V value) {
def shift1 = (getHash() >>> shift) & 0x1f
def shift2 = (hash >>> shift) & 0x1f
def table = new FHashMap<K,V>[Math.max(shift1, shift2) + 1]
table[shift1] = this
def bits1 = 1 << shift1
def bits2 = 1 << shift2
if (shift1 == shift2) {
table[shift2] = table[shift2].update(shift + 5, key, hash, value)
} else {
table[shift2] = new LeafNode(hash, key, value)
}
return new BitmappedNode(shift, bits1 | bits2, table)
}
}
Таким образом, в SingleNode хранится хеш и метод для создания BitmappedNode, который представляет узел с более чем 1 (но менее чем 32) дочерними элементами. Указанные параметры — это уровень, который мы вставляем, и хэш, ключ и значение, вставленные соответственно. Метод начинается с вычисления группы из 5 битов как из хэша, сохраненного в текущем ключе, так и из того, который будет добавлен. Затем он создает фактическое растровое изображение, то есть массив максимум из 32 элементов, и устанавливает соответствующий элемент себе. Затем интересная часть: если добавленный элемент имеет те же 5 битов, то мы рекурсивно разделяем узел, вызывающий update, на следующий уровень, в противном случае мы просто создаем новый лист. Наконец, возвращается новый BitmappedNode с созданной таблицей и установленными битами. Не очень простой код, но определенно весело писать и читать ?
Теперь есть 2 реализации SingleNode, LeafNode и CollisionNode, которые представляют узел, хранящий несколько привязок в случае коллизии хеша.
class LeafNode extends SingleNode {
final K key
final V value
FHashMap<K,V> update(int shift, K key, int hash, V value) {
if (this.key == key) {
if (this.value == value) return this else return new LeafNode(hash, key, value)
} else if (this.hash == hash) {
return new CollisionNode(hash, FList.emptyList + new BucketElement(this.key, this.value) + new BucketElement(key, value))
} else {
return bitmap(shift, hash, key, value)
}
}
}
class CollisionNode extends SingleNode {
final FList<BucketElement<K, V>> bucket
FHashMap<K,V> update(int shift, K key, int hash, V value) {
if (this.hash == hash) {
return new CollisionNode(hash, removeBinding(key, bucket) + [key, value])
} else {
return bitmap(shift, hash, key, value)
}
}
}
Now, you might wonder what is BucketElement and removeBinding? I’ve left the definitions out, but I hope the names speak for themselves. What I would like to mention though is FList which is functional list, available in static groovy standard library. Unlike java.util.List it only supports appending a new element to the list and getting the head and tail of the list (those familiar with scala or some other functional language should feel at home). Also notice how groovy, while still having a Java-like syntax, allows for a much cleaner definitions than Java. And since the binding is static, the performance does not suffer, so no price to pay:)
Finally here are the definitions of the last nodes that make up immutable hash map implementation:
class BitmappedNode<K,V> extends FHashMap<K,V> {
int shift
int bits
FHashMap<K,V> [] table
FHashMap<K,V> update(int shift, K key, int hash, V value) {
def i = (hash >>> shift) & 0x1f
def mask = 1 << i
if (bits & mask) {
def node = table[i].update(shift + 5, key, hash, value)
if (node === table[i]) return this else {
def newTable = new FHashMap<K,V>[table.length]
System.arraycopy table, 0, newTable, 0, table.length
newTable[i] = node
return new BitmappedNode(shift, bits, newTable)
}
} else {
def newTable = new FHashMap<K,V>[Math.max(table.length, i + 1)]
System.arraycopy table, 0, newTable, 0, table.length
newTable[i] = new LeafNode(hash, key, value)
def newBits = bits | mask
if (newBits == ~0) {
return new FullNode(shift, newTable)
} else {
return new BitmappedNode(shift, newBits, newTable)
}
}
}
}
// Just a specialization of BitmappedNode for the case when all bits are set.
class FullNode extends FHashMap<K,V> {
int shift
FHashMap<K,V>[] table
FHashMap<K,V> update(int shift, K key, int hash, V value) {
def i = (hash >>> shift) & 0x1f
def node = table[i].update(shift + 5, key, hash, value)
if (node === table[i]) return this else {
def newTable = new FHashMap<K,V>[32]
System.arraycopy table, 0, newTable, 0, 32
newTable[i] = node
return new FullNode(shift, newTable)
}
}
}
Again I won’t go into much detail here, the curious reader can easily follow what’s going on. One thing worth mentioing still is that update is naturally recursive: in order to insert an element at some level we first insert it on the next and analyze the result. Also note that ‘===‘ means reference equality in static groovy, which makes the recursiive result analysis much cheaper.
One final remark after we are done with the code. As you might see we allocate a new BitmappedNode when it has at least 2 children. If these children are far from each other, we can potentially lose 30 out of 32 slots in the table, which might be seen as a memory leak. The good news is however that you are likely to put objects with ‘near’ hash codes into the map, and for this situation the waste would be minimal. Still you should remember that this collection is tailored towards locality sensitive hashing http://en.wikipedia.org/wiki/Locality_sensitive_hashing and the usual trick to shuffle the bits got from identity hash code calculation makes things just worse.
So as you might see, implementing efficient immutable data structures is not rocket science, especially when you have an expressive language at hand. If you want a full version of the described class, please download static groovy distribution available at http://code.google.com/p/groovypptest/downloads/list and you’ll see all the sources of standard library.
Best regards and until next time,
Eugene.