#quiz

What is the result of running the code above?
Comment your answer and explain, if possible.

Bugun ICPC komandamiz bilan praktika qilayotgandik, bir masalani qancha optimal yechishga harakat qilsak ham time limit olaverdik. Juda hayron bo'ldik, sababi algoritm O(n) vaqtda ishlashi kerak edi va hamma testcaselarga n < 10 ^ 5 limit qo'yilgan. Keyin bilsak, muammo kodda emas, tilda ekan. Python standard inputda 1 ta linedan 10 ^ 5 ta character o'qiyman deb tiqilib qolgan ekan. Xuddi shu yechim C++ da hamma testlardan o'tdi.

P.S. CPda ham Python ishlatasilarmi deydiganlar uchun: Bu shunchaki practice bo'lgani uchun sherigim qiziqib Pythonda yozib ko'rgandi. Contestda doim C++ ishlatamiz.

Group theory muxlislari uchun Cayley Graphs haqida ma'lumot berilgan qiziq page ekan. Page SoME3 onlayn musobaqasida "honorable mention" sifatida yuqori o'rin olgan:

https://juliapoo.github.io/mathematics/2023/07/15/plotting-cayley-graphs.html

Routing bo'yicha nimadir muammo bor menimcha. Ishlab turgan saytlar ora-orada uzilib qolayapti.

Yaqinda bir kishiga compiler vs interpreter mavzusida qisqacha ma'lumot uchun pastdagi linklarni tavsiya qilgandim. Hozir ko'rib kanalda boshqalarga ham foydali bo'lar deb o'yladim.

https://qr.ae/pKhb6S
https://qr.ae/pKhb6t

"Foydasiz" data structure haqida eshitganmisiz? Ya'ni struktura saqlanadi, lekin hech qanday foydali ma'lumot saqlanmaydi. Masalan, klassik singly linked list nodeda value va keyingi nodega pointer saqlanadi. Endi tasavvur qiling, shu yerdan valueni olib tashlab, faqat next pointerni qoldirsak nima bo'ladi? Haliyam linked list, lekin foydali biror narsaga ishlatish qiyin, sababi unda ma'lumot saqlashning iloji yo'q.

Aniqrog'i, shunday deb o'ylardim. Bugun qiziq bir narsa ko'rib qoldim. Ko'pchilik zamonaviy OSlarda free memory linked list va/yoki bitmap sifatida saqlanadi. Linked list sifatida saqlanganda har bir free blockning boshida node joylashib, block haqida metadata (masalan, block uzunligi) va keyingi free block'ka pointer saqlaydi. Lekin metadata saqlashga hojat bo'lmasachi? Masalan, virtual memoryda free pagelarning uzunligini metadata sifatida saqlash shart emas, sababi bu hamma uchun bir xil va o'zgarmaydi. Shunda hech qanday ortiqcha metadatasiz shunchaki page boshlanish joyining addressini bilish yetarli bo'ladi. Shunday holatlarda tepada aytilgandek "foydasiz" strukturalarning ham foydasi tegib qolar ekan.

Ertaga ICPCda qatnashayotganlar bormi?

Humoga ishga o'tsammikan deyapman. Sistema million marta osilib qolsayam birov g'ing demaydi. Deyolmaydiyam-da.

Array vs Tuple

Hozir Pythonda tuple va list bir-biriga juda yaqin obyektlar sifatida qaralsa-da, aslida ikkalasining kelib chiqishi butunlay ikki xil olam.

List (array)
Pythondagi list boshqa ko'pchilik tillardagi dynamic arrayga alternativ.

Array – mantiqiy jihatdan bir turdagi obyektlarning tartibli kolleksiyasi.

Ya'ni array bir xil turdagi bir qancha obyektlarni saqlash uchun ishlatiladi. Masalan, kompaniyadagi ishchilar ro'yxati. Arraydagi elementlar soni juda katta bo'lishi mumkin.

Arrayning eng kuchli tomoni bu ixtiyoriy indeksdagi elementni O(1) da olish mumkinligi. Odatda, oddiy matematikaga asoslangan offset qo'l keladi. Buning uchun ikkita shart bajarilishi kerak: arraydagi elementlar xotirada ketma-ket joylashishi va elementlarning o'lchami bir xil bo'lishi. Deylik, xotirada 1000 addressda joylashgan 32 bitli integerlardan iborat arrayning 6-o'rindagi elementini olish kerak bo'lsin. Array 1000 addressdan boshlanayapti, bizga kerakli elementdan oldingi 5 ta element 4 baytdan jami 20 bayt olsa, demak bizga kerakli element 1000 + 20 = 1020 addressda joylashgan bo'lishi kerak. Oddiy matematika yordamida kerakli element xotirada qayerda joylashganini O(1) da aniqlashning iloji bor. Umuman olganda, ko'p tillarda indekslash 1 emas 0 dan boshlanishiga sabab ham shu: indeks elementning tartib raqamini emas, u arrayning boshidan qancha uzoqda joylashganini ko'rsatadi.

Tuple

Tuple – mantiqiy jihatdan bitta katta obyektni hosil qiladigan har xil turdagi obyekt(cha)larning tartibli kolleksiyasi.

Ya'ni tupledagi har bir element bir xil turda bo'lishi shart emas, aksincha, har bir element butun obyektning kichik bir qismi. Masalan, (ishchining ismi, ishchining yoshi, ishchining maoshi) tupledagi 3 ta alohida element birlashib ishchi haqida (mantiqiy butun) ma'lumot beradi. Tupledagi elementlar soni odatda katta bo'lmaydi.

To'xta, sen aytayotgan narsa struct (yoki class) emasmi deyotgan bo'lsangiz demak tepadagilarni to'g'ri tushunayapsiz. Umuman olganda, struct ham xuddi tuplening ishini bajaradi, faqat qulay tomoni, u yerda har bitta elementga nom berilgan. Natijada 1-element ism, 2-si yosh, 3-si maosh deb eslab yurishga hojat qolmaydi. Aniqrog'i, sizning o'rningizga komputer eslab qoladi buni.

Endi eng qiziq joyi: agar elementlar o'lchami bir xil bo'lmasa unda tupleda qanday qilib elementni topamiz, offsetni hisoblash uchun elementlar o'lchami bir xil bo'lishi kerak edi-ku? Shunchaki bittalab yurib chiqamiz, boshqa variant yo'q. Masalan, tepadagi tupleda maoshni olmoqchi bo'lsak avval ism uchun uncha, yosh uchun buncha joy deb offsetni bittalab qo'shib chiqamiz. Natijada, elementni olish O(n) bo'lishi kerak edi. Lekin ozgina preprocessing orqali buni O(1) ga tushirsa bo'ladi. Tuple size odatda 100-200 dan oshmasligi hisobiga preprocessing ortiqcha ko'p vaqt va joy olmaydi.

P.S.1. Yuqoridagi narsalarni C/C++ kabi tillarda shunga yaqin holatda ko'rishingiz mumkin. Python, Javascript kabi tillarda bu narsalar ancha murakkab qurilgan va original ideadan ancha farq qiladi.

P.S.2. "Obyekt" deganda OOPdagi emas, umumiy, matematik obyekt nazarda tutilgan.

P.S.3. Strictly typed tillarda JSON obyektlarni struct/classga bind qilish yaxshiroqmi yoki map (key-value pair) ga? Bu savolning tepadagi mavzuga qanday aloqasi bor? Fikrlaringizni kommentariyada qoldiring.

@boboshersnotes

Today we present the first version of the Tashkent city metaverse project. The main goal of the project is to help our compatriots understand the streets of the city and introduce the city of Tashkent to foreigners. We have many plans for the future. Stay tuned for updates.

www.poytaxt.com

Shu yoki keyingi hafta oxirida kanalda audiochat o'tkazib ko'rmoqchiman. 1 yoki 2 ta mutaxassislar bilan, live podcast sifatida. Talk/discussion qaysi mavzuda bo'lishini xohlaysiz? Faqat sohaga oid, chuqurroq texnologik mavzuda. Shunga qarab ustozlarni ham chaqiramiz ))

Innovatsiyalar

Olamshumul kashfiyotlarni deyarli hamma yoqtiradi. Lekin aslida juda ko'plab bunday katta kashfiyotlar shunchaki muvaffaqqiyatsizlikka uchraydi va bu haqida hech kim gapirmaydi. Undan ham yomoni, katta kashfiyotlar boshqalarga keragidan ortiqcha motivatsiya beradi va natijada shoshqaloqlik va ehtiyotsizlik boshlanib, muvaffaqqiyatsizlik ehtimolini yanada oshiradi.

Masalan, Elon Musk butun boshli 2 ta industriyani butunday yangi darajaga olib chiqdi. Lekin shuning ortidan entrepreneurlar ko'proq risk qilishni boshladi va o'zini hamma sohada aqlli deb hisoblaydigan puldor qatlam paydo bo'ldi. Natijalarni ham ko'rishni boshladik...

Yozda okean tubida halokatga uchragan OceanGate esingizdami? Halokatga asosiy sabab kapsula dizayni va ishlab chiqarishdagi defektlar ekani aytilgan. Eng qizig'i, bunday muammo chiqishi mumkinligini halokatdan oldin ham bilishgan. Lekin uzoq va jiddiy testlar o'tkazilmagan. Masalan, kompozit materiallardagi defektlarni aniqlash uchun odatdagi, uzoq vaqt va resurs oladigan testlar o'rniga qisqa vaqt davom etadigan akkustik (ovoz yordamida) test o'tkazilgan. Akkustik test quloqqa aqlli eshitilsa ham, hali yangi va rivojlanmagan usul ekanini ko'pchilik mutaxassislar aytishgan. Bunga javoban esa (halokatdan keyin) kompaniya "Innovatsiyalarni oddiy g'oyalardek batafsil tekshirishga vaqt va hojat yo'qligi", "rivojlanish uchun doim risk olish kerakligi" ni bildirgan. Hatto Space X, Blue Origin kabi kompaniyalar shunday qilgani eslab o'tilgan. Natija esa hammaga ma'lum. Va bu birinchi va oxirgisi emas...

P.S.1. Ha aytgancha, Chernobil fojeasiga ham shoshqaloqlik, e'tiborsizlik va balandparvoz gaplar sabab bo'lgan.

P.S.2. Men innovatsiyaga qarshi emasman. Shunchaki ehtiyotkorlik tarafdoriman va shoshqaloqlikning "narxi" qimmat turishini eslatib qo'ymoqchiman. Steve Jobs yoki Elon Muskning kitobini o'qiganlarning hammasi ham innovator bo'lib ketayotgani yo'q. Bu bilim, tajriba, vaqt va omad ham talab qiladi. Muhimi shoshilmang, dunyoni 1-2 kun kechroq o'zgartira qoling ))

Real voqealarga asoslangan

Click ishlayaptimi?