wtorek, września 17, 2019

Który kod (nie kot! ;-)) lepszy?

Mamy kawałek kodu:
public List<List<Integer>> getLevelsOfTree(TreeNode root) {
    List<TreeNode> nodes = List.of(root);
    List<List<Integer>> res = new ArrayList<>();
    while (!nodes.isEmpty()) {
        res.add(nodes.stream().map(curr -> curr.val).collect(Collectors.toList()));
        nodes = nodes.stream().map(curr -> Arrays.asList(curr.left, curr.right)).flatMap(List::stream).filter(Objects::nonNull).collect(Collectors.toList());
    }
    return res;
}

Oraz:
public List<List<Integer>> getLevelsOfTree(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    preOrder(root, 0, res);
    return res;
}

private void preOrder(TreeNode root, int d, List<List<Integer>> res) {
    if (root==null) return;
    if (res.size()==d) res.add(new ArrayList<>());
    res.get(d).add(root.val);
    preOrder(root.left, d+1, res);
    preOrder(root.right, d+1, res);
}

Który jest bardziej czytelny?

Do mnie osobiście przemawia bardziej ten drugi, bo widzę, że robi preOrder po drzewie i zapisuje sobie wartości node'ów.
Ten pierwszy robi magię.
Najpierw wrzuca root'a drzewa do listy, później póki lista node'ów nie jest pusta to dodaje do listy wyników wartości node'ów, a później tworzy nową listę node'ów robiąc lekką magię.

Niby to pierwsze jest bardziej kompaktowe, ale IMHO trudniejsze do zrozumienia.
Do tego jak to drugie zużywa O(N) pamięci na N wartości + O(log(N)) na stos (jeśli drzewo nie jest listą...), a to pierwsze trudniej powiedzieć. Głównie działa na strumieniach, ale terminuje je collectorami. Tak stawiam, że używa O(N) pamięci.
Czasowo pierwsze jest wolniejsze (i to nawet na Java 11!!), nie dam głowy, ale zakładam, że nadal przygotowanie lambd i ich wołanie kosztuje.

Ten pierwszy wydaje mi się bardziej hacky, ten drugi bardziej straight-forward...

Jakieś opinie?


Podobne postybeta
Niecne wykorzystanie refleksji... czyli jak poszukać tekstu w drzewie obiektów? ;-)
Sztuczki tropiciela błędów - breakpoint na sterydach ;-)
Java 8 nadchodzi....
Giń konstruktorze! Giń! ;-)
Java na Raspberry Pi zaskakuje ;-)

2 komentarze:

  1. Ten pierwszy to jakiś masakryczny oneliner. Nie wiem co i dlaczego.

    OdpowiedzUsuń
    Odpowiedzi
    1. Czyli to nie tylko moje wrażenie ;-) To cieszy :-)

      Usuń