Популярный подход к программированию состоит в том, что самый быстрый код, который вы можете написать, - это вообще не писать кода. Более компактный код по определению более эффективен, но сосредоточение внимания исключительно на объеме синтаксиса может легко упустить из виду структуры внутри этого синтаксиса; а именно используемые структуры данных.
То, что вы пишете, так же важно, как и то, что вы пишете. Хорошим примером, который блестяще демонстрирует эти концепции, является проблема Иосифа Флавия. Проблема названа в честь Иосифа Флавия, библейского деятеля, который оказался в окружении римлян вместе с сонмом еврейских солдат.
Краткий синопсис гласит, что солдаты предпочли смерть плену, поэтому они решили встать в круг, где каждый второй мужчина убивал бы солдата слева от него, пока не останется только один. Иосиф, который был довольно неравнодушен к тому, чтобы остаться в живых и хотел оставаться таким, начал рассчитывать, где встать в круг, чтобы он был единственным выжившим.
В самом простом случае цель решения проблемы Иосифа Флавия состоит в том, чтобы решить проблему единственного выжившего в группе из «n» человек.
Чтобы быть более конкретным, он включает в себя процесс исключения, в котором каждый нечетный член группы живых участников убивает следующего соседнего человека слева в чередующемся порядке, начиная с человека один.
Этот процесс кажется немного сложным, и это может быть. В отличном сообщении в блоге Амандо Абреу подробно описано, как программно выполнить это вычисление, которое можно прочитать здесь:
Если мы взглянем на отрывок из предоставленного кода, мы увидим, что решение Amando предоставляет средства для отслеживания состояния каждого участника в рамках общего процесса исключения:
var kill = function(arr){ if (arr.length < 2){ // This is our last soldier alive. return arr; }var survivors = arr.filter((soldier, index) => index % 2 == 0);if (arr.length % 2 !== 0){ // Add the last person the start // if the number of people is odd. survivors.unshift(survivors.pop()); }return kill(survivors); }
Это разумное решение проблемы, но что, если нам нужен только окончательный ответ в кратчайшие сроки и за наименьшее количество шагов?
Большое внимание справедливо уделяется важности понимания кода, но также важно поддерживать разнообразие в ресурсах, из которых вы черпаете информацию. Некоторые аспекты становления лучшего программиста, такие как упомянутые здесь, не всегда можно легко обнаружить в монолитной вселенной изучения стеков и кодовых баз. Иногда, казалось бы, несвязанный контент на YouTube может предложить лучшие ответы.
Проблема Иосифа Иосифа освещалась на Numberphile, отличном канале YouTube, посвященном математике. В их обзоре мое внимание было обращено на очень любопытное и выгодное свойство математики, задействованной в этой конкретной задаче.
Ответ на эту проблему можно вычислить, преобразовав количество участвующих людей в двоичную систему, а затем переместив крайний левый бит на место в правой части. Целое число, представленное новой двоичной строкой, всегда будет решением проблемы.
Зная это, мы можем использовать структуры данных в Number и String, чтобы значительно сократить объем кода, который мы пишем, как показано ниже:
const josephus = (n) => {
/*
* If we have received a valid number, convert it
* to a binary string using a radix of 2.
* Move the left-most bit to the one's place.
* Return the integer equivalent.
*/
if (n && !isNaN(n) && n > 0) {
let bin = (n).toString(2)
let survivor = bin.slice(1) + bin.charAt(0)
return parseInt(survivor, 2)
}
}
Приведенный выше код даст тот же конечный результат, что и решение, написанное Амандо в его более подробной статье, но время выполнения и количество кода значительно сокращаются.
Есть много способов достичь того же результата, что и делает программирование таким увлекательным, выразительным и индивидуальным. Развитие знаний не только о том, как написать решение, но и о том, что писать (и в каком объеме) - это бесконечное дерево навыков, которое будет постоянно строиться в ходе нашей карьеры.
Пара уловок, которые вы можете попробовать улучшить свои навыки, - это использование прикладной математики, которая поможет вам использовать структуры, встроенные в сами данные. Даже большие вещи могут иметь маленькие решения.
Спасибо за чтение, и я надеюсь, что это помогло вам увидеть закономерности, которые в противном случае вы могли бы пропустить.
Если вам нравится сообщение в этой статье, я веду блоги, посвященные более тонким аспектам программирования, включая реализацию математических концепций.
Чтобы посмотреть отличное видео Numberphile по этой теме, вы можете посмотреть его ниже:
