Ну, я просил время работы 5 сообщений назад.
Я не знаю C#, чтобы не разбираться и оценить алгоритм, хорошо было бы понять хоть что-то про время. Я много раз встречал ситуацию, когда «умный велосипед» работает в 100 раз медленнее обычного.
Пришлось разобраться с запуском C#.
Сделал везде 100000 вызовов без вывода в консоль.
На одну итерацию у меня получается:
C# — 0.1013ms
cPython — 0.6469ms
PyPy — 0.1005ms
Rust — 0.0269ms (клон python-решения)
Вот теперь понятен масштаб и уже интересно, до чего можно оптимизировать.
Только вот лучше на доске 12×12 или 14×14. Иначе получается сравнение 0-1ms и 0-1ms.
Так я вообще о другом.
Более эффективный алгоритм на Python'е может быть в 100 раз быстрее неудачного алгоритма на C++ с intrinsic'ами и чем угодно.
ИМХО, ваша реализация неудачная, и даже версия на C++ не обгонит Python.
А на большие доски она вообще очень тяжело масштабируется. А pypy обсчитывает доску 14х14 за 2 секунды.
Какой смысл в «распределить на множестве ядер/процессоров» и «и видюху сунуть и в FPGA», если нормальный алгоритм на одном ядре на тормозном питоне с доской 8×8 работает за 0.650мс?
Запустил ваш код вот здесь, получается 30мс, что в 10 раз медленнее питона на том же onlinegdb.
Уж не знаю, что вы там оптимизировали, но получилось медленно.
Ну ок, для доски 8×8 у вас какое время работы?
Просто битовая «магия» (когда она не нужна сама по себе) хорошо работает, когда чисел много и они не лезут в кеш процессора. Тогда битовые маски, сжатие и т.п. отлично работают. Здесь же хоть и перебор большой, но чисел и bool'ов в любой момент очень мало.
Что-то у вас получилось очень сложно. Обычный перебор с возвратом работает здесь очень хорошо: идём по столбцам, храним позиции ферзей в предыдущих столбцах, а также занятые строки и диагонали. Бонусом в первом столбце ферзя ставим только в верхней половине доски, что ускоряет код в два раза.
Код на медленном cPython: доска 8×8 за 0.000655с, доска 12×12 за 0.302с, доска 14×14 за 10 секунд на cPython и за 2 секунды на PyPy.
У вас есть возможность запустить ваш код на досках 12×12? Какое время работы?
Код на питоне
from time import perf_counter
def queens(n, cur_column=None, all_positions=None, pos_in_prev_columns=None, used_rows=None, used_diags1=None, used_diags2=None):
# При стартовом вызове заполняем все необходимые массивы
if cur_column is None:
cur_column = 0
all_positions = [] # Список всех найденных позиций
pos_in_prev_columns = []
used_rows = [False] * n # Список ферзей в предыдущих столбцах (True=занято)
used_diags1 = [False] * (2 * n - 1) # Список занятых диагоналей первого типа
used_diags2 = [False] * (2 * n - 1) # Список занятых диагоналей второго типа
# В первом столбце перебираем только верхнюю половину доски, дальше по симметрии. Ускоряет в 2 раза
if cur_column == 0:
check_rows_in_this_column = (n + 1) // 2
else:
check_rows_in_this_column = n
for row_num in range(check_rows_in_this_column):
# Если горизонталь или диагональ заняты, идём дальше
if used_rows[row_num] or used_diags1[row_num + cur_column] or used_diags2[row_num - cur_column]:
continue
# Если дошли до конца, то это победа!
elif cur_column == n - 1:
all_positions.append(pos_in_prev_columns + [row_num])
# При необходимости добавляем симметричный вариант
if pos_in_prev_columns[0] < n // 2:
all_positions.append([n - 1 - x for x in all_positions[-1]])
else:
# Стандартный перебор с возвратом. Ставим нового ферзя, запускаем рекурсию, откатываемся
used_rows[row_num] = used_diags1[row_num + cur_column] = used_diags2[row_num - cur_column] = True
pos_in_prev_columns.append(row_num)
queens(n, cur_column + 1, all_positions, pos_in_prev_columns, used_rows, used_diags1, used_diags2)
pos_in_prev_columns.pop()
used_rows[row_num] = used_diags1[row_num + cur_column] = used_diags2[row_num - cur_column] = False
return all_positions
n = 8
st = perf_counter()
all_pos = queens(n)
en = perf_counter()
print(f'Всего {len(all_pos)} позиций для доски {n}×{n}')
print('time:', '{:.3}'.format(en - st))
for pos in sorted(all_pos):
print(', '.join('ABCDEFGHIJKLMNOP'[col_n] + str(row_n + 1) for col_n, row_n in enumerate(pos)))
Конечно, будет мешать! Ровно на потребляемую энергию поделить на КПД.
Зато энергия от локомотива с токоприёмником передаётся в вагоны без участия высоковольтных линий! Даже, если локомотив — это паровоз на угле.
Я продлевал подписку Office 365 Family в мае. Было очень непросто (и дорого!) купить ключ для РФ, но купленный ключ без вопросов продлил подписку на год.
Спред зависит от того, работает ли вот-прямо-сейчас обмен валют на московской бирже. Если работает, то спред нормальный (да и вообще можно валюту там менять). Если не работает, у банка значительные риски. Поэтому спред сразу в небеса.
Мне когда-то нужно было регулярно распознавать очень конкретные бумажки: каждый раз там был один и тот же шрифт и очень похожие по сути тексты (списки ФИО на самом деле).
Обучал тессеракт на этом шрифте долго и упорно, но результат был всё равно отстойный.
По сравнению с тем распознаванием, который выдавал API от ABBYY.
В общем задачу пришло по-другому решать, через распознавание русского текста не сработало (у ABBYY тоже хватало ошибок, поэтому подход пришлось отклонить)
Самое смешное (на самом деле нет), то борьба с этим выглядит так:
Суд вынес решение по иску Рособнадзора, ответчик — преподаватель математики из Питера Дмитрий Гущин
Позиции сторон такие:
Гущин: прошу затребовать в ФИПИ задания ЕГЭ-2018, чтобы сверить их со списком утечки и убедиться в том, что до экзамена в интернете были подлинные задания. Прилагаю нотариально заверенные материалы утечки.
Рособрнадзор: категорически против сверки заданий ЕГЭ с заданиями утечки. Рособрнадзор пишет в суд: «указанные в качестве свидетелей лица, не являются разработчиками контрольных измерительных материалов ЕГЭ по математике, соответственно не обладают необходимым объемом информации для пояснения суду тождества опубликованных материалов и контрольных заданий».
Суд счел, что позиция Д.Д.Гущина о совпадении материалов ЕГЭ по математике и химии, выложенных за сутки в сеть, и фактически данных школьникам — является «субъективным мнением», и «доказательствами не подтверждена». Свидетельские показания судья тоже сочла «субъективным мнением». Всё. Сравнить прямо в суде экзаменационные материалы и распечатку утечки судья отказалась.
Другая возможная проблема — это использование IPython ⩾ 7.0 или соответствующего Jupyter. Там уже запущен свой event loop от ipython'а и нельзя создать новый.
Соответственно нужно вызывать первую функцию сразу с await'ом
Мне кажется, что чтобы алгоритм можно было признать «лучшим алгоритмом 20-го века», у него в 20-м веке не должно быть альтернатив.
Скажем ни одна сортировка не подходит: их есть куча «эффективных»: Хоара, слиянием, пирамидальная и т.д.
То же самое с хешированием. Adler-32, FNV-1, PJW-32, MD4, MD5, SHA-1 — их много.
Вот симплекс метод, матричные вычисления, быстрое преобразование Фурье, коды Рида-Соломона, обход в ширину + в глубину, Диффи-Хеллман — в рамках 20-го века (некоторые из них даже и в рамках 21-го) совершенно безальтернативны.
Я не знаю C#, чтобы не разбираться и оценить алгоритм, хорошо было бы понять хоть что-то про время. Я много раз встречал ситуацию, когда «умный велосипед» работает в 100 раз медленнее обычного.
Пришлось разобраться с запуском C#.
Сделал везде 100000 вызовов без вывода в консоль.
На одну итерацию у меня получается:
C# — 0.1013ms
cPython — 0.6469ms
PyPy — 0.1005ms
Rust — 0.0269ms (клон python-решения)
Вот теперь понятен масштаб и уже интересно, до чего можно оптимизировать.
Только вот лучше на доске 12×12 или 14×14. Иначе получается сравнение 0-1ms и 0-1ms.
Более эффективный алгоритм на Python'е может быть в 100 раз быстрее неудачного алгоритма на C++ с intrinsic'ами и чем угодно.
ИМХО, ваша реализация неудачная, и даже версия на C++ не обгонит Python.
А на большие доски она вообще очень тяжело масштабируется. А pypy обсчитывает доску 14х14 за 2 секунды.
Запустил ваш код вот здесь, получается 30мс, что в 10 раз медленнее питона на том же onlinegdb.
Уж не знаю, что вы там оптимизировали, но получилось медленно.
Просто битовая «магия» (когда она не нужна сама по себе) хорошо работает, когда чисел много и они не лезут в кеш процессора. Тогда битовые маски, сжатие и т.п. отлично работают. Здесь же хоть и перебор большой, но чисел и bool'ов в любой момент очень мало.
Код на медленном cPython: доска 8×8 за 0.000655с, доска 12×12 за 0.302с, доска 14×14 за 10 секунд на cPython и за 2 секунды на PyPy.
У вас есть возможность запустить ваш код на досках 12×12? Какое время работы?
Зато энергия от локомотива с токоприёмником передаётся в вагоны без участия высоковольтных линий! Даже, если локомотив — это паровоз на угле.
Включите в браузере «версия для пк» или что-то такое. Почему-то мобильные браузеры не дают сделать сайт мелким.
Да понятно, почему убрали.
Готовятся к признанию. Рисовать как правильно, опасно. Рисовать, как требуют, *&@^* просто.
Вообще позорище, конечно.
Обучал тессеракт на этом шрифте долго и упорно, но результат был всё равно отстойный.
По сравнению с тем распознаванием, который выдавал API от ABBYY.
В общем задачу пришло по-другому решать, через распознавание русского текста не сработало (у ABBYY тоже хватало ошибок, поэтому подход пришлось отклонить)
Суд вынес решение по иску Рособнадзора, ответчик — преподаватель математики из Питера Дмитрий Гущин
Позиции сторон такие:
Гущин: прошу затребовать в ФИПИ задания ЕГЭ-2018, чтобы сверить их со списком утечки и убедиться в том, что до экзамена в интернете были подлинные задания. Прилагаю нотариально заверенные материалы утечки.
Рособрнадзор: категорически против сверки заданий ЕГЭ с заданиями утечки. Рособрнадзор пишет в суд: «указанные в качестве свидетелей лица, не являются разработчиками контрольных измерительных материалов ЕГЭ по математике, соответственно не обладают необходимым объемом информации для пояснения суду тождества опубликованных материалов и контрольных заданий».
Суд счел, что позиция Д.Д.Гущина о совпадении материалов ЕГЭ по математике и химии, выложенных за сутки в сеть, и фактически данных школьникам — является «субъективным мнением», и «доказательствами не подтверждена». Свидетельские показания судья тоже сочла «субъективным мнением». Всё. Сравнить прямо в суде экзаменационные материалы и распечатку утечки судья отказалась.
Полный текст решения суда
Вышестоящие суды оставили этот шедевр в силе.
А каким образом получают подобные изображения от… живых пациентов?
До этого нужно было писать
Другая возможная проблема — это использование IPython ⩾ 7.0 или соответствующего Jupyter. Там уже запущен свой event loop от ipython'а и нельзя создать новый.
Соответственно нужно вызывать первую функцию сразу с await'ом
А чтобы получить текущий event loop —
Скажем ни одна сортировка не подходит: их есть куча «эффективных»: Хоара, слиянием, пирамидальная и т.д.
То же самое с хешированием. Adler-32, FNV-1, PJW-32, MD4, MD5, SHA-1 — их много.
Вот симплекс метод, матричные вычисления, быстрое преобразование Фурье, коды Рида-Соломона, обход в ширину + в глубину, Диффи-Хеллман — в рамках 20-го века (некоторые из них даже и в рамках 21-го) совершенно безальтернативны.