Навіщо потрібний псевдокод?
Я вивчаю програмування і нещодавно задався питанням:
А навіщо потрібний псевдокод?
Окрім навчання та спілкування між програмістами різних мов програмування є використання псевдокоду?
Aboba Code, Programmer в Software Abobobus
Facebook
Twitter
LinkedIn
Makcuk nporpamicta
у патентах використовується іноді псевдокод який схожий на С, щоб описувати алгоритми
Andrii Sevastianov
Зазвичай його можна зустріти, наприклад, у серйозних книгах по алгоритмах, або у статтях. Наприклад, візьмемо щось на кшталт An Introduction to Counterfactual Regret Minimization. Там можна побачити код на Java з використанням LiterateProgramming, та algorithm 1 приведений як псевдокод. Які переваги? По-перше, можна напряму використовувати математичну символіку, яка є у статті. Зазвичай у мовах програмування написати $v_{\sigma{I \to a}}$ у якості змінної досить проблематично. По-друге, замість рутинної операції, яка займе купу реального кода, можна просто написати її опис.
Або, ось приклад з книги Introduction to Evolutionary Computing
BEGIN /* Assume we wish to select λ members of a pool of μ individuals */ set current member = 1; WHILE ( current member ≤ λ ) DO Pick k individuals randomly, with or without replacement; Compare these k individuals and select the best of them; Denote this individual as i; set mating pool[current member] = i; set current member= current member +1; OD END
Vic
Помітьє ваш приклад «псевдокоду» це по суті Algol 60. Тільки він псевдо бо в ті далекі часи просто не було ще Unicode. Оцей ось «псевдо код» запросто переписується на будь яку імперативну мову, та і сучасні FreePascal із підтримкою Unicode не здивуюсь якщо це ще і успішно зкомпілють із мінімальними правками.
Псевдокод — безумовний аттавізм дуже давніх часів. Сьогодні є ЯВР із ISO стандартами і великою купою наявних компіляторів, які можна використовувати, без необхідності писати код на неіснуючому в залізі ассемблері чи діалекті Algol, Pascal і т.д.
Власне так давно ніхто і не робить.
Навіщо так було треба в
Andrii Sevastianov
Так, по суті це Algol, Pascal, але замість операторів можна писати текст, та формули. Це і є псевдокод, який і зараз дуже часто використовується в літературі та в статтях про алгоритми. От ще приклад з цієї книги, трохи менше схожий на Algol:
BEGIN INITIALISE population; EVALUATE each candidate; REPEAT UNTIL ( TERMINATION CONDITION is satisfied ) DO SELECT parents; RECOMBINE to produce offspring; MUTATE offspring; EVALUATE offspring; [optional] CHOOSE Local Search method to apply; IMPROVE offspring via Local Search; [optional] Assign Credit to Local Search methods; (according to fitness improvements they cause); SELECT individuals for next generation; REWARD currently successful Local Search methods; (by increasing probability that they are used); OD END
Власне так давно ніхто і не робить
Почитайте arxiv.org, всі так роблять. Ось остання стаття, яку виклали сьогодні: Distribution Testing Meets Sum Estimation. Що ми там бачимо? Псевдокод. Так, жорстких стандартів як його писати немає, у когось це наближається до Algol. У когось до стиля Д. Кнута.
res.cloudinary.com/.../heajktend8tj3b1adel6.png
Nikola Utiuzhnikov
На співбесідах часами просять записати рішення в псевдокоді й на білій дошці. Особливо це стосується співбесіди до FAANG, але й інші компанії, особливо якщо в них більше, ніж три етапи інтервʼю, теж просять це.
Vic
Дональд Кнут видумав, абстрактний псвевдо ассемблер для своєї книги щоби пояснювати алгоритми. Коли він писав свої книги було дуже багато не сумісних архітектур комп’ютерів тому він винайшов псевдо ассемблер, щоби читач концентрувався на самому алгоритмі. Це зараз відносно не багато, по суті дві головних архітектури x86_64 та ARM (є ще MIPS, Risc V, SPARC, PowerPC і т.д. та вони не сильно розповсюджені)
Станом на зараз це не має жодного сенсу, можна використовувати наприклад С який є абсолютно де завгодно, або С++, JavaScript чи навіть Python — більшість народу із інших стеків насправді той код зрозуміє якщо підхід імперативний.
Для функціонального теж якщо людина розуміє сам підхід — то там хоч Haskel хоч Scala, читач зрозуміє.
Дональд Кнут видумав, абстрактний псвевдо ассемблер для своєї книги щоби пояснювати алгоритми.
Напевне ви не читали Д. Кнута. Щоб пояснити алгоритм, достатньо псевдокоду. Задача Кнута полягаля у тому, щоб для кожного алгоритму отримати реальний час виконання в інструкціях. На той час не було кешування, ... тому це давало гарну оцінку. Він образ псевдоасемблер щоб (1) уникнути розʼяснення деталів конкретної архітектури; (2) не надавати переваги жодній.
Але окрім псевдоасемблера, у TAoCP також є псевдокод, де саме пояснюється алгоритм.
Напевне ви не читали Д. Кнута.
Я взагалі читати не вмію.
На той час не було кешування, ... тому це давало гарну оцінку.
Це дає дуже гарну оцінку по сьогодні, чим менше інструкцій треба виконати процесором, тим менше треба тактів і швидше виконається алгоритм в цілому.
Власне векторні інструкції SIMD, супер скалярна архітектура із конвеєрами, Hyper Threading, багато ядер і т.д. — це усе про те саме, зменшити кількість тактів потрібних для виконання алгоритму, і рідше засіювати пристрої які повільніші за CPU від контролера пам’яті до контролера USB. Та усе це специфічно до конкретної апаратної платформи і виробника. В
никнути розʼяснення деталів конкретної архітектури;
Про це і була річ. Також про те — що зараз так точно можна писати базові алгоритми на С, як на найближчому до асемблера ЯВР. C звився в 1972, а Мистецтво програмування в 1968.
Також про те — що зараз так точно можна писати базові алгоритми на С, як на найближчому до асемблера ЯВР. C звився в 1972, а Мистецтво програмування в 1968.
Ну... перші видання були написані на архітектурі MIX, пізніші були з використанням архутектури MMIX, яка більш наближена до сучасної, це 1999 рік. Ніж розробляти нову архітектуру, чи не простіше було б обрати Сі?
Max Max
Візьми книгу по алгоритмам там використовують псевдокод
Взяв, але там приклади не на псевдокоді, а на Python.
То значить для початківців. Не кажучи про те, що Python в принципі поганий вибір, бо в алгоритмах ми піклуємося про швидкодію, а Python це x100 на рівному місці.
yvs2014
Для того щоб познайомити з концептами перфоманс ролі не відіграє, якщо не помиляюсь нп CS MIT курси які викладали на паблік були на базі пайтона, однією з причин було те що всі базові концепти представлені та й легко спробувати.
Для того щоб познайомити з концептами перфоманс ролі не відіграє
Ну... для початківців можливо, і то багато питань. Якщо ти студент, то тобі усе одно треба вирішити реальну задачу. Якщо є готовий фреймворк на Python, то так. Але якщо його немає? По-друге, код на Python треба написати та відлагодити, а це зайва робота.
Наприклад, в рамках наукової роботи був розроблений новий алгоритм. Далі, його треба порівняти з існуючими, якщо він буде реалізований на Python, то порівняння відразу не на його користь. Тоді виникає питання, навіщо його писати на Python?
CS MIT курси які викладали на паблік
Курси на паблік не мають до алгоритмів жодного відношення, це просто ази для школярів.
Однозначного консенсусу нема. Станом на зараз, частина провідних університетів світу в якості першої мови програмування використовує Python — з міркувань спрощення навчання, тобто зменшити вірогідність студенту відстрелити собі ногу. Інша частина використовує С — з тих сами аргументів, що ви навели, а також з аргументу Суворого «Тяжело в учении легко в бою».
Мова не йде про першу мову програмування. Мова йде як викладати алгоритми, які в принципі так чи інакше повʼязані зі швидкодією.
Ще з використанням пам’яті. Золоте правило Дональда Кнута — виграєш в швидкості, програєш в пам’яті.
В цілому Python дає такий самий імперативний підхід як і С або FORTRAN. Просто він бере на себе багато нюансів по роботі із операційною системою і обладнанням як і будь яка скріптова мова, тобто на який робиться скріпт для базової виконавчої системи. За ці абстракції доводиться додатково платити по пам’яті і по CPU дуже суттєву ціну. Сам підхід — уберегти студента від набитих шишок роботи із обладнанням та операційною системою, чи навпаки як в бойових мистецтвах почати із набивки і важких тркнувань доки білий пояс не стане чорним віт поту та крові.
У так, те саме пірамідальне сортування можна написати як на C так і на : Python, С++, Java, C#, JavaScript, Pascal, Basic, ML, Kotlin, D, Rust, Go lang і т.д.
Сам підхід — уберегти студента від набитих шишок роботи із обладнанням та операційною системою, чи навпаки як в бойових мистецтвах почати із набивки і важких тркнувань доки білий пояс не стане чорним віт поту та крові.
В алгоритмах зазвичай ми не працюємо з обладнанням чи операційною системою. В алгоритмах у нас є вхід, є вихід. Це математичні структури.
Та я розумію) мій коментар потрібно розглядати більше як жарт
Max Max
макогоненко
Взагалі це з часів коли доступ до компа й людського компілятора був розкіш
Зараз в принципі хіба для якихось статей по компутерсайенс мабуть, більше не бачу сенсу, нмсд краще вчити щось на конкретній мові
По цій причині я й питаю, бо також думав, що це більше для навчання і т.д., але в більшості джерел говорять, що псевдокод — це для проектування, хоча прикладів я ніколи не бачив і не чув.
Для проектування давно застосовують інші підходи та методи. Наприклад метод Буча та UML.
А навіщо тоді блок-схеми взагалі як не для описання алгоритмів, що є одним із елементів та формалізації процесів ? Програмування сам по собі є процес автоматизації через поступову формалізацію до наукового доказового рівня (в деяких випадках математично доказового рівня), за базовими законами логіки. Ансішний ANSI Flowchat — в UML внесено як Activity Diagram. Принаймні мене починаючи ще зі старших класів школи вчили перед написанням коду описувати алгоритм у виді блок-схеми (Flow-chat).
MIX/MMIX асемблер — Дональд Кнут ввів щоби можна було підрахувати використання алгоритмом пам’яті, та кількість потрібних операцій, відповідно швидкість виконання в інструкціях. MMIX — між іншим повноцінна RISC архітектура з якої існують реальні віртуальні машини, та в неї можна компілювати з GCC.
А навіщо тоді блок-схеми взагалі як не для описання алгоритмів, що є одним із елементів та формалізації процесів ?
Я не бачив жодного опису алгоритмів з використанням блок-схем. Просто раніше блок схеми використовувалися як проміжна мова, який користувався алгорітміст, проміжна ланка між постановником задач та кодувальником. Від цієї схеми зараз відійшли. В ті часи алгоритмом називався будь який опис послідовності дій, який можна перекласти на код. Зараз у цьому значенні це слово майже не вживається. Я почну розробляти алгоритм запросу до сервісу та запису в базу даних, це виглядає досить кумедно. Зараз алгоритм це вирішення зазвичай матемаматичних задач з вимогами по швидкодії та памʼяті. Типа Counterfactual Regret Minimization (CFR).
Блок-схеми зараз часткого лишаються частково у документації, поруч з UML, для ілюстрації послідовності невиликих по обʼєму дій. В математичній літературі та статтях переважно псевдокод.
макогоненко
Ну скажем так
Уяви що ти живеш в 68ому році
Не існує ні пітона на всякого сі ні Паскаля. Ти живеш у світі всяких фортранів, алголів, коболів, перфокарт та машинних кодів
Тобі потрібен спосіб щоб виразити алгоритм, неважливо це для книги чи для роботи. Спосіб який ти можеш задокументувати теж, бо потім перезаписати доведеться в спосіб для твоєї конкретної машини.
Ну от тобі й потрібен абстрактний спосіб сказати «тут має бути цикл, тут змінна» без калічного синтаксису і не на асемблері якомусь
Псевдокод — цей абстрактний спосіб
Це просто спосіб записувати алгоритми людською мовою в світі калічних машинних мов
Зараз ти маєш купу мов які дозволяють тобі виразити алгоритм більш-менш зрозуміло наприклад пітон. Але псевдокод не має синтаксису це просто людський запис коли тобі всеодно на синтаксис конкретної мови. Псевдокод вчити нетреба, вчити треба англійську мову хіба
Коли тебе питають написати на псевдокоді — фактично це тебе питають напиши як знаєш і як попало, щоб я побачив що ти розумієш алгоритм
Ну а коли ти і дональд і крут і портиш папір, то ти не можеш на одній сторінці писати так, а на іншій інак. Ну от дональд і видумав собі стандартик псевдокоду.
Я також спочатку думав, що це пережиток минулого :)
Ночне Животне
По цій причині я й питаю, бо в більшості джерел говорять, що псевдокод — це для
«эскизов»
, але прикладів я ніколи не бачив і не чув
Trip Trip
але прикладів я ніколи не бачив і не чув
Eugene Nuribekov
Черновик. Возможность изложить суть идеи не вдаваясь в технические детали конкретного языка. Текстовая альтернатива блок-схеме.
І хто так робить? Я ніколи не чув про таку практику
Можливо є приклади з життя?
Eugene Nuribekov
В книгах по алгоритмам такое часто встречается. На собеседованиях. В обсуждениях каких-то технических решений в команде.
Tymchyshyn Vitalii
та будь-яка стаття по CS. от чисто випадково тицьнув на arxiv: arxiv.org/pdf/2205.11327 . не треба сприймати псевдокод як щось таке на рівні реальних мов програмування: це всього лиш ілюстративний інструмент, щоб краще донести свою думку як-то графіки, картинки, таблиці, формули.
Я думав, що в CS використовують для більшості прикладів C
ні. хіба що конкретно йдеться про щось С-специфічне. а коли треба пояснити алгоритм чи загальний принцип, то тільки псевдокод, інакше пояснення просто втоне в непотрібних деталях реалізації.
Станом на зараз — так не робить напевно ніхто. Машинний час давно не є обмеженою дуже дорогою справою. Так ще в
Великі же транзисторні машини
Тому програмісти і інженери дуже сильно розглядали усі алгоритми і розрахунки на папері, перед використанням комп’ютера.
Сам інженерний підхід тим не менше — має місце, складні системи краще спочатку проектувати — як ті мости чи літаки з кораблями, для яких роблять проекти та креслення, а вже потім реалізовувати в програмному коді. Вийде дешевше і більш прогнозовано. Але за дослідами університету Кернегі Мелоун та Пентагону за моделлю en.wikipedia.org/...Capability_Maturity_Model в світі переважає експериментальний підхід в розробці софта.
Машинний час давно не є обмеженою дуже дорогою справою.
Якщо не брати саме алгоритми, коли питання чекати розвʼязок задачі день чи рік.
Сьогодні 80% народу займається експериментальним програмуванням. Тобто спочатку щось пишуть Bottom Up підходом, потім якщо є проблеми дебажать, фіксять башги профайлять і т.д.
Тоді як вірно проектувати Top Down підходом, але для цього треба повнота знань щодо вимог та можливостей програмно-апаратної платформи, чого майже ніколи немає.
Ці 80% не мають жодного відношення до розробки алгоритмів. Навіть 95% :-)
Це просто технічне кодування.
Slavik Savko
Псевдокод — неформальний опис алгоритму який можна зрозуміти без знань синтаксису мови.
Так він потрібен для навчання.
Для спілкування між програмістами наврядчи — програміст у більшості випадків зрозуміє що там написано навіть якщо не знає тієї мови програмування, якщо щось із синтаксису буде не зрозуміло загуглить чи скормить чату щоб пояснив
В документаціях та наукових статтях ще зустрічав речі написані псевдокодом. Але здається мені це зайве. Особливо для наукових статей, адже якось домовились до математичних формул чому не можна домовитись про єдину мову для написання прикладів коду
Для спілкування між програмістами наврядчи
Почему? На интервью довольно часто предлагают решить задачу в псевдокоде.
Я погоджуюсь з вами на 80% але дякую за відповідь!
Чому на 80%? Та тому, що ви сказали:
Для спілкування між програмістами навряд чи
а я стою за думкою, що псевдокод — це класний інструмент для спілкування між програмістами різних мов програмування (як UML)
Володимир Обрізан
Псевдокод — це абстракція, намагання викинути зайве. Псевдокод — це найкращій кандидат на предметний код (dsl, domain specific language). Більше про різні засоби представлення алгоритмів: Вступ в алгоритми — Представлення алгоритмів
48 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів