Kei Minagawa's Blog

皆川圭(@keimina)のブログ、Pythonで試したことを書いていきます

少数で表される数値の出現頻度を数えてヒストグラムを作成したいAさんの話(問題)

題名の通りの問題です。問題は以下の通りです。汚文字ですいません。

問題文では少数の最小値と最大値が-2.0と2.0で、それを8つの領域に均等に分割していますが、これは一例にしかすぎません。これら(最小値、最大値、分割数)の数字が変化しても機能するように一般化した関数を求めてほしいです。

私の解答は一番下に載せます。
関数に境界値を与えると動作が予測困難な振る舞いになりますので注意が必要です。

もっと良い方法があるよなど、コメントいただけると助かります。
10/20 追記: 一番下にライブラリを使用した簡単な方法を追し記ました。

以上。

f:id:keimina:20181017000415p:plain

解答例 (境界値に弱いので注意):

何が言いたいのかというと`index = int((v - A) / (B - A) * N)`の1行でこの関数は実装できると言うことです。
ただし、テストデータ 2 の検証を見ていただくと分かるように境界値に弱いですので、境界値が入力として来た場合の対策は別途行う必要があります。
境界値が来たら右に少しづらすとかで対処できるかもしれません,

# -*- coding:utf-8 -*-
import numpy as np

# 分割数
N = 8

# 下限
A = -2.0

# 上限
B = 2.0

# 均等に分割した数直線
linespace = np.linspace(A, B, N + 1)

# 数直線を表示

print("================ 数直線 ================")
print("\n|\n".join(linespace.astype(str)))


################################################################
# Notice: len(linespace) have to be greater than 2.
################################################################

# テストデータ 1
print("")
print("================ テストデータ1 ================")
middle_points_of_linespace = np.array([(x2 + x1)/2 for x1, x2 in zip(linespace, linespace[1:])])
print("\n|\n".join(middle_points_of_linespace.astype(str)))

# テストデータ 2 境界値のデータ(関数が境界値でどのような振る舞いをするか調べるために最後に使用する)
print("")
print("================ テストデータ2 ================")
edge_points_of_linespace = linespace[:]
print("\n|\n".join(edge_points_of_linespace.astype(str)))


# 数直線とテストデータの関係(期待値)を表示
print("")
print("================数直線と テストデータ 1 の関係================")
print("\n|\n".join("{}\n|\n(テストデータ{})".format(i, mi) for i, mi in zip(linespace, middle_points_of_linespace)))
print("|\n{}".format(linespace[-1]))

# 変換関数の処理(面倒なので関数化していない)
# テストデータを一つづつ読み込んで、プリントする
print("")
print("================ 検証 テストデータ1 ================")
for v in middle_points_of_linespace:
    # 数値をインデックスに変換する(1行で終わり)
    index = int((v - A) / (B - A) * N)
    # 以下は数値が linespace の範囲外にあった場合の対処
    if index < 0:
        print("変換先がlinespaceのインデックスの範囲外です")
    elif index > len(linespace) - 1:
        print("変換先がlinespaceのインデックスの範囲外です")
    # テストデータの値 と linespace の値の関係を プリントする
    else:
        print("{} < {} < {}".format(linespace[index], v, linespace[index+1]))


# 境界値のテストデータでテストすると予測しにくい動きとなる
print("")
print("================ 検証 テストデータ2 ================")
for v in edge_points_of_linespace:
    # 数値をインデックスに変換する(1行で終わり)
    index = int((v - A) / (B - A) * N)
    # 以下は数値が linespace の範囲外にあった場合の対処
    if index < 0:
        print("変換先がlinespaceのインデックスの範囲外です")
    elif index > len(linespace) - 2:
        print("変換先がlinespaceのインデックスの範囲外です")
    # テストデータの値 と linespace の値の関係を プリントする
    else:
        print("{} < {} < {}".format(linespace[index], v, linespace[index+1]))



出力結果:

================ 数直線 ================
-2.0
|
-1.5
|
-1.0
|
-0.5
|
0.0
|
0.5
|
1.0
|
1.5
|
2.0

================ テストデータ1 ================
-1.75
|
-1.25
|
-0.75
|
-0.25
|
0.25
|
0.75
|
1.25
|
1.75

================ テストデータ2 ================
-2.0
|
-1.5
|
-1.0
|
-0.5
|
0.0
|
0.5
|
1.0
|
1.5
|
2.0

================数直線と テストデータ 1 の関係================
-2.0
|
(テストデータ-1.75)
|
-1.5
|
(テストデータ-1.25)
|
-1.0
|
(テストデータ-0.75)
|
-0.5
|
(テストデータ-0.25)
|
0.0
|
(テストデータ0.25)
|
0.5
|
(テストデータ0.75)
|
1.0
|
(テストデータ1.25)
|
1.5
|
(テストデータ1.75)
|
2.0

================ 検証 テストデータ1 ================
-2.0 < -1.75 < -1.5
-1.5 < -1.25 < -1.0
-1.0 < -0.75 < -0.5
-0.5 < -0.25 < 0.0
0.0 < 0.25 < 0.5
0.5 < 0.75 < 1.0
1.0 < 1.25 < 1.5
1.5 < 1.75 < 2.0

================ 検証 テストデータ2 ================
-2.0 < -2.0 < -1.5
-1.5 < -1.5 < -1.0
-1.0 < -1.0 < -0.5
-0.5 < -0.5 < 0.0
0.0 < 0.0 < 0.5
0.5 < 0.5 < 1.0
1.0 < 1.0 < 1.5
1.5 < 1.5 < 2.0
変換先がlinespaceのインデックスの範囲外です


調べたところ、numpy のライブラリ np.digitize に同様の機能が実装されているようでした。
検証のコードは以下になります。
等号を「a <= b < c」にするか「a < b <= c」にするかは、キーワード引数 right を False か True に設定すると指定できるようです。
(デフォルトでは right=False)
また、範囲外のインデックスは 0 と len(linespace) - 1 のインデックスに変換されるので注意が必要です.

# -*- coding:utf-8 -*-
import numpy as np

# 分割数
N = 8

# 下限
A = -2.0

# 上限
B = 2.0

# 均等に分割した数直線
linespace = np.linspace(A, B, N + 1)

# 数直線を表示

print("================ 数直線 ================")
print("\n|\n".join(linespace.astype(str)))


################################################################
# Notice: len(linespace) have to be greater than 2.
################################################################

# テストデータ 1
print("")
print("================ テストデータ1 ================")
middle_points_of_linespace = np.array([(x2 + x1)/2 for x1, x2 in zip(linespace, linespace[1:])])
print("\n|\n".join(middle_points_of_linespace.astype(str)))

# テストデータ 2 境界値のデータ(関数が境界値でどのような振る舞いをするか調べるために最後に使用する)
print("")
print("================ テストデータ2 ================")
edge_points_of_linespace = linespace[:]
print("\n|\n".join(edge_points_of_linespace.astype(str)))


# 数直線とテストデータの関係(期待値)を表示
print("")
print("================数直線と テストデータ 1 の関係================")
print("\n|\n".join("{}\n|\n(テストデータ{})".format(i, mi) for i, mi in zip(linespace, middle_points_of_linespace)))
print("|\n{}".format(linespace[-1]))

# 変換関数の処理(面倒なので関数化していない)
# テストデータを一つづつ読み込んで、プリントする
print("")
print("================ 検証 テストデータ1 ================")
for v in middle_points_of_linespace:
    # 数値をインデックスに変換する(1行で終わり)
    index = np.digitize(v, linespace)
    print("{} <= {} < {}".format(linespace[index - 1], v, linespace[index]))

# 境界値のテストデータでテストしても問題ないことを確認できる
print("")
print("================ 検証 テストデータ2 ================")
for v in edge_points_of_linespace:
    # 数値をインデックスに変換する(1行で終わり)
    right = False # 右側の等号を有効にする場合はTrue, 左側の等号を有効にする場合は False
    index = np.digitize(v, linespace, right=right)
    # np.digitize は範囲外の値を 0 と len(linespace)-1 に変換するので注意
    # 以下は数値が linespace の範囲外にあった場合の対処
    if index < 1:
        print("{} の変換先がlinespaceのインデックスの範囲外です".format(v))
    elif index > len(linespace) - 1:
        print("{} の変換先がlinespaceのインデックスの範囲外です".format(v))
    # テストデータの値 と linespace の値の関係を プリントする
    else:
        left_eq = "=" if not right else ""
        right_eq = "=" if right else ""
        print("{} <{} {} <{} {}".format(linespace[index - 1], left_eq, v, right_eq, linespace[index]))

出力

 ================ 数直線 ================
-2.0
|
-1.5
|
-1.0
|
-0.5
|
0.0
|
0.5
|
1.0
|
1.5
|
2.0

================ テストデータ1 ================
-1.75
|
-1.25
|
-0.75
|
-0.25
|
0.25
|
0.75
|
1.25
|
1.75

================ テストデータ2 ================
-2.0
|
-1.5
|
-1.0
|
-0.5
|
0.0
|
0.5
|
1.0
|
1.5
|
2.0

================数直線と テストデータ 1 の関係================
-2.0
|
(テストデータ-1.75)
|
-1.5
|
(テストデータ-1.25)
|
-1.0
|
(テストデータ-0.75)
|
-0.5
|
(テストデータ-0.25)
|
0.0
|
(テストデータ0.25)
|
0.5
|
(テストデータ0.75)
|
1.0
|
(テストデータ1.25)
|
1.5
|
(テストデータ1.75)
|
2.0

================ 検証 テストデータ1 ================
-2.0 <= -1.75 < -1.5
-1.5 <= -1.25 < -1.0
-1.0 <= -0.75 < -0.5
-0.5 <= -0.25 < 0.0
0.0 <= 0.25 < 0.5
0.5 <= 0.75 < 1.0
1.0 <= 1.25 < 1.5
1.5 <= 1.75 < 2.0

================ 検証 テストデータ2 ================
-2.0 <= -2.0 < -1.5
-1.5 <= -1.5 < -1.0
-1.0 <= -1.0 < -0.5
-0.5 <= -0.5 < 0.0
0.0 <= 0.0 < 0.5
0.5 <= 0.5 < 1.0
1.0 <= 1.0 < 1.5
1.5 <= 1.5 < 2.0
2.0 の変換先がlinespaceのインデックスの範囲外です

なんか悔しいので timeit を使いスピードを比較してみる。

np.digitize(0, linespace)
455 ns ± 2.48 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

int((0 - A) / (B - A) * N)
179 ns ± 3.53 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

結果を見ると
ライブラリ(上): 455 ns
独自手法(下): 179 ns

独自手法は 2.5 倍くらい早い。さらに
ライブラリはバイナリサーチのようなことをやっているらしいので、データが増えるとバイナリサーチはlog関数的に時間がかかるようになるが、独自手法はデータ数に関わらずこの速度を保ち続ける。
まさに数学の勝利である。(ただし境界値の問題を除く)
そういうことなのですが、境界値の問題があるため、おとなしく np.digitize を使うようにしておきます。

以上です。