ある２つの数字の間の数を取り出すには？
プログラムをやる人なら、大小比較を利用しない人はまずいない。
そのなかで、「値$c$が$a$と$b$の間にあるか？」を判定するのはよくやることだ。
この、$a$と$b$の大小関係が不明なとき、上問題をどうやって解いているだろうか？
手法1
一番脳筋な方法は、まず$a$と$b$の大小関係を把握してから、$c$と比較するというやり方だ。
if a < b:
a < c < b
else:
b < c < a
うーん、あまり美しくない。こんなことに4行も使いたくないなぁ…。
手法2
上記を見ると、$b < c < a$か$a < c < b$どちらかが成り立てば$c$は$a$と$b$の間にあるということがわかる。
つまり、次のようにかけば一行に収まる。
(a < c < b) or (b < c < a)
良くなってきた。
ただ、これも$a,b,c$が一回ずつ出てきてるし、少し冗長に感じる。
pythonだとこんなにきれいに書けるが、C言語だと次のように書かないといけない。
((a < c) && (c < b)) || ((b < c) && (c < a))
やっぱり、美しくない……。
手法3
ということで、筆者は次のように書く方法を思いついた。
(a < c) ^ (b < c)
^はあまり使わないかもしれないが、排他的論理和である。
どっちもTrue、どっちもFalseのときにFalseになり、２つがTrueとFalseならTrueになる。
ただし、これには欠点がある。
上式は以下と同義である。
(a < c <= b) or (b < c <= a)
これは、<を>にしたり、<=にしたりしてもa < c < bのようにすることができない。
ちなみに、
(a <= c) ^ (b <= c)
(a > c) ^ (b > c)
のふたつは
(a <= c < b) or (b <= c < a)
と同義である
手法4
なんとかして、a < c < bやa <= c <= bをできないかなぁって思い、考えてみたのだが、以下のやり方が一番エレガントかもしれない。
(a - c) * (b - c) < 0
(a - c) * (b - c) <= 0
一行目がa < c < bであり、二行目がa <= c <= bである。
値が大きいなら符号関数をとっても良いかも(といっても、計算時間はかなり遅くなりそう)。
計算時間
各手法の計算時間を計測してみた。
プログラムは以下のようなものを利用した。
import time
import numpy as np
n = 100
number1 = np.random.rand(n)
number2 = np.random.rand(n)
t1 = time.time()
for j in range(10000):
for i in range(n):
if number1[i] < number2[i]:
x = number1[i] < 0.5 < number2[i]
else:
x = number1[i] < 0.5 < number2[i]
t2 = time.time()
t = t2-t1
print(t)
t1 = time.time()
for j in range(10000):
for i in range(n):
x = (number1[i] < 0.5 < number2[i]) or (number1[i] < 0.5 < number2[i])
t2 = time.time()
t = t2-t1
print(t)
t1 = time.time()
for j in range(10000):
for i in range(n):
x = (number1[i] < 0.5) ^ (number2[i] < 0.5)
t2 = time.time()
t = t2-t1
print(t)
t1 = time.time()
for j in range(10000):
for i in range(n):
x = (number1[i] - 0.5) * (number2[i] - 0.5) < 0
t2 = time.time()
t = t2-t1
print(t)
計算結果
| 手法 | 計算時間 |
|---|---|
| 手法1 | 0.547s |
| 手法2 | 0.458s |
| 手法3 | 0.370s |
| 手法4 | 0.786s |
……。
(a - c) * (b - c) < 0が最も遅い結果となってしまった。
手法1よりも遅いとは…。美しいだけじゃだめなのか…。
何度か試してみたが、順位は変わらなかった。
うーん、やっぱり掛け算が時間かかるみたいだ。また、andやorは途中でFalse, Trueが出た時点でそれ以降の演算を無視するという特性があるからというのもある。
これだけだと悔しいので、numpyの配列全体での計算でも調べてみた。
import time
import numpy as np
n = 100
number1 = np.random.rand(n)
number2 = np.random.rand(n)
t1 = time.time()
for j in range(10000):
x = ((number1 < 0.5) & ( 0.5 < number2)) | ((number1 < 0.5) & (0.5 < number2))
t2 = time.time()
t = t2-t1
print(t)
t1 = time.time()
for j in range(10000):
x = (number1 < 0.5) ^ (number2 < 0.5)
t2 = time.time()
t = t2-t1
print(t)
t1 = time.time()
for j in range(10000):
x = ((number1 - 0.5) * (number2 < 0.5) < 0)
t2 = time.time()
t = t2-t1
print(t)
numpyでは a < c < bのような書き方はできない。また、and, orもないため、論理演算&や|を利用する必要がある。
計算時間は次のようになる。
| 手法 | 計算時間 |
|---|---|
| 手法2 | 0.037s |
| 手法3 | 0.017s |
| 手法4 | 0.031s |
この場合は、掛け算のほうが早いという結果になった。
なんとか面目保たれた……。
まとめ
cがaとbの間にあるかどうかの判定は次の式を使おう。
１つずつの比較の場合
## a < c < b or b < c < a の場合
a < c < b or b < c < a
## a ≦ c ≦ b or b ≦ c ≦ a の場合
a <= c <= b or b <= c <= a
## a < c ≦ b or b < c ≦ a の場合
(a < c) ^ (b < c)
## a ≦ c < b or b ≦ c < a の場合
(a > c) ^ (b > c)
numpy配列の場合
## a < c < b or b < c < a の場合
(a - c) * (b - c) < 0
## a ≦ c ≦ b or b ≦ c ≦ a の場合
(a - c) * (b - c) <= 0
## a < c ≦ b or b < c ≦ a の場合
(a < c) ^ (b < c)
## a ≦ c < b or b ≦ c < a の場合
(a > c) ^ (b > c)