Да вы правы, задача имеет не мало подводных камней, в основном связанных с точностью вычислений. Например, такая казалось бы тривиальная проблема, как определение принадлежности точки прямой, становится не однозначной при работе с числами с плавающей точкой. В случае целочисленных вычислений возникают свои трудности, например, в вопросе: определения точки пересечения отрезков (0, 0)-(4, 0) и (1, -2)-(2, 2)? Это (1, 0) или (2, 0)? Оба этих решения не лежат на обоих отрезках, что приводит к искажению изначальной картины.
Однако, несмотря на сложности, эти проблемы можно решить, если принять ряд условностей. В этой статье я сознательно опустил ряд сложных деталий, чтобы сфокусироваться на основной концепции. Но, судя по вашему интересу и комментариям, тема действительно заслуживает продолжения.
А разве есть возможность модифицировать данные «на месте». Данные в векторе лежат линейно, физически не получится положить что то большее, в теории можно положить что-то равное либо меньшее. Если с чем то равным профит реален, то с меньшим уже вопрос. Вся эта магия с переразметкой памяти уже относится к хакам и этому нет места в стандартной библиотеке.
А по filter, есть еще retain - оставляет то что нужно в текущей коллекции сохраняя порядок, но требует линейной памяти [bool].
При использование f64 вероятность вырожденных случаев снижается, но не исключает их. Проблема в том, что вырожденные случаи если их правильно не обработать приводят к неправильной логике алгоритма, а это может повлечь за собой не только не правильный результат, но и зацикливание или краш.
Я как раз тоже последние лет 5 увлекаюсь вычислительной геометрией. И за последний год написал библиотеку для вычисления результатов пересечения многоугольников: xor, union, intersection and difference. Первое время пытаешься решать задачу (как и автор статьи) во float числах. Через какое-то время приходит осознание, что из-за потери точности задача в принципе не разрешима в общем случаи. С переходом на int появляется детерминизм и становится сильно проще. Например, параллельность отрезков можно проверять через векторное произведение и тд. С float такие фокусы не проходят. Введение epsilon не спасает, а только маскирует проблему. С вашего позволения оставлю ссылку на свою имплементацию на https://github.com/iShape-Rust/iOverlay и https://github.com/iShape-Swift/iOverlay
Программирование это сложно. Людей, которые хотят гораздо больше, тех которые могут. Старайтесь делиться своим временем и энергией с людьми которые потенциально могут. А тем кто не годится можно попробовать показать подводные камни и трудности профессии. Вопрос в том кто потенциально может? На мой взгляд дело не только в складе ума, а в большей степени желании и усердии человека. Программирование для усидчивых.
Ирония судьбы: WebAssembly был создан для ускорения кода в браузерах, а теперь мы движемся к тому, чтобы компилировать JavaScript обратно в WebAssembly!
С осени работаю в индийском стартапе. И работая в их коллективе не заметил большой разницы, уровень их навыков разработки вполне современный и подход тоже. Все шутки про индуский код вдруг стали не актуальны. Английским они хорошо владеют, ниже уровня B2 в коллективе никого нет. Что самое забавное стартап занимается разработкой CAD системы для проектирования микрочипов. Основным клиентом которого являются крупнейшие университеты Индии. Так что Индия в скором времени сама начнет проектировать и производить чипы. Решил поделится поскольку сам был удивлен от всего этого.
Всех кому интересна компьютерная графика и кто устал просто решать задачи, предлагаю принять участие в одном из своих проектов. Например https://github.com/iShape-Rust/iShape-js
Уверен так гораздо интереснее чем просто решать задачи. Сам попробовал rust меньше года назад
Выглядит итерессно, решил попробовать, но на macOS 13.5.1(intel) не запустился (ffmpeg установил). Вышла ошибка что файл поврежден давай перемещай в корзину. Может сходу знаете в чем проблема? И еще вопрос на виртуалке заработает? Решил попробовать на Ubuntu.
Спасибо за статью, раньше тоже много раз пробовал силы в этой задаче, правда меня манило точное решение. Но ваша статья навеяла интересные мысли. Очень уж много времени отнимает эта задача боюсь если честно возвращаться.
Только при делении-сдвиге вправо отрицательных чисел надо быть аккуратнее. Попробуйте сдвинуть вправо -1. Для остальных чисел к слову все правильно получается
10 июня сделал swift перевод на сумму 115k через 2 часа мне написали, что бы я обосновал происхождения денег. Я БЫЛ клиентом банка около месяца. Переводил им деньги с Альфабанк, поэтому я скинул им выписку со счетов в Альфе за год. Скинул им выписки в течении 10 минут после их просьбы. Спустя 10 минут меня заблокировали по п 4.5 и 7.3.9. Больше ни сказали не слова по причине блокировки. Не большая сумма порядка 2.7k оставалась в валюте ее сказали что конвертируют в рубли по своему курсу и вышлют мне на мой счёт в другой банк. Я предложил забрать деньги наличными в рублях по курсу цб. Они попросили время порядка 4 дней, после чего просто поступил отказ. Заявление в цб я написал уже 12 июня, пока ответа нет. Здесь очевидно не желание банка проводить эти переводы, поэтому они будут предотвращать это любыми методами.
Если на руках уже есть готовое решение его всегда можно попытаться оптимизировать убрав так называемые «пересечения». Посмотрите работу алгоритма Bitonic tour. Этот алгоритм итерационный и с каждой перестановкой он приближается к максимально эффективному решению. Конечно он тоже неимоверно медленный, но как минимум до какого-то шага его можно прогнать.
А динамическое программирование для такого числа городов уже не подходит потому что, требует экспоненциального количества памяти. Я сейчас сам увлечен этой задачей и у меня есть пара оригинальных решений на github, но моя цель не столь амбициозна я поставил себе планку в 64 города.
И да хотелось бы услышать больше деталей вашей реализации, спасибо.
Спасибо, кажется, что вы хорошо разбираетесь.
А подскажите еще, пожалуйста, на что влияет количество кубитов в таком компьютере? Интуитивно мне кажется, что например для NP полных задач число кубитов не должно быть меньше N. Если конечно не учитывать тот факт, что можно разбить на под-задачи.
Да вы правы, задача имеет не мало подводных камней, в основном связанных с точностью вычислений. Например, такая казалось бы тривиальная проблема, как определение принадлежности точки прямой, становится не однозначной при работе с числами с плавающей точкой. В случае целочисленных вычислений возникают свои трудности, например, в вопросе: определения точки пересечения отрезков (0, 0)-(4, 0) и (1, -2)-(2, 2)? Это (1, 0) или (2, 0)? Оба этих решения не лежат на обоих отрезках, что приводит к искажению изначальной картины.
Однако, несмотря на сложности, эти проблемы можно решить, если принять ряд условностей. В этой статье я сознательно опустил ряд сложных деталий, чтобы сфокусироваться на основной концепции. Но, судя по вашему интересу и комментариям, тема действительно заслуживает продолжения.
https://github.com/gfx-rs/wgpu WGPU под Rust забыли. Сам ей пользовался, очень популярна.
А разве есть возможность модифицировать данные «на месте». Данные в векторе лежат линейно, физически не получится положить что то большее, в теории можно положить что-то равное либо меньшее. Если с чем то равным профит реален, то с меньшим уже вопрос. Вся эта магия с переразметкой памяти уже относится к хакам и этому нет места в стандартной библиотеке.
А по filter, есть еще retain - оставляет то что нужно в текущей коллекции сохраняя порядок, но требует линейной памяти [bool].
При использование f64 вероятность вырожденных случаев снижается, но не исключает их. Проблема в том, что вырожденные случаи если их правильно не обработать приводят к неправильной логике алгоритма, а это может повлечь за собой не только не правильный результат, но и зацикливание или краш.
Статья понравилась, спасибо.
Я как раз тоже последние лет 5 увлекаюсь вычислительной геометрией.
И за последний год написал библиотеку для вычисления результатов пересечения многоугольников: xor, union, intersection and difference. Первое время пытаешься решать задачу (как и автор статьи) во float числах. Через какое-то время приходит осознание, что из-за потери точности задача в принципе не разрешима в общем случаи. С переходом на int появляется детерминизм и становится сильно проще. Например, параллельность отрезков можно проверять через векторное произведение и тд. С float такие фокусы не проходят. Введение epsilon не спасает, а только маскирует проблему.
С вашего позволения оставлю ссылку на свою имплементацию на
https://github.com/iShape-Rust/iOverlay
и
https://github.com/iShape-Swift/iOverlay
Программирование это сложно. Людей, которые хотят гораздо больше, тех которые могут.
Старайтесь делиться своим временем и энергией с людьми которые потенциально могут.
А тем кто не годится можно попробовать показать подводные камни и трудности профессии. Вопрос в том кто потенциально может?
На мой взгляд дело не только в складе ума, а в большей степени желании и усердии человека. Программирование для усидчивых.
Ирония судьбы: WebAssembly был создан для ускорения кода в браузерах, а теперь мы движемся к тому, чтобы компилировать JavaScript обратно в WebAssembly!
С осени работаю в индийском стартапе. И работая в их коллективе не заметил большой разницы, уровень их навыков разработки вполне современный и подход тоже. Все шутки про индуский код вдруг стали не актуальны. Английским они хорошо владеют, ниже уровня B2 в коллективе никого нет. Что самое забавное стартап занимается разработкой CAD системы для проектирования микрочипов. Основным клиентом которого являются крупнейшие университеты Индии. Так что Индия в скором времени сама начнет проектировать и производить чипы. Решил поделится поскольку сам был удивлен от всего этого.
Всех кому интересна компьютерная графика и кто устал просто решать задачи, предлагаю принять участие в одном из своих проектов. Например https://github.com/iShape-Rust/iShape-js
Уверен так гораздо интереснее чем просто решать задачи. Сам попробовал rust меньше года назад
Я думаю тот тот же принцип что и в кругосветном путешествии. Смотря какую систему координат выберем получим различный результат.
Выглядит итерессно, решил попробовать, но на macOS 13.5.1(intel) не запустился (ffmpeg установил). Вышла ошибка что файл поврежден давай перемещай в корзину. Может сходу знаете в чем проблема? И еще вопрос на виртуалке заработает? Решил попробовать на Ubuntu.
Прохладная история. Не боитесь так перегреть космос?
Спасибо за статью, раньше тоже много раз пробовал силы в этой задаче, правда меня манило точное решение. Но ваша статья навеяла интересные мысли. Очень уж много времени отнимает эта задача боюсь если честно возвращаться.
Только при делении-сдвиге вправо отрицательных чисел надо быть аккуратнее. Попробуйте сдвинуть вправо -1. Для остальных чисел к слову все правильно получается
10 июня сделал swift перевод на сумму 115k через 2 часа мне написали, что бы я обосновал происхождения денег. Я БЫЛ клиентом банка около месяца. Переводил им деньги с Альфабанк, поэтому я скинул им выписку со счетов в Альфе за год. Скинул им выписки в течении 10 минут после их просьбы. Спустя 10 минут меня заблокировали по п 4.5 и 7.3.9. Больше ни сказали не слова по причине блокировки. Не большая сумма порядка 2.7k оставалась в валюте ее сказали что конвертируют в рубли по своему курсу и вышлют мне на мой счёт в другой банк. Я предложил забрать деньги наличными в рублях по курсу цб. Они попросили время порядка 4 дней, после чего просто поступил отказ. Заявление в цб я написал уже 12 июня, пока ответа нет. Здесь очевидно не желание банка проводить эти переводы, поэтому они будут предотвращать это любыми методами.
Согласен с автором что задача весьма не тривиальна.
Для себя в свое время решил, что лучше уйти от Float вычислений на Int.
Если интерессно нашел свой репозиторий с этим участком кода, как раз на C#
https://github.com/iShapeUnity/Clipper/blob/master/Runtime/iShape/Clipper/Util/PolygonExt.cs
Подскажите пожалуйста. Если рассматривать построение модели белка с математической точки зрения то она сводится к NP задачи коммивояжёра?
А динамическое программирование для такого числа городов уже не подходит потому что, требует экспоненциального количества памяти. Я сейчас сам увлечен этой задачей и у меня есть пара оригинальных решений на github, но моя цель не столь амбициозна я поставил себе планку в 64 города.
И да хотелось бы услышать больше деталей вашей реализации, спасибо.
А подскажите еще, пожалуйста, на что влияет количество кубитов в таком компьютере? Интуитивно мне кажется, что например для NP полных задач число кубитов не должно быть меньше N. Если конечно не учитывать тот факт, что можно разбить на под-задачи.