我有这样一个(python)列表 my_list = [['狗','猫','垫子','好玩'],['鲍勃','猫','平底锅','好玩'],['狗','本','垫子','老鼠'],['猫', '垫子','好玩','狗'],['垫子','好玩','狗','猫'],['好玩','狗','猫','垫子'],['老鼠','狗','本','垫子'],['狗','垫子','猫','好玩'],。 .. ]
my_list有200704个元素
注意这里 my_list[0] = ['dog','cat','mat','fun'] dog->cat->mat->fun->dog my_list[3] = ['cat','mat','fun','dog'] cat->mat->fun->dog-> cat my_list[4] = ['mat','fun','dog','cat'] mat->fun->dog->cat->mat my_list[5] = ['fun','dog','cat','mat'] fun->dog->cat->mat->fun 循环往复,它们都是一样的。所以它们应该被标记为重复的。 注意:my_list[0] = ['dog','cat','mat','fun'] my_list[7] = ['dog','mat','cat','fun'] 这些不应该被标记为重复,因为循环往复,它们是不同的。 同理,my_list[2] = ['狗','本','垫子','老鼠'] my_list[6] = ['老鼠','狗','本','垫子'] 它们应该标记为重复。
def remove_circular_duplicates(my_list):
# the quicker and more elegent logic here
# the function should identify that my_list[0], my_list[3], my_list[4] and my_list[5] are circular duplicates
# keep only my_list[0] and delete the rest 3
# same for my_list[2] and my_list[6] and so on
return (my_list_with_no_circular_duplicates)
---------------------------------------------------------------- 我的尝试。 ---------------------------------------------------------------- 我的尝试: 而且其方式也不优雅。(请原谅我的水平)
t=my_list
tLen=len(t)
while i<tLen:
c=c+1
if c>2000:
# this is just to keep you informed of the progress
print(f'{i} of {tLen} finished ..')
c=0
if (finalT[i][4]=='unmarked'):
# make 0-1-2-3 -> 1-2-3-0 and check any duplicates
x0,x1,x2,x3 = t[i][1],t[i][2],t[i][3],t[i][0]
# make 0-1-2-3 -> 2-3-0-1 and check any duplicates
y0,y1,y2,y3 = t[i][2],t[i][3],t[i][0],t[i][1]
# make 0-1-2-3 -> 3-0-1-2 and check any duplicates
z0,z1,z2,z3 = t[i][3],t[i][0],t[i][1],t[i][2]
while j<tLen:
if (finalT[j][4]=='unmarked' and j!=i):
#j!=i skips checking the same (self) element
tString=t[j][0]+t[j][1]+t[j][2]+t[j][3]
if (x0+x1+x2+x3 == tString) or (y0+y1+y2+y3 == tString) or (z0+z1+z2+z3 == tString):
# duplicate found, mark it as 'duplicate'
finalT[j][4]='duplicate'
tString=''
j=j+1
finalT[i][4] = 'original'
j=0
i=i+1
# make list of only those marked as 'original'
i=0
ultimateT = []
while i<tLen:
if finalT[i][4] == 'original':
ultimateT.append(finalT[i])
i=i+1
# strip the 'oritinal' mark and keep only the quad
i=0
ultimateTLen=len(ultimateT)
while i<ultimateTLen:
ultimateT[i].remove('original')
i=i+1
my_list_with_no_curcular_duplicates = ultimateT
print (f'\n\nDONE!! \nStarted at: {start_time}\nEnded at {datetime.datetime.now()}')
return my_list_with_no_circular_duplicates
我想要的是一种更快捷的方法。 Tnx in advance.
你的实现是n次方算法,这意味着对于一个大数据集,实现时间会急剧增长。20万平方是一个非常大的数字。你需要将其转换为n阶或n-log(n)算法。 要做到这一点,你需要对数据进行预处理,这样你就可以检查循环等价的项目是否也在列表中,而不必在列表中搜索。要做到这一点,将每个条目放到一个可以比较的形式中,而不需要在列表中迭代。我建议你旋转每个条目,使它的字母顺序第一的项目先出现。 例如将['狗','猫','垫子','好玩']改为['猫','垫子','好玩','狗']。这就是一个顺序n的操作,把列表中的每个元素处理一次。
然后,由于它们都有一个共同的格式,你有几种选择来确定每个条目是否是唯一的。我会使用一个集合。对于每一个项目,检查该项目是否在一个集合中,如果不在,它是唯一的,应该被添加到集合中。如果项目已经在集合中,那么已经找到了一个等价的项目,可以删除这个项目。检查一个项目是否在集合中是Python中的一个恒时操作。它通过使用一个哈希表来索引找到一个项目,而不是需要搜索。结果是这也是一个阶数n的操作,通过每个条目做检查。总的来说,这个算法是阶数n的,会比你之前做的事情要快很多。
@BradBudlong Brad Budlong的回答是对的。以下是相同的实现结果。
我的方法(问题中给出)。 耗时: ~结果: len(my_list_without_circular_duplicates) >> 50176 Brad Budlong的方法: 所用时间:~12秒(太棒了!)。~结果: len(my_list_without_circular_duplicates) >> 50176 以下是Brad Budlong方法的实现。
# extract all individual words like 'cat', 'rat', 'fun' and put in a list without duplicates
all_non_duplicate_words_from_my_list = {.. the appropriate code here}
# and sort them alphabetically
alphabetically_sorted_words = sorted(all_non_duplicate_words_from_my_list)
# mark all as 'unsorted'
all_q_marked=[]
for i in my_list:
all_q_marked.append([i,'unsorted'])
# format my_list- in Brad's words,
# rotate each entry so that it has the alphabetically first item first.
# For example change ['dog','cat','mat','fun'] to ['cat','mat','fun','dog']
for w in alphabetically_sorted_words:
print(f'{w} in progress ..')
for q in all_q_marked:
if q[1]=='unsorted':
# check if the word exist in the quad
if w in q[0]:
# word exist, then rotate this quad to put that word in first place
# rotation_count=q[0].index(w) -- alternate method lines
quad=q[0]
for j in range(4):
quad=quad[-1:] + quad[:-1]
if quad[0]==w:
q[0]=quad
break
# mark as sorted
q[1]='sorted'
# strip the 'sorted' mark and keep only the quad
i=0
formatted_my_list=[]
while i<len(all_q_marked):
formatted_my_list.append(all_q_marked[i][0])
i=i+1
# finally remove duplicate lists in the list
my_list_without_circular_duplicates = [list(t) for t in set(tuple(element) for element in formatted_my_list)]
print (my_list_without_circular_duplicates)
请注意,虽然它在处理按字母顺序排序的单词(201)时,仍然会对整个all_q_marked(200704)进行迭代和处理,但随着all_q_marked中的元素被标记为 "排序",处理所需的时间会成倍减少。