Наиболее эффективный способ сравнения двух пар целых чисел

Класс содержит два целых числа; есть два экземпляра этого класса. Я хочу сравнить их, чтобы убедиться, что два экземпляра содержат одинаковые два числа (их заказы не имеют значения).Наиболее эффективный способ сравнения двух пар целых чисел

Я могу это сделать:

bool operator==(const Edge &e, const Edge &f) { 
    return ((e.p1 == f.p1) || (e.p1 == f.p2)) && ((e.p2 == f.p1) || (e.p2 == f.p2)); 
}

Это лучший способ есть? Там будет много таких сравнений, поэтому я хочу убедиться, что сделаю самый эффективный выбор. BTW, оператор будет в основном использоваться классом std::unordered_set - в случае, если эта информация имеет значение.

источник

2013-05-17 deepak

Забудьте о оптимизации. Я думаю, что ваша логика неверна. Эти два условия могут быть правдой: (e.p1 == f.p1) (e.p2 == f.p1), и ваша функция вернет true без рассмотрения f.p2. –

Невозможно оптимизировать это, не зная подробностей использования.Например, существует ли много, гораздо больше сравнений, тогда есть создания Edges? Можем ли мы добавить дополнительные данные в структуру Edge или получить премию за память? Являются ли эти целые числа неизменными для жизни экземпляра класса или могут ли они измениться? (Но, скорее всего, нет смысла оптимизировать его.) –

Если вы беспокоитесь о том, что операция выполняется несколько раз, а порядок чисел не имеет значения, вы можете просто убедиться, что p1 всегда равно или меньше, чем p2, а затем вы можете просто сравнить их непосредственно 'e.p1 == f.p1 && e.p2 == f.p2'. –

Я думаю, что вы немного смешаете логику ... если я правильно вас понимаю, учитывая пары (a, b) и (x, y), вы хотите проверить, что (a, b) == s (x, y), для некоторой подстановки s?

bool operator==(const Edge &e, const Edge &f) { 
    return ((e.p1 == f.p1) && (e.p2 == f.p2)) || 
      ((e.p2 == f.p1) && (e.p1 == f.p2)); 
}

Что касается производительности ... здесь нечего оптимизировать. Идите в другое место, если ваша программа медленная.

источник

2013-05-17 04:27:11

«Здесь нечего оптимизировать. Идите искать где-нибудь еще, если ваша программа медленная» - не так. Как говорит Ричи, возможно, стоит изучить предварительно заказанные значения, а затем, например, упаковку два int32s в объединение с int64, что позволяет использовать один «e.as_int64 == f.as_int64», который, учитывая избегание оценки короткого замыкания, может быть на порядок быстрее, чем ваш код выше. это может быть не существенным в общем контексте программы, но в этом вопросе говорится, что «многие такие сравнения» «хотят ... самого эффективного выбора» - нет смысла отвечать, игнорируя это. –

Это будет нормально работать на двоих. Однако, для более того, он явно становится очень уродливым очень быстро. Фактически, вам нужно будет сделать сравнения n!, чтобы проверить, есть ли у вас переменные n, если вы делаете это с наивным способом.

Простой способ что-то вроде следующего:

static constexpr Edge::number() 
{ 
    return <number_of_values>; 
} 

bool operator==(const Edge& e, const Edge& f) 
{ 
    constexpr size = Edge::number(); 
    std::array<int, size> earr = {{e.p1, e.p2, ..., e.pn}}; 
    std::array<int, size> farr = {{f.p1, f.p2, ..., f.pn}}; 
    return std::is_permutation(earr.begin(), earr.end(), farr.begin()); 
}

Если это всегда два, вы можете просто написать это как:

bool operator==(const Edge& e, const Edge& f) 
{ 
    std::array<int, 2> earr = {{e.p1, e.p2}; 
    std::array<int, 2> farr = {{f.p1, f.p2}}; 
    return std::is_permutation(earr.begin(), earr.end(), farr.begin()); 
}

Тестирование неупорядоченный равенство такое же, как тестирование, если один последовательность является перестановкой другой.

Редактировать: Который, как должно быть очевидно для меня, можно протестировать, проверив, что отсортированные последовательности равны. Заменить std::is_permutation на std::sort и std::equal выше, который будет O(n log n) вместо O(n^2).

источник

2013-05-17 04:30:56 Yuushi

Для больших наборов будет быстрее использовать ' std :: sort() ', который является O (N log N), а не 'std :: is_permutation()', что является O (N^2). –

Почему бы не отсортировать их? Даже если вам нужно скопировать их в другую структуру, это все же быстрее, чем перестановки. – xaxxon

Является ли ваше решение для случая двух значений (как мне нужно) быстрее, чем мое решение (хотя с исправленной логикой, благодаря Стиву и Дитриху)? Не будет ли использование объектов STL чрезмерным? – deepak

Согласно моему пониманию вашего вопроса я предлагаю вам следующее решение:

Просто добавь на функции в классе, как показано ниже:

bool isExist(int point) 
{ 
    if(this.p1==point || this.p2==point) 
    return true; 
    else 
    return false; 
}

Вы можете применить логику вызова этой функции.

Пожалуйста, поправьте меня, если я ошибаюсь ...

источник

2013-05-17 04:33:00

Хотя это нормально, это сравнивает только один элемент за раз. Чтобы сопоставить обе точки края, мне придется дважды звонить. – deepak

Это, вероятно, не самый быстрый, и это требует C++ 11. Но это хорошо и коротко:

bool operator==(const Edge& e, const Edge& f) { 
    return std::minmax(e.p1, e.p2) == std::minmax(f.p1, f.p2); 
}

Он также предполагает, оптимизация (который я обычно использую): держать p1 и p2 в порядке, так что minmax не нужно называть каждый раз. Тогда у вас есть оптимальное решение.

источник

2013-05-17 05:04:34 rici

Наиболее эффективный способ сравнения двух пар целых чисел

ответ

Смежные вопросы