松组合比较

Question

比较 2 种组合的最佳方法是什么？

我的情况：

我目前有一个 string string1 = "xxxxxx";。长度为 6 个字符。每个 char 值是 0 或 1 或 x。我需要将此 string 与另一个具有相同数量字符但值是 1 或 0

的 string 进行比较

char x in first string表示第二个的char值 string 可以是任何东西
char 0 在第一个 string - 在第二个 string

0

char 1 在第一个 string - 在第二个 string

1

这是一个简单的例子：

string pattern = 'xxxxxx';
string test1 = '010101';
// pass

string pattern = '1xxxxx';
string test2 = '010101';
// not pass

string pattern = '0xxxxx';
string test3 = '010101';
// pass

我已经为它做了一个函数：

    public bool passCombination(string pattern, string combination)
    {
        bool combination_passed = true;
        for (int i = 0; i < pattern.Length; i++)
        {
            char test_char = pattern[i];
            if (test_char != 'x' && combination[i] != test_char)
            {
                combination_passed = false;
                break;
            }
        }

        return combination_passed;
    }

很简单。基本上我在 char 之后迭代 char。如果它是 x 那么我不关心第二个字符串中的值。如果是其他字符 - 然后进行比较。

因为它是基于字符串的方法，所以我在考虑其他解决方案吗？在我的真实场景中，我必须执行大约（~700k 这样的检查 * ~150 万次）。这个非常乐观的数字:)

我正在考虑 regex 比较或将所有组合保存到 int[] 数组中并进行比较。或者也许可以使用 hashes?

来完成一些魔法

所以至少有 3 个其他选项可能提高性能。任何人都可以提出更高性能的解决方案吗？

编辑：

我做了运行比较测试。使用旧方法，我得到了 2.5 分钟的执行时间，而使用下面建议的新方法（接受的答案）——大约 2 分钟。大致是20%性能提升。

Answer 1

首先，确保您确实需要优化任何东西，然后再浪费时间编写过于聪明的代码以节省可以浪费的周期。

但如果你确实需要优化，你总是可以玩弄一些位。它通常比遍历内容更快，而且在极少数情况下，它 看起来 对于任何阅读您的代码的人来说都更快。

警告： 如果您永远不会或很少会多次比较任何给定的 "value" 字符串，则此方法没有任何优势，因为编译无论如何都涉及遍历字符串。

如果您确实遇到性能问题，可以将模式 "compile" 分成两个整数：一个是 1 代表每个 1 和 0 的模式对于每个 0 或 x；另一个是掩码，每个 x 有一个 0，每个 0 或 1 有一个 1。你浪费了每个整数 26 位，但我不会告诉任何人。

然后将值编译成整数：1 for 1，0 for 0。

写一个 class 有那些 pattern/mask 整数和一个方法来将它们与值 int 进行比较。你会 "precompile" "values" 并将它们存储为整数而不是字符串，或者可能是一个 class 有一个 int 属性和一个字符串属性 '将需要显示它们（或者您可以编写一个函数将这些整数转换回字符串）。

public class PatternMatcher
{
    public PatternMatcher(String pattern)
    {
        Pattern = CompilePattern(pattern);
        Mask = CompileMask(pattern);
    }

    #region Fields
    //  Could we save any cycles by making these fields instead of properties? 
    //  I think the optimizer is smarter than that. 
    public int Pattern { get; private set; }
    public int Mask { get; private set; }
    #endregion Fields

    public bool CheckValue(String value)
    {
        return CheckValue(CompileValue(value));
    }

    public bool CheckValue(int value)
    {
        //  a & b: Bitwise And
        //      Any bit that's "true" in both numbers is "true" in the result. 
        //      Any bit that's "false" in EITHER number is "false" in the result.

        //      11 & 11 == 11
        //      11 & 01 == 01
        //      11 & 10 == 10
        //      11 & 00 == 00

        //      01 & 11 == 01
        //      01 & 01 == 01
        //      01 & 10 == 00
        //      01 & 00 == 00

        //  So xx0011 -> 
        //      Pattern: 000011
        //      Mask:    001111
        //      Value    110011

        //  (110011 & 001111) == 000011
        //  (000011 & 001111) == 000011
        //
        //  000011 == 000011, so these two match. 

        return (value & Mask) == (Pattern & Mask);
    }

    public static int CompileMask(string patternString)
    {
        int mask = 0;
        int bitoffset = 0;

        //  For each character in patternString, set one bit in mask.
        //  Start with bit zero and move left one bit for each character.
        //  On x86, these bits are in reverse order to the characters in 
        //  the strings, but that doesn't matter. 
        foreach (var ch in patternString)
        {
            switch (ch)
            {
                //  If the pattern has a '0' or a '0', we'll be examining that 
                //  character in the value, so put a 1 at that spot in the mask.
                case '1':
                case '0':
                    //  a | b: Bitwise OR: If a bit is "true" in EITHER number, it's 
                    //  true in the result. So 0110 | 1000 == 1110.
                    //  a << b: Bitwise left shift: Take all the bits in a and move 
                    //  them leftward by 1 bit, so 0010 << 1 == 0100. 
                    //
                    //  So here we shift 1 to the left by some number of bits, and 
                    //  then set that bit in mask to 1. 
                    mask |= 1 << bitoffset;
                    break;

                //  If it's an 'x', we'll ignore that character in the value by 
                //  putting a 0 at that spot in the mask. 
                //  All the bits are zero already.
                case 'x':
                    break;

                default:
                    throw new ArgumentOutOfRangeException("Invalid pattern character: " + ch);
            }

            ++bitoffset;
        }

        return mask;
    }

    public static int CompilePattern(string patternString)
    {
        int pattern = 0;
        int bitoffset = 0;

        foreach (var ch in patternString)
        {
            //  For each character in patternString, set one bit in pattern.
            //  Start with bit zero and move left one bit for each character.
            switch (ch)
            {
                //  If the pattern has a 1, require 1 in the result.
                case '1':
                    pattern |= 1 << bitoffset;
                    break;

                //  For 0, require 0 in the result.
                case '0':
                    //  All the bits were zero already so don't waste time setting 
                    //  it to zero. 
                    break;

                //  Doesn't matter what we do for 'x', since it'll be masked out. 
                //  Just don't throw an exception on it. 
                case 'x':
                    break;

                default:
                    throw new ArgumentOutOfRangeException("Invalid pattern character: " + ch);
            }

            ++bitoffset;
        }

        return pattern;
    }

    public static int CompileValue(string valueString)
    {
        int value = 0;
        int bitoffset = 0;

        //  For each character in patternString, set one bit in mask.
        //  Start with bit zero and move left one bit for each character.
        foreach (var ch in valueString)
        {
            switch (ch)
            {
                //  If the value has a '1', have a 1 for that bit
                case '1':
                    value |= 1 << bitoffset;
                    break;

                //  If the value has a '0', leave a 0 for that bit
                //  All the bits were zero already.
                case '0':
                    break;

                default:
                    throw new ArgumentOutOfRangeException("Invalid pattern character: " + ch);
            }

            ++bitoffset;
        }

        return value;
    }
}

显然，如果您不能预编译您的值并将它们存储为整数（那是一个很大的 "if"），那么您就是在浪费时间。但是如果可以的话，你可以为每个模式创建一个，并在一个循环中使用它 700k+ 次。这可能比循环字符串 700k+ 次要快。

Answer 2

感觉这个问题可能遗漏了一些重要信息。例如，如果值存储在数据库中，那么存储过程应该比将所有数据加载到内存中更快。

另一方面，将数据加载到内存中可以让您更好地控制缓存（将已检查的组合保存在散列 table 或数组中）和并行度（同时检查不同处理器或机器上数据的不同部分）

此外，如果您要针对大约一百万种组合检查大约一百万种模式，那么有更好的算法可以将当前复杂度从 O(n^2) 提高到更接近 O(n) http://bigocheatsheet.com/#chart

对于模式和组合的比较，你现在拥有的应该比将字符串转换为整数快一点点。如果您将一种模式与多种组合进行比较，那么如果您保存不是 x 的位置并仅比较它们，那么可以稍微加快它的速度。例如：

foreach ( string pattern in patterns )
{
    // save the non x indexes
    var indexes = new List<int>(); 
    for (int i = 0; i < pattern.Length; i++)
        if (pattern[i] != 'x')
            indexes.Add(i);

    foreach ( string combination in combinations )
    {
        bool combination_passed = true;
        foreach (int i in indexes)
        {
            if (combination[i] != pattern[i])
            {
                combination_passed = false;
                break;
            }
        }
        // ...
    }
}

松组合比较

loose combination comparison

c#

performance

string-comparison

winforms