c
Minoru
(хоть я и не люблю загадки, да)
Size: a a a
2021 February 15
c
sergevp
Minoru> ну т.е. я написал такое же решение, как и на Питоне: создаём ассоциативный массив со счётчиками чисел, потом обновляем эти счётчики так, чтобы в сумме было n, и потом конструируем выходной массив
Обожди. Там не было ассоциативных массивов! Там обычный массив индексов был. И две сортировки по нему. Сначала сортируем индексы по значениям входного массива, потом в отсортированном массиве отрезаем первые n элементов, сортируем их теперь уже по индексам, и заполняем выходные n элементов из этих индексов?
Minoru> ну т.е. я написал такое же решение, как и на Питоне: создаём ассоциативный массив со счётчиками чисел, потом обновляем эти счётчики так, чтобы в сумме было n, и потом конструируем выходной массив
Обожди. Там не было ассоциативных массивов! Там обычный массив индексов был. И две сортировки по нему. Сначала сортируем индексы по значениям входного массива, потом в отсортированном массиве отрезаем первые n элементов, сортируем их теперь уже по индексам, и заполняем выходные n элементов из этих индексов?
c
sergevp
Minoru> С таким подходом 15 по миллиону проходит за пять секунд :)
И, кстати, лучше делать не 15 по миллиону, а один на 15 миллионов — так сложность выше выходит. :)
Minoru> С таким подходом 15 по миллиону проходит за пять секунд :)
И, кстати, лучше делать не 15 по миллиону, а один на 15 миллионов — так сложность выше выходит. :)
FO
Переслано от FORTRAN ONE LOVE
Being a COBOL developer can be very fun | by Luca Piccinelli | Feb, 2021 | Towards Data Science
https://towardsdatascience.com/being-a-cobol-developer-can-be-very-fun-c0072454d75c
https://towardsdatascience.com/being-a-cobol-developer-can-be-very-fun-c0072454d75c
c
Minoru
sergevp: а, ну это «тупое» решение с O(n * log(n)), оно не интересное. Я в итоге написал «умное», амортизированно-линейное, которое описал выше. А про «15 по миллиону» не я придумывал :)
sergevp: а, ну это «тупое» решение с O(n * log(n)), оно не интересное. Я в итоге написал «умное», амортизированно-линейное, которое описал выше. А про «15 по миллиону» не я придумывал :)
c
Minoru
@foxtran: скажи, а для тебя «по часовой стрелке» — это в направлении уменьшения угла между кончиком стрелки, осью стрелки и отметкой 12? А то, по-моему, ты не в ту сторону во времени движешься :P
@foxtran: скажи, а для тебя «по часовой стрелке» — это в направлении уменьшения угла между кончиком стрелки, осью стрелки и отметкой 12? А то, по-моему, ты не в ту сторону во времени движешься :P
FO
Minoru
@foxtran: скажи, а для тебя «по часовой стрелке» — это в направлении уменьшения угла между кончиком стрелки, осью стрелки и отметкой 12? А то, по-моему, ты не в ту сторону во времени движешься :P
@foxtran: скажи, а для тебя «по часовой стрелке» — это в направлении уменьшения угла между кончиком стрелки, осью стрелки и отметкой 12? А то, по-моему, ты не в ту сторону во времени движешься :P
Тихо. Не спугни молодость!
c
Minoru
sergevp: кстати погоди-погоди, в performance-версии решение с массивом и двумя сортировками как раз не должно проходить, оно чересчур медленное
sergevp: кстати погоди-погоди, в performance-версии решение с массивом и двумя сортировками как раз не должно проходить, оно чересчур медленное
FO
Minoru
@foxtran: скажи, а для тебя «по часовой стрелке» — это в направлении уменьшения угла между кончиком стрелки, осью стрелки и отметкой 12? А то, по-моему, ты не в ту сторону во времени движешься :P
@foxtran: скажи, а для тебя «по часовой стрелке» — это в направлении уменьшения угла между кончиком стрелки, осью стрелки и отметкой 12? А то, по-моему, ты не в ту сторону во времени движешься :P
Гм. Да. И, черт побери, сейчас по часовой стрелке это в прошлое :-)
c
sergevp
Minoru> кстати погоди-погоди, в performance-версии решение с массивом и двумя сортировками как раз не должно проходить, оно чересчур медленное
Ну, вот, если там 15 по миллиону, то может и пройти. O(nlogn) против O(n) при n=миллион отличаются всего лишь в 20 раз. А ассоциативный массив вполне может быть раз в 10 медленнее, чем обычный. То есть финальное отличие на миллионном тесте будет всего в 2 раза, и его можно не поймать.
Minoru> кстати погоди-погоди, в performance-версии решение с массивом и двумя сортировками как раз не должно проходить, оно чересчур медленное
Ну, вот, если там 15 по миллиону, то может и пройти. O(nlogn) против O(n) при n=миллион отличаются всего лишь в 20 раз. А ассоциативный массив вполне может быть раз в 10 медленнее, чем обычный. То есть финальное отличие на миллионном тесте будет всего в 2 раза, и его можно не поймать.
c
sergevp
Чтобы ловить отличие между O(NlogN) и O(N) — нужно поднимать N. Потому я и предложил один 15-миллионный вместо 15и 1миллионных.
Чтобы ловить отличие между O(NlogN) и O(N) — нужно поднимать N. Потому я и предложил один 15-миллионный вместо 15и 1миллионных.
c
Minoru
мне автор performance-версии посоветовал проверить, и я проверил, и оказалось, что вариант с сортировкой на Расте проходит в лучшем случае десять тестов-миллионников
мне автор performance-версии посоветовал проверить, и я проверил, и оказалось, что вариант с сортировкой на Расте проходит в лучшем случае десять тестов-миллионников
c
Minoru
«в лучшем случае» это когда нужно вывести 250 тысяч элементов,
«в лучшем случае» это когда нужно вывести 250 тысяч элементов,
t
Mr.Purple
я даже не возрващаясь после другого языка с десяток секунд не могу вспомнить как "не равно" пишется
я даже не возрващаясь после другого языка с десяток секунд не могу вспомнить как "не равно" пишется
<>
c
sergevp
Minoru> приятная ката: https://www.codewars.com/kata/587f0871f297a6df780000cd
Хех, да, классная. Но перевести её на не-питон будет тяжко...
Minoru> приятная ката: https://www.codewars.com/kata/587f0871f297a6df780000cd
Хех, да, классная. Но перевести её на не-питон будет тяжко...
Dv
Minoru
каждый раз, возвращаясь к Хаскелю после другого языка и написав `!=` вместо `/=`, я чувствую себя предателем — так давно не трогал Хаскель, что позабыл самые основы :(
каждый раз, возвращаясь к Хаскелю после другого языка и написав `!=` вместо `/=`, я чувствую себя предателем — так давно не трогал Хаскель, что позабыл самые основы :(
А в Эрланге есть оператор
=/=, кажется.SE
А в Эрланге есть оператор
=/=, кажется.=/= Exactly not equal to
SE
точно
