Help us understand the problem. What is going on with this article?

Tips: 3つの値の大小比較

ある2つの数字の間の数を取り出すには?

プログラムをやる人なら、大小比較を利用しない人はまずいない。
そのなかで、「値$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になり、2つが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 < ba <= 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の間にあるかどうかの判定は次の式を使おう。

1つずつの比較の場合

## 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)
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした