Преминаване на алгоритъм в дървовидна структура

Class Diagnostic {

//Get the size in bytes of an object
static long sizeOf(Object object);

//Get the references for an object (leafs)
static List<Object> getRefs(Object object);

//Implement this with those above
public Long objectSize(Object object);
}

Как бихте внедрили objectSize, за да върнете размера в байтове на обекта?

Методът objectSize връща размера в байтове на всички комбинирани дъщерни възли (всеки възел в дървото).

Пример:

               Object A (19 bytes)
                      /    \
                     /      \
                   B(20)    C(37)
                   /
                  /
                C(15)

Отговор: 19+20+37+15 = 91

Зададох този въпрос по време на интервю и съм много любопитен да видя отговорите на другите. Тъй като не знаех много за алгоритъма за обхождане на дърво.

Измислих това... (знам, че е лошо или не ;) , просто се опитвам да науча)

    public Long objectSize(Object object) {
    List<Object> objectList = new ArrayList<Object>();

    Long sum = sizeOf(object);
    objectList = getRefs(object);

    for(Object object : objectList){
           sum += objectSize(object);
    }

return sum;
}

Забелязах, че може да имам цикъл и да премина през грешка на stackoverflow, защото не проверих дали вече съм преминал през „възел“. Тогава реших, че трябва да имам друга структура от данни (като hashmap за обработка на ключ/стойност), за да обработвам временен списък за сравнение.


java algorithm tree-traversal
person fneron    schedule 15.05.2013    source източник
comment
Въпросът ви е неясен. Трябва ли objectSize(Object object); да върне размера на себе си и на всички дъщерни възли заедно?   -  person BLuFeNiX    schedule 15.05.2013
comment
Нямате цикли в дърво.   -  person MAV    schedule 15.05.2013
comment
Дърветата нямат цикли, но вашият код все още може да работи с цикли, ако препратките на структурата всъщност не формират DAG. С това имам предвид за всяка двойка Object A и Object B, можете да имате A в getObjects(B) и B в getObjects(A), ако по някаква причина препратките са симетрични. В противен случай мисля, че имахте предвид sum += objectSize(object); в този цикъл.   -  person G. Bach    schedule 15.05.2013
comment
Поправете ме, ако греша, но във вашия пример функцията трябва да върне 19 + 20 + 37 + 15 = 91, прав ли съм?   -  person Rerito    schedule 15.05.2013
comment
@G.Bach Наистина, прав си и за двете.   -  person fneron    schedule 15.05.2013
comment
Предполагам, че сте декларирали sum като променлива на екземпляр или променлива на клас. Ако случаят е такъв, ще трябва да запомните винаги да нулирате sum на 0, преди да извикате метода objectSize. В противен случай алгоритъмът изглежда работи добре. Фактът, че sum е променлива на екземпляр/клас, изглежда малко странен, въпреки че...   -  person Alderath    schedule 15.05.2013
comment
@G.Bach Всъщност, ако той постави sum += objectSize(object); в цикъла, тогава резултатът за примера ще бъде: 19 + 20 + 15 + 54 + 108 + 37 + 253 (т.е. 506). В неговия цикъл променливата sum е променлива на екземпляр/клас, която се увеличава всеки път, когато се посети възел.   -  person Alderath    schedule 15.05.2013
comment
@Alderath В неговия цикъл променливата на сумата е променлива на екземпляр/клас, която се увеличава всеки път, когато се посети възел. Това е идеята, да. Не разбирам как ги измисляш тези числа. Не е като това да добавя сумата от поддървото на всяка стъпка в йерархията.   -  person G. Bach    schedule 15.05.2013
comment
@G.Bach Говорех за първоначалния въпрос. OP актуализира въпроса сега и направи sum локална променлива. т.е. sum += sizeOf(object) (променлива на екземпляр/клас) е заменена с Long sum = sizeOf(object) (локална променлива). Ако беше запазил sum като променлива на класа, променливата sum щеше да се удвоява при всяко извикване на sum += objectSize(object);.   -  person Alderath    schedule 15.05.2013
comment
@Alderath Разбирам, не бях виждал първоначалната версия на въпроса.   -  person G. Bach    schedule 15.05.2013
comment
@Alderath Лошото ми! Току-що написах въпроса си бързо и направих някои грешки, докато записвах кода си. =/   -  person fneron    schedule 15.05.2013
comment
@G.Bach Как бихте атакували проблема, ако всъщност беше DAG? Бихте ли използвали вместо списък hashmap и проверете дали ключът е вече видян например...   -  person fneron    schedule 16.05.2013
comment
@fneron Ако референтната структура, която имате, всъщност формира DAG, това, което сте написали, работи добре. Ако написаното от вас се прекрати, можете да сте сигурни, че вашата структура също е DAG, защото в противен случай всеки кръг ще ви постави в безкраен рекурсивен цикъл.   -  person G. Bach    schedule 16.05.2013

Отговори (3)


arrow_upward
2
arrow_downward

Ако имате работа с истинска "дървовидна" структура, тогава не е нужно да се притеснявате за цикли.

Разбрахте основната идея, но трябва да вземете под внимание действителната върната стойност на рекурсивното извикване. Ако приемем, че общият размер на обекта (objectSize()) е равен на сумата от размерите на неговите деца плюс неговия собствен размер (sizeOf()), тогава просто трябва да се уверите, че добавяте всички размери на поддървото заедно.

Ето един начин, по който можете да го направите:

public Long objectSize(Object object) {
    List<Object> objectList = getRefs(object);
    long sum = sizeOf(object);

    for(Object object : objectList) {
         sum += objectSize(object);
    }

    return Long.valueOf(sum);
}

Нещото, което ви липсваше, беше, че рекурсивното objectSize извикване върна стойност и тази стойност трябваше да бъде включена (в този случай чрез добавяне) във вашата върната стойност.

person Platinum Azure    schedule 15.05.2013
comment
Всъщност аз го направих така. Просто го записах твърде бързо. Сладка! - person fneron; 15.05.2013

arrow_upward
0
arrow_downward

Не съм го тествал, но този прост алгоритъм за търсене на BFS трябва да го направи.

public Long objectSize(Object object) {
   long sum=sizeOf(object);

   Queue<Object> q= new LinkedList<Object>();
   for (Object o : getRefs(object)) {
      q.add(o);
   }
   while (q.peek() != null) {
      Object child= q.poll();
      sum+= sizeOf(child);
      fore (Object o : getRefs(child)) {
         q.add(o);
      }
   }
   return sum;   
}
person darijan    schedule 15.05.2013

arrow_upward
0
arrow_downward

Ето какво бих направил:

Бих изградил стек, съдържащ възлите, които остават за изследване, и бих ги обработил в цикъл while. Тъй като уменията ми за Java са изгубени някъде в съзнанието ми, няма да ви дам имплементация, но ще обясня процеса:

Вход: Дърво T
Изход: Общият размер на обектите на възлите

  1. Инициализирайте стека S, като натиснете T.root (основния възел) в него
  2. Инициализирайте общия размер size на 0 : size = 0
  3. While S is not empty :
    1. Let N be the head of S, we pop S : N = pop(S)
    2. Натиснете N.leftChild и N.rightChild в S, ако съществуват
    3. Актуализиране на размер: размер = размер + N.размер
  4. Върнете размер
person Rerito    schedule 15.05.2013