Эффективный алгоритм сравнения только тех списков, которые были обновлены

Question

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

Хорошо, поэтому я пытаюсь смоделировать «понятия» или «вещи», как я их называю.Просто понятия в общем.Это связано с логикой обработки.

Итак, каждая «вещь» определяется ее отношением к другим вещам.Я храню это как набор из 5 битов на отношения.«Вещь» может быть такой:

class Thing {
    char* Name;
    HashTable<Thing*, int> Relationships;
}

Итак, я моделирую «Вещи» вот так.5 бит на отношения.Каждый бит обозначает одно возможное отношение.Примерно так: 1 равно, 2 внутри, 3 снаружи, 4 содержит, 5 перекрытий.Наличие всех 5 битов означает, что мы совершенно не знаем, каковы отношения.Наличие 2 бит означает, что мы думаем, что отношения могут быть одной из двух возможностей.Отношения начинаются как «неизвестно» (все 5 битов верны) и становятся более конкретными с течением времени.

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

Немного больше предыстории:

Я пытаюсь добавить дополнительное определение в моё моделирование«концепций» (вещей), используя дополнительные классы.Например:

class ArrayDefinition {
    Array<Thing> Items;
}

И мой класс Thing выглядит следующим образом:

class Thing {
    char* Name;
    HashTable<Thing*, int> Relationships;
    ArrayDefinition* ArrayDef;
}

Этот «ArrayDef» НЕ ДОЛЖЕН использоваться.Это просто для использования, если это необходимо.Некоторые «вещи» не имеют массивов, некоторые имеют.Но все «вещи» имеют отношения.

Я могу обработать это «определение массива», чтобы выяснить отношения между двумя вещами!Например, если X = [ A B C D E ] и Y = [ C D E ], мой код может обработать эти два массива и выяснить, что "Y inside X".

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

Вот проблема:

Проблема в том, что это не работает смехотворно медленно.

Представь, есть 2000 "вещей".Допустим, 1000 из них имеют определения массивов.Теперь это дает 500 000 (ish) возможных «пар массивов», которые нам нужно сравнить друг с другом.

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

Итак ... скажем, только 500 из этих "вещей с массивами" имеют неизвестные или частично известные отношения.Это все еще делает 250000 (ish) возможными «парами массивов» для сравнения!

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

Например, скажем, у меня есть эти два массива:

    X = [ A B C D E ]
    Y = [ Q W R T ]

сейчас, если я скажу, что T=R, это очень мило.Но это не влияет на отношения между X и Y. Так что только потому, что отношение T к R стало известно как «равное», тогда как прежде, чем оно могло быть полностью неизвестно, это не означает, что мне нужно снова сравнивать X и Y.

С другой стороны, если я скажу "T outside E", это отношения между вещами, используемыми для определения двух массивов.Поэтому, сказав, что «T outside E» означает, что мне нужно обработать массив X против массива Y.

Я действительно не хочу сравнивать 500 000 «пар-массивов» только для обработки логики на 1000 массивах, когда почтимежду ними ничего не изменилось!

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

Допустим, у меня есть3 массива:

    A = [ X Y Z ]
    B = [ X X X X ]
    C = [ X Z X F ]

Ну, X используется в 3 массивах.Таким образом, X может хранить список всех массивов, внутри которых он используется.

Итак, если бы я сказал "X inside Y", это могло бы вызвать список всех массивов, которые Y используется для определения, и все массивы X используются для определения. Допустим, X используется в 3 массивах, а Y используется в 1 массиве. Из этого мы можем выяснить, что есть 2 «пары массивов», которые нам нужно сравнить (A против B и A против C).

Мы можем дополнительно урезать этот список, проверив, имеет ли какая-либо из пар массивов уже полностью известные отношения.

У меня проблема с этим, это все еще кажется чрезмерным.

Скажем, X - это действительно распространенная "вещь". Он используется в 10 000 массивов. И Y - действительно распространенная вещь, используемая в 10 000 массивов.

Я все еще получаю 100 000 000 пар массивов для сравнения. Итак, допустим, мне не нужно сравнивать их все, на самом деле, только 50 из них были частично известны или совершенно неизвестны.

Но ... Мне все равно пришлось просмотреть список из 100 000 000 пар массивов, чтобы выяснить, какая из них была частично известна. Так что это все еще неэффективно.

Мне действительно интересно, нет ли эффективного способа сделать это. И если на самом деле все, что я могу сделать, это сделать несколько эффективных "эвристических" стратегий. Мне еще не повезло, когда я придумал хорошие стратегии.

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

Если это поможет ... Моя лучшая попытка выразить это в общих терминах - это "как сравнить только те списки, которые были обновлены".

У кого-нибудь есть идеи? Это было бы прекрасно. Если нет ... возможно, только я, написав это, может помочь моему мыслительному процессу.

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

Спасибо всем

Answer 1

Из вашего собственного ответа я делаю вывод, что неизвестные отношения в значительной степени пронумерованы известными отношениями. Затем вы можете отслеживать неизвестные отношения каждой вещи в отдельной хэш-таблице / наборе. В качестве дальнейшей оптимизации вместо отслеживания всех определений, в которых используется объект, отслеживайте, какие из этих определений имеют неизвестные отношения - на какие отношения можно повлиять. Затем, учитывая недавно определенные отношения между X и Y, возьмите затронутые определения одного из них и найдите пересечение каждого из неизвестных отношений с затронутыми определениями другого. Чтобы поддерживать структуру данных ускорения в актуальном состоянии, когда отношения становятся известными, удалите их из неизвестных связей и, если не осталось неизвестных связей, перейдите к массиву def и удалите элемент из наборов, влияющих на влияние.

Структура данных будет выглядеть примерно так:

class Thing {
    char* Name;
    HashTable<Thing*, int> Relationships;
    Set<Thing*> UnknownRelationships;
    ArrayDefinition* ArrayDef;
    Set<Thing*> CanAffect; // Thing where this in ArrayDefinition and UnknownRelationships not empty
}

class ArrayDefinition {
    Array<Thing> Items;
}

Answer 2

Ну, во-первых, немного словарного запаса.

Шаблон проектирования: Observer

Это шаблон проектирования, который позволяет объектам регистрироваться в других и запрашивать уведомления о событиях.

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

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

Таким образом, вы уведомляете только тех, кто действительно заботится об обновлении.

Однако следует принять во внимание один момент: если у вас рекурсивные отношения, это можетстать волосатым, и вам нужно будет придумать способ избежать этого.

Кроме того, следуйте советам ergosys и моделируйте отношения вне объектов.Наличие 1 БОЛЬШОГО класса - это обычно начало неприятностей ... если вам трудно разбить его на логические части, проблема в том, что проблема для вас не ясна, и вам следует обратиться за помощью к тому, как его смоделировать ... Как только выЕсли у вас есть четкая модель, то обычно все становится проще.

Answer 3

Я не уверен, что понимаю, что вы делаете полностью (цель ArrayDefinition особенно тумана), но я думаю, вам следует рассмотреть возможность отделения моделирования объектов от их отношений. Другими словами, создайте отдельное отображение от объекта к объекту для каждого отношения. Если объекты представлены их целочисленным индексом, вам нужно только найти эффективный способ представления целочисленных и целочисленных отображений.

Answer 4

Я выспался, и когда я проснулся, у меня появилась новая идея. Это может сработать ...

Если каждая «вещь» хранит список всех «определений массива», которые она используется для определения.

class Thing {
    char* Name;
    HashTable<Thing*, int> Relationships;
    ArrayDefinition* ArrayDef;
    Set<ArrayDefinition*> UsedInTheseDefs;
}

class ArrayDefinition {
    Array<Thing> Items;
    Set<int> RelationModifiedTag;
}

И я держу глобальный список всех «сопоставимых пар массивов».

И я также создаю глобальный список всех «массивов, которые можно сравнивать» (не попарно, а по одному).

Затем, каждый раз, когда меняется отношение, я могу просмотреть список «определений массивов», в котором я нахожусь, и добавить к нему небольшой «тег»:)

Так что я могу сделать что-то вроде этого:

static CurrRel = 0;
CurrRel++; // the actual number doesn't matter, it's just used for matching

foreach(Arr in this->UsedInTheseDefs) {
    Arr->RelationModifiedTag.Add( CurrRel );
}
foreach(Arr in other->UsedInTheseDefs) {
    Arr->RelationModifiedTag.Add( CurrRel );
}

Я изменил обе стороны отношений. Поэтому, если я сделал это: "A outside B", то я добавил «модифицированный тег» ко всем массивам, которые используются для определения, и все массивы B, которые используются для определения.

Итак, я перебираю свой список «сопоставимых пар массивов». Каждая пара, конечно, состоит из двух массивов, каждый из которых будет иметь набор RelationModifiedTag.

Поэтому я проверяю оба набора RelationModifiedTag друг на друга, чтобы увидеть, есть ли у них совпадающие числа. Если они ДЕЛАЮТ, то это означает, что у этой пары массивов есть отношение, которое только что было изменено! Итак ... тогда я могу сделать сравнение массивов.

Должно работать :) 1022 *

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

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

Извините за то, что прочитал весь этот длинный текст. И спасибо за все попытки помочь.

Answer 5

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

Эта проблема очень похожа на проблему выполнения запросов к реляционной базе данных - SELECT * WHERE ...Вы можете поискать вдохновение там.