Почему большее количество обращений к массиву будет работать лучше?

Я прохожу курс на coursera, который использует minizinc. В одном из заданий я вечно крутил колеса, потому что моя модель не работала достаточно хорошо на скрытом тестовом примере. Я наконец решил это, изменив следующие типы доступа в моей модели

из

constraint sum(neg1,neg2 in party where neg1 < neg2)(joint[neg1,neg2]) >= m;

to

constraint sum(i,j in 1..u where i < j)(joint[party[i],party[j]]) >= m;

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

Разное. Подробности:

  • party - это массив переменных enum
  • набор индексов стороны 1..real_u
  • каждый элемент в party должен быть уникальным, за исключением фиктивной переменной.
  • решатель был Gecode
  • проверка моей модели проводилась на сервере coursera, поэтому я не знаю, какой уровень оптимизации использовал их компилятор.

edit: Поскольку minizinc (mz) является декларативным языком, я понимаю, что «доступ к массиву» в mz не обязательно имеет прямое следствие в императивном языке. Однако для меня эти две строки семантически означают одно и то же. Итак, я предполагаю, что мой вопрос больше: "Почему указанные выше строки семантически различаются в mz?"

edit2: Мне пришлось изменить рассматриваемый пример, я был на грани нарушения кодекса чести Coursera.


constraint-programming minizinc
person Jack    schedule 08.11.2019    source источник
comment
Я не уверен, поделится ли это FlatZinc или нет. Я не умею читать ФЗ, но я посмотрю и поделюсь ФЗ. Это входит в курс «Базовое моделирование для дискретной оптимизации», и это задание 2. Я получил ответ от профессора, он дал короткий ответ, в котором по сути говорилось, что компилятор mz использует оптимизацию во втором случае, но не в первом.   -  person Jack    schedule 08.11.2019
comment
Я видел его ответ. Было бы неплохо взглянуть задним числом на эту более эффективную форму.   -  person Patrick Trentin    schedule 08.11.2019

Ответы (1)


arrow_upward
1
arrow_downward

Разница заключается в способе вычисления предложения where «a‹ b ». Когда «a» и «b» являются параметрами, то компилятор уже может исключить несущественные части суммы во время компиляции. Если «a» или «b» - переменная, то это обычно не может быть решено во время компиляции, и решатель получит более сложное ограничение.

В этом случае решающая программа получила бы сумму по «array [int] of var opt int», что означает, что некоторые переменные в массиве на самом деле могут не присутствовать. Для большинства решателей это переписывается в сумму, где каждая переменная умножается на логическую переменную, что истинно, если переменная присутствует. Вы можете понять, насколько это менее эффективно, чем обычная сумма без умножения.

person Dekker1    schedule 09.11.2019