Bruteforce 比二进制搜索需要更多时间来查找排序列表的第一个元素
Bruteforce takes more time than binary search to find the first element of a sorted list
我对 python 比较陌生,所以我对它的效率方面不是很在意,这就是为什么当我写两个算法来搜索一个元素时,我很惊讶
'''
Making an array with data that can be stored easily
Setting up pointers in data using lists
'''
import time
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] #starting / defining the array i need for the binary seach to work
process_arr = []
ctr = 0
def ARR_SEARCH(INPUT):
start = time.time()
# Have to set R and L in order to find the middle element of this
l = 0
r = len(arr)-1
mid = None
returntup = None
while r > l:
mid = (l+ (r-l))//2 # The R - L is to ensure that it is the mid
if(arr[mid] == INPUT):
end = time.time() - start
r = 0
returntup = mid, end
elif(arr[mid] > INPUT):
r = mid-1
elif(arr[mid] < INPUT):
l = mid+1
if returntup!=None:
return returntup
else:
return -1, 0
def binarySearch (arr, l, r, x):
start = time.time()
# Check base case
if r >= l:
mid = l + (r - l)//2
# If element is present at the middle itself
if arr[mid] == x:
end = time.time() - start
print("BINARY END ", end)
returntup = mid, end
return returntup
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
def BRUTE_FORCE_v2(INPUT):
start = time.time()
ctr = -1
for i in arr:
ctr += 1
if i==INPUT:
end = time.time() - start
print("BRUTE END" , end)
returntup = ctr, end
return returntup
else:
continue
else:
end = time.time() - start
returntup = -1, end
return returntup
def BRUTE_FORCE(INPUT):
start = time.time()
for i in range(len(arr)):
if arr[i]==INPUT:
end = time.time() - start
returntup = i, end
return returntup
else:
continue
else:
end = time.time() - start
returntup = -1, end
return returntup
search = int(input("Enter the required search element"))
out1 = BRUTE_FORCE(search)
out2 = binarySearch(arr, 0, (len(arr)-1), search)
out3 = BRUTE_FORCE_v2(search)
diff1 = out1[1] - out2[1]
diff2 = out1[1] - out3[1]
diff3 = out3[1] - out2[1]
print("Brute vs Force Ratio in this case is: \n \n ", diff1)
print("\n \n \n \n ")
print("The difference between the normal and the upgraded brute force algorithm in this case is: \n \n", diff2)
print("\n \n \n \n ")
print("So, the effective time differnece between the two actual algs are: \n \n ", diff3)
这个程序的输出结果如下
Enter the required search element8
BINARY END 1.430511474609375e-06
BRUTE END 2.6226043701171875e-06
Brute vs Force Ratio in this case is:
5.7220458984375e-06
The difference between the normal and the upgraded brute force algorithm in this case is:
4.5299530029296875e-06
So, the effective time differnece between the two actual algs are:
1.1920928955078125e-06
这很有道理,即使对于一个小列表,二分查找也胜过暴力破解
但是
这里有趣的是当我搜索元素“1”时
1 在列表的开头,理想情况下,bruteforce 应该首先找到它。但是二进制搜索以某种方式击败了它
当我搜索 1 时,我的输出是这样的
Enter the required search element1
BINARY END 1.430511474609375e-06
BRUTE END 2.86102294921875e-06
Brute vs Force Ratio in this case is:
5.245208740234375e-06
The difference between the normal and the upgraded brute force algorithm in this case is: 3.814697265625e-06
So, the effective time differnece between the two actual algs are:
1.430511474609375e-06
如果您想知道为什么有两种暴力破解算法,一种是 python 遍历列表的实现,一种是常规数组解析实现
我正在计算列表解析的 python 实现之间的差异,因为它看起来比其他实现更快,并找出时间之间的差异。
其实很简单,因为暴力破解只需做一次比较,所以它必须比二分查找快,但为什么不呢?
有人可以回答这个问题吗?
PS:这段代码idle玩的不好,所有结束时间都输出0.0。虽然终端似乎提供了正确的输出....
如@kaya3所述
这确实是一个时钟错误。看起来第一个结果纯属偶然,并检查它以获得更多的迭代次数,或者使用提到的库给出了所需的值。
我对 python 比较陌生,所以我对它的效率方面不是很在意,这就是为什么当我写两个算法来搜索一个元素时,我很惊讶
'''
Making an array with data that can be stored easily
Setting up pointers in data using lists
'''
import time
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] #starting / defining the array i need for the binary seach to work
process_arr = []
ctr = 0
def ARR_SEARCH(INPUT):
start = time.time()
# Have to set R and L in order to find the middle element of this
l = 0
r = len(arr)-1
mid = None
returntup = None
while r > l:
mid = (l+ (r-l))//2 # The R - L is to ensure that it is the mid
if(arr[mid] == INPUT):
end = time.time() - start
r = 0
returntup = mid, end
elif(arr[mid] > INPUT):
r = mid-1
elif(arr[mid] < INPUT):
l = mid+1
if returntup!=None:
return returntup
else:
return -1, 0
def binarySearch (arr, l, r, x):
start = time.time()
# Check base case
if r >= l:
mid = l + (r - l)//2
# If element is present at the middle itself
if arr[mid] == x:
end = time.time() - start
print("BINARY END ", end)
returntup = mid, end
return returntup
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
def BRUTE_FORCE_v2(INPUT):
start = time.time()
ctr = -1
for i in arr:
ctr += 1
if i==INPUT:
end = time.time() - start
print("BRUTE END" , end)
returntup = ctr, end
return returntup
else:
continue
else:
end = time.time() - start
returntup = -1, end
return returntup
def BRUTE_FORCE(INPUT):
start = time.time()
for i in range(len(arr)):
if arr[i]==INPUT:
end = time.time() - start
returntup = i, end
return returntup
else:
continue
else:
end = time.time() - start
returntup = -1, end
return returntup
search = int(input("Enter the required search element"))
out1 = BRUTE_FORCE(search)
out2 = binarySearch(arr, 0, (len(arr)-1), search)
out3 = BRUTE_FORCE_v2(search)
diff1 = out1[1] - out2[1]
diff2 = out1[1] - out3[1]
diff3 = out3[1] - out2[1]
print("Brute vs Force Ratio in this case is: \n \n ", diff1)
print("\n \n \n \n ")
print("The difference between the normal and the upgraded brute force algorithm in this case is: \n \n", diff2)
print("\n \n \n \n ")
print("So, the effective time differnece between the two actual algs are: \n \n ", diff3)
这个程序的输出结果如下
Enter the required search element8
BINARY END 1.430511474609375e-06
BRUTE END 2.6226043701171875e-06
Brute vs Force Ratio in this case is:
5.7220458984375e-06
The difference between the normal and the upgraded brute force algorithm in this case is:
4.5299530029296875e-06
So, the effective time differnece between the two actual algs are:
1.1920928955078125e-06
这很有道理,即使对于一个小列表,二分查找也胜过暴力破解
但是
这里有趣的是当我搜索元素“1”时
1 在列表的开头,理想情况下,bruteforce 应该首先找到它。但是二进制搜索以某种方式击败了它
当我搜索 1 时,我的输出是这样的
Enter the required search element1
BINARY END 1.430511474609375e-06
BRUTE END 2.86102294921875e-06
Brute vs Force Ratio in this case is:
5.245208740234375e-06
The difference between the normal and the upgraded brute force algorithm in this case is: 3.814697265625e-06
So, the effective time differnece between the two actual algs are:
1.430511474609375e-06
如果您想知道为什么有两种暴力破解算法,一种是 python 遍历列表的实现,一种是常规数组解析实现
我正在计算列表解析的 python 实现之间的差异,因为它看起来比其他实现更快,并找出时间之间的差异。
其实很简单,因为暴力破解只需做一次比较,所以它必须比二分查找快,但为什么不呢?
有人可以回答这个问题吗?
PS:这段代码idle玩的不好,所有结束时间都输出0.0。虽然终端似乎提供了正确的输出....
如@kaya3所述
这确实是一个时钟错误。看起来第一个结果纯属偶然,并检查它以获得更多的迭代次数,或者使用提到的库给出了所需的值。