Praca z tablicą obiektów

Question

Mam tablicę obiektów, które mogą zawierać dzieci tego samego typu obiektu, na przykład:

var exampleArray = [ 
    { 
     alias: 'alias1', 
     children: [ 
      { 
       alias: 'child1' 
      }, 
      { 
       alias: 'child2', 
       children: [ 
        { 
         alias: 'child4' 
        }, 
        { 
         alias: 'child5' 
        } 
       ] 
      }, 
      { 
       alias: 'child3' 
      } 
     ] 
    }, 
    { 
     alias: 'alias2' 
    }, 
    { 
     alias: 'alias3', 
     children: [ 
      { 
       alias: 'child6' 
      }, 
      { 
       alias: 'child7' 
      } 
     ] 
    } 
]; 

Przedmiotem baza ma inne właściwości, ale nie są one ważne na pytanie (s) na dłoni. Teraz, pozwala zakładać, że obiekty mogą być:

{ 
    alias: 'string', 
    children: [] 
} 

Dzieci są opcjonalne.

Poszukuję najlepszych metod/najszybszych metod zarządzania niektórymi przedmiotami za pomocą takiego obiektu. Stworzyłem kilka cyklicznych metod, aby zrobić kilka rzeczy, które chcę, ale chcę wiedzieć, czy istnieją lepsze sposoby, aby zabrać następujące zadania:

1. hasAlias ​​(ARR, alias) - muszę ustalić jeśli cały obiekt zawiera dowolny obiekt z podanym aliasem.

Obecnie robię to rekursywnie, ale biorąc pod uwagę, że ta tablica może się rozwijać w sposób skończony, metoda rekursywna ostatecznie osiągnie granice stosu.

2. getParent (arr, alias) - Muszę mieć możliwość uzyskania elementu nadrzędnego zawierającego element o podanym aliasie. Biorąc pod uwagę, że alias "są unikalne dla całej tablicy, nigdy nie będzie dwóch takich samych aliasów. Znowu robię to rekurencyjnie teraz, ale chcę znaleźć lepsze metody robienia tego.

3. deleteObject (arr, alias) - Nie jestem pewien, jak to zrobić obecnie. Muszę umieć przekazać tablicę i alias i usunąć ten obiekt (i wszystkie jego dzieci) z podanej tablicy. Rozpocząłem rekursywną metodę robienia tego, ale zatrzymałem się i postanowiłem zamiast tego opublikować tutaj.

Używam Node.js i mam do dyspozycji szybkie metody robienia rzeczy. Wciąż jestem całkiem nowym użytkownikiem JavaScript, więc nie jestem pewien, czy istnieją lepsze sposoby na robienie rzeczy z tablicami o większej skali, jak ta.

Answer 1

Mogę podejść do twojej głównej tablicy nieco inaczej i zachować ją jako płaską tablicę, która odwołuje się do innych elementów, a nie włącza je w całości.

var flat = [ 
    { 
     alias : "str1", 
     children : [ flat[1], flat[2] ], 
     parent : null 
    }, 

    { 
     alias : "str1", 
     children : [], 
     parent : flat[0]  
    }, 

    { 
     alias : "str1", 
     children : [], 
     parent : flat[0]  
    } 
] 

Jest to rodzaj podejścia "linked list". Na połączonych listach znajdują się zalety i wady, ale możesz szybko iterować po wszystkich elementach.

Answer 2

W czasach, w których FORTRAN nie obsługiwał rekurencji, jeden osiągnął podobne efekty, zmieniając zestaw danych, symulując poziom "rekursji". Stosując tę ​​zasadę do struktury przykładem obiektu, funkcję do wyszukiwania obiektu przez jego „alias” (nazwa lub ID przez innego słowa) może być napisany bez rekursji tak:

function findAlias(parent, alias) // parent object, alias value string 
{ function frame(parent) 
    { return {parent: parent, children: parent.children, 
     index: 0, length: parent.children.length}; 
    } 
    var stack, tos, child, children, i; 

    stack = []; 
    if(parent.children) 
     stack.push(frame(parent)); 

    search: 
    while(stack.length) 
    { tos = stack.pop(); // top of generation stack 
     children = tos.children; 
     for(i = tos.index; i < tos.length; ++i) 
     { child = children[i]; 
      if(child.alias == alias) 
      { return { parent: tos.parent, child: child, childIndex: i} 
      } 
      if(child.children) 
      { tos.index = i + 1; 
       stack.push(tos); // put it back 
       stack.push(frame(child)); 
       continue search; 
      } 
     } 
    } 
    return null; 
} 

W krótkim jednego kończy się tworzenie stos małych obiektów danych, które są popychane i wciskane w tę samą funkcję zamiast wykonywania wywołań rekursywnych. Powyższy przykład zwraca i obiekt z wartościami obiektów parent i child. Wartość podrzędna jest tą z dostarczoną właściwością aliasu, a obiekt nadrzędny to obiekt z dzieckiem w tablicy children.

Zwraca wartość null, jeśli nie można znaleźć aliasu, więc można go użyć do funkcji hasAlias. Jeśli nie zwróci wartości null, wykonuje funkcję getParent. Trzeba utworzyć węzeł główny Jednakże:

// create a rootnode 
var rootNode = { alias: "root", children: exampleArray}; 
var found = findAlias(rootNode, "alias3"); 
if(found) 
{ console.log("%s is a child of %s, childIndex = %s", 
     found.child.alias, found.parent.alias, found.childIndex); 
} 
else 
    console.log("not found"); 

---

[Edit. Dodać childIndex szukać przedmiotu powrotną, aktualizacji Test przykładowy kod, dodać wniosku]

Wnioski

Korzystanie z rekursywnych wywołań funkcji, gdy jest obsługiwane dla aplikacji do chodzenia po drzewach, ma sens w zakresie samodzielnego dokumentowania kodu i łatwości konserwacji. Nierekurencyjna odmiana może się opłacić, jeśli można wykazać, że ma ona znaczące korzyści w zmniejszaniu obciążenia serwera w ramach testów ciśnienia objętościowego, ale wymaga solidnej dokumentacji.

Niezależnie od wewnętrznego kodowania, funkcja drzewo spaceru która zwraca obiekt ze szczegółami rodzic, dziecko, i dzieci wartości indeksu może przyczynić się do ogólnej efektywności programu poprzez zmniejszenie całkowitej liczby treewalks kiedykolwiek przeprowadzenia:

• prawdziwość wyszukiwanych wartości zwracanych zastępuje funkcję zwracania obiektu z wyszukiwania w celu aktualizacji, usunięcia lub wstawienia funkcji bez konieczności powtarzania wyszukiwań w drzewie w każdej funkcji.

Answer 3

Gwarantowana najszybszym sposobem jest oczywiście mieć

- an index for the aliases (thats actually a unique id) 
- have a parent backlink on each child item (if it has a parent) 

patrzysz się na indeksie id

var index = {} 
(function build(parent) { 
    index[parent.alias] = parent; 
    (parent.children || []).forEach(item => { 
     item.parent = parent 
     build(item) 
    }) 
})(objectRoot) 


function hasAlias(alias) { return alias in index } 

function getAlias(alias) { return index[alias] } 

function getParent(alias) { return index[alias] && index[alias].parent} 

Usuwanie aliasu oznaczałoby usunięcie go i jego dzieci z indeksu i od jednostka nadrzędna nadal pozostaje w indeksie:

function deleteAlias(alias) { 

    function deleteFromIndex(item) { 
     delete index[item.alias] 
     (item.children || []).forEach(deleteFromIndex) 
    } 
    var item = index[alias] 
    item.parent.children.splice(item.parent.children.indexOf(item)) 
    deleteFromIndex(item) 

}