如何检查两个列表在Python中是否循环相同
例如,我有以下列表:
a[0] = [1, 1, 1, 0, 0]a[1] = [1, 1, 0, 0, 1]
a[2] = [0, 1, 1, 1, 0]
# and so on
它们似乎不同,但是如果假定起点和终点相连,则它们在 循环上是 相同的。
问题是,我拥有的每个列表的长度为55,并且仅包含三个1和52个零。如果没有循环条件,则有26,235(55选择3)个列表。但是,如果存在条件“循环”,则存在大量循环相同的列表
目前,我通过以下方式循环检查身份:
def is_dup(a, b): for i in range(len(a)):
if a == list(numpy.roll(b, i)): # shift b circularly by i
return True
return False
在最坏的情况下,此功能需要55次循环移位操作。并且有26,235个列表可以相互比较。简而言之,我需要55 * 26,235 *(26,235-1)/ 2 =
18,926,847,225个计算。大约有20 Giga!
有什么好方法可以减少计算量吗?还是支持 循环的 任何数据类型?
回答:
首先,这可以根据O(n)
列表的长度来完成。您会注意到,如果将列表重复2次([1, 2, 3]
),[1, 2, 3, 1, 2,
3]则新列表肯定会包含所有可能的循环列表。
因此,您所需要做的就是检查您要搜索的列表是否在起始列表的2倍之内。在python中,您可以通过以下方式实现此功能(假设长度相同)。
list1 = [1, 1, 1, 0, 0]list2 = [1, 1, 0, 0, 1]
print ' '.join(map(str, list2)) in ' '.join(map(str, list1 * 2))
关于我的oneliner的一些解释: list * 2
将列表与自身结合,map(str, [1, 2])
将所有数字转换为字符串, '
'.join()并将数组['1', '2', '111']
转换为字符串'1 2 111'
。
正如某些人在评论中指出的那样,oneliner可能会给出一些误报,因此涵盖了所有可能的极端情况:
def isCircular(arr1, arr2): if len(arr1) != len(arr2):
return False
str1 = ' '.join(map(str, arr1))
str2 = ' '.join(map(str, arr2))
if len(str1) != len(str2):
return False
return str1 in str2 + ' ' + str2
在谈到时间复杂性时,值得注意的是,O(n)
如果可以及时找到子字符串,则可以实现O(n)
。它并非总是如此,并且取决于您所用语言的实现方式(尽管可能可以例如在线性时间KMP中完成)。
对于那些害怕弦乐操作的人,由于这个事实,他们认为答案并不理想。重要的是复杂性和速度。该算法可能会在O(n)
时间和O(n)
空间上运行,这使其比O(n^2)
领域中的任何算法都要好得多。要亲自查看,可以运行一个小的基准测试(创建一个随机列表会弹出第一个元素,并将其附加到末尾,从而创建一个循环列表。您可以自由地进行自己的操作)
from random import randombigList = [int(1000 * random()) for i in xrange(10**6)]
bigList2 = bigList[:]
bigList2.append(bigList2.pop(0))
# then test how much time will it take to come up with an answer
from datetime import datetime
startTime = datetime.now()
print isCircular(bigList, bigList2)
print datetime.now() - startTime # please fill free to use timeit, but it will give similar results
在我的机器上0.3秒。不太长。现在尝试将此与O(n^2)
解决方案进行比较。在进行比较时,您可以从美国到澳大利亚旅行(很可能乘游轮旅行)
以上是 如何检查两个列表在Python中是否循环相同 的全部内容, 来源链接: utcz.com/qa/412278.html