Как эффективно определить симметрию в 4 целочисленных переменных?
Я хочу найти симметрии в 4 целочисленных переменных i,j,k а также l ,
Симметрии:
- все четыре числа равны: хххх,
- три числа равны: XXXY, XXYX, XYXX, YXXX
- две пары равных чисел: XXYY, XYXY, XYYX, …
- одна пара равных чисел и два разных числа: XXYZ, XYXZ, XYZX, …
- все цифры разные.
Все переменные работают в определенном не непрерывном диапазоне. Я использую вложенные операторы if else. Первый if проверяет неравенство всех переменных. Если нет, то у меня есть случай 1. Следующий if проверяет, есть ли какие-либо равные пары. Если нет, то случай 5. Следующий if проверяет наличие трех равных чисел. Если true, то case 2. В противном случае последний if проверяет две пары равных чисел. Если это правда, то случай 3, в противном случае случай 4.
if(!(i==j && j==k && k==l)){
if(i==j || i==k || i==l || j==k || j==l || k==l){
if((i==j && j==k) || (i==j && j==l) || (i==k && k==l) || (j==k && k==l)){ ...//do something
}else{
if((i==j && k==l) || (i==k && j==l) || (i==l && j==k)){
...//do something
}else{
...//do something
}
}
}else{
...//do something
}
}else{
...//do something
}
Есть ли лучший способ сделать это? Я имею в виду лучшее в смысле лучшей производительности, потому что я должен делать этот тест миллионы раз.
Решение
Идея, аналогичная samgak, но без необходимости внешнего стола. Просто посчитай сумму всех совпадений
int count = (i==j) + (i==k) + (i==l) + (j==k) + (j==l) + (k==l);
и делать switch с последующим выбором
switch (count){
case 0: //All differenct
case 1: //One same
case 2: //Two different pairs
case 3: //Three same
case 6: //All are same
}
Опять же, как уже упоминалось, ваш текущий код может быть быстрее в некоторых случаях. Особенно, если наиболее распространенным случаем является тот, где все элементы равны.
Другие решения
Если вы можете позволить себе небольшую (64-байтовую) справочную таблицу, вы можете протестировать каждую пару значений и установить бит для каждого сравнения в числе, которое вы используете в качестве индекса в своей таблице, например:
int classifySymmetries(int i, int j, int k, int l)
{
return table[(i == j) |
((i == k) << 1) |
((i == l) << 2) |
((j == k) << 3) |
((j == l) << 4) |
((k == l) << 5)];
}
Затем сделайте переключение на возвращаемое значение. Вы можете использовать свой существующий код для генерации таблицы, подставляя битовый тест для каждого сравнения или генерируя фиктивные значения i j k l, которые удовлетворяют каждому битовому шаблону от 0 до 63.
Этот подход требует постоянных 6 сравнений. Имейте в виду, что для сортировки 4 значений требуется от 4 до 5 сравнений (существует 4! = 24 возможных порядка, и каждое сравнение дает 1 бит информации). Но тогда вы должны сделать тесты, основанные на отсортированных значениях поверх этого.
То, будет ли использование справочной таблицы лучше, чем ваш текущий подход, будет зависеть от распределения значений и других факторов, таких как время доступа к памяти, вам следует профилировать для подтверждения.
Лучше всего использовать карту:
#include <iostream>
#include <map>
using namespace std;int main()
{
int i, j, k, l;
cin >> i >> j >> k >> l;
std::map<int, int> count;
int outcomes[5] = { 0, 0, 0, 0, 0 };
// Store the values in the map
count[i]++;
count[j]++;
count[k]++;
count[l]++;
// tally types of outcome according to the map
for(typename std::map<int, int>::iterator iter = count.begin(); iter != count.end(); ++iter)
{
outcomes[iter->second] ++;
}
// print out "1 of a kind" count, up to "4 of a kind"// this is just for visualization
for (int i = 1; i <= 4; ++i)
{
cout << i << " of a kind = " << outcomes[i] << endl;
}
// your bit here, it checks on just the "outcomes" array
if(outcomes[4] > 0) // 4 of a kind
{
}
else if(outcomes[3] > 0) // 3 of a kind
{
}
else if(outcomes[2] > 1) // two pair
{
}
else if(outcomes[2] > 0) // one pair
{
}
else // singles only
{
}
cin.ignore();
cin.get();
return 0;
}
Этот подход был бы гораздо более расширяемым, если бы вы хотели расширить его до 4 вариантов.