Как сравнить размеры двух ящиков?

Question

Даны два ящика с размерами (L,B,H). Нужно написать красивую(оптимизация по скорости) функцию сравнения размеров, function sizes_compare(l1, b1, h1, l2, b2, h2):booleean, на выходе: равны/не равны. Учитывая, что ящики (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) и (3,2,1) являются одинаковыми(просто перевёрнуты в пространстве).

Что-то у меня всё ну очень получается длинно. Хеш функцию придумать не получилось, проскакивают коллизии. Прямым сравниванием получается шпагетти-код. Если представить как два массива, отсортировать и сравнить, как-то уж слишком замудрённо...

язык не важен, интересны идеи как это можно оптимально реализовать. Используется в критическом месте, нужна оптимизация по скорости исполнения.

Answer 1

Отсортировать и сравнить последовательно - самый нормальный вариант.

При этом сортировать можно как сортировкой массива, так и просто руками.

https://ideone.com/d9i6xm

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
  int a[3], b[3];

  scanf("%d%d%d%d%d%d", a, a+1, a+2, b, b+1, b+2);

  sort(a, a+3);
  sort(b, b+3);

  puts(a[0]==b[0] && a[1]==b[1] && a[2]==b[2] ? "YES" : "NO");

  return 0;
}

Answer 2

В общем на основе ответов вырисовалось 3 основные концепта, решил реализовать все 3 поиска и сравнить по производительности:

1. Сравнение прямыми проверками:

function sizes_comapre(a, b: TSize): Boolean;
begin
  Result := false;
  if a.x <> b.x then begin
    if a.x <> b.y then begin
      if a.x <> b.z then begin
        exit;
      end else begin
        {$REGION '[1,x,x][x,x,1]'}
        if a.y <> b.x then begin
          if a.y <> b.y then begin
            exit;
          end else begin
            //[1,2,x][x,2,1]
            if a.z <> b.x then begin
              exit;
            end else begin
              //[1,2,3][3,2,1]
              exit(true);
            end;
          end;
        end else begin
          //[1,2,x][2,x,1]
          if a.z <> b.y then begin
            exit;
          end else begin
            //[1,2,3][2,3,1]
            exit(true);
          end;
        end;
        {$ENDREGION}
      end;
    end else begin
      {$REGION '[1,x,x][x,1,x]'}
      if a.y <> b.x then begin
        if a.y <> b.z then begin
          exit;
        end else begin
          //[1,2,x][x,1,2]
          if a.z <> b.x then begin
            exit;
          end else begin
            //[1,2,3][3,1,2]
            exit(true);
          end;
        end;
      end else begin
        //[1,2,x][2,1,x]
        if a.z <> b.z then begin
          exit;
        end else begin
          //[1,2,3][2,1,3]
          exit(true);
        end;
      end;
      {$ENDREGION}
    end;
  end else begin
    {$REGION '[1,x,x][1,x,x]'}
    if a.y <> b.y then begin
      if a.y <> b.z then begin
        exit;
      end else begin
        //[1,2,x][1,x,2]
        if a.z <> b.y then begin
          exit;
        end else begin
          //[1,2,3][1,3,2]
          exit(true);
        end;
      end;
    end else begin
      //[1,2,x][1,2,x]
      if a.z <> b.z then begin
        exit;
      end else begin
        //[1,2,3][1,2,3]
        exit(true);
      end;
    end;
    {$ENDREGION}
  end;
end;

2. Сравнение математически (на основе теоремы Виета):

function sizes_comapre2(a, b: TSize): Boolean;
begin
  Result := false;
  if a.x + a.y + a.z <> b.x + b.y + b.z then
    exit;
  if a.x * a.y * a.z <> b.x * b.y * b.z then
    exit;
  //LB+LH+BH
  Result := (a.x * a.y + a.x * a.z + a.y * a.z = b.x * b.y + b.x * b.z + b.y * b.z);
end;

3. Сравнение сортировкой двух триплетов и последующим последовательным сравнением:

function sizes_comapre3(a, b: TSize): Boolean;
var
  temp: Byte;
begin
  {$REGION 'Sort a'}
  if a.z < a.y then begin
    temp := a.y;
    a.y := a.z;
    a.z := temp;
  end;
  if a.z < a.x then begin
    temp := a.x;
    a.x := a.z;
    a.z := temp;
  end;
  if a.y < a.x then begin
    temp := a.y;
    a.y := a.x;
    a.x := temp;
  end;
  {$ENDREGION}
  {$REGION 'Sort b'}
  if b.z < b.y then begin
    temp := b.y;
    b.y := b.z;
    b.z := temp;
  end;
  if b.z < b.x then begin
    temp := b.x;
    b.x := b.z;
    b.z := temp;
  end;
  if b.y < b.x then begin
    temp := b.y;
    b.y := b.x;
    b.x := temp;
  end;
  {$ENDREGION}
  Result := ((a.x = b.x) and (a.y = b.y) and (a.z = b.z));
end;

Результаты для 10 Млн проверок:

Time[sort1]: 0,2930 sek
Time[sort2]: 0,2896 sek
Time[sort3]: 0,5455 sek
Time[empty pass]: 0,2207 sek

Как и предполагалось, предварительная сортировка с последующим сравненим [3] оказалась самой долгой.

Удивило, что математический подход [2] оказался, хоть и немного, но быстрее прямой проверки [1], хотя там довольно много умножений... При чём при значениях 1..7 последней, самой сложной проверкой можно пренебречь, она нужна только для значений >= 8.

В общем буду использовать его, к тому же он и в реализации самый простой и наиболее наглядный.

Answer 3

На всякий случай, ручная сортировка массива из 3-х элементов по убыванию

#define SWAP(x, i, j) {typeof (*x) *_a = x; typeof (*x) t = _a[i]; _a[i] = _a[j]; _a[j] = t;}

static void inline sort3 (int a[3])
{
  if (a[0] < a[1])
    SWAP(a, 0, 1);
  if (a[0] < a[2])
    SWAP(a, 0, 2);
  if (a[1] < a[2])
    SWAP(a, 1, 2);
}

Answer 4

Такая проверка делает то что вам надо, по крайней мере если все числа целые от 1 до 7, также она очевидно очень быстра)

a1 + b1 + c1 == a2 + b2 + c2 and a1 * b1 * c1 == a2 * b2 * c2

Чтобы доказать отсутствие коллизий можно запустить такой скрипт:

from itertools import product

pairs = product(
    product(range(1, 8), range(1, 8), range(1, 8)),
    product(range(1, 8), range(1, 8), range(1, 8))
)

for box1, box2 in pairs:
    if (box1[0] + box1[1] + box1[2] == box2[0] + box2[1] + box2[2]) and (box1[0] * box1[1] * box1[2] == box2[0] * box2[1] * box2[2]):
        assert list(sorted(box1)) == list(sorted(box2))

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

Answer 5

Для случая сильно ограниченного набора значений, можно просто подобрать хеш-функцию, так чтобы небыло коллизий. Поскольку мы свертываем 9 бит (3*3=9) в 32, то подходит буквально первый попавшийся хеш:

uint32_t circular_hash(uint8_t i)
{
    return  uint32_t(i) ^ uint32_t(12345678u)  ;
}

typedef std::tuple<uint8_t,uint8_t,uint8_t> triple;
uint32_t circular_hash(triple t)
{
    return circular_hash( std::get<0>(t) )
         * circular_hash( std::get<1>(t) )
         * circular_hash( std::get<2>(t) );
}

тест:

std::map< uint32_t, triple > test;

for( uint8_t a=0; a<=8; ++a  )
    for( uint8_t b=a; b<=8; ++b  )
        for( uint8_t c=b; c<=8; ++c  )
        {
            triple t={a,b,c};
            uint32_t h=circular_hash(t);
            if(test.count(h)!=0)
            {
                triple t2=test[h];
                std::cout<<"error: "<<h<< " : " << t  <<" = " << t2  <<std::endl;
            }
            test[h]=t;
        }
return 0;