Как уменьшить сложность времени от O (n) до O (1) для этих списков пользовательских объектов?

Question

#include <stdio.h> 

Class XObject 
{ 
    int id; 
    char *type; 
} 
Class XSubObject : XObject 
{ 
    int remark; 
    char* place; 
} 

** Извините за мой плохой пример, но более или менее данные выглядят так. std :: векторные объекты; данные, хранящиеся в объектах, как это: #1=XObject(1001,"chair"), #2=XObject(1002,"spoon"), #3=XSubObject(1004,"table",2,"center"), #4=XSubObject(1005,"item",0,"left") и so..on

мы CNA имеют разные XObjects с теми же типами.

Class XStructure 
{ 
    XObject parent; 
} 

Class XStructureRow 
{ 
    XObject child; 
    XStructure parentStruct; 
} 

std :: векторные структуры; данные, хранящиеся в структурах, как это: #5=XStructure(NULL), #7=XStructure(#1),#8=XStructure(#2),#9=XStructure(#3),#10=XStructure(#4) и so..on

станд :: вектор structurerows; данные, хранящиеся в структурах, как это: XStructureRow(#4,#5), XStructureRow(#2,#1),XStructureRow(#2,#7),XStructureRow(#3,#10),XStructureRow(#4,#8) и so..on

Как я могу написать быстрый alogirthm, который начинается с XObject и находит его, в котором structurerow и извлечение его структуры и извлечения его родителя. Например, я хочу вернуть всех родителей объекта с именем «table» и вернуть родителям имя «стул».

Мой написанный алгоритм:

std::vector<XObject> getParents(XObject "chair") 
{ 
    std::vector<XObject> objs; 
    for (int i=0;i<structurerows.size() ;i++) 
    { 
     XStructurerow sr=structurerows[i]; 
     XStructutre parent= sr.fetchParent(); 
     if(parent!=NULL) 
     { 
      if(parent.fetchName()=="chair") 
       objs.push_back(parent); 
     } 
    } 
    return objs; 
} 

если я должен извлечь все объекты родителей, то это занимает слишком много времени, если у меня есть огромные данные. Я имею в виду, есть ли какое-либо решение, которое помогает находить родительские объекты с помощью O (1), вместо того, чтобы повторять полный цикл? Я хочу получить этих родителей с минимальными итерациями. Здесь сложность O (n), которую я не удовлетворяет. Надеюсь, я сделал несколько действительных моментов. Предложения пожалуйста.

Answer 1

Единственный способ «найти» что-то с сложностью O (1) - использовать хэш-таблицу. Процесс создания хэш-значения из значения ключа и последующего доступа к объекту, индексированному в таблицу этим хэш-значением, будет иметь сложность O (1). В противном случае любой другой алгоритм поиска в лучшем случае будет O (log n) для отсортированного списка или сортированной структуры древовидного типа.

Answer 2

Несколько предложений.

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

Во-вторых, иерархия классов имеет классы с дочерними и родительскими объектами, но хранит копии этих экземпляров XObject. Поэтому, если вы должны были обновить один из этих объектов независимо, все родительские и дочерние объекты, о которых вы думаете, ссылаются на них, имеют другую копию. (И, следовательно, позже создадут некоторые странные ошибки, особенно потому, что базовые классы содержат указатели). Ваши объектные отношения в объявлениях классов должны быть указаны с помощью указателей, а не экземпляров экземпляра.

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

Не зная ничего о вашей проблеме, если бы вы обратились к этим трем вещам, вы, вероятно, имели бы лучшую производительность и не хотели бы находить решение O (1).

Теперь на самом деле ответить на ваш вопрос:

Я бы держать карту или таблицу (hash_map) массивов, чтобы отслеживать все объекты определенного типа. То есть:

std::map<std::string, std::vector<XObject*>> lookupmap; 

Тогда, как создается каждый объект, вы можете посмотреть его тип в «lookupmap» и добавить его:

void OnObjectCreated(XObject* pObj) 
{ 
    std::string strType(pObj->type); 

    lookupmap[strType].push_back(pObj); 
} 

Я оставлю ту часть, где вы используете зЬй :: map или std :: hash_map как упражнение для вас.