범위탐색 알고리즘(Range Algorithm, 구간탐색 알고리즘)

<정렬되지 않은 실수들로 이루어진 리스트를 특정 구간별로 나누기>

 

이진탐색 알고리즘(Binary Search Alalgorithm)을 응용하였다.

분명히 필요한 기능인데 불구하고 파이썬에서 지원하지 않는다.

도저히 선형탐색으로는 불가능할 정도의 데이터 양이다. (무려 240해..)

 

범위탐색 알고리즘에 대해 구글링 해보았으나 존재하지 않아, 직접 만들었고

혹시 프로젝트에 필요한 사람이 있을까하고 블로그에 올린다.

부디 나처럼 몇시간을 허비하지 않고 프로젝트의 핵심에 더 신경쓸 수 있기를 바란다.

def binary_range_search(data, slices, cycle = False): 
	"""USAGE 
	BASE : data = 구간탐색대상(리스트)
	1. cycle=True : slices = [minimum,maximum,range]
	2. cycle=False : slices = [구간]
	단, slices에 데이터의 최소값보다 작은 값, 데이터의 최댓값 보다 큰 값이 있어야 함.
	RETURN : 순차정렬된 탐색대상의 구간별 끝값이 있는 인덱스로 이루어진 리스트
	"""
	data.sort()
	if cycle == True:
		slices = [k for k in range(slices[0], (slices[1] - (slices[1] % slices[2])+slices[2]+1), slices[2])]
	seperated_list = []
	for target in slices:
		start = 0 
		end = len(data) - 1
		while True:
			mid = (start + end) // 2
			if data[mid] > target:
				if mid-1 == -1 :
					seperated_list.append(0)
					break
				elif data[mid-1] < target:
					seperated_list.append(mid-1)
					break
				else:
					end = mid - 1
			elif data[mid] < target:
				if mid+1 > len(data)-1:
					seperated_list.append(len(data)-1)
					break
				elif data[mid+1] > target:
					seperated_list.append(mid)
					break
				else:
					start = mid + 1
			elif data[mid] == target:
				k = mid
				while (data[mid + 1] if mid + 1 < len(data) else 'Python') == data[k]:
					mid += 1
				seperated_list.append(mid)
				break
	return seperated_list

추가적으로 해당 구간에 해당하는 리스트원소의 개수를 알고 싶다면 다음 함수를 사용하기 바란다.

def add_range_data(data, slices, cycle = False):
  sep = binary_range_search(data , slices, cycle)
  res = []
  for i in range(len(sep)):
    res.append(sep[i+1]-(-1 if sep[i] ==0 else sep[i])) if len(sep) != i+1 else None
  return res

---

예시

binary_range_search(data, slices, cycle = False)

data_list = [1.2, 1.5, 1.8, 4, 4.2, 6.5, 10, 10.5, 11, 11.5, 12.5, 13.8, 14.3, 14.9]
slices = [0,3,6,9,12,15]
print(binary_range_search(data_list,slices))

##출력 : [0, 2, 4, 5, 9, 13]

binary_range_search(data, slices, cycle = True)

data = [38, 80, 100, 84, 45, 19, 1, 16, 99, 81, 5, 63, 74, 70, 51, 7, 50, 17, 57, 88, 49, 37, 25, 81, 25, 30, 81, 86, 11, 95, 90, 57, 44, 53, 82, 37, 68, 95, 46, 8, 93, 84, 40, 53, 4
7, 61, 13, 54, 39, 36, 91, 5, 88, 16, 13, 65, 69, 80, 79, 30, 56, 30, 85, 4, 88, 20, 46, 62, 73, 26, 32, 3, 39, 42, 11, 92, 43, 40, 23, 27, 66, 16, 25, 85, 43, 10, 47, 77, 85,
 31, 80, 58, 29, 93, 81, 58, 50, 17, 19, 71]
MAXNUMBER = 100

print(binary_range_search(data, [0,MAXNUMBER,30], cycle = True))

#출력 [0, 29, 60, 91, 99]

add_range_data(slices, data)

data_list = [1.2, 1.5, 1.8, 4, 4.2, 6.5, 10, 10.5, 11, 11.5, 12.5, 13.8, 14.3, 14.9]
slices = [0,3,6,9,12,15]
print(add_range_data(data_list, slices))

#출력 : [3, 2, 1, 4, 4]

 

---

속도비교

data = []
MAXNUMBER = 100000
for i in range(100000):
  data.append(random.randint(1,MAXNUMBER))

#이진탐색(binary_range_search)
st = time.time()
res1 = add_range_data(data, [0,MAXNUMBER,30], cycle=True)
print(time.time()-st)

#단순 탐색
st = time.time()
res2 = []
rng = 30
for i in range(rng,round(MAXNUMBER),rng) :
  imgrot = i
  res2.append(len([k for k in data if (i-rng) < k and k<=i ]))
if MAXNUMBER % rng !=0:
  res2.append(len([k for k in data if imgrot<k and k<=imgrot+rng]))

print(time.time()-st)
#print(res1)
#print(res2)
print(res1 == res2)

#출력
0.15511441230773926
217.9218988418579

---

추후에, 이를 더 발전시킨 형태를 제작해볼 생각이다.

---

2021-06-24 아래와 속도비교해보자.

python - Numpy: find index of the elements within range - Stack Overflow

Numpy: find index of the elements within range