Для обхода всех соседей можно использовать такой код:
r = (-1, 0, 1)
for dx in r:
for dy in r:
if dx or dy:
paint_it_black(x + dx, y + dy)
Можно сделать код лаконичнее (убрав несколько уровней вложенности):
r = (-1, 0, 1)
neighbors = [
(dx, dy)
for dx in r
for dy in r
if dx or dy
]
for dx, dy in neighbors:
paint_it_black(x + dx, y + dy)
Ну и, как мне кажется, самый изящный способ, который можно использовать для любого количества измерений, следующий:
import itertools
dims = 2
neighbors = [
n
for n in itertools.product((-1, 0, 1), repeat=dims)
if any(n)
]
for dx, dy in neighbors:
paint_it_black(x + dx, y + dy)
P.S. во всех трех вариантах можно убрать if ("if dx or dy" и "if any(n)")и тогда будут не только соседи, но и точка (x, y).
neighbors = [n for n in itertools.product((-1, 0, 1), repeat=dims)]
# or
neighbors = list(itertools.product((-1, 0, 1), repeat=dims))
P.P.S. Для ортогональных соседей ((-1, 0), (0, -1), (0, 1), (1, 0)) можно "if any(n)" заменить на "if sum(abs(x) for x in n) == 1" или "sum(map(abs, n)) == 1" (кому что больше нравится), а "if dx or dy" заменить, например, на "if dx + dy in (-1, 1)" или "if abs(dx + dy) == 1":
neighbors = [
n
for n in itertools.product((-1, 0, 1), repeat=dims)
if sum(map(abs, n)) == 1
]
P.P.P.S. Для диагональных соседей ((-1, -1), (-1, 1), (1, -1) и (1, 1)) можно в коде выше заменить (-1, 0, 1) на (-1, 1) и убрать if, так как он будет не нужен.
neighbors = [n for n in itertools.product((-1, 1), repeat=dims)]
# or
neighbors = list(itertools.product((-1, 1), repeat=dims))
Когда я учился в университете нам рассказывали именно такой вариант. Для этого метода матрица не обязательна быть положительно определенной. Когда возникает необходимость извлекать квадратный корень sqrt(x), то извлекается корень из модуля числа sqrt(abs(x)), а диагональный элемент принимает значение знака того числа из модуля которого извлекается корень sign(x). Это существенно расширяет класс "хороших" матриц.
Подскажите, пожалуйста, системы с какими матрицами можно решить методом LDL, которые нельзя решить методом Холецкого (разложение матрицы в виде L*D*L^t, где L нижнетреугольная, D диагональная с +1/-1 на диагонали)?
Библиотека std::ranges основана на библиотеке range-v3, которая работает на C++14 и новее. Поэтому можно эту библиотеку добавить в свой проект. Кроме того, на сколько я помню, в std::ranges вошли не все возможности из range-v3.
Выбранный автором способ обхода для построения перестановки привел к необходимости учитывать множество факторов таких как четность ширины доски, четность номера столбца с нулем. В таком обилии условий легко запутаться.
Про сложность говорить смысла особо нету, так как размер доски небольшой и оба алгоритма отработают мгновенно.
Существует и другой, как мне кажется более простой, способ проверять решаемость головоломки. Заключается он в том, чтобы вычислить некую характеристику для start и для goal и сравнить ее: если характеристика совпала, то существует "путь" от позиции start к позиции goal.
Теперь непосредственно про вычисление характеристики.
1. Необходимо обойти головоломку "змейкой", то есть обойти в следующем порядке:
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13
Данный обход можно обощить на любой размер доски: обходим доску строчку за строчкой, четные (предполагается нумерация с 0) обходим слева направо, нечетные справа налево.
2. Выписать встретившиеся значения фишек, то есть выписать только ненулевые значения ячеек. Полученная набор чисел является перестановкой множества чисел от 1 до 15.
Для приведенного автором статьи примера
12 13 11 2
4 5 3 14
1 9 15 6
8 7 0 10
числа будут выписаны в следующем порядке: 12, 13, 11, 2, 14, 3, 5, 4, 1, 9, 15, 6, 10, 7, 8.
3. Характеристикой является четность описанной в прошлом пункте перестановки. Как посчитать четность? Отсортировать массив, подсчитав количество swap'ов. Четностью перестановки будет четность количества swap'ов.
Какова сложность данного алгоритма?
По памяти: .
По времени: .
P.S. Может возникнуть вопрос почему сложность по времени , а не . Ошибки здесь нету. Все дело в том, что в данной задаче массив имеет специфичный вид и за счет этого его можно отсортировать за линейное время. Кому интересно предлагаю самостоятельно разобраться почему это так, я же просто оставлю код сортировки массива, являющегося перестановкой множества :
for (int i = 0; i < perm.length; i++) {
while (perm[i] != i) {
// swap(a, i, j) меняет местами a[i] и a[j]
swap(perm, i, perm[i]);
}
}
Отмечу, что в отсортированном массиве perm[i] == i для всех i от 0 до perm.length и что именно это свойство является ключевым.
Можно строки заменить на векторы: x = (1, 0, 0), y = (0, 1, 0), z = (0, 0, 1). Либо самому написать простенький класс, либо, например, воспользоваться numpy.
При исполнении байт кода у JVM есть два сценария: 1. интерпретировать байт код; 2. компилировать байт код. В первом случае, как мне кажется, накладные расходы на интерпретацию будут слишком высоки и прироста в скорости работы заметить не получится. Во втором же случае происходит ровно тоже, что и в случае С++, поэтому ускорение должно наблюдаться.
Где-то я читал, что начиная с какой-то версии JVM всегда компилирует байт код. Мог не так понять. В любом случае, желательно код перед бенчмарками "прогреть", то есть выполнить многократный вызов функции с кодом, чтобы вызвать срабатывание механизма компиляции.
Еще, на сколько мне известно, JVM может обнаружить, что один и тот же код выполняется в цикле и оптимзировать это. Поэтому, возможно, придется как-то аккуратно запускать бенчмарк.
На ubuntu, как и на большинство дистрибутивов легко можно накатить другое окружение рабочего стола. Или сразу скачать версию с другим окружением рабочего стола: ubuntu - gnome, xubuntu - xfce, kubuntu - kde, ubuntu mate - mate и т.д. Для fedora есть fedora spins (xfce, kde, mate, etc.).
Понял. А пробовали ли Вы использовать предобуславливатели? На моей практике без предобуславливания методы ведут себя не очень хорошо.
Можно добавить проверку в духе
где w - ширина области, h - высота
Для обхода всех соседей можно использовать такой код:
Можно сделать код лаконичнее (убрав несколько уровней вложенности):
Ну и, как мне кажется, самый изящный способ, который можно использовать для любого количества измерений, следующий:
P.S. во всех трех вариантах можно убрать if ("if dx or dy" и "if any(n)")и тогда будут не только соседи, но и точка (x, y).
P.P.S. Для ортогональных соседей ((-1, 0), (0, -1), (0, 1), (1, 0)) можно "if any(n)" заменить на "if sum(abs(x) for x in n) == 1" или "sum(map(abs, n)) == 1" (кому что больше нравится), а "if dx or dy" заменить, например, на "if dx + dy in (-1, 1)" или "if abs(dx + dy) == 1":
P.P.P.S. Для диагональных соседей ((-1, -1), (-1, 1), (1, -1) и (1, 1)) можно в коде выше заменить (-1, 0, 1) на (-1, 1) и убрать if, так как он будет не нужен.
Почему выбор пал на точный метод вместо итерационного? Разве не будет расход памяти огромный?
Когда я учился в университете нам рассказывали именно такой вариант. Для этого метода матрица не обязательна быть положительно определенной. Когда возникает необходимость извлекать квадратный корень sqrt(x), то извлекается корень из модуля числа sqrt(abs(x)), а диагональный элемент принимает значение знака того числа из модуля которого извлекается корень sign(x). Это существенно расширяет класс "хороших" матриц.
Подскажите, пожалуйста, системы с какими матрицами можно решить методом LDL, которые нельзя решить методом Холецкого (разложение матрицы в виде L*D*L^t, где L нижнетреугольная, D диагональная с +1/-1 на диагонали)?
Пробовали ли Вы flatpack или snap? Какие были недостатки с ними?
Еще так можно:
Вместо
user_last_photo_timeможно использоватьbot.user_data, см. https://github.com/python-telegram-bot/python-telegram-bot/wiki/Storing-bot%2C-user-and-chat-related-data. Это словарь, который python-telegram-bot создает для каждого пользователя и предоставляет к нему доступ.Библиотека std::ranges основана на библиотеке range-v3, которая работает на C++14 и новее. Поэтому можно эту библиотеку добавить в свой проект. Кроме того, на сколько я помню, в std::ranges вошли не все возможности из range-v3.
Ссылка: https://github.com/ericniebler/range-v3
Что обозначает буква k в именах перечислений?
Ты осторожнее с вопросами, вдруг нас ждет еще один пост с ответом именно на этот вопрос))
Выбранный автором способ обхода для построения перестановки привел к необходимости учитывать множество факторов таких как четность ширины доски, четность номера столбца с нулем. В таком обилии условий легко запутаться.
Про сложность говорить смысла особо нету, так как размер доски небольшой и оба алгоритма отработают мгновенно.
Что-то я накосячил с оформлением формул в пост скриптуме. Я хотел написать ".. O(mn), а не O(mn log(mn))".
Существует и другой, как мне кажется более простой, способ проверять решаемость головоломки. Заключается он в том, чтобы вычислить некую характеристику для start и для goal и сравнить ее: если характеристика совпала, то существует "путь" от позиции start к позиции goal.
Теперь непосредственно про вычисление характеристики.
1. Необходимо обойти головоломку "змейкой", то есть обойти в следующем порядке:
Данный обход можно обощить на любой размер доски: обходим доску строчку за строчкой, четные (предполагается нумерация с 0) обходим слева направо, нечетные справа налево.
2. Выписать встретившиеся значения фишек, то есть выписать только ненулевые значения ячеек. Полученная набор чисел является перестановкой множества чисел от 1 до 15.
Для приведенного автором статьи примера
числа будут выписаны в следующем порядке: 12, 13, 11, 2, 14, 3, 5, 4, 1, 9, 15, 6, 10, 7, 8.
3. Характеристикой является четность описанной в прошлом пункте перестановки. Как посчитать четность? Отсортировать массив, подсчитав количество swap'ов. Четностью перестановки будет четность количества swap'ов.
Какова сложность данного алгоритма?
По памяти:
.
По времени:
.
P.S. Может возникнуть вопрос почему сложность по времени![]()
, а не 
. Ошибки здесь нету. Все дело в том, что в данной задаче массив имеет специфичный вид и за счет этого его можно отсортировать за линейное время. Кому интересно предлагаю самостоятельно разобраться почему это так, я же просто оставлю код сортировки массива, являющегося перестановкой множества 
:
Отмечу, что в отсортированном массиве perm[i] == i для всех i от 0 до perm.length и что именно это свойство является ключевым.
Можно строки заменить на векторы: x = (1, 0, 0), y = (0, 1, 0), z = (0, 0, 1). Либо самому написать простенький класс, либо, например, воспользоваться numpy.
При исполнении байт кода у JVM есть два сценария: 1. интерпретировать байт код; 2. компилировать байт код. В первом случае, как мне кажется, накладные расходы на интерпретацию будут слишком высоки и прироста в скорости работы заметить не получится. Во втором же случае происходит ровно тоже, что и в случае С++, поэтому ускорение должно наблюдаться.
Где-то я читал, что начиная с какой-то версии JVM всегда компилирует байт код. Мог не так понять. В любом случае, желательно код перед бенчмарками "прогреть", то есть выполнить многократный вызов функции с кодом, чтобы вызвать срабатывание механизма компиляции.
Еще, на сколько мне известно, JVM может обнаружить, что один и тот же код выполняется в цикле и оптимзировать это. Поэтому, возможно, придется как-то аккуратно запускать бенчмарк.
На ubuntu, как и на большинство дистрибутивов легко можно накатить другое окружение рабочего стола. Или сразу скачать версию с другим окружением рабочего стола: ubuntu - gnome, xubuntu - xfce, kubuntu - kde, ubuntu mate - mate и т.д. Для fedora есть fedora spins (xfce, kde, mate, etc.).
В некоторых случаях будет достаточно отслеживать не дату пуша коммита, а дату сборки проекта. Для этих целей есть макросы DATE и TIME:
Безопасный компьютер -- выключенный компьютер =)