Page List

Search on the blog

2013年9月30日月曜日

Javaのビット演算いろいろ(1)

Integerクラスにはビット演算の良質な使用例がたくさんあります。
そのうちのいくつかを簡単な解説と一緒に載せておきます。

highestOneBit
public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}
最初の5行(コメントは抜かして)で、1になっている桁より右の桁をすべて1にします。
そして最後の行で1だけ右シフトしたものを引くと、hightest one bitがえられます。

lowestOneBit
public static int lowestOneBit(int i) {
    // HD, Section 2-1
    return i & -i;
}
これは有名。プログラミング(競技プログラミング?)をやっている人なら何度も見たことがあると思います。iを「negateする=ビット反転して1を足す」なので、lowestOneBitだけが1になります。

reverse
public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}
ビット反転処理(順序の反転)です。FFTのプログラムを書くときに使うかもしれません。

これはDivide and Conquerです。
最初の3行(コメントは抜かして)は、以下のような1byte内の反転処理をしています。
次の行では、byte単位の反転を行っています。

2013年9月27日金曜日

Integer.getCharsが面白い

 JavaのIntegerクラスgetCharsメソッドがおもしろい。このメソッド自体はpackage privateなので直接呼び出すことはできないが、Integer.toStringのメイン処理が実装されている。

メソッドのシグネチャはgetChars(int i, int index, char[] buf)で整数iを表す文字列をbufに格納するというもの。このとき文字列はindexから0の方向にLSB -> MSBの順で埋められていく。
これだけ聞くと簡単そうに聞こえるが、高速化のためにおもしろい処理がされている。

とりあえず実装を載せておく。
static void getChars(int i, int index, char[] buf) {
        int q, r;
        int charPos = index;
        char sign = 0;

        if (i < 0) {
            sign = '-';
            i = -i;
        }

        // Generate two digits per iteration
        while (i >= 65536) {
            q = i / 100;
        // really: r = i - (q * 100);
            r = i - ((q << 6) + (q << 5) + (q << 2));
            i = q;
            buf [--charPos] = DigitOnes[r];
            buf [--charPos] = DigitTens[r];
        }

        // Fall thru to fast mode for smaller numbers
        // assert(i <= 65536, i);
        for (;;) {
            q = (i * 52429) >>> (16+3);
            r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
            buf [--charPos] = digits [r];
            i = q;
            if (i == 0) break;
        }
        if (sign != 0) {
            buf [--charPos] = sign;
        }
    }

まず第一段の処理としてiが65536以上の場合は2桁(10進数で)ずつ処理していく。
コメントを見ると、
r = i - ((q << 6) + (q << 5) + (q << 2))

r = i - (q * 100)
が等価であることが分かる。確かに100 = 64 + 32 + 4なのでそのとおり。DigitOnesとDigitTensはそれぞれ2桁の数字の1桁目と2桁目をO(1)で取り出すためのテーブル。これはハードコーディングされている。

まあここまでは分かる。

問題は次の第二段目の処理。

q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1));

何ですか、これは。。
何ですか、これは。∑( ̄Д ̄;)

先ほどの100倍と同じように、
r = i - ((q << 3) + (q << 1));
は、r = i - (q * 10)のこと。

ということは逆算して考えると、
q = (i * 52429) >>> (16+3);
ってのは、
q = i / 10ですか?試してみると確かにそうなっている。

でも何で52429と(16+3)なの?他の数字じゃだめなの??

ということで、いろいろ試行錯誤して「52429」が唯一使える数字ということを確認したコードが以下。
package com.kenjih.test;

public class Clazz {
    public void run() {
        // 割り算をシフト演算にしたいので、2の冪乗のみ
        for (int i = 0 ; i < 32 ; i++) {
            int x = 1<<i;
            
            // 10 * y / x == 1となるようなyが候補。
            int y = x/10;
            if (y++ == 0)
                continue;
            
            // 65535を掛けたとき0xffffffffを越えないか?
            //(シフト演算が>>>なのでCでいうところのunsigned intの範囲までなら扱える)
            if (y * 65535L > 0x0ffffffffL)
                continue;
            
            // 60009 * y - 6000 * x < xか?
            // 上式が成り立たない場合は、60009 * y % x = 6001(以上)になってしまう。
            if (x * 6001 > 60009 * y)
                System.out.println(y);
        }
    }
    
    public static void main(String[] args) {
        new Clazz().run();
    }
}
以下が実行結果。
$ 52429

まさにシフト演算のマジックやぁ~~。(ノ ̄□ ̄)ノオオオォォォォ!
コイツはしびれますね。

で結局これってほんとに速いの??
ということで高速化を考えず書いた普通の処理と比べてみる。

package com.kenjih.test;

public class MyInteger {
    private static char[] digits = {
        '0', '1', '2', '3', '4',
        '5', '6', '7', '8', '9'
    };
    
    public static String toString(int i) {
        char[] buf = new char[16];
        boolean minus = i < 0;
        int pos = 16;
        while (i > 0) {
            buf[--pos] = digits[i % 10];
            i /= 10;
        }
        if (minus)
            buf[pos] = '-';
        return new String(buf, pos, (16 - pos));
    }
}
普通に書くとまあこんなもんでしょっ。
桁数が大きい方が高速化が生きて来そうなので、1,000,000,000 - 1,100,000,000までを変換する処理も用いて比べてみた。

比較結果。
Integer = 0m4.499s
MyInteger = 0m5.681s

2割くらい速い!(微妙っ。いや、この違いは結構大きいのか?)

2013年9月25日水曜日

with replacementとwithout replacementの違い

「sample with replacement」と「sample without replacement」の違いについて。

定義
Wikipediaの説明が明瞭。
The data sample may be drawn from a population without replacement, in which case it is a subset of a population; or with replacement, in which case it is a multisubset.
multisubsetは、重複を許す部分集合のこと。

簡単な例を書いておく。
赤い玉と白い玉が袋の中に入っている。全体の何パーセントが赤い玉か調べたいが、数が多すぎてすべての玉を調べるのは不可能。そこで、n回袋から出してそのうち何個が赤い玉か調べることにした。

sample with replacementの場合:
玉を取る。色をメモる。取った玉を袋の中に戻す
玉を取る。 .... (以下繰り返し)

sample without replacementの場合:
玉を取る。色をメモる。取った玉は袋の中に戻さない
玉を取る。 .... (以下繰り返し)

そうか。この場合のreplaceの意味は「取り替える」じゃなくて、「元に戻す」か。

標本分散と不偏分散

分散と言えば、「平均値からのずれの二乗の平均」だと思っていたけど、分散には二種類あるみたい。
今まで分散と読んでいたものは、厳密には「標本分散(the biased sample variance)」と呼ばれるものだったらしい。これは英語名が表しているように標本サンプルに偏った分散だ。
この標本分散とは別に、不偏分散(the unbiased sample variance)と呼ばれる分散が存在する。統計学の世界で不偏分散の方がよく利用されるらしい。

標本分散は平均値からのずれの二乗和をnで割るのに対して、不偏分散では(n-1)で割る。はて、これは何ぞや??ということで調べてみた。

統計学では、母集団の真の分散を直接計算することは難しいため(母集団大きすぎる場合)、いくつかのデータをサンプリングして分散を計算する。標本分散はこのサンプリングされたデータの分散であって母集団の真の分散とは異なる。

では、母集団の分散を求めるにはどうするかというと、いくつかの異なるサンプリングを行ってそれらの標本分散の平均値を求めるとよい。

標本をy_1, y_2, ..., y_nとすると、この標本に対する標本分散は、σy2 = 1/n * Σ (yi - E(y))2となる。σy2は標本の取り方に依存して変化するので、実際の母集団の分散に近い値をえるためにこの値の平均値を考える。 これを計算すると、

E(σy2) =(n-1)/n * σ2

となる[1]。ここで、σ2は母集団の分散。

上の式から分かるように、標本分散(の平均値)と母集団の分散は一致しない。これを補正するために用いられるのが、不偏分散である。 不偏分散は、標本分散をn/(n-1)倍して、

s2 = n / (n-1) * σy2 = 1/(n-1) * Σ (yi - E(y))2

と表される。なるほど。これが(n-1)で割る理由か。

[1] http://en.wikipedia.org/wiki/Variance#Sample_variance

読書「Animal Farm」

George OrwellのAnimal Farmを読んだ。

牧場の動物たちが反乱を起こし、人間を排除した動物の国を作るという話。すべての動物は平等である。という信念のもと誕生した動物達の国だったが、独裁者が誕生し奴隷制度、反乱者への虐殺が始まる。そして最後には、・・・・

ラストは衝撃的でまったく予想外だった。
まさか「Four legs good, two legs better!」になるとは。

英語の小説を読破するのは人生初のような気がする。数学書やコンピュータ技術書と比べると、やはり単語が難しい。今度は1984に挑戦しようと思う。

2013年9月19日木曜日

OSS日記(3) Unit Testのソースを書いてみる

 org.apache.commons.lang3.ValidateクラスのinclusiveBetweenメソッドのテストを書いてみた。
まず、自分で書いてみたテスト。
@Test
public void testInclusiveBetween()
{
    try {
        Validate.inclusiveBetween(0, 10, -1);
        fail("An IllegalArgumentException was not thrown.");
    } catch (IllegalArgumentException e) {
        assertEquals("The value -1 is not in the specified inclusive range of 0 to 10", e.getMessage());
    }
    Validate.inclusiveBetween(0, 10, 0);
    Validate.inclusiveBetween(0, 10, 3);
    Validate.inclusiveBetween(0, 10, 10);        
    try {
        Validate.inclusiveBetween(0, 10, 11);
        fail("An IllegalArgumentException was not thrown.");
    } catch (IllegalArgumentException e) {
        assertEquals("The value 11 is not in the specified inclusive range of 0 to 10", e.getMessage());
    }
}
実際のテストコード。
@Test
public void testInclusiveBetween()
{
    Validate.inclusiveBetween("a", "c", "b");
    Validate.inclusiveBetween(0, 2, 1);
    Validate.inclusiveBetween(0, 2, 2);
    try {
        Validate.inclusiveBetween(0, 5, 6);
        fail("Expecting IllegalArgumentException");
    } catch (final IllegalArgumentException e) {
        assertEquals("The value 6 is not in the specified inclusive range of 0 to 5", e.getMessage());
    }
}

うーん、なるほど。inclusiveBetweenの内部ではcompareToを使って比較しているので数値だけじゃなくて文字列も確認しないといけないか。
区間の中にあるとき、区間の端にあるとき、区間の外にあるときの3種類でテストされているけど、始点と終点でやらなくてもいいんだろうか??経路網羅はされているからいいのだろうか。大したボリュームじゃないから書いとけばいいのにって気もする。


木 + 頂点間の距離 = LCA

データ構造が木で、問題が頂点間の距離の場合は、LCAが有効。

頂点v, w間の距離を求めたい場合は、dist(v, w) = dist(root, v) + dist(root, w) - 2 * dist(root, lca(v, w))となる。


 以下に簡単な練習問題がある。
http://poj.org/problem?id=1986

ACしたソースコード。

#include <vector>
#include <cstdio>

using namespace std;

vector<pair<int, int> > G[40000];

class LCA {
public:
    int V, logV;
    vector<int> depth, len;
    vector<vector<int> > parent;
    
    LCA(int V) {
        this->V = V;
        logV = 0;
        while (V > (1LL<<logV)) logV++;
        this->depth = vector<int>(V);
        this->len = vector<int>(V);
        this->parent = vector<vector<int> >(logV, vector<int>(V));
    }
    
    void init(int v, int par, int d, int l) {
        depth[v] = d;
        parent[0][v] = par;
        len[v] = l;
        for (int i = 0; i < (int)G[v].size(); i++) {
            int w = G[v][i].first;
            int lc = G[v][i].second;
            if (w == par) continue;
            init(w, v, d+1, lc + l);
        }
    }
    
    void build() {
        for (int k = 0; k + 1 < logV; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) parent[k+1][v] = -1;
                else parent[k+1][v] = parent[k][parent[k][v]];
            }
        }
    }
    
    int query(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        for (int k = 0; k < logV; k++) {
            if ((depth[v] - depth[u]) >> k & 1)
                v = parent[k][v];
        }
        if (u == v) return u;
        
        for (int k = logV-1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};

int main(int argc, char **argv) {
    int N, M;
    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; i++) {
        int x, y, len;
        char c;
        scanf("%d %d %d %c", &x, &y, &len, &c);
        --x, --y;
        G[x].push_back(make_pair(y, len));
        G[y].push_back(make_pair(x, len));
    }

    LCA lca(N);
    lca.init(0, -1, 0, 0);
    lca.build();

    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int x, y;
        scanf("%d %d", &x, &y);
        int z = lca.query(--x, --y);
        int ret = lca.len[x] + lca.len[y] - 2 * lca.len[z];
        printf("%d\n", ret);
    }

    return 0;
}

2013年9月16日月曜日

To Mock a Mockingbird(5)

To Mock a MockingbirdのChapter 5、6を読んだ。面白かった問題を1つ載せておきます。

(問題)
ある日私は社会学者に会いました。彼は私に次のような研究成果を教えてくれました。

「私はこの島のすべての原住民たちにインタビューをした。
その結果私はおもしろい事実を発見した。
すべての原住民Xに対して、『XとYは、どちらもならず者だ』と主張する原住民Yが少なくとも1人は存在する。」

彼の研究報告は論理的に考えて正しいでしょうか?

(前提)
すべての原住民は、騎士とならず者のいずれかです。
騎士は本当のことしか言いません。ならず者は嘘しか言いません。

2013年9月15日日曜日

Stringインスタンスの共有

 JavaのStringインスタンスの共有についていまいち理解していなかったので、JLSを読んでみた。
まず、JLSに書いているサンプルプログラムを動かしてみる。

[Test.java]
package testPackage;

class Test {
    public static void main(String[] args) {
        String hello = "Hello", lo = "lo";
        System.out.println(hello == "Hello");
        System.out.println(Other.hello == hello);
        System.out.println(other.Other.hello == hello);
        System.out.println(hello == ("Hel" + "lo"));
        System.out.println(hello == ("Hel" + lo));
        System.out.println(hello == ("Hel" + lo).intern());
    }
}

class Other {
    static String hello = "Hello";
}

[Other.java]
package other;

public class Other {
    public static String hello = "Hello";
}
上記プログラムの実行結果は以下のとおり。
$ true
$ true
$ true
$ true
$ false
$ true

ほう。これは毎回こうなるのだろうか?
JLS 3.10.5には以下のように書いている。

Literal strings within the same class in the same package represent references to the same String object.
Literal strings within different classes in the same package represent references to the same String object.
Literal strings within different classes in different packages likewise represent references to the same String object.
Strings computed by constant expressions are computed at compile time and then treated as if they were literals.
Strings computed by concatenation at run time are newly created and therefore distinct. 

まとめるとだいたい下のような感じ。
  • 文字列の内容が同じリテラルはクラス/パッケージが違っても同じインスタンスを指す。 
  • コンパイル時に計算される文字列はリテラルと同様に扱われる。
  •  実行時に結合によって生成される文字列は新しいインスタンス化されるため、別インスタンスとなる。
なるほどー。同じリテラルの場合、インスタンスも同じになるかどうかはタイミングとかによるのかなと思い込んでいたけど、常に同一インスタンスになるのか。

JLSには以下のような記述もある。
String literals-or, more generally, strings that are the values of constant expressions -are "interned" so as to share unique instances, using the method String.intern.

internすることでリテラルは同じインスタンスが共有されるらしい。上のサンプルプログラムでもconcatenateした文字列を明示的にinternすることでインスタンスが共有されている。このinternとは何ぞや? Javadocを見てみる。

Returns a canonical representation for the string object. A pool of strings, initially empty, is maintained privately by the class String. When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned. It follows that for any two strings s and t, s.intern() ==t.intern() is true if and only if s.equals(t) is true. All literal strings and string-valued constant expressions are interned. String literals are defined in section 3.10.5 of the The Java Language Specification.
なるほど、concatenateした場合は新しいインスタンスができるけど、プールの中を検索してequalsでヒットしたらそのインスタンスが返されるってことか。

OSS日記(2) HashMapで最頻値を計算するときはIntegerよりMutableIntの方がいい

org.apache.commons.lang3.ObjectUtils#modeのソースを読んでいたら、MutableIntという見慣れないクラスが使われていた。このクラスもCommons Langが提供しているものらしい。
int型のラッパークラスIntegerはimmutableなので、副作用を伴う使い方をしたい場合はMutableIntを使った方がいいということだろうか。確かにそっちの方が速そうだ。

ということで実験してみた。

ソースコード
あるデータ集合内に現れるデータの頻度を数えるような簡単なサンプルを書いて比較。 まず普通のIntegerを使った場合。
package com.kenjih.test;

import java.util.HashMap;
import java.util.Map;

public class Clazz {
    public void run() {
        final String[] names = { "Alice", "Bob", "Carol", "Dave" };

        Map<String, Integer> frequence = new HashMap<String, Integer>();
        for (int i = 0; i < 100000000; i++) {
            String name = names[i % 4];
            if (!frequence.containsKey(name))
                frequence.put(name, 0);
            int cnt = frequence.get(name);
            frequence.put(name, ++cnt);
        }

        System.out.println(frequence);
    }

    public static void main(String[] args) {
        new Clazz().run();
    }
}

次にMutableIntを使った場合。
package com.kenjih.test;

import java.util.HashMap;
import java.util.Map;

import org.apache.commons.lang3.mutable.MutableInt;

public class Clazz {
    public void run() {
        final String[] names = { "Alice", "Bob", "Carol", "Dave" };

        Map<String, MutableInt> frequence = new HashMap<String, MutableInt>();
        for (int i = 0; i < 100000000; i++) {
            String name = names[i % 4];
            if (!frequence.containsKey(name))
                frequence.put(name, new MutableInt());
            frequence.get(name).increment();
        }

        System.out.println(frequence);
    }

    public static void main(String[] args) {
        new Clazz().run();
    }
}

比較結果
[比較環境]
CPU: Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz(4コア)
メモリ: 4GB

 [コンパイル/実行コマンド]
$ javac -cp ${HOME}/bin/commons-lang3-3.1/commons-lang3-3.1.jar -d bin src/com/kenjih/test/Clazz.java
$ time java -cp bin:${HOME}/bin/commons-lang3-3.1/commons-lang3-3.1.jar com.kenjih.test.Clazz

 [比較結果]
# valueの型がIntegerの場合
real 0m2.204s
user 0m2.156s
sys 0m0.100s

# valueの型がMutableIntの場合
real 0m1.339s
user 0m1.356s
sys 0m0.004s

OSS日記(1) Commons Langの開発環境を作る



 Apache CommonsのCommons Langの開発環境をローカルマシン上で整えてみました。いくつかハマったところがあったのでメモを残しておきます。

1. EclipseからSVNを使えるようにする
1-1) 以下の2つのプラグインをインストール
  • Subversive Plug-In
  • SVN Connectors

2. SVNレポジトリをプロジェクトに取り込む
2-1) Window -> Open Perspective -> Java でJavaパースペクティブを開く
2-2) Pakage Explorerビューで右クリック -> New -> Other -> Project from SVNを選択する -> Next
2-3) URLに「http://svn.apache.org/repos/asf/commons/proper/lang/trunk」と入力
-> Advancedタブを選択し、Enable Structure Detectionをオフにする。 -> Next -> Finish
2-4) Check out as a project configured using the New Project Wizardを選択し
Finish
2-5) プロジェクト作成ウィザードが自動で立ち上がるので設定する
Java Projectを選択 -> Next
2-6) Project name: に「Commons-Lang」と入力 -> Finish
2-7) パスワードの設定
Secure Storageウィンドウが立ち上がる。適当にパスワードを設定する。

3. ビルドパスの設定
SVNから取り込んだだけだとEclipse上でビルドパスが正しく設定されないため、手動で設定が必要。
3-1) Package Explorer内の「Commons-Lang」プロジェクトを右クリック -> Properties -> Java Build Pathを選択 -> Sourceタブ
3-2) デフォルトで設定されているCommons-Lang/srcをRemove
3-3) Add Folder -> src/main/javaにチェック -> OK
3-4) Add Folder -> src/test/javaにチェック -> OK
3-5) OKを押してProperties for Commons-Langウィンドウを閉じる

4. 依存ライブラリのインポート
プロジェクト内でjunit, commons-ioなどが使用されているため、これらの外部ライブラリをインポートします。
pom.xmlが同梱されているので、Mavenを使って設定します。
4-1) Package Explorer内の「Commons-Lang」プロジェクトを右クリック -> Configure -> Convert to Maven Project

これだけ。Maven神だよっ!

5. Antの設定
5-1) /Commons-Lang/build.properties.sampleファイルをコピペして、/Commons-Lang/build.propertiesを作成
5-2) Ant関連ファイルを修正(REV 1523209の断面ではMavenで入れたバージョンと差異がある箇所や設定漏れがあるため)

■build.properties
repository=${user.home}/.m2/repository
junit.home=${repository}/junit/junit/4.11/ # 4.10を4.11に修正
easymock.home=${repository}/org/easymock/easymock/3.1/
commons-io.home=${repository}/commons-io/commons-io/2.4/
hamcrest.home=${repository}/org/hamcrest/hamcrest-core/1.3/ # 追記

■default.properties
repository=${user.home}/.m2/repository
# The location of the "junit.jar" JAR file
junit.jar = ${junit.home}/junit-4.11.jar # 4.10を4.11に修正

# The location of the Easymock jar
easymock.jar = ${easymock.home}/easymock-3.1.jar

# The location of the Commons-IO jar
commons-io.jar = ${commons-io.home}/commons-io-2.4.jar

# The location of the hamcrest Jar
hamcrest.jar = ${hamcrest.home}/hamcrest-core-1.3.jar # 追記

■build.xml
repository=${user.home}/.m2/repository
<!-- ========== Construct unit test classpath ============================= -->
<path id="test.classpath">
    <pathelement location="${build.home}/classes"/>
    <pathelement location="${build.home}/tests"/>
    <pathelement location="${junit.jar}"/>
    <pathelement location="${easymock.jar}"/>
    <pathelement location="${commons-io.jar}"/>
    <pathelement location="${hamcrest.jar}"/>   <!-- 追記 -->
</path>

6. ビルド&テスト実行
ようやく設定完了。試しにビルド&テストしてみます。
6-1)ビルド実行
build.xmlを選択 -> Outlineビュー -> compileを選択し右クリック -> Run As Ant Build

6-2)テスト実行
build.xmlを選択 -> Outlineビュー -> testを選択し右クリック -> Run As Ant Build

来たーーーーーーーーっ!

2013年9月14日土曜日

Javaのコンストラクタについて

 Javaのコンストラクタについて理解が曖昧だったのでまとめてみました。

デフォルトコンストラクタについて
Blochの『Effective Java』に以下の記述があります[1]。

In the absence of explicit constructors, however, the compiler provides a public parameterless default constructor.
(和訳: 明示的にコンストラクタを定義しなければ、パラメータ無しのpublicなデフォルトコンストラクタがコンパイラによって作られる。)

以下の場合は明示的に定義はしていませんが、Clazz()が呼ばれることになります。
package com.kenjih.test;

public class Clazz {
    public static void main(String[] args) {
        new Clazz();
    }
}

ここで昔ちょっとはまったのがこれです。上のソースを拡張してパラメータ付きのコンストラクタを追追加してみます。
package com.kenjih.test;

public class Clazz {
    public Clazz(Object param) {
        // do something
    }
    
    public static void main(String[] args) {
        new Clazz("hoge");
        new Clazz();
    }
}
これだとnew Clazz(); のところでコンパイルエラーになってしまいます。明示的にコンストラクタを定義した結果、コンパイラがデフォルトコンストラクタを生成しなくなったためです。以下のように書くとコンパイルエラーは無くなります。
package com.kenjih.test;

public class Clazz {
    public Clazz() {}
 
    public Clazz(Object param) {
        // do something
    }
    
    public static void main(String[] args) {
        new Clazz("hoge");
        new Clazz();
    }
}
「デフォルトコンストラクタが提供されるのは、コンストラクタを1つも定義しなかった場合のみ」ということに注意が必要です。


拡張クラスのコンストラクタについて
同じくBlochの『Effective Java』に以下の記述があります[1]。

All constructors must invoke a superclass constructor, explicitly or implicitly.
(和訳: すべてのコンストラクタはスーパークラスのコンストラクタを、明示的にもしくは暗黙のうちに、呼び出さなければならない。)
明示的に/暗黙のうちにの条件がよく分からなかったので簡単なサンプルソースを書いて調べてみました。
package com.kenjih.test;

public class Par {
    public Par() {
        System.out.println("Par() was invoked.");        
    }
    
    public static void main(String[] args) {
        new Chi();
    }
}

class Chi extends Par {
    public Chi() {
        System.out.println("Chi() was invoked.");
    }
}
実行結果は以下のとおりです。
$ Par() was invoked.
$ Chi() was invoked.
Chiクラスのコンストラクタを呼んだ際に、親クラスであるParのコンストラクタが暗黙のうちに呼ばれています。
親クラスに複数のコンストラクタが存在した場合はどうなるでしょうか?
package com.kenjih.test;

public class Par {
    public Par() {
        System.out.println("Par() was invoked.");        
    }
    
    public Par(Object param) {
        System.out.println("Par(Object) was invoked.");       
    }
    
    public static void main(String[] args) {
        new Chi();
    }
}

class Chi extends Par {
    public Chi() {
        System.out.println("Chi() was invoked.");
    }
}
結果は先ほどと同様です。
$ Par() was invoked.
$ Chi() was invoked.
ということは、「親クラスのコンストラクタを明示的に呼び出さなかった場合は、親クラスのパラメータ無しコンストラクタが暗黙のうちに呼ばれる。」と考えればよさそうです。一応調べてみましたが上記の理解で正しそうです[2]。

If you are satisfied with the default constructor in the superclass, there is no need to make a call to it because it will be supplied automatically.

ということは、以下のようなコードを書くとコンパイルエラーになるということですかね?
package com.kenjih.test;

public class Par {
    public Par(Object param) {
        System.out.println("Par(Object) was invoked.");       
    }
    
    public static void main(String[] args) {
        new Chi();
    }
}

class Chi extends Par {
    public Chi() {
        System.out.println("Chi() was invoked.");
    }
}
予想どおりエラー(Implicit super constructor Par() is undefined. Must explicitly invoke another constructor)になりました。

参考
[1] Effective Java

[2] http://www.leepoint.net/notes-java/oop/constructors/constructor.html