存储各种类型的对象之间的1:1关系:解耦和高性能 [英] store many of relation 1:1 between various type of objects : decoupling & high performance

问题描述

我有300多个课程.它们在某些方面是相关的.

为简单起见，所有关系均为1:1.
这是一个示例图.

(在实际情况下，大约有50个关联对.)

注意:在某些情况下，某些关系可能不存在.
例如，某些 hen 与任何 food 都不相关.

注意2 :无链接=永不，例如每个 egg 与任何 cage 都不相关.
这样的关系将永远不会被添加/删除/查询.

问题:

如何优雅地存储它们之间的关系?
我的所有四个想法(如下)似乎都有缺点.

:我正在使用实体组件用于60fps游戏.
它是一个持久性数据库:用于游戏整个生命周期的单个实例.

Edit2:所有关系都是弱关系，而不是 is-a 或强 std :: unique_ptr 所有权.(谢谢沃尔特)

• 母鸡 在笼子中.
  某些 cages 不在任何 cage 中，而某些 cages 是空的.
• 一个小鸡 来自一个鸡蛋.
  但是，有些小鸡不是来自任何 egg (它们只是从天上掉下来的)，
  还有一些 eggs 不够幸运，无法成为 chick .
• 一只母鸡和一只小鸡 正在吃一盘(可能是一样)的食物.
  某些 food 盘子只是准备好但没有送达.

Edit3 :为每个对象分配一个整数ID可能是个好主意.
(感谢Oliv，ahoxha和Simone Cifani)

Edit4 :: 无需提供可编译的代码，只需一个基本部分/概念就足够了.

解决方案

根据要求，如果您只有一对一的关系，那么在我看来，它就像一张图表.在这种情况下，如果人口稠密(有很多关系)，我将使用图的矩阵表示形式.在下表中，我分别将数字0到4关联到实体(母鸡，笼子，食物，鸡蛋和小鸡).如果存在Hen-Egg关系，则矩阵在 matrix [0] [3] 的位置处将为1，如果不存在，则其值为0(您可以选择以下值:您可以决定如何判断该关系何时存在或不存在).如果关系是无向的，则只需要矩阵的一侧(例如，上三角).

  + --------------------------------- +|母鸡笼子食物|鸡蛋小鸡|+ --------------------------------- +|0 |1 |2 |3 |4 |+ --------------------------------- +0 1 2 3 4+ -------------------- +0 |0 |1 |0 |1 |1 |+ --- + --- + --- + --- + ---- +1 |0 |0 |0 |1 |1 |+ --- + --- + --- + --- + ---- +2 |0 |0 |0 |0 |1 |+ --- + --- + --- + --- + ---- +3 |0 |0 |0 |0 |1 |+ --- + --- + --- + --- + ---- +4 |0 |0 |0 |0 |0 |+ -------------------- + 

此解决方案的不足之处在于内存使用情况，尤其是在矩阵包含很多0(不存在关系)的情况下；您将不必要地占用大量空间.在这种情况下，您可以使用图形的链表表示形式.

I have 300+ classes. They are related in some ways.

For simplicity, all relation are 1:1.
Here is a sample diagram.

(In real case, there are around 50 relation-pairs.)

Note: For some instances, some relation may not exist.
For example, some hens don't relate to any food.

Note2: No link = never, e.g. every egg doesn't relate to any cage.
Such relation will never be added/removed/queried.

Question:

How to store relation between them elegantly?
All 4 of my ideas (below) seem to have disadvantages.

Here is a related question but with 1:N and only 1 relation.

My poor solutions

These are semi-pseudo-codes.

Version 1 Direct

My first thought is to add pointer(s) to each other.

Chick.h:-

class Egg;
class Food;
class Chick{  Egg* egg; Food* food;}

Hen.h:-

class Egg; class Cage; class Food;
class Hen{ Egg* egg; Cage* cage; Food* food;}

It is very cheap to add/remove relation and query, e.g. :-

int main(){
    Hen* hen;    ...    Egg* egg=hen->egg;
}

It works good, but as my program grow, I want to decouple them.
Roughly speaking, Hen.h should not contain word Egg, and vice versa.

There are many ideas, but none seems very good.
I will show a brief snippet for each work-around then summarizes pros & cons at the end of question.

Version 2 Hash-map

Use std::unordered_map.
It becomes a bottle neck of my program. (profiled in release mode)

class Egg{}; class Hen{};  //empty (nice)
.....
int main(){
    std::unordered_map<Hen*,Egg*> henToEgg;
    std::unordered_map<Egg*,Hen*> eggToHen;
    ....
    Hen* hen;    ...    Egg* egg=henToEgg[hen];
}

Version 3 Mediator-single

Store every relation in a single big mediator for every entity.
Waste a lot of memory for empty slots (e.g. Egg has henFood_hen slot).
Total waste = type-of-relation-pair*2*4 bytes (if run at 32 bits) in every entity.

class Mediator {
    Egg* eggHen_egg=nullptr;
    Hen* eggHen_hen=nullptr;
    Hen* henFood_hen=nullptr;
    Food* henFood_food=nullptr;
    //... no of line = relation * 2
};
class Base{public: Mediator m;};
class Egg : public Base{};  //empty (nice)
class Hen : public Base{}; 
int main(){
     Hen* hen;    ...    Egg* egg=hen->eggHen_egg;
}

Version 4 Mediator-array (similar as 3)

Try to standardize - high flexibility.

class Mediator {
    Base* ptrLeft[5];
    Base* ptrRight[5];
};
class Base{public: Mediator m;};
class Egg : public Base{};  //empty (nice)
class Hen : public Base{}; 
int main(){
     enum RELA_X{RELA_HEN_EGG,RELA_HEN_CAGE,RELA_EGG_CHICK, .... };
     Hen* hen;    ...    
     Egg* egg=hen->m.ptrRight[RELA_HEN_EGG]; 
     //^ get right of "hen-egg" === get "egg" from "hen"
     //^ can be encapsulated for more awesome calling
}

Pros & Cons

Green (+) are good. Red (-) are bad.

Edit: I am using Entity-Component for a 60fps game.
It is a persistent database : a single instance used for the entire life of a game.

Edit2: All of the relation are weak relation rather than is-a or strong std::unique_ptr ownership. (Thank Walter)

• A hen is in a cage.
  Some hens are not in any cage, and some cages are empty.
• A chick come from an egg.
  However, some chicks didn't come from any egg (they are just dropped from sky),
  and some eggs are not lucky enough to become chick.
• A hen and a chick are eating a (probably same) plate of food.
  Some food plates are just prepared but not served.

Edit3: Assign an integer id for each object can be a good idea.
(Thank Oliv, ahoxha, and Simone Cifani)

Edit4:: No need to provide a compilable code, just an essential part / concept is enough.

解决方案

Based on the requirements, if you have only one-to-one relations, then it sounds to me like a graph. In this case, if it is densely populated (there are many relations), I would use the matrix representation of the graph. In the tables below, I have associated numbers 0 through 4 to the entities (Hen, Cage, Food, Egg and Chick) respectively. If the relation Hen - Egg exists, then the matrix will have a 1 at the position matrix[0][3], if it doesn't then the value would be 0 (you can choose values of your choice to decide how to tell when the relation exists or doesn't). If the relations are undirected, then you only need one side of the matrix (the upper triangle, for example).

+---------------------------------+
| Hen | Cage | Food | Egg | Chick |
+---------------------------------+
|  0  |  1   |  2   |  3  |   4   |
+---------------------------------+

      0   1   2   3   4
    +--------------------+
  0 | 0 | 1 | 0 | 1 | 1  |
    +---+---+---+---+----+
  1 | 0 | 0 | 0 | 1 | 1  |
    +---+---+---+---+----+
  2 | 0 | 0 | 0 | 0 | 1  |
    +---+---+---+---+----+
  3 | 0 | 0 | 0 | 0 | 1  |
    +---+---+---+---+----+
  4 | 0 | 0 | 0 | 0 | 0  |
    +--------------------+

The downside of this solution hides in the memory usage, especially if the matrix contains a lot of 0's (relations that don't exist); you would be unnecessarily occupying a lot of space. In this case you may use the linked-list representation of the graphs.

这篇关于存储各种类型的对象之间的1:1关系:解耦和高性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！