13

Даны два ящика с размерами (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) являются одинаковыми(просто перевёрнуты в пространстве).

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

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

13
  • Сравнить отсотированные триплеты?
    – Chorkov
    13 янв 2020 в 15:15
  • я это описал уже в вопросе, оно работает стабильно, без промахов, но это максимально не оптимальный код в итоге же
    – Isaev
    13 янв 2020 в 15:20
  • >Если представить как два массива, отсортировать и сравнить, как-то уж слишком замудрённо... - почему же замудрённо? Отсортировать 2 массива по 3 элемента каждый и покомпонентно сравнить. На мой взгляд, самое оптимальное решение. 13 янв 2020 в 15:22
  • т.е. математически никак не получится? Если числа всегда целые и в пределах от 1 до 7 например?
    – Isaev
    13 янв 2020 в 15:24
  • 1
    @Isaev, неверно, сортировка трех элементов выполняется за 3 сравнения, итого 3+3+3=9 14 янв 2020 в 9:22

5 ответов 5

5

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

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

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;
}
3
  • "самый нормальный вариант." возможно... сейчас так и работает, хотелось бы ускориться
    – Isaev
    13 янв 2020 в 17:12
  • 1
    Связанный вопрос: Как быстро отсортировать 3 элемента? 14 янв 2020 в 8:54
  • @АндрейNOP, да, можно так. Хотя тут рядом уже запостили. А вот за что минусы обоим ответам, я не понимаю ((
    – Qwertiy
    14 янв 2020 в 9:40
3

В общем на основе ответов вырисовалось 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.

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

5
  • ничего неожиданного) при "прямой" проверке очень много условных переходов. От которых компилятор даже не факт что избавится. Можно попробовать кстати какую-нибудь ДНФ сделать или подобное на 9 переменных сравнения. Но не уверен что будет быстрее.
    – pavel
    15 янв 2020 в 14:18
  • Сортировка и сравнение на ассемблере (Win64) показывает такую же скорость, как sizes_comapre2. Но неужели 10 нс (30 тактов) на сравнение является в этой задаче лимитирующим фактором?
    – MBo
    24 апр 2020 в 15:03
  • @MBo, спасибо за асм тест! Может именно в данном случае и не является, я не думал, что на столько различные подходы дадут на столько близкие результаты. Но из нс складываются минуты и часы и в итоге, когда программа вместо 16 часов отрабатывает за 10, это приятно.
    – Isaev
    24 апр 2020 в 21:29
  • А подход нельзя изменить, чтобы столько проверок не пришлось делать?
    – MBo
    25 апр 2020 в 2:16
  • @MBo, она строит граф, размер которого ограничен лишь объёмом оперативки, в котором потом ищет решения. Поиск решения потом занимает доли секунды, а вот построение самого графа довольно временнозатратно (в районе 300млн узлов хватает доступных 92гб мне сейчас), т.к. для добавления следующего узла нужно проверить предыдущие, чтобы исключить дубли. Красно-черные деревья в этом деле очень помогли.
    – Isaev
    25 апр 2020 в 6:36
2

На всякий случай, ручная сортировка массива из 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);
}
1
  • Благодарю Прочитал, можно и тут почистить 25 апр 2020 в 12:43
2

Такая проверка делает то что вам надо, по крайней мере если все числа целые от 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))

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

2
  • Да, всё правильно, от 1 до 7 её вполне хватает, сделал обзор трёх проверок в своём ответе, там этот вариант тоже есть
    – Isaev
    15 янв 2020 в 14:22
  • До 7 - вроде да, а вообще - нет. 1 5 8 и 2 2 10. Среди чисел до 100 есть 6787 групп, содержащих более одного набора. Вот код: res = new Map(); for (q=1; q<100; ++q) for (w=q; w<100; ++w) for (e=w; e<100; ++e) s = `${q*w*e} ${q+w+e}`, res.has(s) ? res.get(s).push([q,w,e]) : res.set(s, [[q,w,e]]); [...res.values()].filter(x => x.length>1);
    – Qwertiy
    17 янв 2020 в 8:20
0

Для случая сильно ограниченного набора значений, можно просто подобрать хеш-функцию, так чтобы небыло коллизий. Поскольку мы свертываем 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;

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.