如何检查两个列表在Python中是否循环相同

Question

例如,我有列表:

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,并且只包含三个和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吉加!

有没有什么好方法可以用更少的计算来做到这一点？或者支持循环的任何数据类型？

Answer 1

首先,这可以根据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

PS1在谈到时间复杂度时,值得注意的是,O(n)如果能够及时找到子串,将会实现O(n).它并非总是如此,并且取决于您的语言的实现(尽管可能它可以在线性时间KMP中完成).

PS2对于害怕弦乐操作的人而言,由于这个事实认为答案并不好.复杂性和速度至关重要.该算法可能在O(n)时间和O(n)空间上运行,这使得它比O(n^2)域中的任何东西都要好得多.要自己看这个,你可以运行一个小的基准测试(创建一个随机列表弹出第一个元素并将其追加到最后,从而创建一个循环列表.你可以自由地进行自己的操作)

from random import random
bigList = [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)解决方案进行比较.在进行比较时,您可以从美国到澳大利亚(最有可能乘坐游轮)

Answer 2

在Python中没有足够的知识来满足您所要求的语言,但在C/C++中,根据您的问题的参数,我将零和1转换为位并将它们推送到uint64_t的最低有效位.这将允许您一举比较所有55位 - 1个时钟.

错误快速,整个事情将适合片上缓存(209,880字节).用于同时移动所有55个列表成员的硬件支持仅在CPU的寄存器中可用.同样比较所有55个成员也是如此.这允许将问题映射到软件解决方案.(并使用SIMD/SSE 256位寄存器,如果需要,最多256个成员)因此,代码对读者来说是显而易见的.

您可能能够在Python中实现这一点,我只是不太了解它是否可能或性能可能是什么.

在睡觉之后,一些事情变得明显,并且一切都变得更好.

1.)使用比特旋转圆形链表非常容易,Dali的非常聪明的技巧是不必要的.在64位寄存器内部,标准位移动将非常简单地完成旋转,并试图通过使用算术而不是位操作使这更加友好.

2.)使用除以2可以轻松完成位移.

3.)通过模2可以很容易地检查列表的结尾是0还是1.

4.)从尾部"移动"0到列表的头部可以通过除以2来完成.这是因为如果实际移动了零,它将使第55位为假,它已经完全没有做任何事情.

5.)从尾部"移动"1到列表的头部可以通过除以2并添加18,014,398,509,481,984来完成 - 这是通过将第55位标记为真而其余全部为假而创建的值.

6.)如果在任何给定的旋转之后锚和组合uint64_t的比较为TRUE,则中断并返回TRUE.

我会将整个列表数组转换为前面的uint64_ts数组,以避免重复进行转换.

在花了几个小时试图优化代码后,研究汇编语言我能够节省20%的运行时间.我应该补充一点,O/S和MSVC编译器也在昨天中午更新了.无论出于何种原因,C编译器生成的代码质量在更新后(2014年11月15日)都得到了显着改善.运行时间现在约为70个时钟,17纳秒组成并比较一个锚环与测试环的所有55匝,所有环的NxN与所有其他环相比在12.5秒内完成.

除了4个寄存器在99%的时间内无所事事之外,这个代码非常紧凑.汇编语言几乎与行代码匹配.非常容易阅读和理解.一个伟大的装配项目,如果有人在教自己.

硬件是Hazwell i7,MSVC 64位,完全优化.

#include "stdafx.h"
#include "stdafx.h"
#include <string>
#include <memory>
#include <stdio.h>
#include <time.h>

const uint8_t  LIST_LENGTH = 55;    // uint_8 supports full witdth of SIMD and AVX2
// max left shifts is 32, so must use right shifts to create head_bit
const uint64_t head_bit = (0x8000000000000000 >> (64 - LIST_LENGTH)); 
const uint64_t CPU_FREQ = 3840000000;   // turbo-mode clock freq of my i7 chip

const uint64_t LOOP_KNT = 688275225; // 26235^2 // 1000000000;

// ----------------------------------------------------------------------------
__inline uint8_t is_circular_identical(const uint64_t anchor_ring, uint64_t test_ring)
{
    // By trial and error, try to synch 2 circular lists by holding one constant
    //   and turning the other 0 to LIST_LENGTH positions. Return compare count.

    // Return the number of tries which aligned the circularly identical rings, 
    //  where any non-zero value is treated as a bool TRUE. Return a zero/FALSE,
    //  if all tries failed to find a sequence match. 
    // If anchor_ring and test_ring are equal to start with, return one.

    for (uint8_t i = LIST_LENGTH; i;  i--)
    {
        // This function could be made bool, returning TRUE or FALSE, but
        // as a debugging tool, knowing the try_knt that got a match is nice.
        if (anchor_ring == test_ring) {  // test all 55 list members simultaneously
            return (LIST_LENGTH +1) - i;
        }

        if (test_ring % 2) {    //  ring's tail is 1 ?
            test_ring /= 2;     //  right-shift 1 bit
            // if the ring tail was 1, set head to 1 to simulate wrapping
            test_ring += head_bit;      
        }   else    {           // ring's tail must be 0
            test_ring /= 2;     // right-shift 1 bit
            // if the ring tail was 0, doing nothing leaves head a 0
        }
    }
    // if we got here, they can't be circularly identical
    return 0;
}
// ----------------------------------------------------------------------------
    int main(void)  {
        time_t start = clock();
        uint64_t anchor, test_ring, i,  milliseconds;
        uint8_t try_knt;

        anchor = 31525197391593472; // bits 55,54,53 set true, all others false
        // Anchor right-shifted LIST_LENGTH/2 represents the average search turns
        test_ring = anchor >> (1 + (LIST_LENGTH / 2)); //  117440512; 

        printf("\n\nRunning benchmarks for %llu loops.", LOOP_KNT);
        start = clock();
        for (i = LOOP_KNT; i; i--)  {
            try_knt = is_circular_identical(anchor, test_ring);
            // The shifting of test_ring below is a test fixture to prevent the 
            //  optimizer from optimizing the loop away and returning instantly
            if (i % 2) {
                test_ring /= 2;
            }   else  {
                test_ring *= 2;
            }
        }
        milliseconds = (uint64_t)(clock() - start);
        printf("\nET for is_circular_identical was %f milliseconds."
                "\n\tLast try_knt was %u for test_ring list %llu", 
                        (double)milliseconds, try_knt, test_ring);

        printf("\nConsuming %7.1f clocks per list.\n",
                (double)((milliseconds * (CPU_FREQ / 1000)) / (uint64_t)LOOP_KNT));

        getchar();
        return 0;
}

Answer 3

在行之间进行读取,听起来好像是在尝试枚举每个循环等价类的一个代表,其中包含3个1和52个零.让我们从密集表示切换到稀疏表示(三个数字中的一组range(55)).在这种表示中,sby 的循环移位k由理解给出set((i + k) % 55 for i in s).在一个类的字典最小代表总是包含0给定一组的形式的位置{0, i, j}与0 < i < j,与类中的其它候选者是最小{0, j - i, 55 - i}和{0, 55 - j, 55 + i - j}.因此,我们需要(i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j))将原件降至最低.这是一些枚举代码.

def makereps():
    reps = []
    for i in range(1, 55 - 1):
        for j in range(i + 1, 55):
            if (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j)):
                reps.append('1' + '0' * (i - 1) + '1' + '0' * (j - i - 1) + '1' + '0' * (55 - j - 1))
    return reps

Answer 4

重复第一个数组,然后使用Z算法(O(n)时间)在第一个数组内找到第二个数组.

(注意:您不必在物理上复制第一个数组.您可以在匹配期间进行环绕.)

关于Z算法的好处是它与KMP,BM等相比非常简单.
但是,如果你有野心,你可以在线性时间和恒定空间中进行字符串匹配- strstr例如,这样做.但是,实施它会更加痛苦.

Answer 5

继萨尔瓦多·达利非常聪明的解决方案之后,处理它的最佳方法是确保所有元素的长度相同,并且两个LISTS的长度相同.

def is_circular_equal(lst1, lst2):
    if len(lst1) != len(lst2):
        return False
    lst1, lst2 = map(str, lst1), map(str, lst2)
    len_longest_element = max(map(len, lst1))
    template = "{{:{}}}".format(len_longest_element)
    circ_lst = " ".join([template.format(el) for el in lst1]) * 2
    return " ".join([template.format(el) for el in lst2]) in circ_lst

不知道这是否比AshwiniChaudhary在Salvador Dali的回答中推荐的正则表达式解决方案更快或更慢,其答案如下:

import re

def is_circular_equal(lst1, lst2):
    if len(lst2) != len(lst2):
        return False
    return bool(re.search(r"\b{}\b".format(' '.join(map(str, lst2))),
                          ' '.join(map(str, lst1)) * 2))