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

Question

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

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

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

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

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

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

Побольше фон:

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

class ArrayDefinition { 
    Array<Thing> Items; 
} 

И мой класс Вещь становится так:

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

Это "ArrayDef" не должен использоваться. Это просто необходимо использовать, если необходимо. Некоторые «вещи» не имеют массивов, некоторые делают. Но у всех «вещей» есть отношения.

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

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

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

Проблема делает это не работает до смешного медленно.

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

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

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

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

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

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 vs B и A vs C).

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

Проблема, с которой я столкнулся, это STILL кажется чрезмерным.

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

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

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

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

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

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

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

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

Спасибо всем

Answer 1

В общем, вы не сможете придумать структуру, которая, как-быстро, как-возможно для каждой операции. Есть компромиссы.

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

Answer 2

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

Answer 3

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

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

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", то я добавил «modifiedtag» ко всем массивам A, которые используются для определения, и все массивы B используются для определения.

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

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

Он должен работать :)

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

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

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

Answer 4

Ну, во-первых, некоторый лексикон.

Design Pattern: Observer

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

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

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

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

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

Кроме того, следуйте советам ergosys, а также моделируйте отношения за пределами объектов. Наличие 1 класса BIG обычно является началом неприятностей ... если вам трудно разрезать его на логические части, проблема в том, что проблема вам непонятна, и вы должны спросить о том, как моделировать его ... Как только вы получилась четкая модель, вещи обычно падают на место немного легче.

Answer 5

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

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

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; 
}