5

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

作为参考，我目前正在使用这段代码，它被编写为尽可能接近规范，所以它肯定可以大大改进：

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 个。
  • 只有 1 个必需的数组，它是静态的。
  • required 中的值是不同的。
  • 您可能会认为创建直方图的成本很低。

更新：我也对排序输入数组的解决方案感兴趣。

4

7 回答 7

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

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

于 2010-11-16T10:24:23.177 回答
1

如果你想要快速的方式，你不应该使用 linq，如果给定的列表项都低于 35，你最多可以删除if (lst[i] < 35) bellow answer traverse list 一次，并且行为如下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上面算法中的常数很小，而二进制搜索算法中的常数可能更大。

于 2010-11-16T11:26:33.987 回答
1

如果您有可用的 34+ 位整数类型和 C 风格的位运算，那么您可以从变量列表中计算出这样的整数 V（如果列表是 v[0]、v[1]、...，那么 V 是(1 << v[0]) | (1 << v[1]) ... 其中 1 与 V 的类型相同）并且具有用于静态列表的预定义整数 S，计算方式类似。判断静态列表是否包含在变量列表中的测试是 (S & ~V) == 0。

于 2010-11-16T12:06:58.013 回答
1

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

int[] counts = new int[34];

如果您的列表有一个 1 和两个 3，那么 counts[0] == 1 && counts[2] = 2 （如果这样可以让事情变得更快（更少的减法），您可以交替使用基于 1 的索引。）

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

于 2010-11-16T15:00:24.560 回答
1

这看起来很适合按位运算，因为 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;
}
于 2016-06-19T16:21:45.263 回答
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();
于 2010-11-16T10:43:16.380 回答
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;
}
于 2010-11-16T10:48:11.260 回答