122 Кб, 1280x720В этом треде я буду задротить литкод. Цель - решить 100 задач на литкоде к концу марта 2024. Цель, конечно, не в самом количестве задач. Это так, примерный ориентир. Цель в том, чтобы проработать основные структуры данных и основные алгоритмы, основные методы решения алгоритмических задач (да, такие тоже есть). В наличии имеется книга "Грокаем алгоритмы". Ее необходимо изучить полностью. По мере изучения планирую решать несколько задач на тему раздела. Когда изучу всю книгу, буду уже пробовать решать рандомные задачи, где может встретиться какая угодно СД/алгоритм. Также есть несколько задач, проработать которые я хочу вне очереди, потому что они важные и часто встречаются. Возможно, не только литкод буду использовать. Есть еще yandex code run, например. Пока что решил 3 задачи.
93 Кб, 1260x652Решил задачу на проверку структуры скобочек.
Я раньше встречал ее на дваче, только там были только круглые скобки, а на литкоде 3 типа скобок.
Я помнил, что она решается через стек, но не понимал, нахуя тут нужен вообще стек?
Например, у меня возникла мысль просто создать переменную числовую. И делать +1, если скобка открывающая и -1, если закрывающая. Если в конце получился 0, то все заебись. Почему это не будет работать? Это сработает на строке типа (()()), но не сработает на )()((). Недостаточно чтобы просто количество открывающих и закрывающих скобок совпадало. К тому же, в литкодовском варианте задачи есть еще и другие типы скобок и надо проверять их соответствие, чтобы каждой открывающей соответствовала закрывающая того же типа.
Короче, нужно хранить информацию не только о числе скобок, но еще и об уровне, где они находятся, а также об их типе. Короче, эта задача идеально ложится на стек, со стеком получается очень элегантно и эффективно.
Есть еще одна задача того же типа на стек, которую я хочу попробовать решить - это написание парсера-калькулятора. То есть, он принимает строку вида "(1 * 3) - ((5 + 4) / 13)" и выдает результат вычисления. Тут тоже надо учитывать скобки + операторы + приоритет операторов. Задача как минимум медиум уровня, а может и хард. В универе я писал такой парсер, но не сам + там был костыль через польскую нотацию. Короче, интересно было бы попробовать самому написать с нуля. Задача ультра-хард - интерпретатор простенького япа.
Еще бесит на литкоде, что там задрачивают затраты по времени и памяти, экономя на спичках. Например, вот на пике слева топовое решение по вычислительным ресурсам, а справа мое. Алгоритмической разницы никакой, но слева решение бьет 99% по памяти, а мое только 40%. А все из-за костылей уровня использования объекта вместо карты. И такая хуйня там постоянно. Ты исправляешь буквально пару строк на другие конструкции языка и решение уже получает +40% рейтинга. Потому что литкод смотрит тупо на циферки памяти и времени выполнения, даже если они отличаются на 1%. Впрочем, поебать, главное это вычислительная сложность алгоритма. Все же, я там не за рейтингом, а за знаниями.
Я раньше встречал ее на дваче, только там были только круглые скобки, а на литкоде 3 типа скобок.
Я помнил, что она решается через стек, но не понимал, нахуя тут нужен вообще стек?
Например, у меня возникла мысль просто создать переменную числовую. И делать +1, если скобка открывающая и -1, если закрывающая. Если в конце получился 0, то все заебись. Почему это не будет работать? Это сработает на строке типа (()()), но не сработает на )()((). Недостаточно чтобы просто количество открывающих и закрывающих скобок совпадало. К тому же, в литкодовском варианте задачи есть еще и другие типы скобок и надо проверять их соответствие, чтобы каждой открывающей соответствовала закрывающая того же типа.
Короче, нужно хранить информацию не только о числе скобок, но еще и об уровне, где они находятся, а также об их типе. Короче, эта задача идеально ложится на стек, со стеком получается очень элегантно и эффективно.
Есть еще одна задача того же типа на стек, которую я хочу попробовать решить - это написание парсера-калькулятора. То есть, он принимает строку вида "(1 * 3) - ((5 + 4) / 13)" и выдает результат вычисления. Тут тоже надо учитывать скобки + операторы + приоритет операторов. Задача как минимум медиум уровня, а может и хард. В универе я писал такой парсер, но не сам + там был костыль через польскую нотацию. Короче, интересно было бы попробовать самому написать с нуля. Задача ультра-хард - интерпретатор простенького япа.
Еще бесит на литкоде, что там задрачивают затраты по времени и памяти, экономя на спичках. Например, вот на пике слева топовое решение по вычислительным ресурсам, а справа мое. Алгоритмической разницы никакой, но слева решение бьет 99% по памяти, а мое только 40%. А все из-за костылей уровня использования объекта вместо карты. И такая хуйня там постоянно. Ты исправляешь буквально пару строк на другие конструкции языка и решение уже получает +40% рейтинга. Потому что литкод смотрит тупо на циферки памяти и времени выполнения, даже если они отличаются на 1%. Впрочем, поебать, главное это вычислительная сложность алгоритма. Все же, я там не за рейтингом, а за знаниями.
93 Кб, 1260x652Решил задачу на проверку структуры скобочек.
Я раньше встречал ее на дваче, только там были только круглые скобки, а на литкоде 3 типа скобок.
Я помнил, что она решается через стек, но не понимал, нахуя тут нужен вообще стек?
Например, у меня возникла мысль просто создать переменную числовую. И делать +1, если скобка открывающая и -1, если закрывающая. Если в конце получился 0, то все заебись. Почему это не будет работать? Это сработает на строке типа (()()), но не сработает на )()((). Недостаточно чтобы просто количество открывающих и закрывающих скобок совпадало. К тому же, в литкодовском варианте задачи есть еще и другие типы скобок и надо проверять их соответствие, чтобы каждой открывающей соответствовала закрывающая того же типа.
Короче, нужно хранить информацию не только о числе скобок, но еще и об уровне, где они находятся, а также об их типе. Короче, эта задача идеально ложится на стек, со стеком получается очень элегантно и эффективно.
Есть еще одна задача того же типа на стек, которую я хочу попробовать решить - это написание парсера-калькулятора. То есть, он принимает строку вида "(1 * 3) - ((5 + 4) / 13)" и выдает результат вычисления. Тут тоже надо учитывать скобки + операторы + приоритет операторов. Задача как минимум медиум уровня, а может и хард. В универе я писал такой парсер, но не сам + там был костыль через польскую нотацию. Короче, интересно было бы попробовать самому написать с нуля. Задача ультра-хард - интерпретатор простенького япа.
Еще бесит на литкоде, что там задрачивают затраты по времени и памяти, экономя на спичках. Например, вот на пике слева топовое решение по вычислительным ресурсам, а справа мое. Алгоритмической разницы никакой, но слева решение бьет 99% по памяти, а мое только 40%. А все из-за костылей уровня использования объекта вместо карты. И такая хуйня там постоянно. Ты исправляешь буквально пару строк на другие конструкции языка и решение уже получает +40% рейтинга. Потому что литкод смотрит тупо на циферки памяти и времени выполнения, даже если они отличаются на 1%. Впрочем, поебать, главное это вычислительная сложность алгоритма. Все же, я там не за рейтингом, а за знаниями.
Я раньше встречал ее на дваче, только там были только круглые скобки, а на литкоде 3 типа скобок.
Я помнил, что она решается через стек, но не понимал, нахуя тут нужен вообще стек?
Например, у меня возникла мысль просто создать переменную числовую. И делать +1, если скобка открывающая и -1, если закрывающая. Если в конце получился 0, то все заебись. Почему это не будет работать? Это сработает на строке типа (()()), но не сработает на )()((). Недостаточно чтобы просто количество открывающих и закрывающих скобок совпадало. К тому же, в литкодовском варианте задачи есть еще и другие типы скобок и надо проверять их соответствие, чтобы каждой открывающей соответствовала закрывающая того же типа.
Короче, нужно хранить информацию не только о числе скобок, но еще и об уровне, где они находятся, а также об их типе. Короче, эта задача идеально ложится на стек, со стеком получается очень элегантно и эффективно.
Есть еще одна задача того же типа на стек, которую я хочу попробовать решить - это написание парсера-калькулятора. То есть, он принимает строку вида "(1 * 3) - ((5 + 4) / 13)" и выдает результат вычисления. Тут тоже надо учитывать скобки + операторы + приоритет операторов. Задача как минимум медиум уровня, а может и хард. В универе я писал такой парсер, но не сам + там был костыль через польскую нотацию. Короче, интересно было бы попробовать самому написать с нуля. Задача ультра-хард - интерпретатор простенького япа.
Еще бесит на литкоде, что там задрачивают затраты по времени и памяти, экономя на спичках. Например, вот на пике слева топовое решение по вычислительным ресурсам, а справа мое. Алгоритмической разницы никакой, но слева решение бьет 99% по памяти, а мое только 40%. А все из-за костылей уровня использования объекта вместо карты. И такая хуйня там постоянно. Ты исправляешь буквально пару строк на другие конструкции языка и решение уже получает +40% рейтинга. Потому что литкод смотрит тупо на циферки памяти и времени выполнения, даже если они отличаются на 1%. Впрочем, поебать, главное это вычислительная сложность алгоритма. Все же, я там не за рейтингом, а за знаниями.
225 Кб, 1000x1000>>1869
Ты про парсер или про скобочки? Обе, скорее всего, нет (по-человечески), но:
— Со скобочками можно пытаться удалять из строки (), [], {}, и если осталась пустая строка — структура была правильной, что, очевидно, будет квадратичным решением, чью немасштабируемость любит проповедовать вот он: 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, но, возможно, это позволяет сделать без стека... но опять же, я сказал «по-человечески», а это хуже сортировочной станции... и аппаратный стек всё равно понадобится, чтобы это дерево потом вычислить, поэтому а смысл.)
Ты про парсер или про скобочки? Обе, скорее всего, нет (по-человечески), но:
— Со скобочками можно пытаться удалять из строки (), [], {}, и если осталась пустая строка — структура была правильной, что, очевидно, будет квадратичным решением, чью немасштабируемость любит проповедовать вот он: 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, но, возможно, это позволяет сделать без стека... но опять же, я сказал «по-человечески», а это хуже сортировочной станции... и аппаратный стек всё равно понадобится, чтобы это дерево потом вычислить, поэтому а смысл.)
32 Кб, 430x641>>1874
Это ты забавно придумал, я даже проверил, вроде работает.
Не квадратичным, но пропорциональным арифметической прогрессии с негативным шагом и начальным членом N.
Работает, конечно, медленнее, чем решение на стеке.
Почитал тут про парсеры немного. Там не все так просто, это отдельная область алгоритмов, с полтычка, как со скобочками, уже не сделаешь. И, похоже, я не просто так в универе обратную польскую нотацию использовал. Возможно ли сразу вычислить инфиксную нотацию без перевода в другую? За 1 проход?
>Со скобочками можно пытаться удалять из строки (), [], {}, и если осталась пустая строка — структура была правильной
Это ты забавно придумал, я даже проверил, вроде работает.
>что, очевидно, будет квадратичным решением
Не квадратичным, но пропорциональным арифметической прогрессии с негативным шагом и начальным членом N.
Работает, конечно, медленнее, чем решение на стеке.
Почитал тут про парсеры немного. Там не все так просто, это отдельная область алгоритмов, с полтычка, как со скобочками, уже не сделаешь. И, похоже, я не просто так в универе обратную польскую нотацию использовал. Возможно ли сразу вычислить инфиксную нотацию без перевода в другую? За 1 проход?
4,2 Мб, 2894x4093>>1935
Оно выполнит число действий, пропорциональное сумме этой прогрессии, в которой светится N², это и значит квадратичное :^).
Да, можно, там «рабочий псевдокод» в статье. Сделал на Паскале :) : https://ideone.com/lEIunA.
>>1882
Нашёл кому указывать, биомусор.
>пропорциональным арифметической прогрессии с негативным шагом и начальным членом N
Оно выполнит число действий, пропорциональное сумме этой прогрессии, в которой светится N², это и значит квадратичное :^).
>Возможно ли сразу вычислить инфиксную нотацию без перевода в другую? За 1 проход?
Да, можно, там «рабочий псевдокод» в статье. Сделал на Паскале :) : https://ideone.com/lEIunA.
>>1882
Нашёл кому указывать, биомусор.
>>1982
Хуясе раздутое самомнение
И такими словами разбрасывается чел злоупотребляющий манямэ-джипегами? Ой вэй!
>Нашёл кому указывать
Хуясе раздутое самомнение
> биомусор
И такими словами разбрасывается чел злоупотребляющий манямэ-джипегами? Ой вэй!
42 Кб, 760x554Решаю задачу 224 на написание простого калькулятора. Все началось с того, что я совершенно нихуя не понял алгоритм сортировочной станции, а operator precedence parser, который является генерализацией предыдущего алгоритма и про который даже нет статей на русском - тем более.
Но это все и не нужно! Ведь в этой задаче приоритет всех операторов одинаковый, что значительно упрощает дело. Решил попробовать написать алгоритм сам.
Допустим, есть выражение "(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". А задом наперед вычислять нельзя, иначе получится хуйня. И что делать блять? То есть, это надо мне каким-то хуем прочитать кусок стека в обычном направлении, чтобы вычислить кусок выражения. Это, конечно, можно сделать, но выглядит как костыль. И доп расходы на память. Можно хранить в стеке не токены, а их номер в строке, тогда прочитать будет легче. Хуй знает, короче.
Но это все и не нужно! Ведь в этой задаче приоритет всех операторов одинаковый, что значительно упрощает дело. Решил попробовать написать алгоритм сам.
Допустим, есть выражение "(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". А задом наперед вычислять нельзя, иначе получится хуйня. И что делать блять? То есть, это надо мне каким-то хуем прочитать кусок стека в обычном направлении, чтобы вычислить кусок выражения. Это, конечно, можно сделать, но выглядит как костыль. И доп расходы на память. Можно хранить в стеке не токены, а их номер в строке, тогда прочитать будет легче. Хуй знает, короче.
107 Кб, 1515x648>>2234
https://pastebin.com/mEuu16if
Блять, целый день убил на это говно. Меня радует хотя бы то, что я вообще додумался до идеи раскрытия стека.
В итоге получился какой-то адовый высер обезьяны, код некрасивый и костыльный.
А еще блять, в самом конце стек загадочным образом трансформируется в очередь.
Вот как блять я должен наизусть помнить алгоритмы парсинга, которые диды, всю жизнь занимавшиеся информатикой, годами разрабатывали? Это оно у них выглядит элегантно. При попытке додуматься самому до подобной хуйни, получается хуже и куда более всрато. И это блять в задаче нет приоритетов операторов.
Есть и хороший момент. Например, при проходе по выражению в RPN форме, вычисление куска стека происходит очень просто. Выталкивается оператор/функция, исходя из того, сколько аргументов он ожидает, выталкивается нужное число операндов. У меня же подобной хуйней занимается отдельная функция, которой еще и приходится переворачивать стек. Короче, шибко дохуя лишней работы я не делаю, просто более всрато.
Еще пытался сделать примитивный конвертер в обратную польскую нотацию, но обосрался.
https://pastebin.com/mEuu16if
Блять, целый день убил на это говно. Меня радует хотя бы то, что я вообще додумался до идеи раскрытия стека.
В итоге получился какой-то адовый высер обезьяны, код некрасивый и костыльный.
А еще блять, в самом конце стек загадочным образом трансформируется в очередь.
Вот как блять я должен наизусть помнить алгоритмы парсинга, которые диды, всю жизнь занимавшиеся информатикой, годами разрабатывали? Это оно у них выглядит элегантно. При попытке додуматься самому до подобной хуйни, получается хуже и куда более всрато. И это блять в задаче нет приоритетов операторов.
Есть и хороший момент. Например, при проходе по выражению в RPN форме, вычисление куска стека происходит очень просто. Выталкивается оператор/функция, исходя из того, сколько аргументов он ожидает, выталкивается нужное число операндов. У меня же подобной хуйней занимается отдельная функция, которой еще и приходится переворачивать стек. Короче, шибко дохуя лишней работы я не делаю, просто более всрато.
Еще пытался сделать примитивный конвертер в обратную польскую нотацию, но обосрался.
>>2244
Ухх бля, так плохо, что даже хорошо
Ухх бля, так плохо, что даже хорошо
>>1982
Ты просто реализовал алгоритм из статьи или по памяти нахуярил?
Но... зачем, а главное - нахуя?
>Сделал
Ты просто реализовал алгоритм из статьи или по памяти нахуярил?
>на Паскале :)
Но... зачем, а главное - нахуя?
Увидел вчера в предложке литкода задачу на вычисление обратной польской нотации. Я знал, что это будет легко. Решил решить. По сравнению с алгоритмом сортирной станции (получение этой самой нотации из инфиксной), самое ее вычисление происходит элементарно нахуй.
У меня даже возникло ощущение, что я начинаю интуитивно понимать, как работает стек.
Накидал реализацию минут за 5-7, но потом завис на 15 минут на этом блять truncates towards zero. Что это блять? В первый раз вижу такую хуйню, я даже блять не понял, что от меня хотят. Поставил floor - 1 кейс не работает. Поставил ceil - не работает. Поставил round - не работает блять. Только потом в результате гуглинга догнал, чем отличается этот truncates от округления. Короче, отличается на негативных числах. На позитивных аналогичен floor.
А еще, то ли в результате рандома, то ли еще чего, у меня получились какие-то выдающиеся результаты по памяти, лучше чем у 96% других решений. Наверняка рандом ебаный. Там 1 килобайт в сторону, уже пролетаешь. Тупо путем перезапуска одного и того же решения получаешь разные результаты.
У меня даже возникло ощущение, что я начинаю интуитивно понимать, как работает стек.
Накидал реализацию минут за 5-7, но потом завис на 15 минут на этом блять truncates towards zero. Что это блять? В первый раз вижу такую хуйню, я даже блять не понял, что от меня хотят. Поставил floor - 1 кейс не работает. Поставил ceil - не работает. Поставил round - не работает блять. Только потом в результате гуглинга догнал, чем отличается этот truncates от округления. Короче, отличается на негативных числах. На позитивных аналогичен floor.
А еще, то ли в результате рандома, то ли еще чего, у меня получились какие-то выдающиеся результаты по памяти, лучше чем у 96% других решений. Наверняка рандом ебаный. Там 1 килобайт в сторону, уже пролетаешь. Тупо путем перезапуска одного и того же решения получаешь разные результаты.
>>2336
Там рандом какой-то. Кто-то вроде составлял список советов https://leetcode.com/discuss/general-discussion/601899/how-to-get-90-up-runtime-perf-tips-ft-js как писать жс/тс, чтобы в метить в топовые результаты. Я вроде попробовал применить и как будто решение с первого пика немного чаще бывает быстрее, чем через свитч.
Количество строк / символов - гораздо более надёжная метрика.
Там рандом какой-то. Кто-то вроде составлял список советов https://leetcode.com/discuss/general-discussion/601899/how-to-get-90-up-runtime-perf-tips-ft-js как писать жс/тс, чтобы в метить в топовые результаты. Я вроде попробовал применить и как будто решение с первого пика немного чаще бывает быстрее, чем через свитч.
Количество строк / символов - гораздо более надёжная метрика.
>>2360
Это все бред, конечно, ебаный, выдрачивать костыли языка ради экономии килобайт и миллисекунд, тем более на js-параше, тем более в обучающей задачке на сраном литкоде.
Вот тут чел об этом сказал:
https://leetcodetherapy.com/runtime-useless
>Кто-то вроде составлял список советов
Это все бред, конечно, ебаный, выдрачивать костыли языка ради экономии килобайт и миллисекунд, тем более на js-параше, тем более в обучающей задачке на сраном литкоде.
Вот тут чел об этом сказал:
https://leetcodetherapy.com/runtime-useless
https://leetcodetherapy.com/hard-questions
Также он говорит, что Hard вопросы почти никогда не встречаются на интервью хотя блять, смотря на каких. Читал про собеседование индуса в гугл, ему там навалили таких задач на деревья, что одно описание занимает 3 страницы текста.
Я про это тоже слышал раньше. Что хард вопросы почти никогда спрашивают. Тупо нет времени на это на интервью, тупо тяжело интервьюеру следить за твоим решением.
Также он говорит, что Hard вопросы почти никогда не встречаются на интервью хотя блять, смотря на каких. Читал про собеседование индуса в гугл, ему там навалили таких задач на деревья, что одно описание занимает 3 страницы текста.
Я про это тоже слышал раньше. Что хард вопросы почти никогда спрашивают. Тупо нет времени на это на интервью, тупо тяжело интервьюеру следить за твоим решением.
https://www.youtube.com/watch?v=pS8A-TWAICQ
А еще вот чувак, который решил 1500+ задач на литкоде. Причем он задрачивал это говно целенаправленно для прохождения собеседований в компании США.
А еще вот чувак, который решил 1500+ задач на литкоде. Причем он задрачивал это говно целенаправленно для прохождения собеседований в компании США.
85 Кб, 957x1235>>2373
Звучит интереснее и приносит больше удовлетворения, чем проходить собеседования или работать на работе и писать js код.
>выдрачивать костыли языка ради экономии килобайт и миллисекунд, тем более на js-параше, тем более в обучающей задачке на сраном литкоде
Звучит интереснее и приносит больше удовлетворения, чем проходить собеседования или работать на работе и писать js код.
На мой взгляд, алгоритмы действительно нахуй не нужны программисту. Можно писать очень неплохие программы, не зная, чем массив отличается от связного списка. Иногда, конечно, это приводит к забавным ситуациям, когда чел на ровном месте пишет реализацию, потребляющую овердохуя ресурсов там, где просто выбор иной структуры данных позволил бы сделать в 10 тысяч раз быстрее. Но будем честны, таких случаев с гулькин хуй.
Тем не менее, я считаю, что в повседневной деятельности программиста некая БАЗА по алгоритмам полезна. Как минимум, знание основных структур данных и сколько времени на них занимают базовые операции. Например, если тебе требуется изменять порядок элементов в коллекции, то лучше выбрать для нее связный список, а не массив, потому что там позиция элемента изменяется за константное время, а в массиве за линейное. Что как раз и приводит к ситуациям, когда программа зависает, когда ты строчку в таблице переместил, потому что там при каждой такой операции весь массив нахуй пересобирается. Еще дрочево литкода приводит к пониманию, что нехуй копировать массивы по 8 раз на лету, где можно все сделать in place. Иногда на stackoverflow видишь такие высеры, что просто охуеваешь. Где чел на ровном месте несколько раз копирует строку/массив просто по приколу. Обычно это не приведет к негативным последствиям, но как только у тебя данных становится много, эта хуйня убьет твою программу нахуй. Эти мелкие нюансы начинаешь подмечать. Все, дальше уже не надо. Все эти верчения деревьев и парсеры оставим дидам-информатикам, которые пишут стандартную библиотеку япа.
Но тем не менее, это говно слишком часто стали спрашивать на собесах и я вынужден его учить, чтобы сойти за умного.
Тем не менее, я считаю, что в повседневной деятельности программиста некая БАЗА по алгоритмам полезна. Как минимум, знание основных структур данных и сколько времени на них занимают базовые операции. Например, если тебе требуется изменять порядок элементов в коллекции, то лучше выбрать для нее связный список, а не массив, потому что там позиция элемента изменяется за константное время, а в массиве за линейное. Что как раз и приводит к ситуациям, когда программа зависает, когда ты строчку в таблице переместил, потому что там при каждой такой операции весь массив нахуй пересобирается. Еще дрочево литкода приводит к пониманию, что нехуй копировать массивы по 8 раз на лету, где можно все сделать in place. Иногда на stackoverflow видишь такие высеры, что просто охуеваешь. Где чел на ровном месте несколько раз копирует строку/массив просто по приколу. Обычно это не приведет к негативным последствиям, но как только у тебя данных становится много, эта хуйня убьет твою программу нахуй. Эти мелкие нюансы начинаешь подмечать. Все, дальше уже не надо. Все эти верчения деревьев и парсеры оставим дидам-информатикам, которые пишут стандартную библиотеку япа.
Но тем не менее, это говно слишком часто стали спрашивать на собесах и я вынужден его учить, чтобы сойти за умного.
>>2382
Хороший котик!
Хороший котик!
287 Кб, 1280x1811>>2256
Я перевёл псевдокод из статьи, потому что мне было лень думать, но до этого реально можно самому додуматься. Там есть объяснение через грамматики:
— <ВЫРАЖЕНИЕ>, или <АДДИТИВНОЕ ВЫРАЖЕНИЕ> — это одно или несколько <МУЛЬТИПЛИКАТИВНЫХ ВЫРАЖЕНИЙ>, разделённых «+» или «−»;
— <МУЛЬТИПЛИКАТИВНОЕ ВЫРАЖЕНИЕ> — это одно или несколько <ПРАЙМАРИ>, разделённых «×» или «/»;
— <ПРАЙМАРИ> — это либо число, либо открывающая скобка плюс <ВЫРАЖЕНИЕ> плюс закрывающая скобка, либо ±<ВЫРАЖЕНИЕ>.
Это дословно переводится в scan_expression, которая вызывает один или более (пока следует оператор «+» или «−») scan_multiplicative, которая вызывает один или более scan_primary. Например, в 2+3×4 первым <МУЛЬТИПЛИКАТИВНЫМ ВЫРАЖЕНИЕМ> будет просто «2», вторым — «3×4». Опер-чё-то-там обобщает это на произвольное число приоритетов и разбирается с ассоциативностью.
Я перевёл псевдокод из статьи, потому что мне было лень думать, но до этого реально можно самому додуматься. Там есть объяснение через грамматики:
— <ВЫРАЖЕНИЕ>, или <АДДИТИВНОЕ ВЫРАЖЕНИЕ> — это одно или несколько <МУЛЬТИПЛИКАТИВНЫХ ВЫРАЖЕНИЙ>, разделённых «+» или «−»;
— <МУЛЬТИПЛИКАТИВНОЕ ВЫРАЖЕНИЕ> — это одно или несколько <ПРАЙМАРИ>, разделённых «×» или «/»;
— <ПРАЙМАРИ> — это либо число, либо открывающая скобка плюс <ВЫРАЖЕНИЕ> плюс закрывающая скобка, либо ±<ВЫРАЖЕНИЕ>.
Это дословно переводится в scan_expression, которая вызывает один или более (пока следует оператор «+» или «−») scan_multiplicative, которая вызывает один или более scan_primary. Например, в 2+3×4 первым <МУЛЬТИПЛИКАТИВНЫМ ВЫРАЖЕНИЕМ> будет просто «2», вторым — «3×4». Опер-чё-то-там обобщает это на произвольное число приоритетов и разбирается с ассоциативностью.
Пролистывал тут книгу "Грокаем алгоритмы" для общего ознакомления с материалом.
Для интереса заглянул в раздел про динамическое программирование и охуел. В эту кроличью нору мне лезть пока рано. В частности, увидел там задачу про поиск наибольшей общей подстроки. Блять, я видел эту задачу раньше, натыкался на нее где-то. Но я даже подумать не мог, что решается она настолько ебанистическим способом. Да уж, некоторые задачи имеют очень простую формулировку и очень сложное решение. Типа как великая теорема Ферма.
Так, по в верхам поглядел и понял, что вроде как при выборе значения, которое вписываешь в ячейку таблицы, не требуется бегать по всей остальной таблице, а смотрится только какая-то 1 соседняя ячейка (разная в зависимости от задачи). Также непонятно, а может ли эта таблица быть многомерной? Типа тензор. Хз, пока что похуй.
Еще что странно, в этой книге нет раздела по ДЕРЕВЬЯМ блять. Как так нахуй? Это же база. Зато динамическое програмирование впендюрили, OCR и прочее.
Для интереса заглянул в раздел про динамическое программирование и охуел. В эту кроличью нору мне лезть пока рано. В частности, увидел там задачу про поиск наибольшей общей подстроки. Блять, я видел эту задачу раньше, натыкался на нее где-то. Но я даже подумать не мог, что решается она настолько ебанистическим способом. Да уж, некоторые задачи имеют очень простую формулировку и очень сложное решение. Типа как великая теорема Ферма.
Так, по в верхам поглядел и понял, что вроде как при выборе значения, которое вписываешь в ячейку таблицы, не требуется бегать по всей остальной таблице, а смотрится только какая-то 1 соседняя ячейка (разная в зависимости от задачи). Также непонятно, а может ли эта таблица быть многомерной? Типа тензор. Хз, пока что похуй.
Еще что странно, в этой книге нет раздела по ДЕРЕВЬЯМ блять. Как так нахуй? Это же база. Зато динамическое програмирование впендюрили, OCR и прочее.
35 Кб, 1303x193Ебать я тут набрел на одну хуйню... То есть, КАЖДОЕ целое число раскладывается на простые множители, да притом единственным возможным образом? Это же пиздец странно
Кажется, я понял, почему работает быстрая сортировка (qsort). Мне всегда было непонятно, с каких вообще хуев, если слева поместить мелкие числа, а справа большие, а потом соединить, то в итоге получится отсортированный массив?
А все дело в том, что иначе и быть не может. Если слева мы поместили числа, меньшие опорного, то справа никогда не появятся числа большей величины. Максимальное число в левом массиве всегда будет меньше минимального в правом. Так оно и работает.
Но проблема в том, что эта хуйня работает через рекурсию. А я ненавижу, блядь, рекурсию. Я понимаю, как она работает, именно поэтому и ненавижу. Рекурсия жрет дохуя памяти, а глубина стека вызовов ограничена. Например, в Java там вообще какие-то смехотворные значения, см. пикрил. 9к вызовов. Это типа дохуя? В qsort аж 2 рекурсивных вызова применяются, алгоритм обмякнет очень быстро на довольно скромного размера массиве. Причем глубина стека вызовов не ограничена непосредственно памятью. Она захардкожена в япе. Например, я помню как писал рекурсию на Java и программа сдохла после ~32768 вызовов. То есть, число не от данных зависит, а тупо степень двойки. Хуйня ебаная эта рекурсия, короче. Если можешь не использовать - не используй.
Каждый ли рекурсивный алгоритм можно переписать на не-рекурсивный вариант?
В япах более хитровыебанные версии qsort применяются, хз, может там и без рекурсии обходятся.
А все дело в том, что иначе и быть не может. Если слева мы поместили числа, меньшие опорного, то справа никогда не появятся числа большей величины. Максимальное число в левом массиве всегда будет меньше минимального в правом. Так оно и работает.
Но проблема в том, что эта хуйня работает через рекурсию. А я ненавижу, блядь, рекурсию. Я понимаю, как она работает, именно поэтому и ненавижу. Рекурсия жрет дохуя памяти, а глубина стека вызовов ограничена. Например, в Java там вообще какие-то смехотворные значения, см. пикрил. 9к вызовов. Это типа дохуя? В qsort аж 2 рекурсивных вызова применяются, алгоритм обмякнет очень быстро на довольно скромного размера массиве. Причем глубина стека вызовов не ограничена непосредственно памятью. Она захардкожена в япе. Например, я помню как писал рекурсию на Java и программа сдохла после ~32768 вызовов. То есть, число не от данных зависит, а тупо степень двойки. Хуйня ебаная эта рекурсия, короче. Если можешь не использовать - не используй.
Каждый ли рекурсивный алгоритм можно переписать на не-рекурсивный вариант?
В япах более хитровыебанные версии qsort применяются, хз, может там и без рекурсии обходятся.
Еще про рекурсию. Чем полезен опыт написания калькулятора - ты понимаешь, что парсинг самого языка програмирования происходит почти точно так же.
Вот говорят, что рекурсивная функция вызывает сама себя. Так вот, это полная, блять, хуйня. Никто там сам себя не вызывает. Вызывается другой экземпляр функции с другими данными. Вот и все. Она нихуя не та же самая. То же самое там название только. Технически это вызов многих экземпляров функции с хранением всех промежуточных результатов.
Вот говорят, что рекурсивная функция вызывает сама себя. Так вот, это полная, блять, хуйня. Никто там сам себя не вызывает. Вызывается другой экземпляр функции с другими данными. Вот и все. Она нихуя не та же самая. То же самое там название только. Технически это вызов многих экземпляров функции с хранением всех промежуточных результатов.
47 Кб, 912x239>>2646
Сука, ору. Только блять сказал про глубину стека рекурсии. Загуглил этот баг литкода и мне выдает, что, вероятно, это из-за переполнения стека рекурсии.
Сука, ору. Только блять сказал про глубину стека рекурсии. Загуглил этот баг литкода и мне выдает, что, вероятно, это из-за переполнения стека рекурсии.
9 Кб, 292x130>>2647
Ну точно. Запустил свой код сам и там переполнение стека вызовов. Могли бы и написать прямо, вместе невменяемого бага.
Да, это говорит о том, что мой код изначально нерабочий.
Ну точно. Запустил свой код сам и там переполнение стека вызовов. Могли бы и написать прямо, вместе невменяемого бага.
Да, это говорит о том, что мой код изначально нерабочий.
72 Кб, 790x648Сука, как же я подгорел. Мой алгоритм правильный, а вся хуйня из-за того, что я невнимательно копирнул первый кусок кода вместо второго.
Ебаный жиэс не имеет встроенной функции для получения рандомного целого числа.
Я копирнул код, возвращающий float число, поэтому код и не работал.
Вот не люблю такие костыли, когда в языке элементарная хуйня делается через жопу. Например, вы знали, что в петухоне нет цикла do-while? Только while. Вот как так блять?
Ебаный жиэс не имеет встроенной функции для получения рандомного целого числа.
Я копирнул код, возвращающий float число, поэтому код и не работал.
Вот не люблю такие костыли, когда в языке элементарная хуйня делается через жопу. Например, вы знали, что в петухоне нет цикла do-while? Только while. Вот как так блять?
7 Кб, 285x154>>2654
Продолжаю получать пикрил на этом коде, который точно работает. Какая глубина стека вызовов на литкоде, 20? Пиздец, ненавижу сраную рекурсию.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAcwKZQEoEMwBM4C2AkmFABQExgBciYIBARqgE4A0iBWAHrfU6wCUfBsxaIA3gChEnKogC8iALJYoACwB0EVDAA2FKoIDcMzj0Uq1W4HrhwWFHibMt0IFklUbNt+4+8tFhx8AjJBRAAqRCduRABaOTAIgGoklwBfKSlQSFgERCgWGAA3GCw9AEUAZwdyfmqRARYAbQBdYTpRVnbJM1kYYBiGzT1UMGQNRAAeRAAmCOlZZeW3KA8kBtMVrJWIBGqoRAAHUrgjpQaWtEwQwhJyAAYOEbGJjUE27eX9sEPEMbAKBNMS9JTtb6yX7-YrIdTArrNMGICH9RDABwxMZHGCWR7GRC42avcaTdQEmApFKLNF7A5HfiWK4wL605ZkRmzU4lc6IAD8ANQQMQtFh8MEmmOIGq6g5DBcOzRaw2hWKZQqNTqZEBUAlvwgajIRVK5SqtRY5DFusy2WhRzc1RAeguqpNGvN5BazwALHNvWwAIz+gMAdjYADYAMyBtjRgCscw6pmhcDGozgyBiDqdutMQA
Продолжаю получать пикрил на этом коде, который точно работает. Какая глубина стека вызовов на литкоде, 20? Пиздец, ненавижу сраную рекурсию.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAcwKZQEoEMwBM4C2AkmFABQExgBciYIBARqgE4A0iBWAHrfU6wCUfBsxaIA3gChEnKogC8iALJYoACwB0EVDAA2FKoIDcMzj0Uq1W4HrhwWFHibMt0IFklUbNt+4+8tFhx8AjJBRAAqRCduRABaOTAIgGoklwBfKSlQSFgERCgWGAA3GCw9AEUAZwdyfmqRARYAbQBdYTpRVnbJM1kYYBiGzT1UMGQNRAAeRAAmCOlZZeW3KA8kBtMVrJWIBGqoRAAHUrgjpQaWtEwQwhJyAAYOEbGJjUE27eX9sEPEMbAKBNMS9JTtb6yX7-YrIdTArrNMGICH9RDABwxMZHGCWR7GRC42avcaTdQEmApFKLNF7A5HfiWK4wL605ZkRmzU4lc6IAD8ANQQMQtFh8MEmmOIGq6g5DBcOzRaw2hWKZQqNTqZEBUAlvwgajIRVK5SqtRY5DFusy2WhRzc1RAeguqpNGvN5BazwALHNvWwAIz+gMAdjYADYAMyBtjRgCscw6pmhcDGozgyBiDqdutMQA
23 Кб, 740x227>>2656
На массиве [0, 0] не работает. Но даже если исправить твоё решение с минимальными изменениями кода, то всё равно не будет работать (пикрил ошибка на тесткейсе с массивом из 50к элементов).
На массиве [0, 0] не работает. Но даже если исправить твоё решение с минимальными изменениями кода, то всё равно не будет работать (пикрил ошибка на тесткейсе с массивом из 50к элементов).
>>2661
Да, я уже понял, что обосрался... Все дело в том, что крайне важно убрать из массива опорный элемент.
Этот >>2656 код работает только если все числа в массиве уникальны. А если нет, то уходит в бесконечную рекурсию, потому что массив не может разделиться, один всегда пустой, другой всегда полный.
Quick sort оказался не так прост, как кажется на первый взгляд.
Вот ниже рабочий код. Но литкод один хуй его не принимает. Видимо, потому что там большие расходы по памяти, я гоняю массивы рекурсивно по значению.
План на завтра: переписать qsort, чтобы не гонять в памяти куски массива, желательно вообще без рекурсии.
Зря я гнал на то, что на литкоде маленький стек на рекурсию. Как обычно, долбоебом оказался я, а не литкод.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAcwKZQEoEMwBM4C2AkmFABQExgBciYIBARqgE4A0iBWAHrfU6wCUfBsxaIA3gChEnKogC8iALJYoACwB0EVDAA2FKoIDcMzj0Uq1W4HrhwWFHibMt0IFklUbNt+4+8tFhx8AjJBRAAqRCduRABaOTAIgGoklwBfKSlQSFgERCgWGAA3GCw9AEUAZwdyfmqRARYAbQBdYTpRVnbJM1kYYBiGzT1UMGQNRAAeRAAmCOlZZeW3KA8kBtMVrJWIBGqoRAAHUrgoAGlUAE9LNEwQwhJyAAYOEbGJjRc9g6PTkrnSwNFoA85Xa5tbbLfZgQ6IMbAKBNMS9JTtaGyWHw4rIdTIrrNNGIDH9RDABwxMZHGCWF7GRC02YfcaTdQMmApFKLMkrQYxWkKIUnM6XG48laSmEIWD0VCYyW7KWIbFHfjAhjVFowKG85ZkdWzMFHAD8CNQSMQtFx+MEmmOIGq6gNDB+yyVsjWG0KxTKFRqdTIiKgdthEDUZFBoraHCKpXKVVqLHINpDmWyqsQbmqID0RyUcb9icDLTeABY5mW2ABGKvVgDsbAAbABmGtsNsAVjmNcb3Y6pmxcDGozgyBi2dzIdMQA
Да, я уже понял, что обосрался... Все дело в том, что крайне важно убрать из массива опорный элемент.
Этот >>2656 код работает только если все числа в массиве уникальны. А если нет, то уходит в бесконечную рекурсию, потому что массив не может разделиться, один всегда пустой, другой всегда полный.
Quick sort оказался не так прост, как кажется на первый взгляд.
Вот ниже рабочий код. Но литкод один хуй его не принимает. Видимо, потому что там большие расходы по памяти, я гоняю массивы рекурсивно по значению.
План на завтра: переписать qsort, чтобы не гонять в памяти куски массива, желательно вообще без рекурсии.
Зря я гнал на то, что на литкоде маленький стек на рекурсию. Как обычно, долбоебом оказался я, а не литкод.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAcwKZQEoEMwBM4C2AkmFABQExgBciYIBARqgE4A0iBWAHrfU6wCUfBsxaIA3gChEnKogC8iALJYoACwB0EVDAA2FKoIDcMzj0Uq1W4HrhwWFHibMt0IFklUbNt+4+8tFhx8AjJBRAAqRCduRABaOTAIgGoklwBfKSlQSFgERCgWGAA3GCw9AEUAZwdyfmqRARYAbQBdYTpRVnbJM1kYYBiGzT1UMGQNRAAeRAAmCOlZZeW3KA8kBtMVrJWIBGqoRAAHUrgoAGlUAE9LNEwQwhJyAAYOEbGJjRc9g6PTkrnSwNFoA85Xa5tbbLfZgQ6IMbAKBNMS9JTtaGyWHw4rIdTIrrNNGIDH9RDABwxMZHGCWF7GRC02YfcaTdQMmApFKLMkrQYxWkKIUnM6XG48laSmEIWD0VCYyW7KWIbFHfjAhjVFowKG85ZkdWzMFHAD8CNQSMQtFx+MEmmOIGq6gNDB+yyVsjWG0KxTKFRqdTIiKgdthEDUZFBoraHCKpXKVVqLHINpDmWyqsQbmqID0RyUcb9icDLTeABY5mW2ABGKvVgDsbAAbABmGtsNsAVjmNcb3Y6pmxcDGozgyBi2dzIdMQA
1 Кб, 117x75>>2666
Я просто скопировал из Last Executed Input в литкоде в консоль браузерную и дописал .length. Но можно было бы и просто по количеству символов понять, там все элементы одинаковые.
Я просто скопировал из Last Executed Input в литкоде в консоль браузерную и дописал .length. Но можно было бы и просто по количеству символов понять, там все элементы одинаковые.
6 Кб, 362x88Вот запустил жс-файл через ноду, программа обмякла после 5к рекурсивных вызовов. На больших данных и некоторых алгоритмах можно как нехуй делать превысить этот лимит.
Пишу более оптимизированную версию qsort. Узнал, что в жс массивы передаются по ссылке. Уже хорошо. Но в предыдущем моем алгоритме в стеке рекурсии один хуй хранятся куски массивов по значению.
Пытаюсь написать разделение Хоара с перестановками. И нихуя не выходит. Какой-то рандом блять. При определенных сочетаниях одинаковых цифр код зависает. Если изменить, чтобы не зависал, вообще перестает разделять. Иногда работает, иногда нет. Нихуя непонятно.
Пытаюсь написать разделение Хоара с перестановками. И нихуя не выходит. Какой-то рандом блять. При определенных сочетаниях одинаковых цифр код зависает. Если изменить, чтобы не зависал, вообще перестает разделять. Иногда работает, иногда нет. Нихуя непонятно.
Короче, разделение Хоара сасирует на массивах типа [9, 14, 7, 63, 9] при опорном элементе 9.
Я даже теоретически не могу придумать, какие престановки надо сделать, чтобы разделить такой массив. Как эта хуйня вообще работает блять?
Я даже теоретически не могу придумать, какие престановки надо сделать, чтобы разделить такой массив. Как эта хуйня вообще работает блять?
1,7 Мб, 1248x1813>>2788
Это тонкая вещь, известная тем, что её невозможно сделать с первого и второго раза, прямо как написать бинарный поиск или вставить флешку в разъём. В реализациях обычно так делают: ведут два индекса, L от N−1 и R от 0. L двигают влево, пока элемент под ним строго больше опорного. R двигают вправо, пока элемент под ним строго меньше опорного. Найденную пару обменивают. Заканчивают, когда L < R. Результат — две половинки, от 0 до L (включительно) и от R до N−1. По построению, в каждой будет минимум 1 элемент. На твоём примере будет:
Это тонкая вещь, известная тем, что её невозможно сделать с первого и второго раза, прямо как написать бинарный поиск или вставить флешку в разъём. В реализациях обычно так делают: ведут два индекса, 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), даже красивый.
>>2833
Блять... Только благодаря тебе я догнал. Короче, мой код разделения работал правильно, просто я не догонял ключевую фишку.
Для массива [9, 63, 7, 14, 9] с опорным 9 я ожидал разделения [7, 9, 9], [63, 14] ну или [7], [9, 9, 63, 14].
Но эта хуйня работает по-другому. В левый массив попадают числа, меньшие или равные опорному, в правый - большие или равные опорному. При этом указатель в конечном итоге каким-то хуем оказывается как раз в месте разделения. Очень контринтуитивная хуйня. Ебаная магия, не иначе.
Литкод схавал qsort с in place разделением Хоара. Но это все еще на рекурсии. Плюс я вижу, что на массивах, где дохуя одинаковых цифр, выполняется много перестановок. Попробую оптимизировать немного для таких массивов.
Блять... Только благодаря тебе я догнал. Короче, мой код разделения работал правильно, просто я не догонял ключевую фишку.
Для массива [9, 63, 7, 14, 9] с опорным 9 я ожидал разделения [7, 9, 9], [63, 14] ну или [7], [9, 9, 63, 14].
Но эта хуйня работает по-другому. В левый массив попадают числа, меньшие или равные опорному, в правый - большие или равные опорному. При этом указатель в конечном итоге каким-то хуем оказывается как раз в месте разделения. Очень контринтуитивная хуйня. Ебаная магия, не иначе.
Литкод схавал qsort с in place разделением Хоара. Но это все еще на рекурсии. Плюс я вижу, что на массивах, где дохуя одинаковых цифр, выполняется много перестановок. Попробую оптимизировать немного для таких массивов.
>>2854
Немного оптимизировать не получилось, опять нихуя не работает. Я думал, там одну строку надо дописать. Дописал, код сломался.
>Попробую оптимизировать немного для таких массивов.
Немного оптимизировать не получилось, опять нихуя не работает. Я думал, там одну строку надо дописать. Дописал, код сломался.
34 Кб, 763x238Добавил в разделение Хоара следующий цикл. Воображаю, как охуенно я придумал, что сейчас все одинаковые значения будут пропущены без перестановок. Запускаю на литкоде, там пикрил.
while (i < j && nums === nums[j]) {
// skip useless swaps of equal values.
i++;
j--;
}
while (i < j && nums === nums[j]) {
// skip useless swaps of equal values.
i++;
j--;
}
>>2902
Обезьянья борда сожрала nums :
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--;
}
>>2903
А, ладно, похуй. Короче, коды сюда лучше не постить
А, ладно, похуй. Короче, коды сюда лучше не постить
15 Кб, 767x169Вот моя рабочая версия qsort. Рекурсивная, in-place, с разделением Хоара.
Я пытался оптимизировать работу с одинаковыми значениями, чтобы они не переставлялись. Однако, затем понял, что я занимаюсь оптимизацией констант в О-большом. При перестановке выполняются 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 операции:
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
15 Кб, 767x169Вот моя рабочая версия qsort. Рекурсивная, in-place, с разделением Хоара.
Я пытался оптимизировать работу с одинаковыми значениями, чтобы они не переставлялись. Однако, затем понял, что я занимаюсь оптимизацией констант в О-большом. При перестановке выполняются 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 операции:
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
Переписал qsort на "итеративный" вариант. Как известно, самый тупой и гарантированный способ переписать рекурсивную функцию на не-рекурсивную - вручную реализовать стек. Так я и сделал. И походу, иногда это является единственным вариантом. Не знаю, как конкретно в этом алгоритме.
Как ни странно, все заработало с первого раза, лол. Правда, вначале я потупил, пытаясь реализовать итерацию без стека.
Еще мне кажется, что в данном алгоритме не нужен именно СТЕК для хранения индексов под-массивов. Потому что, по идее, порядок их обработки не имеет значения. Мне кажется, я могу тупо добавлять в массив пары индексов, потом перемешать массив и в любом порядке их обработать.
Блять, только написал и понял, что таки не могу. Потому что массив большего размера всегда должен быть разделен до того, как будут делиться еще подмассивы.
Или могу? Так-то индексы попадают в стек только после того, как массив уже разделен. Не может быть ситуации, когда в стеке есть индексы меньшего массива, когда еще не разделен больший.
Хз короче. По идее я таки могу обработать более мелкие массивы до того, как обработал крупные.
Например, на первом шаге я разделил массив на 2 части.
На втором шаге на 4 части. По идее, я эти 4 части могу в любом порядке обрабатывать и похуй, они уже сбалансированы относительно друг друга.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABARwM5wE5QJJQKYYCGsAbntmAAoA2hEeAFGCALaoBcizLARgQNoBdADSJgGOC07c+GRAF5EABlFQ401rIVdWqAHTU8YAOZQAFogC0iAIwBKDbwGDEAbwBQiL4ggJUURH86AGtHWSFtIQBuT28giGC9AAcQVDMGcUlVODsY2K8AdzMYQ0QGeMTDE3NEAD5lOzd87y9fMH9ENW0K5LgkhkbCVB0nDBiWlraOzJZuqBDe-sHhmQJxida-AKTCLAAZI1MLRS7rGcQAalt1jZhgMp39w5qAHkQAJkaPDY222GY8DcJgBfdzNSZbRCPHBgAAmeAAHtozHBdnhKLtYLAEExdKIZtlcuC4vMEslUukCVDMRR4QiiT9AqTEik0gxobTEZdbISgaDmhg8FAQBgkNxUDF+aBINikCi0RisDBZQxmuKws5hM0Zhq5IoVM01LrtOKDM8LNYbFqWkkYCQ4FBjYpxfwALLEMx6YDUOCYBgZCSzK5qRoAeg+dhE7gcIy0328hgCMG0MyBicQACttGogUUSngylAMCA8F9iYViqVcWx+DAXG9bfaoGXGS1Q+GWHAyFC4DAwPg5BgYMYzAE86VVnJDKhhuYjFC7Q69OWJjALhcgS1QYzxwXq6h+BmXPVGw6W62vO3EJ3u0le-2CIhDMAx5WC5PEMZBcRH3OkKeoGXC8vAzSxLE3bxtx+O4ymTWpFAzc8LyvQVhVFTozALWgOj7OlEDge45yfPAX0QXYiAATyA4DUJFJAMwgrx+UZK9zBgYZ2MQMgMAoxAYBYO8sEIftOjga8uwLXDETwYZCBfX9MMCApCCSaiNlQZSkk5BEZP3UQ1wuURQMsBlIPcKVwGgeAkA0lTtN09VY01Pi4URGxdX01yEXeXUY3tGBYSaCF2gCEhCGoEsbBNXRay8mxBCBKZQvCkt3mimspO8hK1RizL4u0MKIrwd4gRdTL3hcRRCsiyUwSSlyUgCRR+BURAABZ3ja0QbC6nlEAANgAZm6gB2URhsQABWd5RtEabsqmOBDAMOBjAYAAiPtGvYdbPMaolFuWn01vWwVUBAahHV2lB0CwXACGIO1yCoWh6AYLaQGbIkgA
Как ни странно, все заработало с первого раза, лол. Правда, вначале я потупил, пытаясь реализовать итерацию без стека.
Еще мне кажется, что в данном алгоритме не нужен именно СТЕК для хранения индексов под-массивов. Потому что, по идее, порядок их обработки не имеет значения. Мне кажется, я могу тупо добавлять в массив пары индексов, потом перемешать массив и в любом порядке их обработать.
Блять, только написал и понял, что таки не могу. Потому что массив большего размера всегда должен быть разделен до того, как будут делиться еще подмассивы.
Или могу? Так-то индексы попадают в стек только после того, как массив уже разделен. Не может быть ситуации, когда в стеке есть индексы меньшего массива, когда еще не разделен больший.
Хз короче. По идее я таки могу обработать более мелкие массивы до того, как обработал крупные.
Например, на первом шаге я разделил массив на 2 части.
На втором шаге на 4 части. По идее, я эти 4 части могу в любом порядке обрабатывать и похуй, они уже сбалансированы относительно друг друга.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABARwM5wE5QJJQKYYCGsAbntmAAoA2hEeAFGCALaoBcizLARgQNoBdADSJgGOC07c+GRAF5EABlFQ401rIVdWqAHTU8YAOZQAFogC0iAIwBKDbwGDEAbwBQiL4ggJUURH86AGtHWSFtIQBuT28giGC9AAcQVDMGcUlVODsY2K8AdzMYQ0QGeMTDE3NEAD5lOzd87y9fMH9ENW0K5LgkhkbCVB0nDBiWlraOzJZuqBDe-sHhmQJxida-AKTCLAAZI1MLRS7rGcQAalt1jZhgMp39w5qAHkQAJkaPDY222GY8DcJgBfdzNSZbRCPHBgAAmeAAHtozHBdnhKLtYLAEExdKIZtlcuC4vMEslUukCVDMRR4QiiT9AqTEik0gxobTEZdbISgaDmhg8FAQBgkNxUDF+aBINikCi0RisDBZQxmuKws5hM0Zhq5IoVM01LrtOKDM8LNYbFqWkkYCQ4FBjYpxfwALLEMx6YDUOCYBgZCSzK5qRoAeg+dhE7gcIy0328hgCMG0MyBicQACttGogUUSngylAMCA8F9iYViqVcWx+DAXG9bfaoGXGS1Q+GWHAyFC4DAwPg5BgYMYzAE86VVnJDKhhuYjFC7Q69OWJjALhcgS1QYzxwXq6h+BmXPVGw6W62vO3EJ3u0le-2CIhDMAx5WC5PEMZBcRH3OkKeoGXC8vAzSxLE3bxtx+O4ymTWpFAzc8LyvQVhVFTozALWgOj7OlEDge45yfPAX0QXYiAATyA4DUJFJAMwgrx+UZK9zBgYZ2MQMgMAoxAYBYO8sEIftOjga8uwLXDETwYZCBfX9MMCApCCSaiNlQZSkk5BEZP3UQ1wuURQMsBlIPcKVwGgeAkA0lTtN09VY01Pi4URGxdX01yEXeXUY3tGBYSaCF2gCEhCGoEsbBNXRay8mxBCBKZQvCkt3mimspO8hK1RizL4u0MKIrwd4gRdTL3hcRRCsiyUwSSlyUgCRR+BURAABZ3ja0QbC6nlEAANgAZm6gB2URhsQABWd5RtEabsqmOBDAMOBjAYAAiPtGvYdbPMaolFuWn01vWwVUBAahHV2lB0CwXACGIO1yCoWh6AYLaQGbIkgA
Переписал qsort на "итеративный" вариант. Как известно, самый тупой и гарантированный способ переписать рекурсивную функцию на не-рекурсивную - вручную реализовать стек. Так я и сделал. И походу, иногда это является единственным вариантом. Не знаю, как конкретно в этом алгоритме.
Как ни странно, все заработало с первого раза, лол. Правда, вначале я потупил, пытаясь реализовать итерацию без стека.
Еще мне кажется, что в данном алгоритме не нужен именно СТЕК для хранения индексов под-массивов. Потому что, по идее, порядок их обработки не имеет значения. Мне кажется, я могу тупо добавлять в массив пары индексов, потом перемешать массив и в любом порядке их обработать.
Блять, только написал и понял, что таки не могу. Потому что массив большего размера всегда должен быть разделен до того, как будут делиться еще подмассивы.
Или могу? Так-то индексы попадают в стек только после того, как массив уже разделен. Не может быть ситуации, когда в стеке есть индексы меньшего массива, когда еще не разделен больший.
Хз короче. По идее я таки могу обработать более мелкие массивы до того, как обработал крупные.
Например, на первом шаге я разделил массив на 2 части.
На втором шаге на 4 части. По идее, я эти 4 части могу в любом порядке обрабатывать и похуй, они уже сбалансированы относительно друг друга.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABARwM5wE5QJJQKYYCGsAbntmAAoA2hEeAFGCALaoBcizLARgQNoBdADSJgGOC07c+GRAF5EABlFQ401rIVdWqAHTU8YAOZQAFogC0iAIwBKDbwGDEAbwBQiL4ggJUURH86AGtHWSFtIQBuT28giGC9AAcQVDMGcUlVODsY2K8AdzMYQ0QGeMTDE3NEAD5lOzd87y9fMH9ENW0K5LgkhkbCVB0nDBiWlraOzJZuqBDe-sHhmQJxida-AKTCLAAZI1MLRS7rGcQAalt1jZhgMp39w5qAHkQAJkaPDY222GY8DcJgBfdzNSZbRCPHBgAAmeAAHtozHBdnhKLtYLAEExdKIZtlcuC4vMEslUukCVDMRR4QiiT9AqTEik0gxobTEZdbISgaDmhg8FAQBgkNxUDF+aBINikCi0RisDBZQxmuKws5hM0Zhq5IoVM01LrtOKDM8LNYbFqWkkYCQ4FBjYpxfwALLEMx6YDUOCYBgZCSzK5qRoAeg+dhE7gcIy0328hgCMG0MyBicQACttGogUUSngylAMCA8F9iYViqVcWx+DAXG9bfaoGXGS1Q+GWHAyFC4DAwPg5BgYMYzAE86VVnJDKhhuYjFC7Q69OWJjALhcgS1QYzxwXq6h+BmXPVGw6W62vO3EJ3u0le-2CIhDMAx5WC5PEMZBcRH3OkKeoGXC8vAzSxLE3bxtx+O4ymTWpFAzc8LyvQVhVFTozALWgOj7OlEDge45yfPAX0QXYiAATyA4DUJFJAMwgrx+UZK9zBgYZ2MQMgMAoxAYBYO8sEIftOjga8uwLXDETwYZCBfX9MMCApCCSaiNlQZSkk5BEZP3UQ1wuURQMsBlIPcKVwGgeAkA0lTtN09VY01Pi4URGxdX01yEXeXUY3tGBYSaCF2gCEhCGoEsbBNXRay8mxBCBKZQvCkt3mimspO8hK1RizL4u0MKIrwd4gRdTL3hcRRCsiyUwSSlyUgCRR+BURAABZ3ja0QbC6nlEAANgAZm6gB2URhsQABWd5RtEabsqmOBDAMOBjAYAAiPtGvYdbPMaolFuWn01vWwVUBAahHV2lB0CwXACGIO1yCoWh6AYLaQGbIkgA
Как ни странно, все заработало с первого раза, лол. Правда, вначале я потупил, пытаясь реализовать итерацию без стека.
Еще мне кажется, что в данном алгоритме не нужен именно СТЕК для хранения индексов под-массивов. Потому что, по идее, порядок их обработки не имеет значения. Мне кажется, я могу тупо добавлять в массив пары индексов, потом перемешать массив и в любом порядке их обработать.
Блять, только написал и понял, что таки не могу. Потому что массив большего размера всегда должен быть разделен до того, как будут делиться еще подмассивы.
Или могу? Так-то индексы попадают в стек только после того, как массив уже разделен. Не может быть ситуации, когда в стеке есть индексы меньшего массива, когда еще не разделен больший.
Хз короче. По идее я таки могу обработать более мелкие массивы до того, как обработал крупные.
Например, на первом шаге я разделил массив на 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
Пытался скормить литкоду, но там 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
И ведь в "Грокаем алгоритмы" в качестве qsort приведен именно упрощенный обучающий пример с хранением подмассивов в памяти, а про разделение Хоара даже не сказано нихуя, даже блядь не упомянуто сука.
Пытался решить задачу на нахождение цикла в связном списке.
Сразу же беспокойство вызвала плашка
Can you solve it using O(1) (i.e. constant) memory?
Также вызывал беспокойство тот факт, что связный список - ни что иное как направленный граф, а про графы я пока не знаю приблизительно нихуя.
Ну что ж, с памятью O(N) я решил: пихаем все ссылки на ноды в Set, если встретили повторяющуюся, значит есть цикл.
А как блять с константной памятью? Я так и не додумался.
Но зато сделал ХОД КОНЕМ и сохранил информацию о прохождении узла тупо в самом узле, таким образом, уничтожив связный список. Зато O(1), лишней памяти не использовано, лол.
Посмотрел решения, оказывается есть блять некий хитровыебанный алгоритм решения конкретно этой задачи с константной памятью, называется "Алгоритм черепахи и зайца".
Вот какого хуя это хуйня easy? Это хард нахуй. Например, помню задачу по переводу чисел в английские слова. Она имеет уровень hard, хотя по сути изи, там ничего сложного нет, просто объемная, дохуя слов в массиве надо хранить. А тут хуй додумаешься без знания конкретного алгоритма. В смысле для константной памяти.
Сразу же беспокойство вызвала плашка
Can you solve it using O(1) (i.e. constant) memory?
Также вызывал беспокойство тот факт, что связный список - ни что иное как направленный граф, а про графы я пока не знаю приблизительно нихуя.
Ну что ж, с памятью O(N) я решил: пихаем все ссылки на ноды в Set, если встретили повторяющуюся, значит есть цикл.
А как блять с константной памятью? Я так и не додумался.
Но зато сделал ХОД КОНЕМ и сохранил информацию о прохождении узла тупо в самом узле, таким образом, уничтожив связный список. Зато O(1), лишней памяти не использовано, лол.
Посмотрел решения, оказывается есть блять некий хитровыебанный алгоритм решения конкретно этой задачи с константной памятью, называется "Алгоритм черепахи и зайца".
Вот какого хуя это хуйня easy? Это хард нахуй. Например, помню задачу по переводу чисел в английские слова. Она имеет уровень hard, хотя по сути изи, там ничего сложного нет, просто объемная, дохуя слов в массиве надо хранить. А тут хуй додумаешься без знания конкретного алгоритма. В смысле для константной памяти.
>>3070
Информация по алгоритму.
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
Что ж, не один я такой долбоеб, что додумался хранить информацию о прохождении узла в самом узле
Информация по алгоритму.
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
Что ж, не один я такой долбоеб, что додумался хранить информацию о прохождении узла в самом узле
13 Кб, 389x172Перевернул связный список двумя способами: итерационно и рекурсивно (задание 206).
Хотя рекурсия тут нахуй не нужна, только жрет память на ровном месте.
Вот прям яркий пример, когда рекурсия не нужна. Рекурсия всегда жрет память пропорционально количеству рекурсивных вызовов, потому что при рекурсии в памяти всегда хранится какая-нибудь хуйня.
Решил уже 10 заданий.
https://www.typescriptlang.org/play?#code/MYGwhgzhAEAyCWEAuA5A9gEwKbQN4ChojoA3MEALmgDsBXAWwCMsAnQ46rADySoWXTZoAHxq0QIdkWBpqyFrWBI0LABRkQAfip0mrADQ1uSbXESpMOUXQkBKPFOJEkAC0QA6DdAC80deR9vX1pqbAAzeE4MaE1oAAZoKg1bRydXD04eHz9MpEDg0KwIqJixCUSjHhSnAF98OvwAegAqZsJm6AAlLGBaFgh4EhwWLHJ4AC8wJHhZaBk5BiwYAHlVant6LHoVAE93dsb8MJClGepoEaH+rH4kbt7+waw1yz5zQSsykEMAB0uPt4CSwiL7ZGwgWyAixCaziEAOJzwMI5YFBXzg+wEJxOEZIPrnP5YEgfADcjjqTnmyEq0Jw6Ms7lyZKc1AZuWyhOJlmZxFx+IuRNYEBu5nufQGQzWxg+hlZ2FsZIaLTa0A6AEkkKwpmc5rIIIsVqoAIwbLa7faqw7HainWaXIUi5AarXTSUuUYYKEfEEYr3A2HlLHEEBYPKcgFmIEw0HouE8oghvJyrB+6Pg7LusAYePQADubhDKKEAEIgl9MaliFSk9LUTQ2cYcyyG1lfOHuZWiO2hPTsE2OHXcqTyY4+SwCf8Ow0jidpnbBddbqpM57I7SfXDIWvvQH4UGiGPzvbF6KeuKnsuPQr6vggA
Хотя рекурсия тут нахуй не нужна, только жрет память на ровном месте.
Вот прям яркий пример, когда рекурсия не нужна. Рекурсия всегда жрет память пропорционально количеству рекурсивных вызовов, потому что при рекурсии в памяти всегда хранится какая-нибудь хуйня.
Решил уже 10 заданий.
https://www.typescriptlang.org/play?#code/MYGwhgzhAEAyCWEAuA5A9gEwKbQN4ChojoA3MEALmgDsBXAWwCMsAnQ46rADySoWXTZoAHxq0QIdkWBpqyFrWBI0LABRkQAfip0mrADQ1uSbXESpMOUXQkBKPFOJEkAC0QA6DdAC80deR9vX1pqbAAzeE4MaE1oAAZoKg1bRydXD04eHz9MpEDg0KwIqJixCUSjHhSnAF98OvwAegAqZsJm6AAlLGBaFgh4EhwWLHJ4AC8wJHhZaBk5BiwYAHlVant6LHoVAE93dsb8MJClGepoEaH+rH4kbt7+waw1yz5zQSsykEMAB0uPt4CSwiL7ZGwgWyAixCaziEAOJzwMI5YFBXzg+wEJxOEZIPrnP5YEgfADcjjqTnmyEq0Jw6Ms7lyZKc1AZuWyhOJlmZxFx+IuRNYEBu5nufQGQzWxg+hlZ2FsZIaLTa0A6AEkkKwpmc5rIIIsVqoAIwbLa7faqw7HainWaXIUi5AarXTSUuUYYKEfEEYr3A2HlLHEEBYPKcgFmIEw0HouE8oghvJyrB+6Pg7LusAYePQADubhDKKEAEIgl9MaliFSk9LUTQ2cYcyyG1lfOHuZWiO2hPTsE2OHXcqTyY4+SwCf8Ow0jidpnbBddbqpM57I7SfXDIWvvQH4UGiGPzvbF6KeuKnsuPQr6vggA
79 Кб, 757x534Решил похожее задание (92). Переворот части связного списка.
Я сразу же подумал, что это элементарная хуйня, в чем разница с переворотом всего списка? Всего-то скипнуть часть диапазона листа, да соединить концы.
Но по факту, тут заебешься следить за этими индексами ебаными. Как в qsort. Звучит просто, но при попытке реализации постоянно какие-то баги идут из-за несоответствия индексов. В итоге решил. Самое главное - сложность линейная, затраты памяти константные. Глянул в решения, там можно чуть меньше кода написать, если сделать фантомный узел листа. Похуй.
https://www.typescriptlang.org/play?#code/MYGwhgzhAEAyCWEAuA5A9gEwKbQN4ChojoA3MEALmgDsBXAWwCMsAnQ46rADySoWXTZoAHxq0QIdkWBpqyFrWBI0LABRkQAfip0mrADQ1uSbXESpMOUXQkBKPFOJEkAC0QA6DdAC80deR9vX1pqbAAzeE4MaE1oAAZoKg1bRydXD04eHz9MpEDg0KwIqJixCUSjHhSnAF98OvwwkKV4WWgWLBJWCCwAISwkAHcsLGpVFywwDD5zQSsykEMQIt4xPRZDFngAcxdV3WYWWxmBSxEFhycAeivoADFI6LBoZDAWPOpLd0dlvMfubJxADcPwGLyQbws2BOUPmNhA2XhIKcv2gyzCsJhc3O8OyEymyOIgzcyz8AGoyf8uNAADxolbQABkjPpGLm9gITicr3e2N86NhhK5rNh2QFc3cuSF0Aa11uACVOt0cAAHSHQNBhaCuHAgczfFFglUdEhzLFnaziBG+JGgj6Wc1CS3lfkrObS4nwUmqKkU2m+La7PLMmiWDmpYgyOQfYx80PYSXGaVOT4J3LZY2dd0RoiZ01nG2WZMcAuVQWOOpOKPIdo7PZmsynJ0XXx57OGvKjDAN-ii53W+NYEGOG7QADCsk4SmgaveGq1OrR5m1aG1E3aWHoYEikW2S+QBuI8C1qh5sPDwqIZ4l6YDdfLtUcx784rDl0vr7TxmyXfbxErR4ngK0AAHzQAAjBel4dEgtAsNQ0D4hg0oAUQMFwQhgb1kW9T4EAA
Я сразу же подумал, что это элементарная хуйня, в чем разница с переворотом всего списка? Всего-то скипнуть часть диапазона листа, да соединить концы.
Но по факту, тут заебешься следить за этими индексами ебаными. Как в qsort. Звучит просто, но при попытке реализации постоянно какие-то баги идут из-за несоответствия индексов. В итоге решил. Самое главное - сложность линейная, затраты памяти константные. Глянул в решения, там можно чуть меньше кода написать, если сделать фантомный узел листа. Похуй.
https://www.typescriptlang.org/play?#code/MYGwhgzhAEAyCWEAuA5A9gEwKbQN4ChojoA3MEALmgDsBXAWwCMsAnQ46rADySoWXTZoAHxq0QIdkWBpqyFrWBI0LABRkQAfip0mrADQ1uSbXESpMOUXQkBKPFOJEkAC0QA6DdAC80deR9vX1pqbAAzeE4MaE1oAAZoKg1bRydXD04eHz9MpEDg0KwIqJixCUSjHhSnAF98OvwwkKV4WWgWLBJWCCwAISwkAHcsLGpVFywwDD5zQSsykEMQIt4xPRZDFngAcxdV3WYWWxmBSxEFhycAeivoADFI6LBoZDAWPOpLd0dlvMfubJxADcPwGLyQbws2BOUPmNhA2XhIKcv2gyzCsJhc3O8OyEymyOIgzcyz8AGoyf8uNAADxolbQABkjPpGLm9gITicr3e2N86NhhK5rNh2QFc3cuSF0Aa11uACVOt0cAAHSHQNBhaCuHAgczfFFglUdEhzLFnaziBG+JGgj6Wc1CS3lfkrObS4nwUmqKkU2m+La7PLMmiWDmpYgyOQfYx80PYSXGaVOT4J3LZY2dd0RoiZ01nG2WZMcAuVQWOOpOKPIdo7PZmsynJ0XXx57OGvKjDAN-ii53W+NYEGOG7QADCsk4SmgaveGq1OrR5m1aG1E3aWHoYEikW2S+QBuI8C1qh5sPDwqIZ4l6YDdfLtUcx784rDl0vr7TxmyXfbxErR4ngK0AAHzQAAjBel4dEgtAsNQ0D4hg0oAUQMFwQhgb1kW9T4EAA
Решил дейлик (1637). Какая-то тупая задача. Нахуя там вообще точки на оси Y? Они не участвуют в вычислении. Опять же, в очередной раз недоумеваю с уровни сложности литкода. Эта откровенная параша для даунов там имеет уровень medium. Я вчера на изи охуел как на харде. Эти уровни сложности довольно расплывчаты.
https://www.typescriptlang.org/play?#code/PQKhCgAIUhxBTALpAtgQwB6QDbwHYDmiAFpAEZIDu8+kADgPYCWeiAzpA3pCfJABqRMTNgDooMACpMU8AFyRIAeQAUAJhB4Q2BgRV4AlAYmQAynTQBjecpUBGY9GDgAZgFc8lxEy6pMAdSYAExIlFwA1eAAnb0s0bABBKPg0FUYWdgU8NxQKKIBtAF0igyycvMgAbyhFemZWMTYGGJUVNDLc6KKAGnIOvJLIAF4APiF8gAZCyABacknCgwBucBrFZMQ3KO50htFkoLdrFXdPb18VdAwAGXwiYn7o3t3ER4LC3pYg+Aw33rQolE3kVBtVauDIJYuGxkHgfogAAr1ZBDISA-JfH6QADUkDs0wA-AS6hkVhDalC8DDIHDKLdCCRhjT4UiMgtZiTWAsyeTIBsttwALJoEiiK6XTD0+69WlSkjLNaQAC+vQmCqVq0p1JYdDcKMg+XyAFZulNusbuvjzXZTR98gAWW2FFZahi4UQ6PQ6vUK13uz0qABEV0glGCJDkge6V0CIWIYUiMSYcUSyVS3sQRhWQA
https://www.typescriptlang.org/play?#code/PQKhCgAIUhxBTALpAtgQwB6QDbwHYDmiAFpAEZIDu8+kADgPYCWeiAzpA3pCfJABqRMTNgDooMACpMU8AFyRIAeQAUAJhB4Q2BgRV4AlAYmQAynTQBjecpUBGY9GDgAZgFc8lxEy6pMAdSYAExIlFwA1eAAnb0s0bABBKPg0FUYWdgU8NxQKKIBtAF0igyycvMgAbyhFemZWMTYGGJUVNDLc6KKAGnIOvJLIAF4APiF8gAZCyABacknCgwBucBrFZMQ3KO50htFkoLdrFXdPb18VdAwAGXwiYn7o3t3ER4LC3pYg+Aw33rQolE3kVBtVauDIJYuGxkHgfogAAr1ZBDISA-JfH6QADUkDs0wA-AS6hkVhDalC8DDIHDKLdCCRhjT4UiMgtZiTWAsyeTIBsttwALJoEiiK6XTD0+69WlSkjLNaQAC+vQmCqVq0p1JYdDcKMg+XyAFZulNusbuvjzXZTR98gAWW2FFZahi4UQ6PQ6vUK13uz0qABEV0glGCJDkge6V0CIWIYUiMSYcUSyVS3sQRhWQA
Решил задачку быстрого возведения в степень за логарифмическое время (50).
Рекурсивно быстро понял, но итеративную реализацию пришлось подглядеть.
Также по этой же схеме можно сделать умножение числа.
Это снова упрощенный алгоритм, так-то есть еще алгоритм, где степень переводится в бинарный вид, его не хочу трогать.
https://www.typescriptlang.org/play?#code/PQKhCgAIUglBDAlgZwKaXpAdgVwLYBGqATpAC4D2GkADhQO4kB0UMAKonqgFySQDyACgA2FAOaCsASimtIAZRrwAxjwGCAjLOiQAAkuLw8kAB6QAglgCe2fEWIsd++IeNZIASSxlUYkrcISABpsCjJIADNReDJHEGBwCJwsZTJECnc6eg8fQzSAN1RBE15cQOIQrFK7Eilq8sgAbyg+SEQIyElIAF5eyAAGKSaW1tbiVDIcYncNAG4RyABfBfbO9wAeAaHm0dGzbsgNSGBTed3W9wOAWiwz1uXR4QnIVBMyQwANHsO7vnoAC0QTzWkAAfIdtgtRsoMsgKE8mKIJAADEqQAAkjRMi2RIWRVQxjSwOKkv12qy6AFJIAAmSAAQj6g2G53Or3e8C+B3Znx0JjJrOw33cVx+UPu4r4+1MfIFF2Fx1pZIeYwmU3cPM5svAy3AoAgOgQKHQmDK9nIVEwWWYcg4XF46iRkhkckUKjUQid0m0MGcrhllhsZptTgMRiFXh8flIwYqoXCUQoMTiCSSKTSGVoDFgqGUU2QiEKxXq9kqJdq5dIO1aMKwcIRTtRvEx2NxkHxzaJJLJFMuTMhgvGk2mYtGKr4vZ6fS0LNZQ-VpwW47aHS6m2Z1fO85HWRzeeIBaLRxOJhCN1JS5Wq-c1LpvQOG8lkG3mWzufzhaKZhgp6FJxpF5jgsL4yjAu7vgen7FHyIRdKKM7-heuq1vWqCIuIggAETjMgODCGQ3CYSEWQ5CQMRQQArCEGhaBeQA
Рекурсивно быстро понял, но итеративную реализацию пришлось подглядеть.
Также по этой же схеме можно сделать умножение числа.
Это снова упрощенный алгоритм, так-то есть еще алгоритм, где степень переводится в бинарный вид, его не хочу трогать.
https://www.typescriptlang.org/play?#code/PQKhCgAIUglBDAlgZwKaXpAdgVwLYBGqATpAC4D2GkADhQO4kB0UMAKonqgFySQDyACgA2FAOaCsASimtIAZRrwAxjwGCAjLOiQAAkuLw8kAB6QAglgCe2fEWIsd++IeNZIASSxlUYkrcISABpsCjJIADNReDJHEGBwCJwsZTJECnc6eg8fQzSAN1RBE15cQOIQrFK7Eilq8sgAbyg+SEQIyElIAF5eyAAGKSaW1tbiVDIcYncNAG4RyABfBfbO9wAeAaHm0dGzbsgNSGBTed3W9wOAWiwz1uXR4QnIVBMyQwANHsO7vnoAC0QTzWkAAfIdtgtRsoMsgKE8mKIJAADEqQAAkjRMi2RIWRVQxjSwOKkv12qy6AFJIAAmSAAQj6g2G53Or3e8C+B3Znx0JjJrOw33cVx+UPu4r4+1MfIFF2Fx1pZIeYwmU3cPM5svAy3AoAgOgQKHQmDK9nIVEwWWYcg4XF46iRkhkckUKjUQid0m0MGcrhllhsZptTgMRiFXh8flIwYqoXCUQoMTiCSSKTSGVoDFgqGUU2QiEKxXq9kqJdq5dIO1aMKwcIRTtRvEx2NxkHxzaJJLJFMuTMhgvGk2mYtGKr4vZ6fS0LNZQ-VpwW47aHS6m2Z1fO85HWRzeeIBaLRxOJhCN1JS5Wq-c1LpvQOG8lkG3mWzufzhaKZhgp6FJxpF5jgsL4yjAu7vgen7FHyIRdKKM7-heuq1vWqCIuIggAETjMgODCGQ3CYSEWQ5CQMRQQArCEGhaBeQA
19 Кб, 549x132>>3360
Поначалу нагуглил функцию Math.log() и подумал, что в жс только она и есть. Ладно, думаю, похуй, можно же накостылить через формулу, позволяющую вычислить логарифм по любому основанию, если на калькуляторе есть только кнопка логарифма по какому-то конкретному основанию.
Надо логарифм числа разделить на логарифм основания, тогда получится логарифм числа по основанию.
Но я не учел ограниченной точности вычислений в кудахтере + жопаскрипт имеет фишку добавлять к числам при вычислении рандом далеко после запятой.
Вообще, конечно, костыль еще тот, на проде такую хуйню лучше не использовать.
Потом я узнал, что в жс есть функция Math.log2().
Если бы ее не было, пришлось бы делать через цикл. Благо, там сложность логарифмическая.
Поначалу нагуглил функцию Math.log() и подумал, что в жс только она и есть. Ладно, думаю, похуй, можно же накостылить через формулу, позволяющую вычислить логарифм по любому основанию, если на калькуляторе есть только кнопка логарифма по какому-то конкретному основанию.
Надо логарифм числа разделить на логарифм основания, тогда получится логарифм числа по основанию.
Но я не учел ограниченной точности вычислений в кудахтере + жопаскрипт имеет фишку добавлять к числам при вычислении рандом далеко после запятой.
Вообще, конечно, костыль еще тот, на проде такую хуйню лучше не использовать.
Потом я узнал, что в жс есть функция Math.log2().
Если бы ее не было, пришлось бы делать через цикл. Благо, там сложность логарифмическая.
88 Кб, 1362x633>>3361
Ору, для тройки точности в одну миллиардную уже недостаточно.
Блять, ну я тогда хуй знает, как тут сделать без циклов и чтобы было надежно.
Ору, для тройки точности в одну миллиардную уже недостаточно.
Блять, ну я тогда хуй знает, как тут сделать без циклов и чтобы было надежно.
>>3363
Поглядел решения, ебать охуел с вот этого. Оно реально работает, но только для простых чисел.
Поглядел решения, ебать охуел с вот этого. Оно реально работает, но только для простых чисел.
>>3364
Для двойки тоже есть аналоговнетный метод через бинарное представление числа.
Для двойки тоже есть аналоговнетный метод через бинарное представление числа.
64 Кб, 1310x368Прорабатываю вещи из самого начала учебника, прежде чем двигаться дальше. Казалось бы, что может быть проще бинарного поиска? В чем вообще может быть проблема? Но Рируру оказался прав: нельзя так просто взять и написать бинарный поиск. Как и с сортировкой, тяжело уследить за индексами, чтобы они не пересекались, чтобы массив правильно разделялся, чтобы эта хуйня не уходила в бесконечный цикл.
Для меня неочевидной хуйней оказался тот факт, что проверяемый индекс нужно исключить из диапазона. Ибо, во-первых, он уже блять проверен, но самое главное, что если не исключить, то функция зависнет, когда достигнет массива из двух элементов, индекс все время будет указывать на одну и ту же ячейку. А если исключить, то массив всегда гарантированно будет уменьшаться и программа не зависнет, даже если в массиве ничего не найдено.
Еще рандом литкода выдал мне пикрил. Как обычно, оно является хуйней.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAZwKYEMBOEAWAKMEAW2QC5FCiAjVTAbQF0AaRKLAc1SnMpswEoexPogDeAKERTEAGy6IYiALyIADAG5J0uVEQArZRWLIAdHLDsoORAFpEARk1apAdxww5iPAbuKAfCqq-GLO0lIQCMi6MGAAJqgAHoYAsuhWJsAycHCYeHiKANT6wQD0iABM-JphYRFgyHByZnDseAAGMOQAJKIwAL4set2iegMKcYnDMfEJfW1VoWEwwF6UyHTTiQzKSipsmJxQwRI1p4iYXCCYSJsJ1Wd9i9LLq8YbEwnbADysHFzHT1OihUt0QRUcgMQjzOChWBDet22fl+B3+IRhYQMII+tgc91O0OkhKkFygVyQNkciBKZQAbugZCBUIgXOhkBQ4LpgHBwLETOJHuI6g0mllWgAiC7IEAybjilhoLC4PAAQUwmHQAE8Mpg4ERVeqtXhUukAA5wFx4coscpBfgmADWqE1yDw-H4LAAnO7NEA
Для меня неочевидной хуйней оказался тот факт, что проверяемый индекс нужно исключить из диапазона. Ибо, во-первых, он уже блять проверен, но самое главное, что если не исключить, то функция зависнет, когда достигнет массива из двух элементов, индекс все время будет указывать на одну и ту же ячейку. А если исключить, то массив всегда гарантированно будет уменьшаться и программа не зависнет, даже если в массиве ничего не найдено.
Еще рандом литкода выдал мне пикрил. Как обычно, оно является хуйней.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAZwKYEMBOEAWAKMEAW2QC5FCiAjVTAbQF0AaRKLAc1SnMpswEoexPogDeAKERTEAGy6IYiALyIADAG5J0uVEQArZRWLIAdHLDsoORAFpEARk1apAdxww5iPAbuKAfCqq-GLO0lIQCMi6MGAAJqgAHoYAsuhWJsAycHCYeHiKANT6wQD0iABM-JphYRFgyHByZnDseAAGMOQAJKIwAL4set2iegMKcYnDMfEJfW1VoWEwwF6UyHTTiQzKSipsmJxQwRI1p4iYXCCYSJsJ1Wd9i9LLq8YbEwnbADysHFzHT1OihUt0QRUcgMQjzOChWBDet22fl+B3+IRhYQMII+tgc91O0OkhKkFygVyQNkciBKZQAbugZCBUIgXOhkBQ4LpgHBwLETOJHuI6g0mllWgAiC7IEAybjilhoLC4PAAQUwmHQAE8Mpg4ERVeqtXhUukAA5wFx4coscpBfgmADWqE1yDw-H4LAAnO7NEA
58 Кб, 1247x751Ебать нашел тут задачку. Вот тут уже реальный хардкор. Длинная арифметика. Ее можно реализовать сотней разных способов с разными затратами памяти и времени.
Если кто не понял, в чем вообще проблема, скажу, что числа в языке программирования имеют четко ограниченный максимальный размер. Например, в 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 бита не бывает).
Тут куча разных подходов может быть в зависимости от целей и ограничений.
Если кто не понял, в чем вообще проблема, скажу, что числа в языке программирования имеют четко ограниченный максимальный размер. Например, в 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 бита не бывает).
Тут куча разных подходов может быть в зависимости от целей и ограничений.
58 Кб, 1247x751Ебать нашел тут задачку. Вот тут уже реальный хардкор. Длинная арифметика. Ее можно реализовать сотней разных способов с разными затратами памяти и времени.
Если кто не понял, в чем вообще проблема, скажу, что числа в языке программирования имеют четко ограниченный максимальный размер. Например, в 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 бита не бывает).
Тут куча разных подходов может быть в зависимости от целей и ограничений.
Если кто не понял, в чем вообще проблема, скажу, что числа в языке программирования имеют четко ограниченный максимальный размер. Например, в 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 бита не бывает).
Тут куча разных подходов может быть в зависимости от целей и ограничений.
>>3568
Думал над этой задачей, реализовал классический алгоритм умножения столбиком, который выполняется за O(n^2).
Но самое смешное - я обнаружил, что при умножении столбиком можно умножать не только 1 разряд, лол.
См. пикрил. На первом скрине классическое умножение столбиком, которому учат в школе.
На втором я умножил 35x39 и прибавил 16x39, но со сдвигом сразу на 2 разряда.
В моем костыльном алгоритме реализуется первый вариант, происходит очень много операций умножения.
Компьютеру похуй насколько большое число умножать в пределах разрядности, оно умножается за одинаковое время. Так что, можно умножать сразу большие куски чисел и складывать с большими сдвигами.
Я же говорил, количество возможных оптимизаций этой хуйни бесконечно.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAWxAG1gBzQTwBQCGAXImCMgEYCmATgNoC6ANIhSWZbYwJTvnX0GiAN4AoRBMQQEAZyiIaVGeih9OgxAF5EdAAwMA3OMnSwcxGgJyAklsQEAdGipgA5lAAWiALSIAjEaSiMBwNIh4zvIAVna6BogxADysTi7uHvFRANRZ3CLGQRKRiFBUyJixgYUSIWERVPIwlYhNidqWNvEwOXli1dWm5hAgNIpgUABKSioAIjCuMFDWYAAmVAAedk1ZCVX9JrLyw6Muk9MYcwvy2orKGHTHY2d3UJeLy2vrQgD834hxBX2UkOiEwNDgKxA0DsBDoMCEACpWHQooZAftiit5os1AIWKVygA5KgAd1xtD2QLoBMwxJJLCxVyE2hk2EWhP4tDwYIhUPkOxpiB2j1OUxebyg3Ep+1uKgeIyeYtm2KWqw2zMQjMW0v6gu0NLpOuqMGA4SamgtFisS0QADJbSUyhUAHz-XrooESWUYByYEAyDx4GlSj3VAC+ocQEaC0ckiigIyQ3qgRgjolAkFgCEQrLQ7M5NDwHHJNF4Og4eNIBaEfQOZnkpTMdgAsgRPA5gGg4KEi+REAB6fy6ENBQbyBBKOwcHyOptIvwAoLxxM6RsyFgTmRotMZ6DwJCoDAwbA4ACCqwACjQYONCCXGCw2FX1DwSAA3OAwFb5UeyODOJw4FcPAACJiBAlhHCiT8wDwAByODuBHOsZH-KhAOAkC2AglJoJveDEOQiRBjQjDQMwIgcMPLBcEIBxFDfWgZCoPBuEfeiqEYmhmNY7gOK4ni+Lw2CEKQ1NRFEajj1wc8VivG8oDwOg-BYAA2FgAGYWAAVhYFTEAAFj0lgAHY1J0lgjMQMzEAADmYHRbM0lgAE5LOM-4WF0UzzMQXTEC0wzXI8gAmUyGBDIA
Думал над этой задачей, реализовал классический алгоритм умножения столбиком, который выполняется за O(n^2).
Но самое смешное - я обнаружил, что при умножении столбиком можно умножать не только 1 разряд, лол.
См. пикрил. На первом скрине классическое умножение столбиком, которому учат в школе.
На втором я умножил 35x39 и прибавил 16x39, но со сдвигом сразу на 2 разряда.
В моем костыльном алгоритме реализуется первый вариант, происходит очень много операций умножения.
Компьютеру похуй насколько большое число умножать в пределах разрядности, оно умножается за одинаковое время. Так что, можно умножать сразу большие куски чисел и складывать с большими сдвигами.
Я же говорил, количество возможных оптимизаций этой хуйни бесконечно.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAWxAG1gBzQTwBQCGAXImCMgEYCmATgNoC6ANIhSWZbYwJTvnX0GiAN4AoRBMQQEAZyiIaVGeih9OgxAF5EdAAwMA3OMnSwcxGgJyAklsQEAdGipgA5lAAWiALSIAjEaSiMBwNIh4zvIAVna6BogxADysTi7uHvFRANRZ3CLGQRKRiFBUyJixgYUSIWERVPIwlYhNidqWNvEwOXli1dWm5hAgNIpgUABKSioAIjCuMFDWYAAmVAAedk1ZCVX9JrLyw6Muk9MYcwvy2orKGHTHY2d3UJeLy2vrQgD834hxBX2UkOiEwNDgKxA0DsBDoMCEACpWHQooZAftiit5os1AIWKVygA5KgAd1xtD2QLoBMwxJJLCxVyE2hk2EWhP4tDwYIhUPkOxpiB2j1OUxebyg3Ep+1uKgeIyeYtm2KWqw2zMQjMW0v6gu0NLpOuqMGA4SamgtFisS0QADJbSUyhUAHz-XrooESWUYByYEAyDx4GlSj3VAC+ocQEaC0ckiigIyQ3qgRgjolAkFgCEQrLQ7M5NDwHHJNF4Og4eNIBaEfQOZnkpTMdgAsgRPA5gGg4KEi+REAB6fy6ENBQbyBBKOwcHyOptIvwAoLxxM6RsyFgTmRotMZ6DwJCoDAwbA4ACCqwACjQYONCCXGCw2FX1DwSAA3OAwFb5UeyODOJw4FcPAACJiBAlhHCiT8wDwAByODuBHOsZH-KhAOAkC2AglJoJveDEOQiRBjQjDQMwIgcMPLBcEIBxFDfWgZCoPBuEfeiqEYmhmNY7gOK4ni+Lw2CEKQ1NRFEajj1wc8VivG8oDwOg-BYAA2FgAGYWAAVhYFTEAAFj0lgAHY1J0lgjMQMzEAADmYHRbM0lgAE5LOM-4WF0UzzMQXTEC0wzXI8gAmUyGBDIA
58 Кб, 240x246>>3568
Нееееет, это немножко не тааааак. Попробуй вывести 18446744073709551615 в stout, чтобы понять, в чём же дело, и почему это так интересно и необычно.
Нееееет, это тоже немножко не тааааак. Минимально возможный 1 бит никто не выделит. В интернетиках пишут, что Boolean занимает 4 байта, но это с учётом выравнивания, в массивчике они наверное плотно лягут друг к дружке валетиками, и будут занимать по одному честному БАЙТУ, и из честных 256 значений ты сможешь занимать... 2 :( Сэкономил.
И вообще по-моему у вас есть встроенный тип BigInt, но чтобы им пользоваться в TypeScript, нужно какую-то фичу компилятора включить.
> Если кто не понял, в чем вообще проблема, скажу, что числа в языке программирования имеют четко ограниченный максимальный размер. Например, в js тип number имеет размер 64 бита, то есть, число не может превышать 2^64. В двоичном представлении число будет представлять собой последовательность 64 единиц: 1111111111111111111111111111111111111111111111111111111111111111. То есть, все биты ячейки памяти забиты единицами, нулей нет. В десятичном виде это будет 18446744073709551615.
Нееееет, это немножко не тааааак. Попробуй вывести 18446744073709551615 в stout, чтобы понять, в чём же дело, и почему это так интересно и необычно.
> Например, можно создать массив типа boolean[] и работать в двоичной системе счисления. Для хранения цифры будет использован 1 бит - минимально возможная память.
Нееееет, это тоже немножко не тааааак. Минимально возможный 1 бит никто не выделит. В интернетиках пишут, что Boolean занимает 4 байта, но это с учётом выравнивания, в массивчике они наверное плотно лягут друг к дружке валетиками, и будут занимать по одному честному БАЙТУ, и из честных 256 значений ты сможешь занимать... 2 :( Сэкономил.
И вообще по-моему у вас есть встроенный тип BigInt, но чтобы им пользоваться в TypeScript, нужно какую-то фичу компилятора включить.
>>3568
Нееееет, это немножко не тааааак. Её и не должно хватать. Есть куча алгоритмов по быстрому введению огромных чисел в огромные степени по какому-то модулю. Например, простенький на пикрил 2.
> В данной задаче нужно возвести число в степень, одна длина которой может быть 2000 цифр. Я даже хз, хватит ли вообще памяти на такую хуйню.
Нееееет, это немножко не тааааак. Её и не должно хватать. Есть куча алгоритмов по быстрому введению огромных чисел в огромные степени по какому-то модулю. Например, простенький на пикрил 2.
>>3609
Бляяяяять... Опять меня наебали. Пишут, что даже 8 байт может занимать. Как так нахуй? Всем настолько похуй на память? Ладно, я еще могу понять, почему не упаковывают в 1 байт по 8 булеанов, может там накладные расходы на такие многоходовочки будут превышать выгоду на большинстве приложений. Но какого хуя 4 или 8 байт блять?
Что-то я не понимаю. В оперативке ведь каждый БИТ имеет свой адрес? Или каждый БАЙТ?
Придумали эти байты ебаные, они только все путают. Раньше были компьютеры и с байтами из 4 и 6 битов. Байт - по сути, выдуманная хуйня.
Как решили проблему адресации памяти, когда она превысила 4 гигабайта? 32-битное число хватает только что адресовать память максимум в 4 Гб. Тупо стали использовать 64-разрядные адреса?
Почитал, вроде во всей современной оперативке адреса указывают на байты. Так какого хуя в жс булеан имеет размер, кратный степени двойки? Это как-то связано с тем, чтобы удобнее было размещать в оперативке другую хуйню, тоже кратную по размеру степени двойки? Чтобы не было нечетных байтов?
>В интернетиках пишут, что Boolean занимает 4 байта, но это с учётом выравнивания
Бляяяяять... Опять меня наебали. Пишут, что даже 8 байт может занимать. Как так нахуй? Всем настолько похуй на память? Ладно, я еще могу понять, почему не упаковывают в 1 байт по 8 булеанов, может там накладные расходы на такие многоходовочки будут превышать выгоду на большинстве приложений. Но какого хуя 4 или 8 байт блять?
Что-то я не понимаю. В оперативке ведь каждый БИТ имеет свой адрес? Или каждый БАЙТ?
Придумали эти байты ебаные, они только все путают. Раньше были компьютеры и с байтами из 4 и 6 битов. Байт - по сути, выдуманная хуйня.
Как решили проблему адресации памяти, когда она превысила 4 гигабайта? 32-битное число хватает только что адресовать память максимум в 4 Гб. Тупо стали использовать 64-разрядные адреса?
Почитал, вроде во всей современной оперативке адреса указывают на байты. Так какого хуя в жс булеан имеет размер, кратный степени двойки? Это как-то связано с тем, чтобы удобнее было размещать в оперативке другую хуйню, тоже кратную по размеру степени двойки? Чтобы не было нечетных байтов?
>>3612
Еще и тут математики залили говна в жопу... Как жопой чуял, что не обязательно число в степень возводить.
По сути, самые эффективные алгоритмы плотно связаны с математикой. Яркий пример - криптография, по сути, чистый матан.
Еще и тут математики залили говна в жопу... Как жопой чуял, что не обязательно число в степень возводить.
По сути, самые эффективные алгоритмы плотно связаны с математикой. Яркий пример - криптография, по сути, чистый матан.
31 Кб, 1477x156>>3609
Ебаный рот этого казино! Это что еще за нахуй? Почему 2^53? Что вообще происходит? Оно должно идеально работать с числами вплоть до 2^64 - 1. Пиздец...
>Попробуй вывести 18446744073709551615 в stout, чтобы понять, в чём же дело, и почему это так интересно и необычно.
Ебаный рот этого казино! Это что еще за нахуй? Почему 2^53? Что вообще происходит? Оно должно идеально работать с числами вплоть до 2^64 - 1. Пиздец...
95 Кб, 783x589>>3654
Блять, понял.
Блять, понял.
>>3651
boolean[] - это просто предохранитель, чтобы ты случайно не положил элемент неправильного типа в массив, это не говорит ничего о том, сколько памяти в жаваскрипте под него выделится
Если тебе нужен кусок памяти конкретного размера в байтах, в жс есть ArrayBuffer https://learn.javascript.ru/arraybuffer-binary-arrays Тут можешь вручную делать упаковку 8 булеанов в 1 байт, если тебе нужно.
boolean[] - это просто предохранитель, чтобы ты случайно не положил элемент неправильного типа в массив, это не говорит ничего о том, сколько памяти в жаваскрипте под него выделится
Если тебе нужен кусок памяти конкретного размера в байтах, в жс есть ArrayBuffer https://learn.javascript.ru/arraybuffer-binary-arrays Тут можешь вручную делать упаковку 8 булеанов в 1 байт, если тебе нужно.
165 Кб, 1280x720>>3651
Динамическая типизация, то есть то, что в массив можно добавить элемент любого типа, означает, что внутри он будет реализован как массив таких структур: https://ideone.com/00Nva4, со всеми вытекающими.
(Есть реалистичные варианты это оптимизировать, например, в терминах моего примера — хранить отдельно массив однобайтовых типов ty[] и отдельно массив восьмибайтовых юнионов, получив 9 байт на элемент; затем спешлкейснуть случай, когда все элементы имеют один тип, получив 8; это приводит нас к тому, как оно и сделано на практике: https://itnext.io/v8-deep-dives-understanding-array-internals-5b17d7a28ecc; теоретически можно было бы, по аналогии с PACKED_DOUBLE_ELEMENTS и пр., спешлкейснуть случай массива булеанов и хранить его как 1 бит/элемент, но массив булеанов не является особенно частым и важным случаем, заслуживающим того, чтобы так ради него заморачиваться.)
Динамическая типизация, то есть то, что в массив можно добавить элемент любого типа, означает, что внутри он будет реализован как массив таких структур: https://ideone.com/00Nva4, со всеми вытекающими.
(Есть реалистичные варианты это оптимизировать, например, в терминах моего примера — хранить отдельно массив однобайтовых типов ty[] и отдельно массив восьмибайтовых юнионов, получив 9 байт на элемент; затем спешлкейснуть случай, когда все элементы имеют один тип, получив 8; это приводит нас к тому, как оно и сделано на практике: https://itnext.io/v8-deep-dives-understanding-array-internals-5b17d7a28ecc; теоретически можно было бы, по аналогии с PACKED_DOUBLE_ELEMENTS и пр., спешлкейснуть случай массива булеанов и хранить его как 1 бит/элемент, но массив булеанов не является особенно частым и важным случаем, заслуживающим того, чтобы так ради него заморачиваться.)
3 Кб, 331x52>>3657
>>3674
Да, что-то я забыл, что в жс динамическая типизация. Я думал, что если в массив кладут только значения одного типа, то он будет оптимизирован для них. На самом деле нет.
Попробовал решить ту задачку с литкода в лоб (сначала возвести в степень, потом разделить). Через BigInt, так как вручную в жс с его динамической типизацией я быстрее один хуй не сделаю. Получил пикрил. Что за мир, даже у BigInt есть максимальный размер... Я думал, что размер только оперативкой ограничен, покуда кудахтер не расплавится. Но нихуя.
Похоже, единственным возможным вариантом в этой задаче является специализированный математический алгоритм возведения в степень по модулю.
>>3674
Да, что-то я забыл, что в жс динамическая типизация. Я думал, что если в массив кладут только значения одного типа, то он будет оптимизирован для них. На самом деле нет.
Попробовал решить ту задачку с литкода в лоб (сначала возвести в степень, потом разделить). Через BigInt, так как вручную в жс с его динамической типизацией я быстрее один хуй не сделаю. Получил пикрил. Что за мир, даже у BigInt есть максимальный размер... Я думал, что размер только оперативкой ограничен, покуда кудахтер не расплавится. Но нихуя.
Похоже, единственным возможным вариантом в этой задаче является специализированный математический алгоритм возведения в степень по модулю.
100 Кб, 949x565Реализовал подозрительно простой алгоритм возведения в степень по модулю.
Работает уже лучше, чем вычисление в лоб и память не жрет.
Но все равно есть проблемка. Его временная сложность равна O(n), где n - степень. То есть, он один хуй неприемлем для возведения в ебанистические степени с 2000 цифр.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAWzgExAGwIYCcAKcA7gGLYDOUAFNgFyJgjIBGAprgDSLP2MvsBtALpdUaXkza5EAXkQBGAMyKA7AEoJ-aQG8AUIgOIICSolYAPAA4JWYKLMQAhGAHMAknarMAdACs4MGBUAOTBamoA3PqGmKz2EA7yUYaIwHDSVLH2MA4ADGARiDkAPGZWNnaFMADU1WqIeikpCXI0iABURvUApCjoyYYAvtEGuHEguEgQUcO6xmDkcLHemHAuVGJYeISkFNQqABwATABsKlwC8ly517eIN-fXQuFRQA
Работает уже лучше, чем вычисление в лоб и память не жрет.
Но все равно есть проблемка. Его временная сложность равна O(n), где n - степень. То есть, он один хуй неприемлем для возведения в ебанистические степени с 2000 цифр.
https://www.typescriptlang.org/play?#code/GYVwdgxgLglg9mABAWzgExAGwIYCcAKcA7gGLYDOUAFNgFyJgjIBGAprgDSLP2MvsBtALpdUaXkza5EAXkQBGAMyKA7AEoJ-aQG8AUIgOIICSolYAPAA4JWYKLMQAhGAHMAknarMAdACs4MGBUAOTBamoA3PqGmKz2EA7yUYaIwHDSVLH2MA4ADGARiDkAPGZWNnaFMADU1WqIeikpCXI0iABURvUApCjoyYYAvtEGuHEguEgQUcO6xmDkcLHemHAuVGJYeISkFNQqABwATABsKlwC8ly517eIN-fXQuFRQA
Скопипастил с википедии алгоритм возведения в степень по модулю за логарифмическое время. Right-to-left binary method. Работает.
Жалко, я абсолютно нихуя не понимаю почему и как.
Математика - не мой конек.
Нет, я пойму, если буду изучать эту хуйню пару недель, но у меня нет на это времени. А сходу понять - я слишком тупой.
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
Жалко, я абсолютно нихуя не понимаю почему и как.
Математика - не мой конек.
Нет, я пойму, если буду изучать эту хуйню пару недель, но у меня нет на это времени. А сходу понять - я слишком тупой.
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
Изучил сортировку слиянием (merge sort).
Намного проще qsort. В qsort в разделении Хоара вообще происходит ебаная черная магия, а тут можно накостылить алгоритм слияния без особых напрягов.
Сортировка слиянием всем хороша, кроме того, что жрет память в размере исходного массива.
Ну что ж, теперь я знаю аж 2 эффективных алгоритма сортировки.
https://www.typescriptlang.org/play?#code/PQKhCgAIUhZBTATgc3pAzge0QFwHRQwAqAlgLbwBckkA8gBQB2IANpskwJScHSQDKABwCGAYyp0uvEMHAAzAK6NROEpkaQKKeP2w4mCsumqNDAIyQBtALoAaSHMSYyJ80kgBeSAAZ7OTK5kFoiekKZGeCzwjMg4ABacgcE2kADeUDSQJHKQ9P6QALQOTmSQADyQAEycaRmZmYjwOAqIGuHoeOgsJOL0js5+mJwA3HWQAL5jouroOJokACYLUQCSjAvwAB6hsMLxeHJs2PR9JZAA1JD+NcBVI2ONza2aSKj0Wqi6uAZG9v1k9jIi2W8DWG02nEBrx0eh+6EBwNW6y2g24o0m8iUKjUGg+8D6JEQsySVjsGHg03WJMQNkSYTcNOstXqlNmkEa6AULBw1JSXhso3qUTmckJszBW1C3kFmWF5MpCwl2y80rGAHc4iQorkOVz8FEYvFyg4xfrorE4hd5eoFpFzfEaul6vVsrl0BSbUrPB4vO6FXbDZaAD5Bk1EnCWUXhpVMsq+j3rSx+z3IzbWR1jZ0NeCc7l4QQKdBxAnhyOmpXnc7pmVZyZZmjwFjurI5Evi1PerxR2YBi2QENh2Zl6OppkAPnjCqTCcVo4z9edurzBaL9GTifXs-Blermcydf34AeTRaGiXOHRR9ZcxIjALPPpQVJoUsvkgABZKu-7ABGb+QH97AANgAZl-AB2ewwMgABWSoIPsODrFGVlMCiSJ2HoAAiW970oLD7FwhQcHuVD0LYDgsKwXB4AWfCoW0L59CIkj7iAA
Намного проще qsort. В qsort в разделении Хоара вообще происходит ебаная черная магия, а тут можно накостылить алгоритм слияния без особых напрягов.
Сортировка слиянием всем хороша, кроме того, что жрет память в размере исходного массива.
Ну что ж, теперь я знаю аж 2 эффективных алгоритма сортировки.
https://www.typescriptlang.org/play?#code/PQKhCgAIUhZBTATgc3pAzge0QFwHRQwAqAlgLbwBckkA8gBQB2IANpskwJScHSQDKABwCGAYyp0uvEMHAAzAK6NROEpkaQKKeP2w4mCsumqNDAIyQBtALoAaSHMSYyJ80kgBeSAAZ7OTK5kFoiekKZGeCzwjMg4ABacgcE2kADeUDSQJHKQ9P6QALQOTmSQADyQAEycaRmZmYjwOAqIGuHoeOgsJOL0js5+mJwA3HWQAL5jouroOJokACYLUQCSjAvwAB6hsMLxeHJs2PR9JZAA1JD+NcBVI2ONza2aSKj0Wqi6uAZG9v1k9jIi2W8DWG02nEBrx0eh+6EBwNW6y2g24o0m8iUKjUGg+8D6JEQsySVjsGHg03WJMQNkSYTcNOstXqlNmkEa6AULBw1JSXhso3qUTmckJszBW1C3kFmWF5MpCwl2y80rGAHc4iQorkOVz8FEYvFyg4xfrorE4hd5eoFpFzfEaul6vVsrl0BSbUrPB4vO6FXbDZaAD5Bk1EnCWUXhpVMsq+j3rSx+z3IzbWR1jZ0NeCc7l4QQKdBxAnhyOmpXnc7pmVZyZZmjwFjurI5Evi1PerxR2YBi2QENh2Zl6OppkAPnjCqTCcVo4z9edurzBaL9GTifXs-Blermcydf34AeTRaGiXOHRR9ZcxIjALPPpQVJoUsvkgABZKu-7ABGb+QH97AANgAZl-AB2ewwMgABWSoIPsODrFGVlMCiSJ2HoAAiW970oLD7FwhQcHuVD0LYDgsKwXB4AWfCoW0L59CIkj7iAA
4,7 Мб, 2480x3496>>3840
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^0 или a^1, но далее делаем наблюдение, что «x // 2» и «а чётное ли x» соответствуют операциям «сдвинуть x на 1 бит вправо» и «посмотреть на младший бит x», то есть весь алгоритм сводится к «проанализировать двоичное представление x и перевести его в последовательность операций».
>>3878
Так это обычное возведение в степень, это хуйня, это я понимаю.
Надо по модулю. a^x % m, где x длиной 2000 цифр.
>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 цифр.
1,8 Мб, 1771x2559>>3883
(a × b) mod n = ((a mod n) × (b mod n)) mod n, в чём легко убедиться, расписав a и b как суммы вида kn + r: https://crypto.stackexchange.com/a/13290. :>
(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, когда похожие данные выдают похожие хеши, но это другое
Написано, что хеш-функция выдает сразу индексы массива. Но как блять? Вот есть md5 или sha1. Они выдают хеш определенной фиксированной длины. Как мне эту срань использовать как индекс массива? Допустим, хеш длиной 32 бита. Это мне надо использовать массив длиной 2^32? Чтобы сохранить 10 элементов? Че за хуйня вообще?
В другом месте написано, что хеш-функция принимает аргументом количество элементов в массиве. Допустим. Ну тупо длина хеша будет ограничена. И все равно, это надо заранее размер массива знать? И потом пересобирать его, когда он заполняется? Но тогда и перехешировать придется.
В хеш-таблицах используются какие-то особые хеш-функции?
Слыхал про symhash, когда похожие данные выдают похожие хеши, но это другое
703 Кб, 1072x1500>>4442
Используется хэш % размер_таблицы (на практике в качестве размера_таблицы используется степень двойки, чтобы можно было вместо медленного % сделать хэш & (размер_таблицы − 1); иными словами, берутся последние log₂_размера_таблицы бит хэша), но можно (во всяком случае, с открытой адресацией...) много придумать сверх этого. Например, остальные биты хэша можно использовать для сдвигов в ходе разрешения коллизии, то есть в https://ru.wikipedia.org/wiki/Линейное_зондирование#Поиск вместо прибавления единицы прибавлять следующие log₂_размера_таблицы бит хэша, так что в случае 4-байтовых хэшей ABCD, EFGD, HIJD, ... и 256-элементной таблицы изначальным индексом каждого из них будет XXXD % 256 = D и они все сколлидятся, но до 3 шагов дальнейшего разрешения коллизии будут разными.
И да, массив в любом случае нужно пересобирать и перехэшировать, от этого не уйти, это нормально и естественно, все это делают.
Используется хэш % размер_таблицы (на практике в качестве размера_таблицы используется степень двойки, чтобы можно было вместо медленного % сделать хэш & (размер_таблицы − 1); иными словами, берутся последние log₂_размера_таблицы бит хэша), но можно (во всяком случае, с открытой адресацией...) много придумать сверх этого. Например, остальные биты хэша можно использовать для сдвигов в ходе разрешения коллизии, то есть в https://ru.wikipedia.org/wiki/Линейное_зондирование#Поиск вместо прибавления единицы прибавлять следующие log₂_размера_таблицы бит хэша, так что в случае 4-байтовых хэшей ABCD, EFGD, HIJD, ... и 256-элементной таблицы изначальным индексом каждого из них будет XXXD % 256 = D и они все сколлидятся, но до 3 шагов дальнейшего разрешения коллизии будут разными.
И да, массив в любом случае нужно пересобирать и перехэшировать, от этого не уйти, это нормально и естественно, все это делают.