LG уже не первый раз накосячили. Раньше были новости, что их телики собирают данные и без подключения к интернету заполняют ими весь диск и перестают работать, пока память не по чистишь.
Наоборот. Глупых телевизоров мало и они, если и есть, то дороже. Потому что с продажи всех данных покупателя можно заработать намного больше чем с одного жалкого устройства.
И ведь человек даже не думает, наверное, что зло делает.
Удивительно, что может настолько отсутствовать рефлексия и здравый смысл, что человек хвастается своим спам-ботом, к тому же нарушающим копирайт, и засирающим информационное пространство мусором ради абуза системы монетизации.
И каждый раз находится куча комментаторов, которые по своему понимают "действуют идеально логично и знают что все такие" и поэтому не согласны с решением.
Нагородили какие-то кеши ответов. При чем только с двумя слотами, потому что код работает с двумя строками. Так почему-бы тогда в вызывающем коде и не запомнить результат isPlain для каждой строки в локальной переменной?
Слишком переусложненное и накрученное решение тривиальной проблемы.
Корректное решение -это не использовать c = charAt(s, i) и charLength(s), a сделать i = nextChar(i), который прибавляет к индексу 1 или 2. И не надо никаких отдельных случаев и всегда линия будет вместо квардрата.
Пошел почитал. Признаю, что вы были правы. Действительно все переносы локальны.
Суть идеи в том, чтобы делать перевнтивные переносы. Даже если сумма в этом разряде помещается в избыточность, надо все-равно сделать перенос заранее, чтобы пришедший справа перенос поместился и не пошел дальше. При этом число будет длинее, чем могло бы быть с учетом избыточности. Не самая интуитивная идея.
Эта хитрость, действительно, делает алгоритм сложения гораздо лучше распаралелливаемым.
Вот только для этого алгоритма вам все еще надо N^2 потоков что ставит полный крест на любом практическом применении. А с теоретической точки зрения бесконечная параллельность слишком спецефична.
Все еще не согласен, что без упоминания этого алгоритма статья не полна.
Если это правда, то это уже не настолько очевидное решение. На статью не влияет, потому что бесконечный параллелизм изучаемому предмету параллелен и с ним не особо пересекается.
А в системах с избыточностью распространение переноса можно ограничить константой (есть системы, где эта константа равна 1), соответственно, сложение можно распараллелить и выполнить за один шаг, т.е. получить O(1).
Мне кажется, вы ошибаетесь. Может быть, сложение двух "нормальных" чисел обладает таким свойством, когда входные числа без (или с ограниченной) избыточностью. И потом лишняя избыточность съест переносы и не даст им прыгать по всему числу. Но в процессе умножении складываются числа, которые сами результаты умножений на цифру и других сложений, поэтому они сами уже эту избыточность могут использовать до предела.
что процессорах умножение и сложение целых чисел выполняется довольно хитро и гораздо быстрее, по числу шагов, чем Карацуба. Потому что под капотом там как раз избыточные системы,
Нет, потому что там под капотом высокий параллелизм. Не бесконечный, ибо числа ограничены.
В любом случае, рассматривать бесконечный параллелизм - небогоугодное занятие.
Очень даже правильно. Во-первых, формула не должна быть безразмерной. Она должна давать километры (или метры, неважно). Вы же тут возражаете по поводу размерностей, ну так соблюдайте их. Так что у этой вашей безразмерной формулы должен быть множитель k=1км. Это еще не говоря о том, что в статье речь о соотношении, так что там на самом деле какая-то отличная от 1 константа.
И тогда можно L0 из под корня вынести, константы сократить и останется там константа С=k/L0^0.6 с размерностью км^-0.2.
Я почти ничего не понял. Есть несколько вопросов/комментариев.
Могли бы вы описать, что конкретно вы сделали? Нашли полиномиальное приближенное решение? Придумали эвристику, ускоряющую перебор?
Стоит в начале указать, почему задача NP-трудна. Вы во введении обещаете рассмотреть этот вопрос, но забываете о нем. Например, надо какую-нибудь известную задачу свести к этой.
Потом вы какую-то рыбу вводитите и тут я нить повествования потерял. Что вы вкладываете в термин "релаксация"?
Как это вообще опубликовали. *facepalm*. Статья утверждает, что не нужны никакие комплексные числа: вместо n-мерного комплексного пространства можно взять 2n мерное вещественное. Ну еще там операторы должны быть особые немного, половина базисов обрабатывается немного не так, как другая - там минусы какие-то вылезают, но главное, никаких комплексных чисел не надо.
И в итоге получается полностью эквивалентный стандартному комплексному математический объект. Даже показано, как из одного в другой пересчитывать все.
Это практически как: комплексные числа - не нужны! Достаточно пары вещественных чисел (a,b) со смешной операцией умножения (a,b)(c,d)=(ac-bd, ad+bc). И никаких этих ваших комплексных чисел.
Все элементарно же. На самом деле в формуле есть коэффициент, допустим в . Чтобы из (км^2)^0.6 получить длину. Ну потому что если квадратные километры вовзвести в степень k - вы получите км^2k, а ответ должен быть в км^1.
И этот коэффициент естественно пересчитывается, например, из км в м домножением на 1000^(-0.2), если у вас площадь в м^2, а потом можно перевести в акры, квадратные футы и назад в километры и все будет согласовано.
Так все формулы в физике и работают. Только в школьных формулах все степени целые и размерности у констант условные Дж/К или Н·м²/кг².
Ну нет, совсем за O(1) никак. Ибо все потоки должны в итоге данные в одни и те же места записать. В лучшем случае O(log n) на перемножение без переносов будет, если они в виде дерева будут координироваться. А вот переносы уже даже за O(log n) не сделать, ибо там зависимость по данным линейная.
N - это само число, да? Значит этот log(N) в терминах статьи на самом деле O(N). Ибо все эти количества шагов считают от количества бит во входе, а не от значения (там вообще может быть много разных значений), так что N - это обычно длина числа.
Ну, с неограниченным параллелизмом-то и не мудрено. Да, задача умножения - черезвучайно параллельна. Даже в обычных системах счисления, и без избыточности, тоже за O(N) все делается весьма просто, ведь надо только переносы сделать вконце, что делается за O(N).
Но неограниченный параллелизм в Computer Science, это как нефальсифицируемая теория в физике. Обычно тривиально, практической пользы не несет, теоретически не интересно.
дорога например убитая (вы бы хотели ломать подвеску на своей машине?)
Вспоминается анекдот: Все хорошо в работе пожарным: платят хорошо, кормят вкусно. Но, как пожар - хоть увольняйся!
Конечно в идеальном мире вы бы хотли получать деньги и ничего не делать вообще. Машину не изнашивать, время и бензин не тратить. Оно и понятно, все хотят как можно выгоднее себе. Но износ машины - это натуральные издержки работы такси. По убитой дороге надо ехать медленно и подвеску менять не придется.
Потом, дорога не вина пассажира. И она не 100% коррелирует с ним. Иногда какому-то человеку куда-то надо один-два раза в жизни, и там дорога убитая. Ну не повезло ему. А рейтинг ему снимают, как будто он только по этой дороге и едет (и сам ее разломал).
поднять рейтинг водителю гораздо медленнее чем пассажиру.
Вот это интересный вопрос. Вон, в убере тоже есть рейтинг. И судя по моим данным, там тупо среднее арифметическое. И пишут, что там берутся аж 500 последних поездок. Это мне 10 лет надо идеальным пассажиром быть, чтобы рейтинг поднять. У таксиста же поездок до фига. Если там не какая-то хитрая формула, которая специально надолго занижает рейтинг при одной ошибке, то водителю-то как раз на порядки быстрее и легче рейтинг поднять после случайной ошибки.
У вас там на каждый чих аллокация, что весьма плохо для производительности. Особенно в fft. Не надо выделять каждый раз массивы под четные/нечетные элементы. Можно передавать индекс первого элемента и шаг, например. А можно вообще на месте делать преобразование, без выделения двух массивов для входа и выхода, да еще и весь доступ к памяти будет последовательный. Этот алгоритм даже на вики описан.
Умножение/деление на короткое должно быть отдельной функцией, особенно *=. У вас там вообще даже += все число переаллоцирует, хотя это совсем не обязательно.
Gcd гораздо быстрее работает не через длинное деление, а с помощью деления на 2 и вычитания - тоже на википедии есть описание алгоритма. При чем и деление и вычитание можно делать на месте, вообще без аллокаций.
Базу стоит брать не 256, а 2^32 хотя бы. Все будет почти в 4 раза быстрее и переполнений в long long вызывать не должно, если аккуратно писать.
Как упраждение - неплохо. Но, вообще, на практике гораздо лучше использовать GMP. Оно сильно лучше вылизано. Там и оптимизации под конкретную архитектуру, и SIMD, и лучшие алгоритмы. Можно быстренько сделать c++ обертку с перегруженными арифметическими операторами, или взять любую из кучи готовых.
По поводу аллокаций - нормальные списки делаются поверх массива (вместо указателей используются индексы в массиве). Тогда все элементы списка, хоть и идут не по-порядку, но лежат кучно. Независимо от того, как и что вы там аллоцируете параллельно. Если вы еще и часто по списку проходитесь, то можно его периодически "сортировать" - во время прохода перепешите его в новый массив по порядку и все следующие проходы будут удобны для кэша и сильно быстрее. Эти оптимизации делают список гораздо выгоднее и лучше массива для меньших n и с большим соотношением поиска/вставки.
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 потоков что ставит полный крест на любом практическом применении. А с теоретической точки зрения бесконечная параллельность слишком спецефична.
Все еще не согласен, что без упоминания этого алгоритма статья не полна.
Если это правда, то это уже не настолько очевидное решение. На статью не влияет, потому что бесконечный параллелизм изучаемому предмету параллелен и с ним не особо пересекается.
Мне кажется, вы ошибаетесь. Может быть, сложение двух "нормальных" чисел обладает таким свойством, когда входные числа без (или с ограниченной) избыточностью. И потом лишняя избыточность съест переносы и не даст им прыгать по всему числу. Но в процессе умножении складываются числа, которые сами результаты умножений на цифру и других сложений, поэтому они сами уже эту избыточность могут использовать до предела.
Нет, потому что там под капотом высокий параллелизм. Не бесконечный, ибо числа ограничены.
В любом случае, рассматривать бесконечный параллелизм - небогоугодное занятие.
Очень даже правильно. Во-первых, формула не должна быть безразмерной. Она должна давать километры (или метры, неважно). Вы же тут возражаете по поводу размерностей, ну так соблюдайте их. Так что у этой вашей безразмерной формулы должен быть множитель k=1км. Это еще не говоря о том, что в статье речь о соотношении, так что там на самом деле какая-то отличная от 1 константа.
И тогда можно L0 из под корня вынести, константы сократить и останется там константа С=k/L0^0.6 с размерностью км^-0.2.
Я почти ничего не понял. Есть несколько вопросов/комментариев.
Могли бы вы описать, что конкретно вы сделали? Нашли полиномиальное приближенное решение? Придумали эвристику, ускоряющую перебор?
Стоит в начале указать, почему задача NP-трудна. Вы во введении обещаете рассмотреть этот вопрос, но забываете о нем. Например, надо какую-нибудь известную задачу свести к этой.
Потом вы какую-то рыбу вводитите и тут я нить повествования потерял. Что вы вкладываете в термин "релаксация"?
Как это вообще опубликовали. *facepalm*. Статья утверждает, что не нужны никакие комплексные числа: вместо n-мерного комплексного пространства можно взять 2n мерное вещественное. Ну еще там операторы должны быть особые немного, половина базисов обрабатывается немного не так, как другая - там минусы какие-то вылезают, но главное, никаких комплексных чисел не надо.
И в итоге получается полностью эквивалентный стандартному комплексному математический объект. Даже показано, как из одного в другой пересчитывать все.
Это практически как: комплексные числа - не нужны! Достаточно пары вещественных чисел (a,b) со смешной операцией умножения (a,b)(c,d)=(ac-bd, ad+bc). И никаких этих ваших комплексных чисел.
Все элементарно же. На самом деле в формуле есть коэффициент, допустим в
. Чтобы из (км^2)^0.6 получить длину. Ну потому что если квадратные километры вовзвести в степень k - вы получите км^2k, а ответ должен быть в км^1.
И этот коэффициент естественно пересчитывается, например, из км в м домножением на 1000^(-0.2), если у вас площадь в м^2, а потом можно перевести в акры, квадратные футы и назад в километры и все будет согласовано.
Так все формулы в физике и работают. Только в школьных формулах все степени целые и размерности у констант условные Дж/К или Н·м²/кг².
Ну нет, совсем за O(1) никак. Ибо все потоки должны в итоге данные в одни и те же места записать. В лучшем случае O(log n) на перемножение без переносов будет, если они в виде дерева будут координироваться. А вот переносы уже даже за O(log n) не сделать, ибо там зависимость по данным линейная.
N - это само число, да? Значит этот log(N) в терминах статьи на самом деле O(N). Ибо все эти количества шагов считают от количества бит во входе, а не от значения (там вообще может быть много разных значений), так что N - это обычно длина числа.
Ну, с неограниченным параллелизмом-то и не мудрено. Да, задача умножения - черезвучайно параллельна. Даже в обычных системах счисления, и без избыточности, тоже за O(N) все делается весьма просто, ведь надо только переносы сделать вконце, что делается за O(N).
Но неограниченный параллелизм в Computer Science, это как нефальсифицируемая теория в физике. Обычно тривиально, практической пользы не несет, теоретически не интересно.
Вспоминается анекдот: Все хорошо в работе пожарным: платят хорошо, кормят вкусно. Но, как пожар - хоть увольняйся!
Конечно в идеальном мире вы бы хотли получать деньги и ничего не делать вообще. Машину не изнашивать, время и бензин не тратить. Оно и понятно, все хотят как можно выгоднее себе. Но износ машины - это натуральные издержки работы такси. По убитой дороге надо ехать медленно и подвеску менять не придется.
Потом, дорога не вина пассажира. И она не 100% коррелирует с ним. Иногда какому-то человеку куда-то надо один-два раза в жизни, и там дорога убитая. Ну не повезло ему. А рейтинг ему снимают, как будто он только по этой дороге и едет (и сам ее разломал).
Вот это интересный вопрос. Вон, в убере тоже есть рейтинг. И судя по моим данным, там тупо среднее арифметическое. И пишут, что там берутся аж 500 последних поездок. Это мне 10 лет надо идеальным пассажиром быть, чтобы рейтинг поднять. У таксиста же поездок до фига. Если там не какая-то хитрая формула, которая специально надолго занижает рейтинг при одной ошибке, то водителю-то как раз на порядки быстрее и легче рейтинг поднять после случайной ошибки.
Раз уж вы ссылку запостили, оставлю отзыв.
У вас там на каждый чих аллокация, что весьма плохо для производительности. Особенно в fft. Не надо выделять каждый раз массивы под четные/нечетные элементы. Можно передавать индекс первого элемента и шаг, например. А можно вообще на месте делать преобразование, без выделения двух массивов для входа и выхода, да еще и весь доступ к памяти будет последовательный. Этот алгоритм даже на вики описан.
Умножение/деление на короткое должно быть отдельной функцией, особенно *=. У вас там вообще даже += все число переаллоцирует, хотя это совсем не обязательно.
Gcd гораздо быстрее работает не через длинное деление, а с помощью деления на 2 и вычитания - тоже на википедии есть описание алгоритма. При чем и деление и вычитание можно делать на месте, вообще без аллокаций.
Базу стоит брать не 256, а 2^32 хотя бы. Все будет почти в 4 раза быстрее и переполнений в long long вызывать не должно, если аккуратно писать.
Как упраждение - неплохо. Но, вообще, на практике гораздо лучше использовать GMP. Оно сильно лучше вылизано. Там и оптимизации под конкретную архитектуру, и SIMD, и лучшие алгоритмы. Можно быстренько сделать c++ обертку с перегруженными арифметическими операторами, или взять любую из кучи готовых.
По поводу аллокаций - нормальные списки делаются поверх массива (вместо указателей используются индексы в массиве). Тогда все элементы списка, хоть и идут не по-порядку, но лежат кучно. Независимо от того, как и что вы там аллоцируете параллельно. Если вы еще и часто по списку проходитесь, то можно его периодически "сортировать" - во время прохода перепешите его в новый массив по порядку и все следующие проходы будут удобны для кэша и сильно быстрее. Эти оптимизации делают список гораздо выгоднее и лучше массива для меньших n и с большим соотношением поиска/вставки.