Что такое самонастраивающиеся структуры данных?

Question

Что такое самонастраивающиеся структуры данных?

Что вы подразумеваете под" самонастраивающимися " структурами данных? Чем они отличаются от других структур данных? Где они используются?

Edit: зачем корректировать структуру данных, если выполняются операции, отличные от insert и delete?

625 3

data-structures

3 ответов:

Comments

Ничего не найдено.

Welbog · Accepted Answer · 2009-05-20 04:17:14

Самонастраивающаяся структура данных - это структура, которая может перестраиваться, когда на нее совершаются операции. Иногда они перестраиваются широко или минимально.

Например, деревья AVL балансируют себя каждый раз, когда узел вставляется или удаляется, чтобы обеспечить сбалансированность дерева в целом и, следовательно, гарантировать быстрый поиск за счет вставки и удаления.

Примером несаморегулирующейся структуры может служить наивное бинарное дерево, в котором узлы остаются там, где они были впервые вставлены, независимо от того, что происходит с деревом.

Добавление: другие структуры настраиваются на основе чтения, а не вставки или удаления. Эти структуры могут быть усовершенствованы и собирать большое количество статистических данных о доступе, или же они могут быть более эвристичными по своей природе. Цель этих структур состоит в том, чтобы сделать чтение быстрее на основе того, что было прочитано в прошлом. Распространенным примером такой структуры является кэш , в котором данные, которые были недавно полученные данные доступны быстрее, чем данные, которые еще не были доступны.

unj2 · Accepted Answer · 2009-05-20 05:31:55

Я нашел хорошие конспекты лекций по этим видам структуры данных. Это от Advanced Эрик Demaine класса структуры данных в МТИ: http://courses.csail.mit.edu/6.851/spring07/scribe/lec01_2.pdf

Rob Jellinghaus · Accepted Answer · 2010-07-29 00:13:48

В этом контексте есть еще одно значение слова "самонастраивающийся". У вас может быть структура данных (например, мини-куча), которая, учитывая набор входных данных, предоставляет некоторое выходное значение, такое как минимальный элемент. Обычно затем требуется внести небольшое изменение во входные данные и обновить кучу, чтобы доставить новый минимальный элемент. В идеале вы хотели бы сделать это за время, пропорциональное размеру изменения, а не общему размеру кучи.

Самонастраивающиеся данные структуры поддерживают этот тип поведения "изменить входные данные, пересчитать выходные данные постепенно". См. Эту недавнюю статью из PLDI '10 .

В некотором смысле это связано с функциональным реактивным программированием, которое разделяет цель эффективного отслеживания зависимостей и инкрементных вычислений.