Я раньше встречал ее на дваче, только там были только круглые скобки, а на литкоде 3 типа скобок.
Я помнил, что она решается через стек, но не понимал, нахуя тут нужен вообще стек?
Например, у меня возникла мысль просто создать переменную числовую. И делать +1, если скобка открывающая и -1, если закрывающая. Если в конце получился 0, то все заебись. Почему это не будет работать? Это сработает на строке типа (()()), но не сработает на )()((). Недостаточно чтобы просто количество открывающих и закрывающих скобок совпадало. К тому же, в литкодовском варианте задачи есть еще и другие типы скобок и надо проверять их соответствие, чтобы каждой открывающей соответствовала закрывающая того же типа.
Короче, нужно хранить информацию не только о числе скобок, но еще и об уровне, где они находятся, а также об их типе. Короче, эта задача идеально ложится на стек, со стеком получается очень элегантно и эффективно.
Есть еще одна задача того же типа на стек, которую я хочу попробовать решить - это написание парсера-калькулятора. То есть, он принимает строку вида "(1 * 3) - ((5 + 4) / 13)" и выдает результат вычисления. Тут тоже надо учитывать скобки + операторы + приоритет операторов. Задача как минимум медиум уровня, а может и хард. В универе я писал такой парсер, но не сам + там был костыль через польскую нотацию. Короче, интересно было бы попробовать самому написать с нуля. Задача ультра-хард - интерпретатор простенького япа.
Еще бесит на литкоде, что там задрачивают затраты по времени и памяти, экономя на спичках. Например, вот на пике слева топовое решение по вычислительным ресурсам, а справа мое. Алгоритмической разницы никакой, но слева решение бьет 99% по памяти, а мое только 40%. А все из-за костылей уровня использования объекта вместо карты. И такая хуйня там постоянно. Ты исправляешь буквально пару строк на другие конструкции языка и решение уже получает +40% рейтинга. Потому что литкод смотрит тупо на циферки памяти и времени выполнения, даже если они отличаются на 1%. Впрочем, поебать, главное это вычислительная сложность алгоритма. Все же, я там не за рейтингом, а за знаниями.
Ты про парсер или про скобочки? Обе, скорее всего, нет (по-человечески), но:
— Со скобочками можно пытаться удалять из строки (), [], {}, и если осталась пустая строка — структура была правильной, что, очевидно, будет квадратичным решением, чью немасштабируемость любит проповедовать вот он: https://randomascii.wordpress.com/2018/10/15/making-windows-slower-part-2-process-creation/, https://twitter.com/BruceDawson0xB/status/1120381406700429312;
— Парсер без стека сделать нереально, но алгоритм сортировочной станции мне всегда казался тупостью какой-то (потому что я не понимаю, как он работает), я себе переизобрёл https://en.wikipedia.org/wiki/Operator-precedence_parser, он проще, выдаёт сразу дерево, и использует аппаратный стек C:. (Я не хочу знать, что там описано как full parenthesization, но, возможно, это позволяет сделать без стека... но опять же, я сказал «по-человечески», а это хуже сортировочной станции... и аппаратный стек всё равно понадобится, чтобы это дерево потом вычислить, поэтому а смысл.)
>Со скобочками можно пытаться удалять из строки (), [], {}, и если осталась пустая строка — структура была правильной
Это ты забавно придумал, я даже проверил, вроде работает.
>что, очевидно, будет квадратичным решением
Не квадратичным, но пропорциональным арифметической прогрессии с негативным шагом и начальным членом N.
Работает, конечно, медленнее, чем решение на стеке.
Почитал тут про парсеры немного. Там не все так просто, это отдельная область алгоритмов, с полтычка, как со скобочками, уже не сделаешь. И, похоже, я не просто так в универе обратную польскую нотацию использовал. Возможно ли сразу вычислить инфиксную нотацию без перевода в другую? За 1 проход?
>пропорциональным арифметической прогрессии с негативным шагом и начальным членом N
Оно выполнит число действий, пропорциональное сумме этой прогрессии, в которой светится N², это и значит квадратичное :^).
>Возможно ли сразу вычислить инфиксную нотацию без перевода в другую? За 1 проход?
Да, можно, там «рабочий псевдокод» в статье. Сделал на Паскале :) : https://ideone.com/lEIunA.
>>721882
Нашёл кому указывать, биомусор.
>Нашёл кому указывать
Хуясе раздутое самомнение
> биомусор
И такими словами разбрасывается чел злоупотребляющий манямэ-джипегами? Ой вэй!
Но это все и не нужно! Ведь в этой задаче приоритет всех операторов одинаковый, что значительно упрощает дело. Решил попробовать написать алгоритм сам.
Допустим, есть выражение "(1+(4+5+(7-2+3))-3)+(6+8)"
Додумался вот до какой хуйни:
1. Кладем в стек вообще все, пока не встретим закрывающую скобку.
То есть, в стеке будет "(1+(4+5+(7-2+3".
2. Далее выталкиваем из стека всю хуйню до тех пор, пока не будет встречена открывающая скобка, вычисляем ее и заменяем вместе с открывающей скобкой на результат вычисления.
То есть, выталкиваем 7-2+3, вычисляем из него 8 и заменяем, стек будет "(1+(4+5+8".
3. Go to 1.
Далее читаем входную строку дальше и встречаем еще одну закрывающую скобку: "(1+(4+5+8)". Соответственно, вычисляем выражение в скобках и таким образом раскрываем стек.
Но есть одна проблемка.. В стеке все лежит задом наперед. То есть, "7-2+3" будет "3+2-7". А задом наперед вычислять нельзя, иначе получится хуйня. И что делать блять? То есть, это надо мне каким-то хуем прочитать кусок стека в обычном направлении, чтобы вычислить кусок выражения. Это, конечно, можно сделать, но выглядит как костыль. И доп расходы на память. Можно хранить в стеке не токены, а их номер в строке, тогда прочитать будет легче. Хуй знает, короче.
https://pastebin.com/mEuu16if
Блять, целый день убил на это говно. Меня радует хотя бы то, что я вообще додумался до идеи раскрытия стека.
В итоге получился какой-то адовый высер обезьяны, код некрасивый и костыльный.
А еще блять, в самом конце стек загадочным образом трансформируется в очередь.
Вот как блять я должен наизусть помнить алгоритмы парсинга, которые диды, всю жизнь занимавшиеся информатикой, годами разрабатывали? Это оно у них выглядит элегантно. При попытке додуматься самому до подобной хуйни, получается хуже и куда более всрато. И это блять в задаче нет приоритетов операторов.
Есть и хороший момент. Например, при проходе по выражению в RPN форме, вычисление куска стека происходит очень просто. Выталкивается оператор/функция, исходя из того, сколько аргументов он ожидает, выталкивается нужное число операндов. У меня же подобной хуйней занимается отдельная функция, которой еще и приходится переворачивать стек. Короче, шибко дохуя лишней работы я не делаю, просто более всрато.
Еще пытался сделать примитивный конвертер в обратную польскую нотацию, но обосрался.
>Сделал
Ты просто реализовал алгоритм из статьи или по памяти нахуярил?
>на Паскале :)
Но... зачем, а главное - нахуя?
У меня даже возникло ощущение, что я начинаю интуитивно понимать, как работает стек.
Накидал реализацию минут за 5-7, но потом завис на 15 минут на этом блять truncates towards zero. Что это блять? В первый раз вижу такую хуйню, я даже блять не понял, что от меня хотят. Поставил floor - 1 кейс не работает. Поставил ceil - не работает. Поставил round - не работает блять. Только потом в результате гуглинга догнал, чем отличается этот truncates от округления. Короче, отличается на негативных числах. На позитивных аналогичен floor.
А еще, то ли в результате рандома, то ли еще чего, у меня получились какие-то выдающиеся результаты по памяти, лучше чем у 96% других решений. Наверняка рандом ебаный. Там 1 килобайт в сторону, уже пролетаешь. Тупо путем перезапуска одного и того же решения получаешь разные результаты.
Там рандом какой-то. Кто-то вроде составлял список советов https://leetcode.com/discuss/general-discussion/601899/how-to-get-90-up-runtime-perf-tips-ft-js как писать жс/тс, чтобы в метить в топовые результаты. Я вроде попробовал применить и как будто решение с первого пика немного чаще бывает быстрее, чем через свитч.
Количество строк / символов - гораздо более надёжная метрика.
>Кто-то вроде составлял список советов
Это все бред, конечно, ебаный, выдрачивать костыли языка ради экономии килобайт и миллисекунд, тем более на js-параше, тем более в обучающей задачке на сраном литкоде.
Вот тут чел об этом сказал:
https://leetcodetherapy.com/runtime-useless
Также он говорит, что Hard вопросы почти никогда не встречаются на интервью хотя блять, смотря на каких. Читал про собеседование индуса в гугл, ему там навалили таких задач на деревья, что одно описание занимает 3 страницы текста.
Я про это тоже слышал раньше. Что хард вопросы почти никогда спрашивают. Тупо нет времени на это на интервью, тупо тяжело интервьюеру следить за твоим решением.
А еще вот чувак, который решил 1500+ задач на литкоде. Причем он задрачивал это говно целенаправленно для прохождения собеседований в компании США.
>выдрачивать костыли языка ради экономии килобайт и миллисекунд, тем более на js-параше, тем более в обучающей задачке на сраном литкоде
Звучит интереснее и приносит больше удовлетворения, чем проходить собеседования или работать на работе и писать js код.
Тем не менее, я считаю, что в повседневной деятельности программиста некая БАЗА по алгоритмам полезна. Как минимум, знание основных структур данных и сколько времени на них занимают базовые операции. Например, если тебе требуется изменять порядок элементов в коллекции, то лучше выбрать для нее связный список, а не массив, потому что там позиция элемента изменяется за константное время, а в массиве за линейное. Что как раз и приводит к ситуациям, когда программа зависает, когда ты строчку в таблице переместил, потому что там при каждой такой операции весь массив нахуй пересобирается. Еще дрочево литкода приводит к пониманию, что нехуй копировать массивы по 8 раз на лету, где можно все сделать in place. Иногда на stackoverflow видишь такие высеры, что просто охуеваешь. Где чел на ровном месте несколько раз копирует строку/массив просто по приколу. Обычно это не приведет к негативным последствиям, но как только у тебя данных становится много, эта хуйня убьет твою программу нахуй. Эти мелкие нюансы начинаешь подмечать. Все, дальше уже не надо. Все эти верчения деревьев и парсеры оставим дидам-информатикам, которые пишут стандартную библиотеку япа.
Но тем не менее, это говно слишком часто стали спрашивать на собесах и я вынужден его учить, чтобы сойти за умного.
Я перевёл псевдокод из статьи, потому что мне было лень думать, но до этого реально можно самому додуматься. Там есть объяснение через грамматики:
— <ВЫРАЖЕНИЕ>, или <АДДИТИВНОЕ ВЫРАЖЕНИЕ> — это одно или несколько <МУЛЬТИПЛИКАТИВНЫХ ВЫРАЖЕНИЙ>, разделённых «+» или «−»;
— <МУЛЬТИПЛИКАТИВНОЕ ВЫРАЖЕНИЕ> — это одно или несколько <ПРАЙМАРИ>, разделённых «×» или «/»;
— <ПРАЙМАРИ> — это либо число, либо открывающая скобка плюс <ВЫРАЖЕНИЕ> плюс закрывающая скобка, либо ±<ВЫРАЖЕНИЕ>.
Это дословно переводится в scan_expression, которая вызывает один или более (пока следует оператор «+» или «−») scan_multiplicative, которая вызывает один или более scan_primary. Например, в 2+3×4 первым <МУЛЬТИПЛИКАТИВНЫМ ВЫРАЖЕНИЕМ> будет просто «2», вторым — «3×4». Опер-чё-то-там обобщает это на произвольное число приоритетов и разбирается с ассоциативностью.
Для интереса заглянул в раздел про динамическое программирование и охуел. В эту кроличью нору мне лезть пока рано. В частности, увидел там задачу про поиск наибольшей общей подстроки. Блять, я видел эту задачу раньше, натыкался на нее где-то. Но я даже подумать не мог, что решается она настолько ебанистическим способом. Да уж, некоторые задачи имеют очень простую формулировку и очень сложное решение. Типа как великая теорема Ферма.
Так, по в верхам поглядел и понял, что вроде как при выборе значения, которое вписываешь в ячейку таблицы, не требуется бегать по всей остальной таблице, а смотрится только какая-то 1 соседняя ячейка (разная в зависимости от задачи). Также непонятно, а может ли эта таблица быть многомерной? Типа тензор. Хз, пока что похуй.
Еще что странно, в этой книге нет раздела по ДЕРЕВЬЯМ блять. Как так нахуй? Это же база. Зато динамическое програмирование впендюрили, OCR и прочее.
>>721982
Что-то я опять нихуя не понял... Почему n x n = n^2?
Почему блять правый n превратился в квадрат? Почему не в куб?
А, блять, что-то я совсем завис. Число умножить на число это же и есть квадрат числа. Было бы там n x n x n, был бы куб.
А все дело в том, что иначе и быть не может. Если слева мы поместили числа, меньшие опорного, то справа никогда не появятся числа большей величины. Максимальное число в левом массиве всегда будет меньше минимального в правом. Так оно и работает.
Но проблема в том, что эта хуйня работает через рекурсию. А я ненавижу, блядь, рекурсию. Я понимаю, как она работает, именно поэтому и ненавижу. Рекурсия жрет дохуя памяти, а глубина стека вызовов ограничена. Например, в Java там вообще какие-то смехотворные значения, см. пикрил. 9к вызовов. Это типа дохуя? В qsort аж 2 рекурсивных вызова применяются, алгоритм обмякнет очень быстро на довольно скромного размера массиве. Причем глубина стека вызовов не ограничена непосредственно памятью. Она захардкожена в япе. Например, я помню как писал рекурсию на Java и программа сдохла после ~32768 вызовов. То есть, число не от данных зависит, а тупо степень двойки. Хуйня ебаная эта рекурсия, короче. Если можешь не использовать - не используй.
Каждый ли рекурсивный алгоритм можно переписать на не-рекурсивный вариант?
В япах более хитровыебанные версии qsort применяются, хз, может там и без рекурсии обходятся.
Вот говорят, что рекурсивная функция вызывает сама себя. Так вот, это полная, блять, хуйня. Никто там сам себя не вызывает. Вызывается другой экземпляр функции с другими данными. Вот и все. Она нихуя не та же самая. То же самое там название только. Технически это вызов многих экземпляров функции с хранением всех промежуточных результатов.
Сука, ору. Только блять сказал про глубину стека рекурсии. Загуглил этот баг литкода и мне выдает, что, вероятно, это из-за переполнения стека рекурсии.
Ну точно. Запустил свой код сам и там переполнение стека вызовов. Могли бы и написать прямо, вместе невменяемого бага.
Да, это говорит о том, что мой код изначально нерабочий.
Ебаный жиэс не имеет встроенной функции для получения рандомного целого числа.
Я копирнул код, возвращающий float число, поэтому код и не работал.
Вот не люблю такие костыли, когда в языке элементарная хуйня делается через жопу. Например, вы знали, что в петухоне нет цикла do-while? Только while. Вот как так блять?
Продолжаю получать пикрил на этом коде, который точно работает. Какая глубина стека вызовов на литкоде, 20? Пиздец, ненавижу сраную рекурсию.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAcwKZQEoEMwBM4C2AkmFABQExgBciYIBARqgE4A0iBWAHrfU6wCUfBsxaIA3gChEnKogC8iALJYoACwB0EVDAA2FKoIDcMzj0Uq1W4HrhwWFHibMt0IFklUbNt+4+8tFhx8AjJBRAAqRCduRABaOTAIgGoklwBfKSlQSFgERCgWGAA3GCw9AEUAZwdyfmqRARYAbQBdYTpRVnbJM1kYYBiGzT1UMGQNRAAeRAAmCOlZZeW3KA8kBtMVrJWIBGqoRAAHUrgjpQaWtEwQwhJyAAYOEbGJjUE27eX9sEPEMbAKBNMS9JTtb6yX7-YrIdTArrNMGICH9RDABwxMZHGCWR7GRC42avcaTdQEmApFKLNF7A5HfiWK4wL605ZkRmzU4lc6IAD8ANQQMQtFh8MEmmOIGq6g5DBcOzRaw2hWKZQqNTqZEBUAlvwgajIRVK5SqtRY5DFusy2WhRzc1RAeguqpNGvN5BazwALHNvWwAIz+gMAdjYADYAMyBtjRgCscw6pmhcDGozgyBiDqdutMQA
На массиве [0, 0] не работает. Но даже если исправить твоё решение с минимальными изменениями кода, то всё равно не будет работать (пикрил ошибка на тесткейсе с массивом из 50к элементов).
Да, я уже понял, что обосрался... Все дело в том, что крайне важно убрать из массива опорный элемент.
Этот >>722656 код работает только если все числа в массиве уникальны. А если нет, то уходит в бесконечную рекурсию, потому что массив не может разделиться, один всегда пустой, другой всегда полный.
Quick sort оказался не так прост, как кажется на первый взгляд.
Вот ниже рабочий код. Но литкод один хуй его не принимает. Видимо, потому что там большие расходы по памяти, я гоняю массивы рекурсивно по значению.
План на завтра: переписать qsort, чтобы не гонять в памяти куски массива, желательно вообще без рекурсии.
Зря я гнал на то, что на литкоде маленький стек на рекурсию. Как обычно, долбоебом оказался я, а не литкод.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAcwKZQEoEMwBM4C2AkmFABQExgBciYIBARqgE4A0iBWAHrfU6wCUfBsxaIA3gChEnKogC8iALJYoACwB0EVDAA2FKoIDcMzj0Uq1W4HrhwWFHibMt0IFklUbNt+4+8tFhx8AjJBRAAqRCduRABaOTAIgGoklwBfKSlQSFgERCgWGAA3GCw9AEUAZwdyfmqRARYAbQBdYTpRVnbJM1kYYBiGzT1UMGQNRAAeRAAmCOlZZeW3KA8kBtMVrJWIBGqoRAAHUrgoAGlUAE9LNEwQwhJyAAYOEbGJjRc9g6PTkrnSwNFoA85Xa5tbbLfZgQ6IMbAKBNMS9JTtaGyWHw4rIdTIrrNNGIDH9RDABwxMZHGCWF7GRC02YfcaTdQMmApFKLMkrQYxWkKIUnM6XG48laSmEIWD0VCYyW7KWIbFHfjAhjVFowKG85ZkdWzMFHAD8CNQSMQtFx+MEmmOIGq6gNDB+yyVsjWG0KxTKFRqdTIiKgdthEDUZFBoraHCKpXKVVqLHINpDmWyqsQbmqID0RyUcb9icDLTeABY5mW2ABGKvVgDsbAAbABmGtsNsAVjmNcb3Y6pmxcDGozgyBi2dzIdMQA
>тесткейсе с массивом из 50к элементов
Кстати, как ты узнал, что в этом тесте 50к элементов?
Я просто скопировал из Last Executed Input в литкоде в консоль браузерную и дописал .length. Но можно было бы и просто по количеству символов понять, там все элементы одинаковые.
Пытаюсь написать разделение Хоара с перестановками. И нихуя не выходит. Какой-то рандом блять. При определенных сочетаниях одинаковых цифр код зависает. Если изменить, чтобы не зависал, вообще перестает разделять. Иногда работает, иногда нет. Нихуя непонятно.
Я даже теоретически не могу придумать, какие престановки надо сделать, чтобы разделить такой массив. Как эта хуйня вообще работает блять?
Это тонкая вещь, известная тем, что её невозможно сделать с первого и второго раза, прямо как написать бинарный поиск или вставить флешку в разъём. В реализациях обычно так делают: ведут два индекса, L от N−1 и R от 0. L двигают влево, пока элемент под ним строго больше опорного. R двигают вправо, пока элемент под ним строго меньше опорного. Найденную пару обменивают. Заканчивают, когда L < R. Результат — две половинки, от 0 до L (включительно) и от R до N−1. По построению, в каждой будет минимум 1 элемент. На твоём примере будет:
>R>9, 14, 7, 63, L>9 ← свапаем (бесполезно) и продвигаем оба.
>9, R>14, 7, L>63, 9
>9, R>14, L>7, 63, 9 ← свапаем и продвигаем оба.
>9, L>7, R>14, 63, 9 ← готовый партишн (9, 7) + (14, 63, 9), даже красивый.
Блять... Только благодаря тебе я догнал. Короче, мой код разделения работал правильно, просто я не догонял ключевую фишку.
Для массива [9, 63, 7, 14, 9] с опорным 9 я ожидал разделения [7, 9, 9], [63, 14] ну или [7], [9, 9, 63, 14].
Но эта хуйня работает по-другому. В левый массив попадают числа, меньшие или равные опорному, в правый - большие или равные опорному. При этом указатель в конечном итоге каким-то хуем оказывается как раз в месте разделения. Очень контринтуитивная хуйня. Ебаная магия, не иначе.
Литкод схавал qsort с in place разделением Хоара. Но это все еще на рекурсии. Плюс я вижу, что на массивах, где дохуя одинаковых цифр, выполняется много перестановок. Попробую оптимизировать немного для таких массивов.
>Попробую оптимизировать немного для таких массивов.
Немного оптимизировать не получилось, опять нихуя не работает. Я думал, там одну строку надо дописать. Дописал, код сломался.
while (i < j && nums === nums[j]) {
// skip useless swaps of equal values.
i++;
j--;
}
Обезьянья борда сожрала nums :
while (i < j && nums === nums[j]) {
// skip useless swaps of equal values.
i++;
j--;
}
Я пытался оптимизировать работу с одинаковыми значениями, чтобы они не переставлялись. Однако, затем понял, что я занимаюсь оптимизацией констант в О-большом. При перестановке выполняются 2 операции:
1. считать значения ячеек.
2. записать новые значения ячеек.
У меня же при проверке один хуй считываются ячейки, только новые данные не записываются. Это оправданно на одинаковых данных, но на разных у меня наоборот дополнительные расходы на повторное чтение ячеек. Можно было бы в функции swapIndexes выполнять эту проверку, было бы оптимальнее. Но это все, как я уже сказал, оптимизация констант, выдрачивание минимально возможного количества операций кудахтера. Дрочево вприсядку, короче. Этим занимаются при создании конкретных реализаций алгоритмов для прода, а не в обучающих целях.
Смысл разделения Хоара по сравнению с хранением кусков массивов в стеке рекурсии очевиден - огромный выигрыш по памяти, памяти используется ровно на хранение одного оригинального массива + копейки на переменные.
Запустил код на литкоде, он выдал проценты хуже, чем без оптимизации. Но оно и понятно - литкод пишет хуиту рандомную. Чтобы реально посчитать выигрыш от оптимизации констант, надо гонять алгоритм на больших данных по часу.
Надо уже прекращать дрочиться с qsort и двигаться дальше. Разве что можно переписать на не-рекурсивный вариант. По идее, это еще несколько копеек сэкономит на хранении индексов в стеке рекурсии. Но смысл даже не в этом, а чтобы избежать stack overflow на больших данных, потому что в япах какая-то блять смехотворная глубина стека рекурсии, как я уже показывал выше.
Иногда на собесах любят набрасывать говна на вентилятор по типу:
1. Отсортируйте массив.
Вот рекурсивный qsort с хранением подмассивов в памяти.
2. А теперь без доп расходов на память))0
Вот рекурсивный qsort с разделением Хоара.
3. А теперь без рекурсии)
Вот qsort без рекурсии с разделением Хоара.
4. А теперь с разделением на 3 части)).
Пошел нахуй пидор бля.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABARwM5wE5QEoFMIgarxgCSYACgDYCGEuAFGCALaoBcizLARrhgG0AugBpEwDHBadufDIgC8iAAxiocGazmKurVADoquMAHMoAC0QBaRAEYAlJt79hiAN4AoRN8QQEqKEQABxosABljM0sldWtxSRZEAGo7AG4vHxhgRAYQ8MiLRAAeRAAme3cMnx8MXChCJG5UdOqAXw8q339AvKhyABNcAA8dczhQ3ApQ2FgEJj0xCSk1OHsWnzRMHHxCYgRyajpGJsWEsV6B4bXOzaw8AiISA9p6ebZz6cuRlNsV6+ravUMI09Ol2h5QJBZkgxhMplgYNCGJ0mk45MIRJ0ltJdM55EpVJ11Gj+DomoYCpYbL9OkEYAA3OBQEn43GoAQAWRoFn0wCocEwDAY2OSiHUFQA9GV7KIPI5cdpPNUjIEYDpsetvCrEAArHTqTWIADu5hgRhyUAwIFwFSV1R8JrNuByTQEMCExWCDKZts69p8EqlLDg9OdQTgMDAUFJGBgJnMgUd5tkpKMqFQYvMxi9jKg+j9-sQMCSSUNbQL3iTzre7J1HoAfDmfZVC-bA4hg6HghGo6ncMBE6bk1pSSZatzSRZs3Tc-nW9UdVYrGWfO1W1kcmr60odb75wGpYCGpnnbQAkWwIMRnBslPEEYB4hQhgaABPOf7xBH4G6lfecGtu2qAANYwEEiAgKguBphmqBGjQQQZjeiC4MgIA0FQiD0hh1oGBWRbZDWboegAhAoSiunWe6fnBCFfLgqA1mIMBiLuf6IGuhbthYMAZrxWH8K+RYsOGWA0FGYpwB2IbOpGV4MU+A6TlmiC0UEH7+sWpb4Yuy6dO04KQtAJCqfBQT0YxqIKi4ogXletgssxl7DKULLyoyMD9C2Ph+GA57YVQ1q2GSehus5Qy2EIhq+f5OG4KUIVsGFV6lFFKKhXJwyRToAXWqUhquplQypTlcW2GCHQxaqYBBCAgRKAIqiIAALKUzViLY7V2GIABsADMHUAOxiANiAAKylENYgTWlMVwEYhhwCYDAAESRrVzIrU5G3XHNC38stK21KgIBUJtYi3NsDx7GQlAvIw611fY1xAA
Как ни странно, все заработало с первого раза, лол. Правда, вначале я потупил, пытаясь реализовать итерацию без стека.
Еще мне кажется, что в данном алгоритме не нужен именно СТЕК для хранения индексов под-массивов. Потому что, по идее, порядок их обработки не имеет значения. Мне кажется, я могу тупо добавлять в массив пары индексов, потом перемешать массив и в любом порядке их обработать.
Блять, только написал и понял, что таки не могу. Потому что массив большего размера всегда должен быть разделен до того, как будут делиться еще подмассивы.
Или могу? Так-то индексы попадают в стек только после того, как массив уже разделен. Не может быть ситуации, когда в стеке есть индексы меньшего массива, когда еще не разделен больший.
Хз короче. По идее я таки могу обработать более мелкие массивы до того, как обработал крупные.
Например, на первом шаге я разделил массив на 2 части.
На втором шаге на 4 части. По идее, я эти 4 части могу в любом порядке обрабатывать и похуй, они уже сбалансированы относительно друг друга.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABARwM5wE5QJJQKYYCGsAbntmAAoA2hEeAFGCALaoBcizLARgQNoBdADSJgGOC07c+GRAF5EABlFQ401rIVdWqAHTU8YAOZQAFogC0iAIwBKDbwGDEAbwBQiL4ggJUURH86AGtHWSFtIQBuT28giGC9AAcQVDMGcUlVODsY2K8AdzMYQ0QGeMTDE3NEAD5lOzd87y9fMH9ENW0K5LgkhkbCVB0nDBiWlraOzJZuqBDe-sHhmQJxida-AKTCLAAZI1MLRS7rGcQAalt1jZhgMp39w5qAHkQAJkaPDY222GY8DcJgBfdzNSZbRCPHBgAAmeAAHtozHBdnhKLtYLAEExdKIZtlcuC4vMEslUukCVDMRR4QiiT9AqTEik0gxobTEZdbISgaDmhg8FAQBgkNxUDF+aBINikCi0RisDBZQxmuKws5hM0Zhq5IoVM01LrtOKDM8LNYbFqWkkYCQ4FBjYpxfwALLEMx6YDUOCYBgZCSzK5qRoAeg+dhE7gcIy0328hgCMG0MyBicQACttGogUUSngylAMCA8F9iYViqVcWx+DAXG9bfaoGXGS1Q+GWHAyFC4DAwPg5BgYMYzAE86VVnJDKhhuYjFC7Q69OWJjALhcgS1QYzxwXq6h+BmXPVGw6W62vO3EJ3u0le-2CIhDMAx5WC5PEMZBcRH3OkKeoGXC8vAzSxLE3bxtx+O4ymTWpFAzc8LyvQVhVFTozALWgOj7OlEDge45yfPAX0QXYiAATyA4DUJFJAMwgrx+UZK9zBgYZ2MQMgMAoxAYBYO8sEIftOjga8uwLXDETwYZCBfX9MMCApCCSaiNlQZSkk5BEZP3UQ1wuURQMsBlIPcKVwGgeAkA0lTtN09VY01Pi4URGxdX01yEXeXUY3tGBYSaCF2gCEhCGoEsbBNXRay8mxBCBKZQvCkt3mimspO8hK1RizL4u0MKIrwd4gRdTL3hcRRCsiyUwSSlyUgCRR+BURAABZ3ja0QbC6nlEAANgAZm6gB2URhsQABWd5RtEabsqmOBDAMOBjAYAAiPtGvYdbPMaolFuWn01vWwVUBAahHV2lB0CwXACGIO1yCoWh6AYLaQGbIkgA
Пытался скормить литкоду, но там time limit exceeded. Очевидно, из-за перетасовки массива на каждой итерации. Можно было бы сделать pop() рандомного элемента, но для массива удаление элемента с середины - дорогая операция за O(n) в худшем случае.
Чисто для проверки концепции.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABARwM5wE5QJJQKYYCGsAbntmAAoA2hEeAFGCALaoBcizLARgQNoBdADSJgGOC07c+GRAF5EABlFQ401rIVdWqAHTU8YAOZQAFogC0iAIwBKDbwGDEAbwBQiL4ggJUUREIMDE5+GQJRcIxBIW0hAG5PbyCMPQAHEFQzBn5xSVU4QTtEpK8AdzMYQ0QGFIMjUwsAPmU7N1LvLwB6LsQAUQAPNIIYFiMArLgymBNEc2JEAE84EB9CJDSJelRURFQQHksUwkXdmcCwRcRMABMCPQ7OrJBgYEMAQWCT2uDix+9chIWAUXNo6mk4GkGG1CLswpoIjonNFEp1Or4wP5EGkglAADINczaNRWMRAxAAalsqLRXhgwBqOKwBJMRIAPIgAExtDy02kY2DMPA02kAX3c-y8GKxTJwYDuA20ZjgQTwlFxMFgCCYulEeWBczgfz5gWC6Uy2UB+WxuIoCqKIrR4ItOVldrwiqpNhBxu84o6GDwUBAGCQ3FQiX9oEgWqQytV6qwmvgYAYHXDjlkQmEHX1mYI2hUHTU+bkinD9VZFms3o6aRgJDgUFL2nD-AAssQzHo3nBMAwGPrKYa2r1uSJ3A4kVped5DAEYNp9Y754gAFbEuCOipVPA1KAYEB4HmSxA76o6tj8GAuDn1xtQE8mzo9RAsOBkbFwGb4OQYGDGGYATnnuUSIIYOxzGYRjYg2TYPM+3gwBSFKOp04omiBNRtmuLgtPeTZPohiCvu+n4Qj+BaGMAwGVNUYHGIGxAFuYMEEVACHEWuliWGhfqnvSNSLk0ihrkRiGvoGwahlBe60FiMwKtcDKseBeA0aaRCLJxiFSSGSBrnxXj+iar7mDAZy7GQGBXKMEJYOsAQkmRe6KR6eC7IQNEsdBexlIQaQ6WiqD+Wk7oDB5l6oKIyEUqI3GWL6xnuFG4DQCmfkBeFkUZtOzgxfKHo2KWBUKpypZTo2MA3O06J+AEJCENQR42K2ujXoVAw2IIjrSg1TVHpybVXm5Aycj16btaN3XaI1zV4JyjptqN42zQNeA2JGEpdAAVIgABK6w3JIMAAF57sctlgJYaS0PQiCZDMxiIAAIiG-hGMAeDUDVzyvNUTXGJgmpmCwiA7V07jRulCB7GYLxvHgnxaWyAAqTQ-FpnCo0I4liJgNSNXIi6KJdlaNKSm2IMJyjxNTPF450RPrtonbmD21B9hgDBs92RDypI0Lg0Jw72ElaLM-gLBpGCXyLNeE0mpdCuy1p-C4UZmknOrLiKFLaSOuK-p9dTYAZAEij8CoiAACycjbog2A7tiiAAbAAzI7ADsoie4gACsnLe6IgcTdKcCGAYcDGAwABEMzm+wscFebfzh5HnMx7Hgb7NQzbJyg6BYLgBDEA25BUHdjAJyAj5-EAA
Сразу же беспокойство вызвала плашка
Can you solve it using O(1) (i.e. constant) memory?
Также вызывал беспокойство тот факт, что связный список - ни что иное как направленный граф, а про графы я пока не знаю приблизительно нихуя.
Ну что ж, с памятью O(N) я решил: пихаем все ссылки на ноды в Set, если встретили повторяющуюся, значит есть цикл.
А как блять с константной памятью? Я так и не додумался.
Но зато сделал ХОД КОНЕМ и сохранил информацию о прохождении узла тупо в самом узле, таким образом, уничтожив связный список. Зато O(1), лишней памяти не использовано, лол.
Посмотрел решения, оказывается есть блять некий хитровыебанный алгоритм решения конкретно этой задачи с константной памятью, называется "Алгоритм черепахи и зайца".
Вот какого хуя это хуйня easy? Это хард нахуй. Например, помню задачу по переводу чисел в английские слова. Она имеет уровень hard, хотя по сути изи, там ничего сложного нет, просто объемная, дохуя слов в массиве надо хранить. А тут хуй додумаешься без знания конкретного алгоритма. В смысле для константной памяти.
Информация по алгоритму.
https://habr.com/ru/articles/743514/
https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D1%85%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0#%D0%A7%D0%B5%D1%80%D0%B5%D0%BF%D0%B0%D1%85%D0%B0_%D0%B8_%D0%B7%D0%B0%D1%8F%D1%86
Что ж, не один я такой долбоеб, что додумался хранить информацию о прохождении узла в самом узле
Хотя рекурсия тут нахуй не нужна, только жрет память на ровном месте.
Вот прям яркий пример, когда рекурсия не нужна. Рекурсия всегда жрет память пропорционально количеству рекурсивных вызовов, потому что при рекурсии в памяти всегда хранится какая-нибудь хуйня.
Решил уже 10 заданий.
https://www.typescriptlang.org/play?#code/MYGwhgzhAEAyCWEAuA5A9gEwKbQN4ChojoA3MEALmgDsBXAWwCMsAnQ46rADySoWXTZoAHxq0QIdkWBpqyFrWBI0LABRkQAfip0mrADQ1uSbXESpMOUXQkBKPFOJEkAC0QA6DdAC80deR9vX1pqbAAzeE4MaE1oAAZoKg1bRydXD04eHz9MpEDg0KwIqJixCUSjHhSnAF98OvwAegAqZsJm6AAlLGBaFgh4EhwWLHJ4AC8wJHhZaBk5BiwYAHlVant6LHoVAE93dsb8MJClGepoEaH+rH4kbt7+waw1yz5zQSsykEMAB0uPt4CSwiL7ZGwgWyAixCaziEAOJzwMI5YFBXzg+wEJxOEZIPrnP5YEgfADcjjqTnmyEq0Jw6Ms7lyZKc1AZuWyhOJlmZxFx+IuRNYEBu5nufQGQzWxg+hlZ2FsZIaLTa0A6AEkkKwpmc5rIIIsVqoAIwbLa7faqw7HainWaXIUi5AarXTSUuUYYKEfEEYr3A2HlLHEEBYPKcgFmIEw0HouE8oghvJyrB+6Pg7LusAYePQADubhDKKEAEIgl9MaliFSk9LUTQ2cYcyyG1lfOHuZWiO2hPTsE2OHXcqTyY4+SwCf8Ow0jidpnbBddbqpM57I7SfXDIWvvQH4UGiGPzvbF6KeuKnsuPQr6vggA
Я сразу же подумал, что это элементарная хуйня, в чем разница с переворотом всего списка? Всего-то скипнуть часть диапазона листа, да соединить концы.
Но по факту, тут заебешься следить за этими индексами ебаными. Как в qsort. Звучит просто, но при попытке реализации постоянно какие-то баги идут из-за несоответствия индексов. В итоге решил. Самое главное - сложность линейная, затраты памяти константные. Глянул в решения, там можно чуть меньше кода написать, если сделать фантомный узел листа. Похуй.
https://www.typescriptlang.org/play?#code/MYGwhgzhAEAyCWEAuA5A9gEwKbQN4ChojoA3MEALmgDsBXAWwCMsAnQ46rADySoWXTZoAHxq0QIdkWBpqyFrWBI0LABRkQAfip0mrADQ1uSbXESpMOUXQkBKPFOJEkAC0QA6DdAC80deR9vX1pqbAAzeE4MaE1oAAZoKg1bRydXD04eHz9MpEDg0KwIqJixCUSjHhSnAF98OvwwkKV4WWgWLBJWCCwAISwkAHcsLGpVFywwDD5zQSsykEMQIt4xPRZDFngAcxdV3WYWWxmBSxEFhycAeivoADFI6LBoZDAWPOpLd0dlvMfubJxADcPwGLyQbws2BOUPmNhA2XhIKcv2gyzCsJhc3O8OyEymyOIgzcyz8AGoyf8uNAADxolbQABkjPpGLm9gITicr3e2N86NhhK5rNh2QFc3cuSF0Aa11uACVOt0cAAHSHQNBhaCuHAgczfFFglUdEhzLFnaziBG+JGgj6Wc1CS3lfkrObS4nwUmqKkU2m+La7PLMmiWDmpYgyOQfYx80PYSXGaVOT4J3LZY2dd0RoiZ01nG2WZMcAuVQWOOpOKPIdo7PZmsynJ0XXx57OGvKjDAN-ii53W+NYEGOG7QADCsk4SmgaveGq1OrR5m1aG1E3aWHoYEikW2S+QBuI8C1qh5sPDwqIZ4l6YDdfLtUcx784rDl0vr7TxmyXfbxErR4ngK0AAHzQAAjBel4dEgtAsNQ0D4hg0oAUQMFwQhgb1kW9T4EAA
https://www.typescriptlang.org/play?#code/PQKhCgAIUhxBTALpAtgQwB6QDbwHYDmiAFpAEZIDu8+kADgPYCWeiAzpA3pCfJABqRMTNgDooMACpMU8AFyRIAeQAUAJhB4Q2BgRV4AlAYmQAynTQBjecpUBGY9GDgAZgFc8lxEy6pMAdSYAExIlFwA1eAAnb0s0bABBKPg0FUYWdgU8NxQKKIBtAF0igyycvMgAbyhFemZWMTYGGJUVNDLc6KKAGnIOvJLIAF4APiF8gAZCyABacknCgwBucBrFZMQ3KO50htFkoLdrFXdPb18VdAwAGXwiYn7o3t3ER4LC3pYg+Aw33rQolE3kVBtVauDIJYuGxkHgfogAAr1ZBDISA-JfH6QADUkDs0wA-AS6hkVhDalC8DDIHDKLdCCRhjT4UiMgtZiTWAsyeTIBsttwALJoEiiK6XTD0+69WlSkjLNaQAC+vQmCqVq0p1JYdDcKMg+XyAFZulNusbuvjzXZTR98gAWW2FFZahi4UQ6PQ6vUK13uz0qABEV0glGCJDkge6V0CIWIYUiMSYcUSyVS3sQRhWQA
Рекурсивно быстро понял, но итеративную реализацию пришлось подглядеть.
Также по этой же схеме можно сделать умножение числа.
Это снова упрощенный алгоритм, так-то есть еще алгоритм, где степень переводится в бинарный вид, его не хочу трогать.
https://www.typescriptlang.org/play?#code/PQKhCgAIUglBDAlgZwKaXpAdgVwLYBGqATpAC4D2GkADhQO4kB0UMAKonqgFySQDyACgA2FAOaCsASimtIAZRrwAxjwGCAjLOiQAAkuLw8kAB6QAglgCe2fEWIsd++IeNZIASSxlUYkrcISABpsCjJIADNReDJHEGBwCJwsZTJECnc6eg8fQzSAN1RBE15cQOIQrFK7Eilq8sgAbyg+SEQIyElIAF5eyAAGKSaW1tbiVDIcYncNAG4RyABfBfbO9wAeAaHm0dGzbsgNSGBTed3W9wOAWiwz1uXR4QnIVBMyQwANHsO7vnoAC0QTzWkAAfIdtgtRsoMsgKE8mKIJAADEqQAAkjRMi2RIWRVQxjSwOKkv12qy6AFJIAAmSAAQj6g2G53Or3e8C+B3Znx0JjJrOw33cVx+UPu4r4+1MfIFF2Fx1pZIeYwmU3cPM5svAy3AoAgOgQKHQmDK9nIVEwWWYcg4XF46iRkhkckUKjUQid0m0MGcrhllhsZptTgMRiFXh8flIwYqoXCUQoMTiCSSKTSGVoDFgqGUU2QiEKxXq9kqJdq5dIO1aMKwcIRTtRvEx2NxkHxzaJJLJFMuTMhgvGk2mYtGKr4vZ6fS0LNZQ-VpwW47aHS6m2Z1fO85HWRzeeIBaLRxOJhCN1JS5Wq-c1LpvQOG8lkG3mWzufzhaKZhgp6FJxpF5jgsL4yjAu7vgen7FHyIRdKKM7-heuq1vWqCIuIggAETjMgODCGQ3CYSEWQ5CQMRQQArCEGhaBeQA
Поначалу нагуглил функцию Math.log() и подумал, что в жс только она и есть. Ладно, думаю, похуй, можно же накостылить через формулу, позволяющую вычислить логарифм по любому основанию, если на калькуляторе есть только кнопка логарифма по какому-то конкретному основанию.
Надо логарифм числа разделить на логарифм основания, тогда получится логарифм числа по основанию.
Но я не учел ограниченной точности вычислений в кудахтере + жопаскрипт имеет фишку добавлять к числам при вычислении рандом далеко после запятой.
Вообще, конечно, костыль еще тот, на проде такую хуйню лучше не использовать.
Потом я узнал, что в жс есть функция Math.log2().
Если бы ее не было, пришлось бы делать через цикл. Благо, там сложность логарифмическая.
Ору, для тройки точности в одну миллиардную уже недостаточно.
Блять, ну я тогда хуй знает, как тут сделать без циклов и чтобы было надежно.
Поглядел решения, ебать охуел с вот этого. Оно реально работает, но только для простых чисел.
Для двойки тоже есть аналоговнетный метод через бинарное представление числа.
Для меня неочевидной хуйней оказался тот факт, что проверяемый индекс нужно исключить из диапазона. Ибо, во-первых, он уже блять проверен, но самое главное, что если не исключить, то функция зависнет, когда достигнет массива из двух элементов, индекс все время будет указывать на одну и ту же ячейку. А если исключить, то массив всегда гарантированно будет уменьшаться и программа не зависнет, даже если в массиве ничего не найдено.
Еще рандом литкода выдал мне пикрил. Как обычно, оно является хуйней.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAZwKYEMBOEAWAKMEAW2QC5FCiAjVTAbQF0AaRKLAc1SnMpswEoexPogDeAKERTEAGy6IYiALyIADAG5J0uVEQArZRWLIAdHLDsoORAFpEARk1apAdxww5iPAbuKAfCqq-GLO0lIQCMi6MGAAJqgAHoYAsuhWJsAycHCYeHiKANT6wQD0iABM-JphYRFgyHByZnDseAAGMOQAJKIwAL4set2iegMKcYnDMfEJfW1VoWEwwF6UyHTTiQzKSipsmJxQwRI1p4iYXCCYSJsJ1Wd9i9LLq8YbEwnbADysHFzHT1OihUt0QRUcgMQjzOChWBDet22fl+B3+IRhYQMII+tgc91O0OkhKkFygVyQNkciBKZQAbugZCBUIgXOhkBQ4LpgHBwLETOJHuI6g0mllWgAiC7IEAybjilhoLC4PAAQUwmHQAE8Mpg4ERVeqtXhUukAA5wFx4coscpBfgmADWqE1yDw-H4LAAnO7NEA
Если кто не понял, в чем вообще проблема, скажу, что числа в языке программирования имеют четко ограниченный максимальный размер. Например, в js тип number имеет размер 64 бита, то есть, число не может превышать 2^64. В двоичном представлении число будет представлять собой последовательность 64 единиц: 1111111111111111111111111111111111111111111111111111111111111111. То есть, все биты ячейки памяти забиты единицами, нулей нет. В десятичном виде это будет 18446744073709551615.
То есть, числами большими, чем это, оперировать в принципе нельзя стандартными средствами. Выбор именно 64 битов обусловлен тем, что процессор кудахтера умеет аппаратно работать с числами такой размерности. Раньше было распространено ограничение в 32 бита в эпоху 32-битных процессоров.
В данной задаче нужно возвести число в степень, одна длина которой может быть 2000 цифр. Я даже хз, хватит ли вообще памяти на такую хуйню. А потом еще и разделить на другое число.
То есть, нужно реализовать как минимум операции умножения и деления (с остатком) в длинном варианте.
И вот тут и наступает момент, когда оказывается, что это можно сделать кучей разных способов с разными затратами памяти / времени.
Говорю про js.
Сразу становится очевидным, что создавать массив типа number[] для хранения десятичных цифр большого числа, мягко говоря, нихуя не рационально. Ибо для хранения одной цифры используется аж 8 байт. Хотя даже 1 байт способен хранить числа до 255. И че делать? Например, можно создать массив типа boolean[] и работать в двоичной системе счисления. Для хранения цифры будет использован 1 бит - минимально возможная память.
Для двоичных чисел также есть хитровыебаные алгоритмы умножения / деления.
Но перевод чисел между системами счисления - тоже не шибко простая хуйня. Например, для перевода из десятичной в двоичную требуется делать это большое длинное число. То есть, чтобы разделить, надо делить.
Можно, например, в ячейке типа number хранить по 19 десятичных цифр, утилизируя ее по-максимому. Но это усложнит код.
Или, например, отвести для хранения десятичной цифры 4 бита в boolean[] массиве (3 недостаточно, 4 с избытком, но 3.5 бита не бывает).
Тут куча разных подходов может быть в зависимости от целей и ограничений.
Думал над этой задачей, реализовал классический алгоритм умножения столбиком, который выполняется за O(n^2).
Но самое смешное - я обнаружил, что при умножении столбиком можно умножать не только 1 разряд, лол.
См. пикрил. На первом скрине классическое умножение столбиком, которому учат в школе.
На втором я умножил 35x39 и прибавил 16x39, но со сдвигом сразу на 2 разряда.
В моем костыльном алгоритме реализуется первый вариант, происходит очень много операций умножения.
Компьютеру похуй насколько большое число умножать в пределах разрядности, оно умножается за одинаковое время. Так что, можно умножать сразу большие куски чисел и складывать с большими сдвигами.
Я же говорил, количество возможных оптимизаций этой хуйни бесконечно.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAWxAG1gBzQTwBQCGAXImCMgEYCmATgNoC6ANIhSWZbYwJTvnX0GiAN4AoRBMQQEAZyiIaVGeih9OgxAF5EdAAwMA3OMnSwcxGgJyAklsQEAdGipgA5lAAWiALSIAjEaSiMBwNIh4zvIAVna6BogxADysTi7uHvFRANRZ3CLGQRKRiFBUyJixgYUSIWERVPIwlYhNidqWNvEwOXli1dWm5hAgNIpgUABKSioAIjCuMFDWYAAmVAAedk1ZCVX9JrLyw6Muk9MYcwvy2orKGHTHY2d3UJeLy2vrQgD834hxBX2UkOiEwNDgKxA0DsBDoMCEACpWHQooZAftiit5os1AIWKVygA5KgAd1xtD2QLoBMwxJJLCxVyE2hk2EWhP4tDwYIhUPkOxpiB2j1OUxebyg3Ep+1uKgeIyeYtm2KWqw2zMQjMW0v6gu0NLpOuqMGA4SamgtFisS0QADJbSUyhUAHz-XrooESWUYByYEAyDx4GlSj3VAC+ocQEaC0ckiigIyQ3qgRgjolAkFgCEQrLQ7M5NDwHHJNF4Og4eNIBaEfQOZnkpTMdgAsgRPA5gGg4KEi+REAB6fy6ENBQbyBBKOwcHyOptIvwAoLxxM6RsyFgTmRotMZ6DwJCoDAwbA4ACCqwACjQYONCCXGCw2FX1DwSAA3OAwFb5UeyODOJw4FcPAACJiBAlhHCiT8wDwAByODuBHOsZH-KhAOAkC2AglJoJveDEOQiRBjQjDQMwIgcMPLBcEIBxFDfWgZCoPBuEfeiqEYmhmNY7gOK4ni+Lw2CEKQ1NRFEajj1wc8VivG8oDwOg-BYAA2FgAGYWAAVhYFTEAAFj0lgAHY1J0lgjMQMzEAADmYHRbM0lgAE5LOM-4WF0UzzMQXTEC0wzXI8gAmUyGBDIA
> Если кто не понял, в чем вообще проблема, скажу, что числа в языке программирования имеют четко ограниченный максимальный размер. Например, в js тип number имеет размер 64 бита, то есть, число не может превышать 2^64. В двоичном представлении число будет представлять собой последовательность 64 единиц: 1111111111111111111111111111111111111111111111111111111111111111. То есть, все биты ячейки памяти забиты единицами, нулей нет. В десятичном виде это будет 18446744073709551615.
Нееееет, это немножко не тааааак. Попробуй вывести 18446744073709551615 в stout, чтобы понять, в чём же дело, и почему это так интересно и необычно.
> Например, можно создать массив типа boolean[] и работать в двоичной системе счисления. Для хранения цифры будет использован 1 бит - минимально возможная память.
Нееееет, это тоже немножко не тааааак. Минимально возможный 1 бит никто не выделит. В интернетиках пишут, что Boolean занимает 4 байта, но это с учётом выравнивания, в массивчике они наверное плотно лягут друг к дружке валетиками, и будут занимать по одному честному БАЙТУ, и из честных 256 значений ты сможешь занимать... 2 :( Сэкономил.
И вообще по-моему у вас есть встроенный тип BigInt, но чтобы им пользоваться в TypeScript, нужно какую-то фичу компилятора включить.
> В данной задаче нужно возвести число в степень, одна длина которой может быть 2000 цифр. Я даже хз, хватит ли вообще памяти на такую хуйню.
Нееееет, это немножко не тааааак. Её и не должно хватать. Есть куча алгоритмов по быстрому введению огромных чисел в огромные степени по какому-то модулю. Например, простенький на пикрил 2.
>В интернетиках пишут, что Boolean занимает 4 байта, но это с учётом выравнивания
Бляяяяять... Опять меня наебали. Пишут, что даже 8 байт может занимать. Как так нахуй? Всем настолько похуй на память? Ладно, я еще могу понять, почему не упаковывают в 1 байт по 8 булеанов, может там накладные расходы на такие многоходовочки будут превышать выгоду на большинстве приложений. Но какого хуя 4 или 8 байт блять?
Что-то я не понимаю. В оперативке ведь каждый БИТ имеет свой адрес? Или каждый БАЙТ?
Придумали эти байты ебаные, они только все путают. Раньше были компьютеры и с байтами из 4 и 6 битов. Байт - по сути, выдуманная хуйня.
Как решили проблему адресации памяти, когда она превысила 4 гигабайта? 32-битное число хватает только что адресовать память максимум в 4 Гб. Тупо стали использовать 64-разрядные адреса?
Почитал, вроде во всей современной оперативке адреса указывают на байты. Так какого хуя в жс булеан имеет размер, кратный степени двойки? Это как-то связано с тем, чтобы удобнее было размещать в оперативке другую хуйню, тоже кратную по размеру степени двойки? Чтобы не было нечетных байтов?
Еще и тут математики залили говна в жопу... Как жопой чуял, что не обязательно число в степень возводить.
По сути, самые эффективные алгоритмы плотно связаны с математикой. Яркий пример - криптография, по сути, чистый матан.
>Попробуй вывести 18446744073709551615 в stout, чтобы понять, в чём же дело, и почему это так интересно и необычно.
Ебаный рот этого казино! Это что еще за нахуй? Почему 2^53? Что вообще происходит? Оно должно идеально работать с числами вплоть до 2^64 - 1. Пиздец...
boolean[] - это просто предохранитель, чтобы ты случайно не положил элемент неправильного типа в массив, это не говорит ничего о том, сколько памяти в жаваскрипте под него выделится
Если тебе нужен кусок памяти конкретного размера в байтах, в жс есть ArrayBuffer https://learn.javascript.ru/arraybuffer-binary-arrays Тут можешь вручную делать упаковку 8 булеанов в 1 байт, если тебе нужно.
Динамическая типизация, то есть то, что в массив можно добавить элемент любого типа, означает, что внутри он будет реализован как массив таких структур: https://ideone.com/00Nva4, со всеми вытекающими.
(Есть реалистичные варианты это оптимизировать, например, в терминах моего примера — хранить отдельно массив однобайтовых типов ty[] и отдельно массив восьмибайтовых юнионов, получив 9 байт на элемент; затем спешлкейснуть случай, когда все элементы имеют один тип, получив 8; это приводит нас к тому, как оно и сделано на практике: https://itnext.io/v8-deep-dives-understanding-array-internals-5b17d7a28ecc; теоретически можно было бы, по аналогии с PACKED_DOUBLE_ELEMENTS и пр., спешлкейснуть случай массива булеанов и хранить его как 1 бит/элемент, но массив булеанов не является особенно частым и важным случаем, заслуживающим того, чтобы так ради него заморачиваться.)
>>723674
Да, что-то я забыл, что в жс динамическая типизация. Я думал, что если в массив кладут только значения одного типа, то он будет оптимизирован для них. На самом деле нет.
Попробовал решить ту задачку с литкода в лоб (сначала возвести в степень, потом разделить). Через BigInt, так как вручную в жс с его динамической типизацией я быстрее один хуй не сделаю. Получил пикрил. Что за мир, даже у BigInt есть максимальный размер... Я думал, что размер только оперативкой ограничен, покуда кудахтер не расплавится. Но нихуя.
Похоже, единственным возможным вариантом в этой задаче является специализированный математический алгоритм возведения в степень по модулю.
Работает уже лучше, чем вычисление в лоб и память не жрет.
Но все равно есть проблемка. Его временная сложность равна O(n), где n - степень. То есть, он один хуй неприемлем для возведения в ебанистические степени с 2000 цифр.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAWzgExAGwIYCcAKcA7gGLYDOUAFNgFyJgjIBGAprgDSLP2MvsBtALpdUaXkza5EAXkQBGAMyKA7AEoJ-aQG8AUIgOIICSolYAPAA4JWYKLMQAhGAHMAknarMAdACs4MGBUAOTBamoA3PqGmKz2EA7yUYaIwHDSVLH2MA4ADGARiDkAPGZWNnaFMADU1WqIeikpCXI0iABURvUApCjoyYYAvtEGuHEguEgQUcO6xmDkcLHemHAuVGJYeISkFNQqABwATABsKlwC8ly517eIN-fXQuFRQA
Жалко, я абсолютно нихуя не понимаю почему и как.
Математика - не мой конек.
Нет, я пойму, если буду изучать эту хуйню пару недель, но у меня нет на это времени. А сходу понять - я слишком тупой.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAWzgExAGwIYCcAKcA7gEowDmAFlACpwAyApsFABQBG2AzowFyJgQydo1wAaRIwAeABwSMwUfoOGiA2gF0JqNMqEjciALyIAjAGZzAdgCUe1YYDeAKERvEmRlEmzjiAEIUAJKKrNJyYApQAHQAVnAwYKwA5Mk2NgDcru6e3riMXFjeJqZZ7oicPH6VjIgApCjoZe5ElDCeiGG+AHyIAAw2iC7l5TDAneH1iABMSEbzZmCDwyOr+YWYxZ3rRYgAVBXcjIMNOs2rAL7Zq5Mmk929pmDnIzV+HEf7B9MnjWgvV2uiHyUBAuCQO02WUBEAQXDgnmimDg5FYOiweEIpAo1DoTBYrCsAA5pgA2KwSNSmCQUxC0gAsEnMEmpdIkfRZEkZiG5AE4JNMJESJABWdnixD8xDMswC0USKWkiVSqUcyUSJX9eXSmkKoX69WIYUzbXc1lSmXGtViw02zWs1nGi26o3a402m0ytXcmWsm1ml2Kg1Og1qzW042+zmyrWITXGh0apOGx3azWqiWs2lZl2C12If1c7V5oMFiUJ5Vul2asPR420ksG1lq2lS7m09NynUxmUq5NWg1S2nDpl6svjhljyOZrt+8tFnmj-POtnj3sLvlLmV57kh7uWrsV7t5vPG7l5m217tqjPjgMxgeLk3j407ru0wurzuxvf2hcjw0I2jbkfWTbkbTzGtoznbtHylY1HyvVlv01G16wXPcpTfVdWzHCCu2-AD4O1Yjx0vJc0Lwl0ZW5TVaK7GV8O7VlwLHGUZTo6N2K7NVvX-Bil1IoCyPnbt725G9tU-TccIXVNVyYmTcJjYSsLk6MOwXDjtTVPMWMEniJUbfNWNXRiDTzddxyleS90sl0+JjeTaV06iFz-WMDxfKcMIo6CFwvMdrSXHMn1-XM-LXMdvylG1aXM58+xEmMry84Lx1QsDtVC1KxxAsdWRol0Pwsytn3isqW2K9TnxtQql04-NAttUTmsahCDQqh8dOLXzx0TWNlMymNIKy1dJIytiXQ6-NhunfNP0oidtS608XVC5yt2TYzuMNKN+qkpt30HLtFoC5N6rjCUUOjNV9NjUylpPZMirEpc9xK6y6xIgrOtnb6YztA0ltcp92xOr783StUEqY+Ml3E9aIoU4Nkfsw1nrMrtb3RwjD1E5DeuvQzYwmzHceTCbmwlBL5rzGHspq+GvzKx9qafIHYzW2qjOBgSueTLreP+w07rHNTY0J2TDVLe73TTByLrcyGrPSiXd2TTVMashLJxjb9X2TW81Xl6Wr3SvXSyqkyDPzdCnxgqDDXvNs8oB8NSvHdHXt2qX7w8uKjsAynQ2Ahcxe62D3ttqXrcu16V0Ukmuq8gCZom-bMdA-clauw0tZnFG8+ahKGfK-my484SXPDwXNdt035q9aKkYxrjGbzn2mYNc9RQ0dIsiAA
Намного проще qsort. В qsort в разделении Хоара вообще происходит ебаная черная магия, а тут можно накостылить алгоритм слияния без особых напрягов.
Сортировка слиянием всем хороша, кроме того, что жрет память в размере исходного массива.
Ну что ж, теперь я знаю аж 2 эффективных алгоритма сортировки.
https://www.typescriptlang.org/play?#code/PQKhCgAIUhZBTATgc3pAzge0QFwHRQwAqAlgLbwBckkA8gBQB2IANpskwJScHSQDKABwCGAYyp0uvEMHAAzAK6NROEpkaQKKeP2w4mCsumqNDAIyQBtALoAaSHMSYyJ80kgBeSAAZ7OTK5kFoiekKZGeCzwjMg4ABacgcE2kADeUDSQJHKQ9P6QALQOTmSQADyQAEycaRmZmYjwOAqIGuHoeOgsJOL0js5+mJwA3HWQAL5jouroOJokACYLUQCSjAvwAB6hsMLxeHJs2PR9JZAA1JD+NcBVI2ONza2aSKj0Wqi6uAZG9v1k9jIi2W8DWG02nEBrx0eh+6EBwNW6y2g24o0m8iUKjUGg+8D6JEQsySVjsGHg03WJMQNkSYTcNOstXqlNmkEa6AULBw1JSXhso3qUTmckJszBW1C3kFmWF5MpCwl2y80rGAHc4iQorkOVz8FEYvFyg4xfrorE4hd5eoFpFzfEaul6vVsrl0BSbUrPB4vO6FXbDZaAD5Bk1EnCWUXhpVMsq+j3rSx+z3IzbWR1jZ0NeCc7l4QQKdBxAnhyOmpXnc7pmVZyZZmjwFjurI5Evi1PerxR2YBi2QENh2Zl6OppkAPnjCqTCcVo4z9edurzBaL9GTifXs-Blermcydf34AeTRaGiXOHRR9ZcxIjALPPpQVJoUsvkgABZKu-7ABGb+QH97AANgAZl-AB2ewwMgABWSoIPsODrFGVlMCiSJ2HoAAiW970oLD7FwhQcHuVD0LYDgsKwXB4AWfCoW0L59CIkj7iAA
a^x = a^(x / 2 × 2) =
= a^(x // 2 × 2) = (a^(x // 2))^2, если x чётное, и
= a^(x // 2 × 2 + 1) = (a^(x // 2))^2 × a, если x нечётное.
Это позволяет реализовать алгоритм рекурсивно с базовым случаем a^0 или a^1, но далее делаем наблюдение, что «x // 2» и «а чётное ли x» соответствуют операциям «сдвинуть x на 1 бит вправо» и «посмотреть на младший бит x», то есть весь алгоритм сводится к «проанализировать двоичное представление x и перевести его в последовательность операций».
>a^x = a^(x / 2 × 2) =
>= a^(x // 2 × 2) = (a^(x // 2))^2, если x чётное, и
>= a^(x // 2 × 2 + 1) = (a^(x // 2))^2 × a, если x нечётное.
Так это обычное возведение в степень, это хуйня, это я понимаю.
Надо по модулю. a^x % m, где x длиной 2000 цифр.
(a × b) mod n = ((a mod n) × (b mod n)) mod n, в чём легко убедиться, расписав a и b как суммы вида kn + r: https://crypto.stackexchange.com/a/13290. :>
Написано, что хеш-функция выдает сразу индексы массива. Но как блять? Вот есть md5 или sha1. Они выдают хеш определенной фиксированной длины. Как мне эту срань использовать как индекс массива? Допустим, хеш длиной 32 бита. Это мне надо использовать массив длиной 2^32? Чтобы сохранить 10 элементов? Че за хуйня вообще?
В другом месте написано, что хеш-функция принимает аргументом количество элементов в массиве. Допустим. Ну тупо длина хеша будет ограничена. И все равно, это надо заранее размер массива знать? И потом пересобирать его, когда он заполняется? Но тогда и перехешировать придется.
В хеш-таблицах используются какие-то особые хеш-функции?
Слыхал про symhash, когда похожие данные выдают похожие хеши, но это другое
Используется хэш % размер_таблицы (на практике в качестве размера_таблицы используется степень двойки, чтобы можно было вместо медленного % сделать хэш & (размер_таблицы − 1); иными словами, берутся последние log₂_размера_таблицы бит хэша), но можно (во всяком случае, с открытой адресацией...) много придумать сверх этого. Например, остальные биты хэша можно использовать для сдвигов в ходе разрешения коллизии, то есть в https://ru.wikipedia.org/wiki/Линейное_зондирование#Поиск вместо прибавления единицы прибавлять следующие log₂_размера_таблицы бит хэша, так что в случае 4-байтовых хэшей ABCD, EFGD, HIJD, ... и 256-элементной таблицы изначальным индексом каждого из них будет XXXD % 256 = D и они все сколлидятся, но до 3 шагов дальнейшего разрешения коллизии будут разными.
И да, массив в любом случае нужно пересобирать и перехэшировать, от этого не уйти, это нормально и естественно, все это делают.