#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).