Блог

Главная - Вопросы по программированию - Как эффективно найти помеченные элементы в списке помеченных элементов, теги которых включают все указанные мной теги?

Как эффективно найти помеченные элементы в списке помеченных элементов, теги которых включают все указанные мной теги?

#algorithm #search #data-structures #filtering #keyword

Вопрос:

У меня есть несколько помеченных объектов (называемых TagObj):

 class TagObj { 
    name: string;
    tags: string[];
}

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

 getTagObjsMatching(objs: TagObj[], tagsFilters: string[]): TagObj[] {
    // return all elements of objs which contain all specified filter tags
}
 
 var objsExample: TagObj[] = [
    { name: "apple", tags: ["round", "red", "sweet"] },
    { name: "banana", tags: ["long", "yellow", "sweet"] },
    { name: "sea urchin", tags: ["round", "spiked", "salty", "savory"] },
    { name: "watermelon", tags: ["oblong", "red", "sweet"] },
];
getTagObjsMatching(objsExample, ["sweet", "red"]); 
// returns:
// [{ name: "apple", tags: ["round", "red", "sweet"] }, { name: "watermelon", tags: ["oblong", "red", "sweet"] }]

Я хочу иметь возможность хранить свои TAGOBJ в памяти, позволяя эффективно добавлять и удалять элементы TagObj. Я могу предположить, что нет 2 TAGOBJ с одинаковым именем.
Промежуточные структуры данных могут быть построены для повышения производительности функции getTagObjsMatching ().
В моем текущем решении используется двустороннее сопоставление словарей:

 dictionary1 from name to TagObj (used for retrieval and deletion)
dictionary2 from tag to all a set containing TagObjs (for getTagObjsMatching())
  Initialize the result to all TagObjs.
  For each tag of tagsFilters:
    delete from the result all elements that do not contain the tag (use dictionary2 for lookup)
  return the filtered result.

Я ищу решение, которое работает лучше, чем O(n^2).

Метки: ,