Ну казалось бы что тут улучшить?! Повторю опять, что алгоритм А.А,Карацубы в данной ситуации не рассматриваем, просто ищем улучшение простого алгоритма умножение-с-накоплением реализованного в столбик.
Давайте улучшать, но известные и на порядки более быстрые улучшения применять не будем. Потому что иначе все изыскания из статьи бесполезны будут, да?
Еще, просто вывалить 2 простыни ассемблерного кода - такое себе. Хоть бы объяснили подробно, в чем ваша изящная и замечательная идея заключается, почему оно работает. Я так вижу, что вы просто переставили местами операции. Эта микрооптимизация похоже увеличенивает параллельность кода потому что позволяет суперскалярным процессорам лучше загружать конвеер?
Поэтому и понятно, почему оно не ускоряет работу на видяхах - там процессоры не такие суперскалярные как cpu.
Кроме того, стоит отдельно описать, почему этот код корректен. Не теряется ли там пренос из-за скачков через разряд?
Реально думать и самому создавать алгоритм с нуля, а не копипастить готовые приходилось довольно много раз.
Правда, изобрести что-то принципиально новое сложно. Кто-то где-то почти наверняка что бы вы ни придумали уже когда-то придумал раньше вас. Так часто потом получалось даже найти как придуманный мною алгоритм на самом деле называется.
Внезапно, один из соавторов статьи по вашей ссылке упоминается в оригинале этого поста на хабре. И там как раз почти вся статья посещена 5 игрокам. Т.е. это оригинал из которого эта новость на хабре и выросла.
Тогда уж проще просто назначить числам от 1 до 6 различные перестановки трех последних игроков и одним броском шестигранного кубика определить их порядок.
А еще можно взять кубик с n! сторон и одним броском найти порядок всех n игроков.
Но задача не об этом. Это теоретическая задача о существовании костей, любое подмножество которых честное. И решают ее не потому что не знают, как еще определить порядок игроков в ДнД, а потому что это офигенно.
чтобы правило "больше-меньше" работало взаимно равновероятно
Оно не может работать равновероятно, потому что элементарных исходов 1000. Вероятность любого события составляется из этих элементарных исходов, а значит любая вероятность будет суммой скольких-то 1/1000. Значит, искомую вероятность 1/3 вы никак не получите.
Вообще, из попарной справедливости костей не следует, что они справедливы группой.
Например, пусть у нас 3 кости которые дают вот такие перестановки с такими вероятностями:
1 2 3 - 1/10 - с вероятностью 1/10 первая кость даст максимальное число, потом вторая кость, а третья - минимальное число.
1 3 2 - 2/10
2 1 3 - 2/10
2 3 1 - 2/10
3 1 2 - 2/10
3 2 1 - 1/10
Можете убедиться, что любая пара выпадет с вероятностью 1/2. Например, 1<2 в первой, второй и предпоследней строке, что дает (1+2+2)/10 = 1/2 - ровно половина случаев.
Однако тут 1 идет первым с вероятностью 3/10, 2 - 4/10, 3 - 3/10. Нечестно, 2 выигрывает чаще других.
Надо же не сумму на костях делать одинаковой, а вероятности выигрыша.
Ваша система, кстати, гарантирует что каждая пара костей честная - одна выиграет у другой с вероятностью 1/2, ведь все исходы можно сгруппировать в парочки. Пусть x выкинул первый игрок, y -второй: (x,y) <-> (51-x, 51-y). В каждой паре исходов выигрывает то один то другой игрок.
Но вот это не гарантирует общую честность. Если играет 3 или более игроков, то первая кость выигрывает заметно чаще.
Ответ прост - не используйте структуры данных с произвольными графами ссылок. Если ваша программа как-то использует, что изменение foo.x еще и изменяет foo.bar.y, то это отвратительная, негодная программа. Бить по рукам линейкой надо того программиста, кто это написал.
Даже если ваш язык программирования позволяет делать такие извращения, это еще не значит, что это надо делать.
Элементарно. Автор выжал все микрооптимизации, и применил все алгоритмы, о которых знал. Но нейронка знала больше алгоритмов и применила что-то другое.
Судя по обрывкам данных из коммента выше - вообще нет. Mееt-in-the-middle это стандартный прием, позволяющий сокращать O(N) до O(sqrt(N)). Если там порядка N=250000, как раз 500 раз и получится. Без размерностей задачи, это числов вообще ничего не говорит.
Да, нейронки знают больше и могут перебором и за счет кругозора найти такой известный прием, которого вы не заметили, но ни на какую фильдофскую премию это не тянет.
Пока все решения знаменитых задач, что я видел - нейронки взяли готовые наработки и идеи из каких-то забытых статей лохматых готов, где-то что-то по-другому из применили, где-то соединили что-то. Фактически это перебор, грубая сила, но направленный. Каких-то новых методов решения задач или идей они нигде не делали.
Конечно, решение задачи тысячелетия - это решение задачи тысячилетия. Но все намного приземленнее и проще чем хайп раздувает.
LG уже не первый раз накосячили. Раньше были новости, что их телики собирают данные и без подключения к интернету заполняют ими весь диск и перестают работать, пока память не по чистишь.
Наоборот. Глупых телевизоров мало и они, если и есть, то дороже. Потому что с продажи всех данных покупателя можно заработать намного больше чем с одного жалкого устройства.
И ведь человек даже не думает, наверное, что зло делает.
Удивительно, что может настолько отсутствовать рефлексия и здравый смысл, что человек хвастается своим спам-ботом, к тому же нарушающим копирайт, и засирающим информационное пространство мусором ради абуза системы монетизации.
И каждый раз находится куча комментаторов, которые по своему понимают "действуют идеально логично и знают что все такие" и поэтому не согласны с решением.
Нагородили какие-то кеши ответов. При чем только с двумя слотами, потому что код работает с двумя строками. Так почему-бы тогда в вызывающем коде и не запомнить результат isPlain для каждой строки в локальной переменной?
Слишком переусложненное и накрученное решение тривиальной проблемы.
Корректное решение -это не использовать c = charAt(s, i) и charLength(s), a сделать i = nextChar(i), который прибавляет к индексу 1 или 2. И не надо никаких отдельных случаев и всегда линия будет вместо квардрата.
Пошел почитал. Признаю, что вы были правы. Действительно все переносы локальны.
Суть идеи в том, чтобы делать перевнтивные переносы. Даже если сумма в этом разряде помещается в избыточность, надо все-равно сделать перенос заранее, чтобы пришедший справа перенос поместился и не пошел дальше. При этом число будет длинее, чем могло бы быть с учетом избыточности. Не самая интуитивная идея.
Эта хитрость, действительно, делает алгоритм сложения гораздо лучше распаралелливаемым.
Вот только для этого алгоритма вам все еще надо N^2 потоков что ставит полный крест на любом практическом применении. А с теоретической точки зрения бесконечная параллельность слишком спецефична.
Все еще не согласен, что без упоминания этого алгоритма статья не полна.
Законы пишут для себя бюракраты, им надо "просто дайте данные удобно", а не возиться с электронными сертификатами.
Давайте улучшать, но известные и на порядки более быстрые улучшения применять не будем. Потому что иначе все изыскания из статьи бесполезны будут, да?
Еще, просто вывалить 2 простыни ассемблерного кода - такое себе. Хоть бы объяснили подробно, в чем ваша изящная и замечательная идея заключается, почему оно работает. Я так вижу, что вы просто переставили местами операции. Эта микрооптимизация похоже увеличенивает параллельность кода потому что позволяет суперскалярным процессорам лучше загружать конвеер?
Поэтому и понятно, почему оно не ускоряет работу на видяхах - там процессоры не такие суперскалярные как cpu.
Кроме того, стоит отдельно описать, почему этот код корректен. Не теряется ли там пренос из-за скачков через разряд?
Реально думать и самому создавать алгоритм с нуля, а не копипастить готовые приходилось довольно много раз.
Правда, изобрести что-то принципиально новое сложно. Кто-то где-то почти наверняка что бы вы ни придумали уже когда-то придумал раньше вас. Так часто потом получалось даже найти как придуманный мною алгоритм на самом деле называется.
Внезапно, один из соавторов статьи по вашей ссылке упоминается в оригинале этого поста на хабре. И там как раз почти вся статья посещена 5 игрокам. Т.е. это оригинал из которого эта новость на хабре и выросла.
Тогда уж проще просто назначить числам от 1 до 6 различные перестановки трех последних игроков и одним броском шестигранного кубика определить их порядок.
А еще можно взять кубик с n! сторон и одним броском найти порядок всех n игроков.
Но задача не об этом. Это теоретическая задача о существовании костей, любое подмножество которых честное. И решают ее не потому что не знают, как еще определить порядок игроков в ДнД, а потому что это офигенно.
Оно не может работать равновероятно, потому что элементарных исходов 1000. Вероятность любого события составляется из этих элементарных исходов, а значит любая вероятность будет суммой скольких-то 1/1000. Значит, искомую вероятность 1/3 вы никак не получите.
Вообще, из попарной справедливости костей не следует, что они справедливы группой.
Например, пусть у нас 3 кости которые дают вот такие перестановки с такими вероятностями:
1 2 3 - 1/10 - с вероятностью 1/10 первая кость даст максимальное число, потом вторая кость, а третья - минимальное число.
1 3 2 - 2/10
2 1 3 - 2/10
2 3 1 - 2/10
3 1 2 - 2/10
3 2 1 - 1/10
Можете убедиться, что любая пара выпадет с вероятностью 1/2. Например, 1<2 в первой, второй и предпоследней строке, что дает (1+2+2)/10 = 1/2 - ровно половина случаев.
Однако тут 1 идет первым с вероятностью 3/10, 2 - 4/10, 3 - 3/10. Нечестно, 2 выигрывает чаще других.
Все числа уникальные, так что можно и порядок получать. Равновероятность всех перестановок как раз и делает задачу сложной.
Надо же не сумму на костях делать одинаковой, а вероятности выигрыша.
Ваша система, кстати, гарантирует что каждая пара костей честная - одна выиграет у другой с вероятностью 1/2, ведь все исходы можно сгруппировать в парочки. Пусть x выкинул первый игрок, y -второй: (x,y) <-> (51-x, 51-y). В каждой паре исходов выигрывает то один то другой игрок.
Но вот это не гарантирует общую честность. Если играет 3 или более игроков, то первая кость выигрывает заметно чаще.
Ответ прост - не используйте структуры данных с произвольными графами ссылок. Если ваша программа как-то использует, что изменение foo.x еще и изменяет foo.bar.y, то это отвратительная, негодная программа. Бить по рукам линейкой надо того программиста, кто это написал.
Даже если ваш язык программирования позволяет делать такие извращения, это еще не значит, что это надо делать.
Элементарно. Автор выжал все микрооптимизации, и применил все алгоритмы, о которых знал. Но нейронка знала больше алгоритмов и применила что-то другое.
Судя по обрывкам данных из коммента выше - вообще нет. Mееt-in-the-middle это стандартный прием, позволяющий сокращать O(N) до O(sqrt(N)). Если там порядка N=250000, как раз 500 раз и получится. Без размерностей задачи, это числов вообще ничего не говорит.
Да, нейронки знают больше и могут перебором и за счет кругозора найти такой известный прием, которого вы не заметили, но ни на какую фильдофскую премию это не тянет.
Пока все решения знаменитых задач, что я видел - нейронки взяли готовые наработки и идеи из каких-то забытых статей лохматых готов, где-то что-то по-другому из применили, где-то соединили что-то. Фактически это перебор, грубая сила, но направленный. Каких-то новых методов решения задач или идей они нигде не делали.
Конечно, решение задачи тысячелетия - это решение задачи тысячилетия. Но все намного приземленнее и проще чем хайп раздувает.
LG уже не первый раз накосячили. Раньше были новости, что их телики собирают данные и без подключения к интернету заполняют ими весь диск и перестают работать, пока память не по чистишь.
Наоборот. Глупых телевизоров мало и они, если и есть, то дороже. Потому что с продажи всех данных покупателя можно заработать намного больше чем с одного жалкого устройства.
Библиотека gtest тоже умеет регрессии строить и оценивать O().
И ведь человек даже не думает, наверное, что зло делает.
Удивительно, что может настолько отсутствовать рефлексия и здравый смысл, что человек хвастается своим спам-ботом, к тому же нарушающим копирайт, и засирающим информационное пространство мусором ради абуза системы монетизации.
Да, заметил, у вас пираты кровожадные. Это минимальное изменение, не меняющее логику решения.
Уже было на хабре, причем уже несколько раз: https://habr.com/ru/articles/125769/ https://habr.com/ru/articles/1050532/
И каждый раз находится куча комментаторов, которые по своему понимают "действуют идеально логично и знают что все такие" и поэтому не согласны с решением.
Нагородили какие-то кеши ответов. При чем только с двумя слотами, потому что код работает с двумя строками. Так почему-бы тогда в вызывающем коде и не запомнить результат isPlain для каждой строки в локальной переменной?
Слишком переусложненное и накрученное решение тривиальной проблемы.
Корректное решение -это не использовать
c = charAt(s, i)иcharLength(s), a сделатьi = nextChar(i), который прибавляет к индексу 1 или 2. И не надо никаких отдельных случаев и всегда линия будет вместо квардрата.Пошел почитал. Признаю, что вы были правы. Действительно все переносы локальны.
Суть идеи в том, чтобы делать перевнтивные переносы. Даже если сумма в этом разряде помещается в избыточность, надо все-равно сделать перенос заранее, чтобы пришедший справа перенос поместился и не пошел дальше. При этом число будет длинее, чем могло бы быть с учетом избыточности. Не самая интуитивная идея.
Эта хитрость, действительно, делает алгоритм сложения гораздо лучше распаралелливаемым.
Вот только для этого алгоритма вам все еще надо N^2 потоков что ставит полный крест на любом практическом применении. А с теоретической точки зрения бесконечная параллельность слишком спецефична.
Все еще не согласен, что без упоминания этого алгоритма статья не полна.