如何快速判断列表是否包含列表?

想法1
如果你需要与几个 required 然后,您可以对输入列表进行排序,然后通过迭代进行比较。但排序当然不会太快,但也不会太慢。但是,如果您与几个必需的列表进行比较,排序的开销可能会很快摊销。

一旦数组排序,比较就很简单了:

for(int i = 0; i < 14; i++)
  if(arr[i] != required[i]) return false;

return true;

想法2
或者如果14个整数是不同的/唯一的,您可以简单地 必修的 散列集和do

input.Count(i => required.Contains(i)) == 14

但我不知道如果没有实际测试它是否比排序快。

想法3
计算一个在14个整数上的置换下不变的快速散列,并将其与已知的 require . 只有在哈希匹配的情况下才能进行更昂贵的比较。

//Prepare/precalculated
int[] hashes = new int[34];
Random random = new Random();
for(int i = 0; i < 34; i++)
  hashes[i] = random.NextInt();

//On each list
int HashInts(int[] ints)
{
  int result = 0;
  foreach(int i in ints)
    result += hashes[i - 1];

  return result;
}

明智的价值选择 hashes 可能会有所改善,但随机值应该没问题。

想法4
创建直方图:

int[] CreateHistogram(int[] ints)
{
  int[] counts = new int[34];
  foreach(int i in ints)
  {
    counts[i - 1]++;
  }

  return counts;
}

如果性能是可用的,则可以通过重用现有数组来避免数组创建。 真正地 很重要。

如果有34位整数类型可用,并且有C位操作,那么可以从变量列表(如果列表是V[0]、V[1]、。。。那么V是(1<<V[0]);(1<<V[1])。。。其中1与V)是同一类型的,并且具有用于静态列表的预定义整数S,其计算方式类似。查看静态列表是否包含在变量列表中的测试是(S&V)==0。

一种可能是改变存储数据的方式。由于可能值的范围限制为1-34,因此您可以存储每个数字的计数,而不是存储数字列表:

int[] counts = new int[34];

如果你的列表有一个1和两个3s,那么计数[0 ]=1和&&计数[2 ]=2(如果这使事情变得更快(更少的减法),你可以交替使用1个索引。

现在要计算列表中的每个int至少出现一次,只需为每个x按顺序索引到数组中,并验证所有计数都为[x]>0。将数据从counts表单转换为list表单会产生相关的开销,但如果您还经常需要查看list表单中的数据,则这只是一个问题。这种存储格式的另一个优点是,向counts添加/删除永远只涉及一个数组元素;在列表格式中,删除列表中间的元素需要多个元素的副本。

如果你想要快速的方式,你不应该使用linq,如果一个给定的列表项都在35以下,你可以删除 if (lst[i] < 35) 下面的答案最多一次遍历列表,并且 counting sort :

public bool FindExactMatch(int[] array, List<int> lst)
{
    bool[] a34 = new bool[35];

    foreach(var item in array)
    {
        a34[item] = true;
    }

    int exact = 0;

    for (int i = 0; i < lst.Count; i++)
    {
        if (a34[lst[i]])
        {
            exact++;
            if (exact == array.Length) return true;

            a34[lst[i]] = false;
        }
    }

    return false;
}

对于排序列表,如果列表大小很大,则可以执行以下操作 lst.BinarySearch(array[i]) 它最多需要14*log(n)*c1,我认为如果你实现它可能会更快,并且我没有用我自己的实现测试二进制搜索,但是linq中的Min,Max,Sort比你自己的(好的)实现慢(4到10次)。 如果排序列表的大小很小,我更喜欢使用上面的算法,因为常量 c1 在上述算法中较小,在二进制搜索算法中可能较大。

这看起来很适合按位操作,因为required中的值是不同的、静态的,并且介于1和34之间。不要将required保存为数组,而是将其保存为const ulong。在要检查的数组中,创建一个由左移每个值和按位或填充的新ulong。

const ulong comparator = (1UL << 1) | (1UL << 9) | (1UL << 10) | (1UL << 18) | (1UL << 19) | (1UL << 27) | (1UL << 28) | (1UL << 29) | (1UL << 30) | (1UL << 31) | (1UL << 32) | (1UL << 33) | (1UL << 34);

public static bool ContainsDistinct13Values(int[] array)
{
    ulong word = 0;
    foreach (int i in array)
    {
        word |= (1UL << i);
    }
    return word == comparator;
}

编辑: 所以我理解了你的问题,可能有一些非常复杂的解决方案。另一个问题是,它的表现有多好。

static void Main(string[] args)
{
    var required = new int[]
                       {
                           0*9 + 1,
                           0*9 + 9,
                           1*9 + 1,
                           1*9 + 9,
                           2*9 + 1,
                           2*9 + 9,
                           3*9 + 1,
                           3*9 + 2,
                           3*9 + 3,
                           3*9 + 4,
                           3*9 + 5,
                           3*9 + 6,
                           3*9 + 7,
                       };

    precomputed = required.Select((x, i) => new { Value = x, Offset = (UInt16)(1 << i) }).ToDictionary(x => x.Value, x => x.Offset);

    for (int i = 0; i < required.Length; i++)
    {
        precomputedResult |= (UInt16)(1 << i);
    }

    int[] array = new int[34]; // your array goes here..
    Console.WriteLine(ContainsList(array));

    Console.ReadKey();
}

// precompute dictionary
private static Dictionary<int, UInt16> precomputed;
// precomputed result
private static UInt16 precomputedResult = 0;

public static bool ContainsList(int[] values)
{
    UInt16 result = 0;
    for (int i = 0; i < values.Length; i++)
    {
        UInt16 v;
        if (precomputed.TryGetValue(values[i], out v))
            result |= v;
    }

    return result == precomputedResult;
}

你可以很容易地循环浏览这些项目,找出是否有任何项目丢失。通过您的示例,我理解您只是想知道数组中是否缺少required中的任何项。所以你可以写

bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;
    }

    if (notContains == false) break;
}

这比你的方法快得多。查看下面添加了计时器的代码。你的方法用了5毫秒,但新的方法用了0毫秒

System.Diagnostics.Stopwatch aTimer = new System.Diagnostics.Stopwatch();
aTimer.Start();

var IsThirteenOrphans = !required.Except(array).Any();
aTimer.Stop();

System.Diagnostics.Stopwatch bTimer = new System.Diagnostics.Stopwatch();
bTimer.Start();
bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;            
    }

    if (notContains == false) break;
}

bTimer.Stop();