logo标签列表

如何快速判断一个列表中是否包含另一个列表？

c#.netalgorithmlistmahjong
5

有很多相关的问题，但我正在寻找特定于我的情况的解决方案。有一个包含（通常）14个整数的数组，每个整数的范围在1到34之间。如何快速判断特定静态列表中的每个整数是否至少出现一次在这个数组中？

供参考，我目前正在使用以下代码，它被编写得尽可能接近规范，因此肯定可以大大改进：

if (array.Count < 13) {
    return;
}

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,
};

IsThirteenOrphans = !required.Except (array).Any ();

所需列表不是动态的，即在运行时它将始终保持不变。使用Linq是可选的，主要方面是性能。
编辑：
  • 输入数组未排序。
  • 输入值可能出现多次。
  • 输入数组将包含至少14个项目，即比所需数组多1个。
  • 只有一个必需的数组，并且它是静态的。
  • 所需中的值是不同的。
  • 您可以假设直方图创建是便宜的。
更新：我还对已排序的输入数组的解决方案感兴趣。
我认为你的代码也有一个错误。如果required包含重复项，但是对于某个整数，array中没有重复项，则它将通过你的测试。 - CodesInChaos
@Code确实，我忘了提到required不包含重复项。 - mafu
顺便提一下，如果你追求每微秒的性能，普通的for循环比foreach更快。 - Dan Bryant
我的算法是O(n + 34)，而不是34 * n。你看到了吗？有没有考虑过这个问题？如果没有，我就要删除它了。 - Saeed Amiri
@Saeed 我是。我不明白你为什么要删除它，对我来说这看起来是一个很好的答案。 - mafu
显示剩余3条评论
7个回答
1

这似乎是位运算的好候选，因为需要检查的值是不同的、静态的且在1到34之间。不要将需要检查的值保存为数组，而是将其保存为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;
}
有趣的想法，因为它高度可并行化且占用空间很小。很抱歉我目前无法测试它，但你得到了我的赞成。 - mafu
@mafu，我目前也没有可用的开发环境，否则我会尝试找到更快的实现方法。有一件事需要考虑：如果要检查的数组大小永远不会超过某个合理的长度（例如16），您可以将其设置为固定长度，用零填充未使用的索引并展开以获得性能提升。https://en.m.wikipedia.org/wiki/Loop_unrolling - Mr Anderson
1

如果您有一个34位以上的整数类型，并且具备C风格的位运算，那么您可以从变量列表中计算出这样一个整数V（如果列表是v [0]，v [1]，...，则V为（1 << v [0]）|（1 << v [1]）...其中1与V的类型相同），并预定义一个类似地计算出静态列表的整数S。然后，测试静态列表是否包含在变量列表中的方法是（S＆〜V）== 0。

1

想法1
如果您需要与多个required列表进行比较，那么您可以对输入列表进行排序，然后通过迭代简单地进行比较。但是排序当然不太快，但也不太慢。但是，如果您需要与多个必需列表进行比较，则排序的开销可能会很快被摊销。

一旦数组排序完成，比较就变得微不足道：

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

return true;
想法2
或者如果这14个整数是不同/唯一的，你可以简单地将required设置为一个HashSet并执行
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;
}

如果性能非常重要，您可以通过重复使用现有数组来避免创建数组。

1

如果你想要快速的方法，就不应该使用linq。如果给定的列表项都小于35，你可以删除if (lst[i] < 35)。下面的答案最多遍历一次列表，并且像计数排序一样运作：

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很小，而在二分查找算法中可能较大。

1
通过将a34中的true更改为false，您可以跳过初始化循环。由于所有项目都保证小于35，因此您也可以跳过if条件。 - mafu
@mafutrct，我认为我不能在a34中将true更改为false，因为我正在使用它的默认false值，并且只有在相关位置存在项目时才初始化a34数组的项。此外，我已经根据您在<35处的评论更新了答案。 - Saeed Amiri
1
一种可能性是改变数据存储方式。由于可能值的范围限制在1-34之间，因此您可以存储每个数字出现的计数，而不是存储数字列表。
int[] counts = new int[34];

如果你的列表中有一个1和两个3，那么counts[0] == 1 && counts[2] = 2（如果使用基于1的索引可能会使事情更快（减少了一些减法））。

现在要评估列表中的每个int至少出现一次，您只需按顺序为每个x索引到数组中并验证所有counts[x]> 0。将数据从计数形式转换为列表形式将带来一些开销，但仅当您经常需要以列表形式查看数据时才会成为问题。这种存储格式的另一个优点是，添加/删除计数永远不会涉及多个数组元素；在列表形式中，在列表中间删除一个元素需要复制多个元素。

0

你可以轻松地循环遍历这些项并找出是否有任何缺失的项。根据你的示例，我理解你只想知道所需的任何项是否在数组中缺失。因此，你可以编写以下代码：

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();
1
你不要停止一个计时器，而是启动它两次……他的代码对于单个迭代将显示0毫秒。你需要对一百万次迭代进行计时以获得合理的结果。 3秒钟不是现实的结果，你在测量时一定犯了一些大错误。 - CodesInChaos
@CodeInChaos，我修改了代码以停止计时器。但是它仍然需要更多时间。 - RameshVel
是的，我在数组对象中使用的数据是5。所以经过的时间是5毫秒。我测试了200个项目，它增加到了10毫秒，但第二种方法仍然是0毫秒。考虑到百万项目，性能肯定会降低。 - RameshVel
1
你的基准测试并不是很好。你只运行一次，这意味着你必须支付初始设置、JIT和可能更多的费用。对于这么小的事情，需要完成的工作量非常少，你可能需要尝试几十万次才能得到一个有效的数字。 - Cine
0

编辑： 所以我理解了你的问题，并且可能有一些很好但过于复杂的解决方案。另一个问题是，它有多好的性能。

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;
}
他不需要更大的列表。14个项目的列表大小直接遵循麻将的规则。 - CodesInChaos
哦，好的。那么问题是，他真的需要担心性能吗？在这种情况下，我会选择更好的可读性，除非他将重复执行该函数数百万次。 - Euphoric
实际上，我将重复执行该函数数百万次 :) - mafu
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接