「xs.size() == 0 と xs.isEmpty() の違い」のツイートより

今日は教育資料にブチきれて xs.size() == 0 と xs.isEmpty() の違いについて新人の子に熱く語ってしまった。教育資料と違うことを言って混乱させて申し訳ない

2012-09-06 22:34:07 via atig.rb

@keita44_f4 サイズ取ると、例えばxsがリストだったりすると、それだけでO(N)になっちゃうけど、isEmptyはすぐに返せるとかそういうことかと。たぶん。

2012-09-06 22:47:42 via Tween to @keita44_f4

おお、そうか……と思ったんだ。連結リストはサイズ持つ必要ないから、sizeとると全部走って O(n) になりかねない。1件でもあればisEmptyはfalseになるんだから、そう実装すれば O(1) にできるんだなー。

と思ってLinkedListさんを見てみる

isEmptyは影も形もない。AbstractSequentialListにもない。AbstractListにもない。なのでAbstractCollectionの実装のまま、これ。

    public boolean isEmpty() {
        return size() == 0;
    }

え、なに。てことはLinkedListにisEmptyはNG？

……と思ったけど、LinkedListがふつーにsize持ってた。で、ふつーにそれをサイズで返してた。

    transient int size = 0;

    public int size() {
        return size;
    }

とりあえずJavaでArrayListやLinkedList使ってる時は、計算量は関係無さげっぽい。EmptyListとかだと即true返してるから違うと言えば違けど、それが明確な差になることは無いだろう。

そこでConcurrentLinkedQueueさんの登場です

流石に「関係ありませんでしたー！」で終わるのはアレなんで、関係あるのを。java.util.concurrent.ConcurrentLinkedQueue です。他にもあるけど、何故か一番最初に目についたので。

サイズ取得でがんばってます。

    public int size() {
        int count = 0;
        for (Node<E> p = first(); p != null; p = succ(p))
            if (p.item != null)
                // Collection.size() spec says to max out
                if (++count == Integer.MAX_VALUE)
                    break;
        return count;
    }

なのでisEmptyはこう。

    public boolean isEmpty() {
        return first() == null;
    }

あったあった。期待通りの実装があってほっとした。だからisEmpty使いましょう！（と言うには弱い？）

それ以上に可読性

xs.size() == 0 と xs.isEmpty() のどちらが読みやすいかは好みかもしれませんが、コードには「何をしたいか」を書くのが良いです。なので「サイズが0か」のか「空か」のどちらに興味があるかによって書き分けるべきです。
「サイズが0かどうか」に興味があることは少ないと思うので、だいたいisEmptyを使うことになると思います。

（追記）名前で気づけ

@irof あー、JavaのLinkedListはC++みたいにspliceできないので、サイズ持ってても平気なんですよね。俺はコンスセル的なリストを思い浮かべてて、その場合はやはりサイズ持てないのでO(N)になっちゃいます

2012-09-07 00:17:22 via Tween to @irof

コンスセルってのは x:xs みたいなのと認識してる。xsは単純にxの複数形と捉えるのがわかり良いと思います。0以上って感じで0も含む複数形です。正規表現で書くとx*みたいな。余計わかり辛いか。とにかく要素が一個しかなくても x:xs で表現できます。たぶん嘘ついてるんで、真面目な人はググってください。
Haskellとかでリスト xs は、とりあえず x:xs にして x をアレして、残った xs をまた x:xs にして……と、 xs が空っぽになるまでやったりするっぽいです。
で、元ツイートでは親切にも xs と書いてくれてるので、最初からJavaなリストの話はしてません。してないんです。たぶん。Javaでリストに xs なんて名前つけませんしね。そういうの知らない過去の私のような人に向けてのエントリです。って言い張っとく。