Как получить все возможные значения функции, вызываемой с любыми двумя значениями массива? - PullRequest
Новая
       18

Как получить все возможные значения функции, вызываемой с любыми двумя значениями массива?

0 голосов
/ 13 августа 2010

Рассмотрим этот код: 

class MyClass {
    string PropertyA;
    int PropertyB;
    double PropertyC;
    object PropertyD;
    static ComparisonResult Compare(MyClass a, MyClass b){
        // returns a ComparisonResult with
        // _sampleElement = a
        // _commonProperties = flags that describe the common properties of a and b
    }
}

enum SimilarityFlags {
    SharedPropertyA = 1,
    SharedPropertyB = 2,
    SharedPropertyC = 4,
    SharedPropertyD = 8
}

class ComparisonResult {
    private MyClass _sampleElement;
    private SimilarityFlags _commonProperties;

    bool Equals(object obj){
        ComparisonResult other = obj as ComparisonResult;
        if(other==null) return false;
        if(this._commonProperties != other._commonProperties) return false;
        MyClass s1 = this._sampleElement;
        MyClass s2 = other._sampleElement;
        if(_commonProperties.HasFlag(SimilarityFlags.SharedPropertyA) && s1.PropertyA != s2.PropertyA) return false; 
        if(_commonProperties.HasFlag(SimilarityFlags.SharedPropertyB) && s1.PropertyB != s2.PropertyB) return false; 
        if(_commonProperties.HasFlag(SimilarityFlags.SharedPropertyC) && s1.PropertyC != s2.PropertyC) return false; 
        if(_commonProperties.HasFlag(SimilarityFlags.SharedPropertyD) && s1.PropertyD != s2.PropertyD) return false; 
        return true;
    }

    int GetHashCode(){
        return (int)_commonProperties;
    }
}



MyClass[] array;
HashSet<ComparisonResult> possibleValues = GetAllPossibleComparisonValues(array);

Как я могу получить все возможные значения, которые возвращает Compare, когда он принимает любые два элемента в массиве?

Примечание: Сравните (a, b) == Сравните (b, a) и a! = B

Пример (псевдокод, 3 свойства вместо 4): 

GetAllPossibleComparisonValues( [  {"foo", 5, 0x00}, {"foo", 77, 0x00}, {"BAR", 5, 0x00}, {"foo", 5, 0x00}, {"BAR", 5, 0x00}  ] )

должен вернуть этот набор: [{any, any, 0x00}, {"foo", any, 0x00}, {"foo", 5, 0x00}, {"BAR", 5, 0x00}, {any, 5, 0x00}] 

GetAllPossibleComparisonValues( [ {"foobar", 1}, {"foobar", 2},  {"foobar", 3},  {"foobar", 4} ])

должен вернуться [{"foobar", любой}]

В настоящее время я использую этот алгоритм: 

for(int i = 0; i < array.Length - 1; i++){
    for(int j = i + 1; i < array.Length; j++){
        possibleValues.Add(MyClass.Compare(array[i], array[j]));
    }
}

но это очень неэффективно, особенно с длинными массивами, где любые два элемента имеют одинаковый ComparisonResult. После вычисления возможное значение ValueValues.Count обычно очень мало (1..3), даже для длинных массивов (более 2000 элементов).

Я думаю, что можно значительно повысить эффективность вычислений. Например, если Compare (array [0], array [1]) == Compare (array [0], array [2]), нет необходимости вызывать Compare (array [1], array [2])

Как мне это сделать?

1 Ответ

0 голосов
/ 13 августа 2010

Эта проблема, похоже, является проблемой логической выполнимости . Если вы смоделируете каждое значение вашего массива как логическую входную переменную, возможно, будет возможно использовать алгоритмы, перечисленные на странице википедии, чтобы получить все входные векторы, которые удовлетворяют определенной выходной переменной. Усилия не являются низкими, поэтому это зависит от того, действительно ли вам нужно это ускорение или можете ли вы жить с уже работающим решением, поскольку это очень легко понять.

Другое дело, что вы кешируете уже найденные решения и изменяете эти найденные векторы, только если было добавлено новое значение в одном массиве. Таким образом, вам нужно только сначала найти векторы решения. Если вы можете применить это в зависимости от погоды, возможные значения меняются очень часто, или если они не сильно меняются.

...