Затрудняюсь тут ответить про 3D. Следующим уровенем оптимизации перебора - будут паттерны. Я пытался знакомых озадачить, по каким критериям первая картинка в статье не имеет дальнейшего решения, не рассматривая вариантов дальнейшего перебора. Пока мне никто не смог дать логичного ответа. А он - есть. Постановка ферзей на A1+B3+C5 не имеет дальнейшего решения, в этой комбинации уже имеется стоп-сигнал.
Это означает - что, смотрят, но не видят. Интуиция видимо срабатыаает, только тогда, когда мозг хорошо натренирован.
Выбор языка для статьи определялся способностью программисткой аудитории читать код. Мой листинг на C# спокойно будет читаться программистами: С#, С++, Java С некоторым напрягом будет доступен программистам: JS, Typescript, AS3 А вот исходники на C++ читаются труднее и заранее отторгаются к прочтению широкой аудиторией.
Лично мне проще всё писать сразу на SystemC))) Сразу удаляется куча заморочек и шаманские танцы с бубном
Я пытался объяснить в комментариях под этой статьей, почему я выбрал C# и почему работаю на стандартной доске 8x8.
Если бы я начал делать, как говорите/предлагаете Вы, то сложность бы листинга многократно возросла, что привело бы читателя к "закипанию мозгов". И в таком формате "лишь только немногие" могут прочитать код. А дальше - будет ещё намного сложнее.
Я выбрал формат для наиболее популярного изложения замысла и реализации. Естественно в итоге я построю реализацию на C++ с интринсиками и в том числе для разноразмерных досок.
Из-за ограниченности процессорных инструкций приходится прибегать к различным ухищрениям и дополнением, которые даны в новом алгоритме.
Тут все предельно упростилось бы при помощи FPGA на простейшей и элементарной перекоммутации сигналов (Массово переставить биты в числах), но обычный читатель наверно этого бы не понял.
И дальше будут продолжения по теме "оптимизации перебора". Так как акцент именно на оптимизации/отсечении!
1. У меня не осталось полного перебора. Я ввел первичный позиционный анализ. И число переборов значительно сократилось. Я прерываю перебор и делаю реверс-шаги по доске. Реверс-шаг это установка ферзя в единственно возможную позицию на доске. И я обнаруживаю такие ситуации на столбцах и строках. и это собственно моё нововведение/ноухау. Я прерываю линейное прохождение и это отображается в переменной reverse_count. А при помощи 64-разрядной арифметики и SIMD-стиля я делаю это очень быстро. Реверс-ситуация уже может случиться после установки 3-го ферзя. Уже первых три ферзя своими атаками могут образовать строку или столбец, куда можно поставить только одного ферзя.
2. Мои переменные работают в SIMD-стиле. И довольно странно слышать утверждение о том, что они не будут работать на повышенной мерности. Это практически, аналогично как работают MMX/SSE. А они и создавались для обработки больших векторов
Супер-мерности - это доски с очень большим размером. Я только это и имел ввиду. Например 1000x1000
Доска с размером 27 - уже имеет 234,907,967,154,122,528 решений
Вроде и возраст у вас солидный, но каждое высказывание - АХИНЕЯ. Как будто вы сюда потроллить зашли. Абсолютно во всем царит упоротое непонимание. Вы не видите, что написано и сделано. Вы придумываете себе тезисы - и с ними и проводите спор. Ну а я то, тут причём спрашивается. Спорьте сам-с-собой в другом месте.
На доске 8x8 я хотел изложить концепты. Оптимизации будут работать и на досках другой мерности. Но код будет достаточно огромный, чтобы его размещать в статье. Неужели - это непонятно? Я уже изъял из кода много вещей для статьи, чтобы не загромождать концепт и был подвержен различным замечаниям и полезным советам.
Для других мерностей потребуется кластеризация арифметики. Можно оптимизировать по быстродействию определенные из них. Но данная задача настолько синтетическая и не приносящая практической пользы, что непонятно зачем устраивать вообще весь этот трудоёмкий цирк.
Для супер-мерностей можно прибегнуть к распараллеливанию, шейдерам, FPGA. Только объясните, зачем весь этот балаган нужен?
Эффектов SIMD-байт-вектора хватит до мерности N=127. Для мерностей некратных 8-ми потребуется просто прибавить довесок к числу. Дальше идет переход на слова(2 байта).
Ну... трудно что-либо сказать, если Вы "по памяти" говорите. За основу и меня взята установка ферзей в не угрожающие позиции. Это 2056 вариантов перебора. Я добавил в алгоритм позиционный анализ, что сократило число шагов перебора до 592. Если первого ферзя двигать в пределах [A1-A4] - это 592 / 2 = 296. Все атаки фиксируются битами в 64-битном числе.
Тест выполнения дает 0мс на процессоре от 2011 года. Было бы интересно, если бы восстановили свой алгоритм.
В чём эффективность Вашего алгоритма? В лобовом переборе? В маркировке атак, через массив? Я маркирую атаки в ЕДИНОМ 64-битном числе и не затрачиваюсь на циклы для установки/снятия атак во время выполнения алгоритма.
Дождитесь версии на C++ пожалуйста, прежде чем делать выводы. Я много раз повторил уже - это прототип для ознакомления с логикой. Я планировал 3 публикации сделать, на эту тему.
Не может язык с динамической типизацией (Python) работать быстрее, чем алгоритм, где каждая операция представляется соответствующей инструкцией процессора, да еще и однотактной или полутактной(U+V Pipes). Исходник на C++ будет по завершению статьи.
Это потому-что, алгоритм нацелен на C/C++ с применением intrinsic и forceinline. Здесь в статье дан прототип на C#. В этом прототипе идут вызовы функций, которые выделены намеряно демонстративно! Для лучшего понимания читателем.
Каким образом буферизируется вывод на консоль C# и Python? А это время не зависящее от работы алгоритма. Для правильных замеров надо в тестах убирать вывод на консоль. Надо делать оптимизацию "A1-A4". Надо убирать лишние вызовы функций. Надо делать 1000-кратные вызовы алгоритма, и в моем случае не вызывать постоянно функцию init().
Когда я говорил про видюху и FPGA - то естественно подразумевались решения на доске типа 1000x1000 и более.
Я по своему огромному опыту знаю, что на C/C++ - всё будет очень угарно. А ведь задачу можно еще и распределить на множестве ядер/процессоров. Можно её и видюху сунуть и в FPGA. Так что вопрос замера скорости у меня пока не возникал.
Еще раз, - первоочередная цель - "оптимизация перебора". И демонстрация целочисленной арифметики, как средства наилучшей реализации по-скорости.
Получилось у меня достаточно просто, для людей разбирающихся в целочисленной арифметике. Ведь я ввел в алгоритм первичный позиционный анализ.
Целью исследования является сокращения числа переборов, так называемая "оптимизация перебора". Также целью публикации является акцентировать внимание читателя на так называемой "битовой магии". Битовой магией владе/ли/ют достаточно известные личности - Брезенхем, Кармак, Абраш...
Я не закончил еще с оптимизацией 8×8. Я на данный вижу несколько новых возможностей для оптимизации перебора.
Как закончу исследования переключусь на доски других размерностей. Для этого просто потребуется кластеризация 64-битной арифметики на N-битную. Ожидается стократный выигрыш перед Pyton (как минимум), ведь все состоит из элементарных процессорных инструкций с минимумом обращений по памяти.
Я это знаю. И в первом наброске - это присутствовало (A1-A4). Я удалил этот код. Кол-во переборов по схеме A1-A4 равняется 592/2=296 по алгоритму 1а. Я достиг своего начального предположения, что кол-во шагов перебора не будет превышать 300. Теперь надо постараться снизить и это количество
Увы! Мне не удалось подключить BitOperations на момент написания прототипа. Итоговый вариант будет дополнительно сопровождаться исходником на MS C++. Я выбрал C# для быстрого прототипирования. На данный момент, код уже подвергся сильной модифакации, по сравнению с данным исходником.
BSR-инструкция - не заменяет обычный цикл! Я привел прототип на 64-битной арифметике. Примерно также, BSR-инструкция реализована на вентилях процессора (развернутый цикл из 6 операций)
Со smart_check так сделано по причине, чтобы не усугублять вложенность блоков (отступ) для демо-примера. По идее нужны две функции с "классикой" и моей оптимизацией. Учту при последующих продолжениях
Информация
В рейтинге
Не участвует
Откуда
Москва, Москва и Московская обл., Россия
Дата рождения
Зарегистрирован
Активность
Специализация
Фулстек разработчик, Архитектор программного обеспечения
Затрудняюсь тут ответить про 3D. Следующим уровенем оптимизации перебора - будут паттерны. Я пытался знакомых озадачить, по каким критериям первая картинка в статье не имеет дальнейшего решения, не рассматривая вариантов дальнейшего перебора. Пока мне никто не смог дать логичного ответа. А он - есть. Постановка ферзей на A1+B3+C5 не имеет дальнейшего решения, в этой комбинации уже имеется стоп-сигнал.
Это означает - что, смотрят, но не видят. Интуиция видимо срабатыаает, только тогда, когда мозг хорошо натренирован.
Выбор языка для статьи определялся способностью программисткой аудитории читать код.
Мой листинг на C# спокойно будет читаться программистами: С#, С++, Java
С некоторым напрягом будет доступен программистам: JS, Typescript, AS3
А вот исходники на C++ читаются труднее и заранее отторгаются к прочтению широкой аудиторией.
Лично мне проще всё писать сразу на SystemC)))
Сразу удаляется куча заморочек и шаманские танцы с бубном
Я пытался объяснить в комментариях под этой статьей, почему я выбрал C# и почему работаю на стандартной доске 8x8.
Если бы я начал делать, как говорите/предлагаете Вы, то сложность бы листинга многократно возросла, что привело бы читателя к "закипанию мозгов". И в таком формате "лишь только немногие" могут прочитать код. А дальше - будет ещё намного сложнее.
Я выбрал формат для наиболее популярного изложения замысла и реализации. Естественно в итоге я построю реализацию на C++ с интринсиками и в том числе для разноразмерных досок.
Из-за ограниченности процессорных инструкций приходится прибегать к различным ухищрениям и дополнением, которые даны в новом алгоритме.
Тут все предельно упростилось бы при помощи FPGA на простейшей и элементарной перекоммутации сигналов (Массово переставить биты в числах), но обычный читатель наверно этого бы не понял.
И дальше будут продолжения по теме "оптимизации перебора".
Так как акцент именно на оптимизации/отсечении!
https://habr.com/ru/post/679738/
Не вникнув в первую версию реализации, еще труднее вникнуть в версию 1a
Вы абсолютно невнимательно смотрели!
1. У меня не осталось полного перебора. Я ввел первичный позиционный анализ. И число переборов значительно сократилось. Я прерываю перебор и делаю реверс-шаги по доске. Реверс-шаг это установка ферзя в единственно возможную позицию на доске. И я обнаруживаю такие ситуации на столбцах и строках. и это собственно моё нововведение/ноухау. Я прерываю линейное прохождение и это отображается в переменной reverse_count. А при помощи 64-разрядной арифметики и SIMD-стиля я делаю это очень быстро. Реверс-ситуация уже может случиться после установки 3-го ферзя. Уже первых три ферзя своими атаками могут образовать строку или столбец, куда можно поставить только одного ферзя.
2. Мои переменные работают в SIMD-стиле. И довольно странно слышать утверждение о том, что они не будут работать на повышенной мерности. Это практически, аналогично как работают MMX/SSE. А они и создавались для обработки больших векторов
Супер-мерности - это доски с очень большим размером. Я только это и имел ввиду. Например 1000x1000
Доска с размером 27 - уже имеет 234,907,967,154,122,528 решений
Вроде и возраст у вас солидный, но каждое высказывание - АХИНЕЯ. Как будто вы сюда потроллить зашли. Абсолютно во всем царит упоротое непонимание. Вы не видите, что написано и сделано. Вы придумываете себе тезисы - и с ними и проводите спор. Ну а я то, тут причём спрашивается. Спорьте сам-с-собой в другом месте.
На доске 8x8 я хотел изложить концепты. Оптимизации будут работать и на досках другой мерности. Но код будет достаточно огромный, чтобы его размещать в статье. Неужели - это непонятно? Я уже изъял из кода много вещей для статьи, чтобы не загромождать концепт и был подвержен различным замечаниям и полезным советам.
Для других мерностей потребуется кластеризация арифметики. Можно оптимизировать по быстродействию определенные из них. Но данная задача настолько синтетическая и не приносящая практической пользы, что непонятно зачем устраивать вообще весь этот трудоёмкий цирк.
Для супер-мерностей можно прибегнуть к распараллеливанию, шейдерам, FPGA. Только объясните, зачем весь этот балаган нужен?
Эффектов SIMD-байт-вектора хватит до мерности N=127. Для мерностей некратных 8-ми потребуется просто прибавить довесок к числу. Дальше идет переход на слова(2 байта).
Ну... трудно что-либо сказать, если Вы "по памяти" говорите. За основу и меня взята установка ферзей в не угрожающие позиции. Это 2056 вариантов перебора. Я добавил в алгоритм позиционный анализ, что сократило число шагов перебора до 592. Если первого ферзя двигать в пределах [A1-A4] - это 592 / 2 = 296. Все атаки фиксируются битами в 64-битном числе.
Тест выполнения дает 0мс на процессоре от 2011 года. Было бы интересно, если бы восстановили свой алгоритм.
Вы меня порядком вымучили сегодня! 0-1мс у меня на процессоре от 2011 года. Вывод в консоль отключен. Перестаньте уже пожалуйста!
В чём эффективность Вашего алгоритма? В лобовом переборе? В маркировке атак, через массив? Я маркирую атаки в ЕДИНОМ 64-битном числе и не затрачиваюсь на циклы для установки/снятия атак во время выполнения алгоритма.
Дождитесь версии на C++ пожалуйста, прежде чем делать выводы. Я много раз повторил уже - это прототип для ознакомления с логикой. Я планировал 3 публикации сделать, на эту тему.
Не может язык с динамической типизацией (Python) работать быстрее, чем алгоритм, где каждая операция представляется соответствующей инструкцией процессора, да еще и однотактной или полутактной(U+V Pipes). Исходник на C++ будет по завершению статьи.
Это потому-что, алгоритм нацелен на C/C++ с применением intrinsic и forceinline. Здесь в статье дан прототип на C#. В этом прототипе идут вызовы функций, которые выделены намеряно демонстративно! Для лучшего понимания читателем.
Каким образом буферизируется вывод на консоль C# и Python? А это время не зависящее от работы алгоритма. Для правильных замеров надо в тестах убирать вывод на консоль. Надо делать оптимизацию "A1-A4". Надо убирать лишние вызовы функций. Надо делать 1000-кратные вызовы алгоритма, и в моем случае не вызывать постоянно функцию init().
Когда я говорил про видюху и FPGA - то естественно подразумевались решения на доске типа 1000x1000 и более.
Я по своему огромному опыту знаю, что на C/C++ - всё будет очень угарно. А ведь задачу можно еще и распределить на множестве ядер/процессоров. Можно её и видюху сунуть и в FPGA. Так что вопрос замера скорости у меня пока не возникал.
Еще раз, - первоочередная цель - "оптимизация перебора". И демонстрация целочисленной арифметики, как средства наилучшей реализации по-скорости.
Получилось у меня достаточно просто, для людей разбирающихся в целочисленной арифметике. Ведь я ввел в алгоритм первичный позиционный анализ.
Целью исследования является сокращения числа переборов, так называемая "оптимизация перебора". Также целью публикации является акцентировать внимание читателя на так называемой "битовой магии". Битовой магией владе/ли/ют достаточно известные личности - Брезенхем, Кармак, Абраш...
Я не закончил еще с оптимизацией 8×8. Я на данный вижу несколько новых возможностей для оптимизации перебора.
Как закончу исследования переключусь на доски других размерностей. Для этого просто потребуется кластеризация 64-битной арифметики на N-битную. Ожидается стократный выигрыш перед Pyton (как минимум), ведь все состоит из элементарных процессорных инструкций с минимумом обращений по памяти.
Я это знаю. И в первом наброске - это присутствовало (A1-A4). Я удалил этот код. Кол-во переборов по схеме A1-A4 равняется 592/2=296 по алгоритму 1а.
Я достиг своего начального предположения, что кол-во шагов перебора не будет превышать 300. Теперь надо постараться снизить и это количество
Увы! Мне не удалось подключить BitOperations на момент написания прототипа. Итоговый вариант будет дополнительно сопровождаться исходником на MS C++. Я выбрал C# для быстрого прототипирования. На данный момент, код уже подвергся сильной модифакации, по сравнению с данным исходником.
Уже есть второй шаг. Надо аккуратно его прописать. Кол-во переборов и реверсов - снизилось ещё
solution_count = 92
solve_count = 592
reverse_count = 622
Надеюсь будет и 3-й шаг. Заключительный, так сказать
BSR-инструкция - не заменяет обычный цикл! Я привел прототип на 64-битной арифметике. Примерно также, BSR-инструкция реализована на вентилях процессора (развернутый цикл из 6 операций)
Со
smart_check так сделано по причине, чтобы не усугублять вложенность блоков (отступ) для демо-примера. По идее нужны две функции с "классикой" и моей оптимизацией. Учту при последующих продолжениях