Как представить двоичное отношение

Question

Я планирую создать класс, представляющий строгий частично упорядоченный набор, и я предполагаю, что наиболее естественным способом моделирования его интерфейса является двоичное отношение. Это дает такие функции, как:

bool test(elementA, elementB); //return true if elementA < elementB 
void set(elementA, elementB); //declare that elementA < elementB 
void clear(elementA, elementB); //forget that elementA < elementB 

и, возможно, такие функции, как:

void applyTransitivity(); //if test(a,b) and test(b, c), then set(a, c) 
bool checkIrreflexivity(); //return true if for no a, a < a 
bool checkAsymmetry(); //return true if for no a and b, a < b and b < a 

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

В идеале, в представлении памяти по своей природе должно быть обязательным всегда быть «в действии» и не допускать создания ребер, которые вызывают рефлексивность или симметрию. Другими словами, степени свободы структуры данных представляют собой степени свободы строгого набора. Есть ли известный способ сделать это? Или, что более реалистично, есть ли средство для проверки цикличности и поддержания транзитивности, которая амортизируется и повторяется при каждом вызове set и clear, так что затраты на обеспечение правильности низки. Есть ли рабочая реализация?

Answer 1

Хорошо, давайте поговорим о достижении головокружения с помощью микро-эффективности, и вы можете выбрать, насколько глубоко в этой пропасти вы хотите пойти. На этом архитектурном уровне нет таких структур данных, как хэш-карты и списки, нет даже типов данных, только бит и байты в памяти.

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

Здесь мы хотим, чтобы данные для a были объединены с данными смежности в один блок памяти. Поэтому вы хотите сохранить «список», так сказать, элементов, которые имеют отношение к a в a's собственном блоке памяти, чтобы мы могли получить доступ к a и всем элементам, связанным с a, в пределах одной строки кеша (бонусные баллы, если эти связанные элементы могут также входить в одну и ту же строку кэша, но это проблема NP-hard).

Вы можете сделать это, сохранив, скажем, 32-разрядные индексы в a. Мы можем моделировать такие объекты, как так, если мы пойдем немного более высокий уровень и использовать C для примера:

struct Node 
{ 
    // node data 
    ... 
    int links[]; // variable-length struct 
}; 

Это делает Node переменной длиной структуры, размера и потенциально даже адрес изменения, так что нам нужны дополнительный уровень косвенности, чтобы получить стабильность и избежать недействительности, например индекс индекса (если вы управляете распределением памяти/массивом, и это чисто смежный), или указатель на указатель (или ссылку на некоторых языках).

Это означает, что ваша тестовая функция по-прежнему связана с линейным поиском по времени, но линейна относительно количества элементов, связанных с a, а не количеством элементов. Поскольку мы использовали структуру переменной длины, a и ее соседние индексы потенциально вписываются в одну строку кеша, и вполне вероятно, что a уже будет в кеше, чтобы сделать запрос.

Это похоже на основную идею, содержащуюся в списках хранения хеш-карт, но без взлома списков накладных расходов и без хэш-поиска (это может быть постоянное время, но не так быстро, как просто доступ к соединениям с a тот же блок памяти). Самое главное, это гораздо больше кэш-памяти, и это часто будет иметь значение между несколькими циклами и сотнями.

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

Если вам нужен контейнер, чтобы быть универсальным и a может быть любой данный тип, T, то вы всегда можете обернуть его (с помощью C++ сейчас):

template <class T> 
struct Node 
{ 
    T node_data; 
    int links[1]; // VLS, not necessarily actually storing 1 element 
}; 

И еще сплавить этот блок все в один памяти сюда. Нам нужно разместить новое место здесь, чтобы сохранить семантику объектов C++ и, возможно, следить за выравниванием здесь.

Проверки транзитивности всегда связаны с поиском какого-либо рода (сначала первой или первой). Я не думаю, что есть какой-либо rep, который позволяет избежать этого, если вы не захотите memoize/cache потенциально массивный взрыв транзитивных данных.

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