快速消除大名单中的"circular duplicates"(python)

Question

我有这个 (python) 列表

my_list = [['dog','cat','mat','fun'],['bob','cat','pan','fun'],['dog','ben','mat','rat'],
['cat','mat','fun','dog'],['mat','fun','dog','cat' ],['fun','dog','cat','mat'],
['rat','dog','ben','mat'],['dog','mat','cat','fun' ], ...
]

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']
垫子->乐趣->狗->猫->垫子
my_list[5] = ['fun','dog','cat','mat']
乐趣->狗->猫->垫子->乐趣
循环往复，它们都是一样的。所以他们应该被标记为重复。

注：
my_list[0] = ['dog','cat','mat','fun']
my_list[7] = ['dog','mat','cat','fun']
这些不应该被标记为重复，因为它们是循环的，它们是不同的。

同样，
my_list[2] = ['dog','ben','mat','rat']
my_list[6] = ['rat','dog','ben','mat']
它们应该被标记为重复。

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)

-------------------------------------------- ------------------
我的尝试：
---------------------------------------------- --------------
这可行，但是需要 3 个多小时才能完成 200704 个元素。
而且这也不是一种优雅的方式..（请原谅我的水平）

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.

Answer 1

您的实施是一个 n 平方算法，这意味着对于大型数据集，实施时间将急剧增加。 200,000 的平方是一个非常大的数字。您需要将其转换为 n 阶或 n-log(n) 算法。为此，您需要对数据进行预处理，以便您可以检查循环等效项是否也在列表中，而无需搜索整个列表。要做到这一点，请将每个条目放入一个可以比较它们的表格，而无需遍历列表。我建议您旋转每个条目，以便它首先具有按字母顺序排列的第一项。例如，将 ['dog'、'cat'、'mat'、'fun'] 更改为 ['cat'、'mat'、'fun'、'dog']。即n次操作，对list的每个元素处理一次。

然后将它们全部采用通用格式，您可以通过多种选择来确定每个条目是否唯一。我会用一套。对于每个项目，检查该项目是否在集合中，如果不在，则它是唯一的，应该添加到集合中。如果该项目已经在集合中，则已经找到了等效项目并且可以删除该项目。检查一个项目是否在集合中是 Python 中的常数时间操作。它通过使用哈希 table 来索引以查找项目而不是需要搜索来实现这一点。结果是这也是一个 order n 操作，用于检查每个条目。总的来说，该算法是 n 阶的，并且会比您正在做的快得多。

Answer 2

@BradBudlong
Brad Budlong 的回答是正确的。下面是同样的执行结果。

我的方法（问题中给出）：
耗时：~274 分钟
结果：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)

注意这里，虽然它迭代和处理 alphabetically_sorted_words (201) 仍然是整个 all_q_marked (200704)，处理时间随着 all_q_marked 中元素的获取呈指数级减少标记为 'sorted'.

快速消除大名单中的"circular duplicates"(python)

Quickly eliminate "circular duplicates" in a big list (python)

python

logic

list

circular-dependency

duplicates