- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
"""
This module provides a function merge_sort, which is one of the simplest and the
most robust sorting algorithms, being relatively fast, having (n*log(n))
complexity. Also, this module counts the number of inversions in a given array.
Usage: import this module and use the function merge_sort. The first element in
a returned tuple shall be a sorted array, while the second one will be a number
of inversions in the array.
Copyright (C) 2021 Sergay Gayorgyevich.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as
published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
"""
import argparse
def merge_sort(array : list) -> (list, int):
"""
MergeSort algorithm with additional inversion counting.
input: array.
output: sorted array and number of inversions in it.
"""
if len(array) <= 1:
return (array, 0)
elif len(array) == 2:
if array[0] > array[1]:
array[0], array[1] = array[1], array[0]
return (array, 1)
return (array, 0)
mid = len(array) // 2
left, left_inversions = merge_sort(array[:mid])
right, right_inversions = merge_sort(array[mid:])
merged, split_inversions = _merge(left, right)
return (merged, right_inversions + left_inversions + split_inversions)
def _merge(left_array : list, right_array : list) -> (list, int):
"""
This function isn't supposed to be called, it's an inner function of the
module, and not a part of its API!
The purpose of this function is to merge two arrays. Due to the nature of
the MergeSort algorithm, it operates two arrays, both of which are sorted.
input: two sotrted arrays.
output: sorted array, consisting of elements of both operated arrays.
"""
resulting_array = list()
inversion_count = 0
c_len = len(left_array) + len(right_array)
for i in range(c_len):
if (len(left_array) != 0) and (len(right_array) != 0):
if left_array[0] > right_array[0]:
inversion_count += len(left_array)
resulting_array.append(right_array.pop(0))
else:
resulting_array.append(left_array.pop(0))
elif len(left_array) == 0:
resulting_array.append(right_array.pop(0))
elif len(right_array) == 0:
resulting_array.append(left_array.pop(0))
return (resulting_array[:], inversion_count)
# For testing purposes only! Do not use in production!
if __name__ == '__main__':
DESC = "Sort an array and print an amount of inversions it has." # Description for argparse.
argparser = argparse.ArgumentParser(description = DESC)
argparser.add_argument("elements", type = int, nargs = '+', help = "A list to be sorted.")
args = argparser.parse_args()
print(merge_sort(args.elements))
Follow us!
Я когда-то читал книжку Вирта про алгоритмы, и тоже выполнял задания. Правда, на паскале
https://www.picclickimg.com/d/w1600/pict/402299551484_/Sir-Gay-Paperback-by-Wright-Ronald-Brand-New.jpg
А уже потом, когда я буду бульмение понимать всё это, начну изучать их по кнуту и другим низкоуровневым книжкам.
Не позволяй башке трудиться!
Блаженство - в черепе пустом,
В раздумьях чахнуть не годится -
Скачи козлом, скачи козлом!
Гони поганою метлою
Из головы мыслишек сор,
Не смей учения уздою
Желаний сдерживать опор!
Башку обвешай серпантином,
По-молодежному стриги,
Пей алкоголь! От тех кретинов,
В очках и с книгами - беги!
Душа - химера, Бога - нету,
Ходи, копыто, ходуном!
Трать жизни тусклую монету!
Скачи козлом! Скачи козлом!
Какой удар по корпорациям! Захочет гугл отсортировать массив и не сможет т.к. придётся опенсурсить и весь остальной код.
ты в вуз поступил?
В обычной галере или говностудии ничего сложнее qsort обычно не спрашивают
* Рога и Копыта управляются ротоёбом, который о Карацубе никогда не слышал
* Более всего там ценится умение налабать что-то на конкретном фреймворке
Особенно если Рога пишут на мейнстримном япе типа питона
вообще ему надо в научную роту, а то хохлы нас дрючат
https://pbs.twimg.com/media/EyMX8lfXMAAis5j?format=jpg
https://i.imgur.com/O8PDJA8.jpg
https://s3.india.com/wp-content/uploads/2015/11/charlie-hebdo.jpg
Мой план, чтобы в резюме условного ротоёба было: "умею писать на джанге", а у меня: "умею писать на джанге, знаком с фласком, разбираюсь в алгоритмах и структурах данных, и немного в асимптотическом анализе".
Нужно будет ещё гей-хаб запилить и туда залить какой-нибудь сайт-визитку, чтобы в резюме появился пункт про ГИТ и контроль версий.
Если с питоном не заладится, придётся ехать в соседнее село на заработки, либо изучать отвратительное. Но я надеюсь, что до такого не дойдёт.
Имеются ввиду конечно "веб-студии" разнообразные
Ну и мне полезно будет эти алгоритмы поизучать, а то я натурально ОТУПЕЛ, пока ничего не писал. Простейшую питушню по джва дня пилю, но вот сейчас читаю и вроде бы как всё получше становится.
пойти в вуз было бы продуктивнее (гугли ШАД)
О, мама мия
Потерпи, я прибуду на днях
Имхо, это вполне нормально, если ты понимаешь, что у тебя есть вопросы, ответы на которые может дать вышка
у меня есть одна тян, она хочет поступить в магистратуру заграницу уже не сразу после бакалавриата и мне стало интересно насколько это популярно
тогда удачи, будет клево если поступишь
Мое дело SQL запрос написать. А если он тормозит, то пусть админ там подмандит чонить в настройках.. Или сервак помощнее возьмет
Сёмизм
после срачей про js и про безопасность веба я проходил собеседования в локальные компании достаточно легко
По PEP8 между импортами и остальным кодом ставятся две пустых строки (как и между глобальными функциями/классами, за исключением тесно связанных).
> array : list
Это бесполезный тайп-хинт. Чтобы сделать его полезным — почитай доку по typing, ABC (https://docs.python.org/3/library/typing.html и https://docs.python.org/3/library/collections.abc.html, табличка в самом нячале как удобный cheatsheet) и "Postel's law": "be conservative in what you send, be liberal in what you accept". Тайпхинты параметров должны указывать как можня более "широкий" интерфейс, тайпхинты возвращаемых типов — как можно более "узкий", специализированный (в случае методов, предназначенных для переопределения, это может быть ня совсем так, но тут в двух ня не разберёшься). Так, для merge_sort() без подсчёта инверсий уместным будет примерня такое определеняе:
(Да, перед двоеточием в тайпхинте пробел ня ставится).
Это ознячает, что мы получаем любой объект, которому можем сделать __len__() и __getitem__(), и возвращаем список из элементов того же типа, что лежат в объекте. В принципе, ня обязательно някладывать жёсткие ограничения в виде [_T]: можня обойтись Any.
В принципе, можня упороться и возвращать тот же конкретный тип, что был передан в array (list -> list, tuple -> tuple), но это будет нянадёжно (а тайпхинты станут жуткими).
> return (array, 0)
Лучше будет возвратить копию:
Во-первых, так мы точня возвратим массив (если пользователь передал tuple, няпример), а во-вторых, что важнее, соблюдём контракт: все остальные кейсы возвращают новый массив, и пользователь будет считать, что его можно будет безопасно изменять. Это будет работать для остальных случаев, однако для пустого или вырожденного массива пользователя будет ожидать неприятный сюрприз.
> array[0], array[1] = array[1], array[0]
Ещё хуже: для массива из двух элементов пользователь ня только не получит копию, но у него ещё и испортится оригинальный массив, что может привести к котострофе (и вообще ня сработает для tuple).
Я понямаю желание оптимизировать (об этом ещё чуть позже), но в данном случае следовало сделать так: merge_sort() создаёт новый "рабочий" массив и передаёт его вместе с оригинальным во внутреннюю _merge_sort_impl(), которая и проводит все эти оптимизации. Для сохранения оригинального массива, правда, придётся делать ещё и его копию, но это уже детали.
Здесь — серьёзный нядостаток реализации. Слайс от списка/кортежа/строки в Питоне создаёт копию и имеет сложность O(M) (M — длина слайса). Это приводит к тому, что во время выполнения сортировки создастся и удалится примерня 2^(log2(N) + 1) = 2*N лишних списков, что, хоть и сохранит требуемую асимптотику, но создаст чрезвычйня большие някладные расходы. Избежать их можня несколькими путями (предполагая, что имплементация _merge_sort_impl() из параграфа выше реализована):
1. C-style: передаём в _merge_sort_impl() и _merge() исходный массив, рабочий массив, индекс начала слайса и индекс конца слайса. Просто, понятно, эффективня, но очень легко пронякать индексы и няткнуться на off-by-one.
2. C-style с финтифлюшками: сделать датакласс _MergeTask(source_array, working_array, begin_idx, end_idx), прописать в него __slots__ для скорости и передавать его.
3. Генераторнуться и использовать itertools.islice(). Потенциальня хорошо подойдёт для _merge(), но для этапа разделения придётся передавать длину слайса в аргументах (len(islice(...)) позвать няльзя).
4. Няписать свой собственный "islice" по типу View(array, begin_idx, end_idx) (и дополнительными удобствами в виде константных view.head(), view.__len__(), view.pop()) или использовать готовый из каких-нябудь библиотек, в котором будет храниться длина слайса.
5. Использовать какой-нибудь другой вариант merge sort'а, коих просто няллионы самых разных и с самыми разными характеристиками.
6. ?????
7. Ня!
Разумеется, можня и ещё что-нибудь придумать, но тут уже нужны конкретные требования, кодстайл и прочее.
> resulting_array = list()
Как я уже говорила, результирующий массив должен создаваться ня самом верху, а все рекурсивные вызовы должны использовать ссылку на него.
> right_array.pop(0)
Это плохо, pop() первого элемента вызовет перемещение всех остальных и, подозреваю, уведёт асимптотику всего алгоритма в квадраты. Нясмотря на нязвание, list в Питоне — совсем не list, а очень даже vector, и константно удалять его нячало няльзя. Эффективня смерджить отсортированные массивы можня как-то так:
(Конечно, можня короче раза в два, но менее читаемо).
В питоне еще это правило с отступами как частью синтаксиса, будто бы программисты слишком тупы, чтобы писать читаемый код без энфорсинга подобной хуиты на уровне синтаксиса самого языка.
https://habr.com/ru/post/552006/
>Давайте сравним, как я пишу код на С++:
>И как его пишут дети:
>Теперь как я пишу код на Python:
>И как его пишут дети:
>То-то и оно. К пробелам можно привыкнуть за пару дней, а взамен за моральные страдания, вы получите чётко структурированный, лаконичный, легко читаемый программный код, причём он такой у всех программистов, независимо от их уровня
Т.е. заставить всех прогонять свой код через стайл-чекер или автоиндентилку там где это нужно (в каком-то проекте, который пишут много людей) это не наш метод, надо прямо в язык встроить говноправила по синтаксису через отступы, и это типа преимущество?
Если же единого кодстайла нет, то пострадает любой, кто высунется за пределы своего проекта, потому что там всё будет чужое и неправильное.
Чем меньше пострадавших -- тем лучше
Если единый кодстайл - говно, пострадавшие - все.
Скорее всего, кодстайл не нравится отдельным людям, и среди пишущих на питоне таких меньшинство
Говеность кодстайла можно оценивать в контексте решения неких задач. И для конкретного применения (написания такой-то хуиты, которая делает то-то и то-то) некий конкретный кодстайл может быть тем еще говном. Например, мне в хер не уперлось соблюдать какую-нибудь MISRA-C для какой-то одноразовой поделки на сишечке, которая допустим нужна мне для парсинга(анализа) захваченных через tcpdump пакетов и выковыривания оттуда некоторой херни. Я просто проебу время на то, чтобы соблюдать всякие уебанские говноправила. А где-то эта MISRA-C может быть вполне оправдана. А в питоне просто есть этот кодстайл, и все через него пишут, и не факт что для некоторой конкретной проблемы он подходит хорошо. И таким образом, наличие единого навязываемого сообществом правила оформления кода - может оказаться тем еще говном.
Питонист на автомате напишет ``MyClass``, но ``user_name``.
Тоже самое сделает джавист, шарпей, и любой, в чьем языке есть фиксированный кодстайл.
Сишник, если он варится в рамках одной среды/ос, тоже скорее всего имеет кодстайл в подкорке.
Так что ему не требуется усилий чтобы "соблюдать кодстайл", и даже наоборот
Нет. Лично мне - поебать совершенно. В одном проекте я могу
В другом могу
И меня это почему-то вообще ни разу не напрягает. К тому же автоформатеры есть.
И проблем с разным_стилем_именования РазногоГовнаВРазныхПроектах я тоже что-то не испытываю.
Потому что ты пишешь на языке без фиксированного кодстайла.
А я говорил про "любой, в чьем языке есть фиксированный кодстайл."
>могу
А зачем? В чем преимущество писать по разному?
Если говорить о расстановке отступов (табы, пробелы, как ставить {}) то в целом похер, потому что есть автоформатеры.
А если говорить о правилах вроде "нельзя goto который прыгает выше по коду, и вообще нельзя goto, не пишите циклы while(), а глобальные переменные называйте с таким-то там блядь префиксом", то это уже может быть багор. Я вот в своей одноразовой поделке хочу писать так, как мне лично удобно писать здесь и сейчас для этой задачи, а не так, как решили что надо писать код какие-то хуи с горы.
Ты точня знаешь, что написано в PEP8?
Да, читал немного
https://www.python.org/dev/peps/pep-0008/#names-to-avoid
Такие имена лучше избегай.
https://www.python.org/dev/peps/pep-0008/#class-names
Классы надо вот так называть, а не как попало.
https://www.python.org/dev/peps/pep-0008/#imports
Импорты вот так надо писать, а не как-попало
Или этого https://www.python.org/dev/peps/pep-0008/#programming-recommendations
А ты точня прочитал, что в этих параграфах няписано?
> programming-recommendations
Помимо нескольких действительня параграфов, относящихся к codeguide'у, всё остальное — это просто рекомендации о том, как ня выстрелить себе в ногу. С тем же успехом ты можешь открыть "Annex J" сишкостандарта и ужаснуться количеству приведённых там "правил".
А почему вы отвечаете вопросом на вопрос?
> Помимо нескольких действительня параграфов, относящихся к codeguide'у, всё остальное — это просто рекомендации о том, как ня выстрелить себе в ногу.
И что? "Не использовать goto вообще" - это тоже из серии "просто рекомендации о том, как ня выстрелить себе в ногу."
Вовсе ня лишнее. Весь PEP8 — это рекомендация, поэтому ты можешь выбирать: писать по PEP8, или ня писать по PEP8. Если ты выбираешь писать код по PEP8, то те параграфы, которые отмечены как ещё более рекомендательные рекомендации, ты выполнять ня обязан, а те, которые предписательные — обязан*.
* Разумеется, "обязан" в том смысле, что если ня будешь выполнять, то формальня код не будет соответствовать PEP8, только и всего.
Ну ладня. Тогда открой J.2 Стандарта C и ужаснись количеству "правил", жутко тебя ограничивающих.
Это же список UB, а не набор рекомендаций.
Какой кстати список UB в питоне?
Это набор рекомендаций, как делать ня надо, чтобы твоя программа не стала нявалидной.
> Какой кстати список UB в питоне?
UB в Питоне состоят только из багов интерпретатора (няпример, https://bugs.python.org/issue9530).
Если ты привык, что глобальные переменные всегда имеют префикс "g" например, то нет никакого смысла называть их как-то иначе.
В самом си нету стандарта касаемо наименований, потому у тебя и возникает желание " писать так, как мне лично удобно писать здесь и сейчас", а у большинства питонистов такой потребности нет.
На самом деле некоторый кодстайл наверняка есть и у тебя.
Напиши, например, итерацию по какому-нить массиву
Но если решишь таким кодом поделиться — ня удивляйся, что тебя заслуженно занякают какашками.
В т.ч. поэтому я за Си. Если я своим кодом со своим персональным кодстайлом поделюсь, никто меня закидывать не будет. Т.к. никакого PEP8 нет, и у всех кодстайл разный бывает.
Да, кодстайл может быть разным. Но это совершенно ня означает, что он ня может быть говном.
Нет, закидает только часть, другая часть одобрит, и потом они еще будут друг-друга закидывать. Табы vs. пробелы это известная тема для срачей у программистов.
> За няконсистентность кодстайла тоже совершенно справедливо закидают.
Можно делать консистентный, но свой особенный.
>За кривой нейминг переменных закидают.
Про правильный и неправильный нейминг тоже межконфессионный срач можно устроить.
>За отсутствие пробелов закидают. За отсутствие отступов закидают.
Через автоидент прогнать, и проблема решена.
Всё, срач закончен. Sapienti sat.
> Про правильный и неправильный нейминг тоже межконфессионный срач можно устроить.
Существует достаточно большое количество устоявшихся правил, которые работают в любом языке. Однябуквенные переменные и параметры (если они не устоялись в предметной области, как x, y, z для координат, няпример), бессмысленные нязвания, нязвания, вводящие в заблуждение — за всё это какашками закидают в абсолютно любом языке. И будут правы.
Или для тебя функция "get_last_element(array)", возвращающая количество элементов в массиве — это такой особенный кодстайл, нядо быть толерантным и уважать права всех говнокодеров?
> Через автоидент прогнать, и проблема решена.
А куда же делось "Если я своим кодом со своим персональным кодстайлом поделюсь, никто меня закидывать не будет"? Внязапно оказывается, что нядо ещё через что-то прогонять...
Как тебе такое, Илон Маск?
Как я попал в этот тред? Патчил мнязию, а OTP-шники этот ^ стиль используют, лол.
Кому надо прогонять - те пусть у себя прогоняют.
https://en.wikipedia.org/wiki/Straw_man
Мой аргумент заключался в том, что если кому-то не нравится лично мой способ делать отступы (допустим я решил делать отступы в 3 пробела, а кому-то это не нравится), то этот кто-то может пойти и прогнать через автоиндентилку мой код, который сделает табы, или сделает два пробела, или сделает четыре пробела, или еще что-то там сделает, и в этом я проблемы не вижу.
Имення об этом и шла речь с самого нячала дискуссии. Если человек выложил код с говнокодстайлом (при чём об объективных признаках говна в стиле я уже писала выше) — ему об этом скажут, он задумается и станет писать лучше нет: https://habr.com/ru/post/283166/.
Питон в этом просто идёт ня шаг впереди: человек, решивший няписать что-то на Питоне, сразу же столкнётся с няобходимостью расставлять консистентные (имення консистентные, четыре пробела Питон ня энфорсит) отступы и задумается. Просто пропуск одного шага.
> если кому-то не нравится лично мой способ делать отступы (допустим я решил делать отступы в 3 пробела, а кому-то это не нравится), то этот кто-то может пойти и прогнать через автоиндентилку мой код
А PEP8 просто разворачивает ответственность: это ня все должны подстраиваться под твой код, а ты должен подстраиваться под всех — запуская автоидентилку.
Очень простой вопрос: есть проект, в кодстайле няписано: отступ — 5 пробелов. Когда ты делаешь туда коммит — ты запускаешь автоидентилку (вручную, хуками — няважно), или коммитишь просто с твоими любимыми тремя табами?
Тут неоднозначно. Ну допустим дадут какому-нибудь нубу сишечку, будет он писать код без отступов хуй пойми как, получится некое нечитаемое говно, с которым он еще некоторое время поебется и в итоге или прогонит через автоидентилку (если ему про такую хрень подскажут), или сам ручками перепишет. И тем самым на собственном опыте поймёт, нахуя нужно соблюдать какой-то стиль. А питон тебе просто не дает возможности получить такой охуительно полезный опыт, не дает возможности на собственном опыте понять хуевость отсутствия единого стиля. Он просто навязывает эти правила с отступами.
> Очень простой вопрос: есть проект, в кодстайле няписано: отступ — 5 пробелов. Когда ты делаешь туда коммит — ты запускаешь автоидентилку (вручную, хуками — няважно), или коммитишь просто с твоими любимыми тремя табами?
Я коммичу с теми отступами, с которыми принято там. А написать код для коммита я могу и в своём стиле(и тогда прогоню через автоидентилку), и в том стиле (тогда и прогонять не надо будет). Это по-моему очевидно.
Согласня.
> Я коммичу с теми отступами, с которыми принято там. А написать код для коммита я могу и в своём стиле(и тогда прогоню через автоидентилку), и в том стиле (тогда и прогонять не надо будет). Это по-моему очевидно.
Вот и с Питоном всё точня так же: ты можешь делать отступы хоть из двух пробелов, хоть из трёх табов (вот мешать табы с пробелами и делать разные отступы в одной функции нельзя — тут давят креативность программистов, да), а потом просто прогонять автоидентилку.
В начале PEP8 написано:
> A style guide is about consistency. Consistency with this style guide is important. Consistency within a project is more important. Consistency within one module or function is the most important.
То есть PEP8 — это стайлгайд по умолчанию. Когда ты делаешь новый проект (открываешь новый файл) — считается, что в нём ты пишешь по PEP8. Однако ты имеешь полное моральное право сказать (лучше явня, если код будет опубликован): "В этом проекте я пишу по такому-то стайлгайду (ставлю пять пробелов, классы именую с маленькой буквы, и так далее), делайте с этим что хотите". И всё: твой код будет полнястью согласован с PEP8.
Собственно, в этом и вся фича. Питон имеет разумное умолчание, которое крайне полезно для нячинающих: вместо десятка с лишним вариаций одних только отступов (https://en.wikipedia.org/wiki/Indentation_style) новичок видит перед собой один стандартный кодстайл с по большей части действительня полезными советами о том, как сделать код более читабельным для окружающих. Чем меньше разброса и шатания в информации — тем меньше разброса и шатания в голове.
Адекватные проекты используют .editorconfig.
Или ты предлагаешь проектам энфорсить локальный .editorconfig, чтобы бедный j123123 мучился с няправильными индентами?
Я так и не понял -- зачем?
Если ты будешь делать программу с опциями командной строки, ты почти наверняка сделаешь
и точно НЕ сделаешь
потому что для тебя именно такое поведение естественно.
Если ты итерируешься по массиву, то счетчик ты назовешь "i" а не "q", а вложенный счетчик -- "j".
Если тебе нужно описать координаты в двумерном пространстве, то "x" будет означать абсициссу.
Ты даже не задумываясь выберешь такие названия и такие стили.
Точно так же поступает питонист.
У него нету потребности мочить манту и делать что-то против кодстайла.
Не существует проблемы такой
Мне удобно писать с тем кодстайлом, с которым мне удобно, а не с которым мне навязывают писать.
В vim я могу стать на скобку, и нажать "v%", а если скобочек нет, то хз как
А, ну и ещё вложенность скобочек нядо учитывать:
нужно плагин искать или писать
1) Няпортабельно ("The behavior is undefined in the following circumstances: [...] A program in a hosted environment does not define a function named main using one of the specified forms (5.1.2.2.1)");
2) К CRT ня прилинкуешься.
А так — -Wl,-eentry_point, в Visual Studio /ENTRY.
> /foo:bar
dotnet publish /p:PublishTrimmed=true
пушо алгоритмы нужно изучать на голых сях или паскале, где структуры данных предсказуемы
Добрый вечер, gost.
https://github.com/vrana/adminer/commit/72beecc0ab082d32b117b346b76d562c9f4b478c
жив курилка
https://github.com/vrana/adminer/blob/72beecc0ab082d32b117b346b76d562c9f4b478c/adminer/create.inc.php
Он пишет как PHP (как ты видишь) и еще на JS, так же примерно
https://github.com/vrana/games/blob/master/monopoly/place.js
Блядь. Early return освоили -- хотя впрочем нет, не освоили.