Записки программиста, обо всем и ни о чем. Но, наверное, больше профессионального.


WQUPC reduces time from 30 years to 6 seconds

Потрясающий факт: добавлением пары строчек в алгоритм, мы сокращаем время выполнения с 30 лет до 6 секунд!

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        parent[rootP] = rootQ; 

    public int find(int p) {
        while (p != parent[p])
            p = parent[p];
        return p;

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];

    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        return p;

Это из проблемы Union-Find, где надо определять/задавать принадлежность объектов одному/разным наборам.

Если взять миллиард (10^9) объектов и выполнить над ними 10^9 операций Union-Find, то в первом случае (Quick-Union UF) ждать придется 30 лет.
А во втором случае (Weighted Quick-Union with Path Compression UF) задача будет выполнена через 6 секунд.

Вот так всю жизнь используешь алгоритмы/структуры и знать не знаешь, какие страшные тайны скрыты под поверхностью.
А ведь я помню, как радовался народ, когда я чутка переписал алгоритм рассчета полигонов (древняя ГИС на древнем Автокаде) и вместо часов ожидания мы получали результат через секунды.

Но с 30 лет до 6 секунд парой строк? Это потрясающе.

original post http://vasnake.blogspot.com/2016/01/wqupc-reduces-time-from-30-years-to-6.html


Funny videos

Сегодня решил утянуть себе в плейлист два забавных видеоролика про IT:

– The Website is Down https://youtu.be/R5M5fwsoMc0

типичные 10 минут жизни из IT саппорта.

переделка Uptown Funk, на тему живого патчевания ядра Linux.

Наслаждайтесь пельмешком.

Uptime Funk Lyrics:

This bit
A bad bug,
Make my system fold
This bug, in the kernel
My kernel
My uptime ceases
Freakin’, Spazzin’
My manager’s mad, it ain’t pretty
I need caffeine, a big screen
Gotta fix this server in a jiffy

It’s too hot (hot patch)
Call Torvalds and Kroah-Hartman
It’s too hot (hot patch)
Make a Sys Admin retire man
It’s too hot (hot patch)
Holy cow, am I in a jam
It’s too hot (hot patch)
Tellin' ya now it ain't that funny
Server's down

Live patching hallelujah (whoo)
Live patching hallelujah (whoo)
Live patching hallelujah (whoo)
‘Cause Uptime Funk gon’ give it to ya
‘Cause Uptime Funk gon’ give it to ya
‘Cause Uptime Funk gon’ give it to ya
Saturday night and servers alright
Don’t reboot it just patch (come on)
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Hey, hey, hey, oh

Don’t reboot, init
Found a fix, grab code from git
Make a build, passed the tests
Julio! Make a patch!
Ride to Provo, Nuremberg, Newbury in the UK
We got Linux, and there's no doubt
Gonna fix that server in a jiffy

I'm all green (hot patch)
Called a Penguin and Chameleon
I'm all green (hot patch)
Call Torvalds and Kroah-Hartman
It’s too hot (hot patch)
Yo, say my name you know who I am
It’s too hot (hot patch)
I ain't no simple code monkey
Nuthin's down

Live patching hallelujah (whoo)
Live patching hallelujah (whoo)
Live patching hallelujah (whoo)
‘Cause Uptime Funk gon’ give it to ya
‘Cause Uptime Funk gon’ give it to ya
‘Cause Uptime Funk gon’ give it to ya
Saturday night and servers alright
Don’t reboot it just patch (come on)
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Hey, hey, hey, oh!

Before we leave
Imma tell y'all a lil something
Uptime Funk you up, Uptime Funk you up
Uptime Funk you up, Uptime Funk you up
I said Uptime Funk you up, Uptime Funk you up
Uptime Funk you up, Uptime Funk you up

Come on, patch
Get on it
If you stable then flaunt it
If you online then own it
Don't text about it, come show me
Come on, patch

Get on it
If you stable then flaunt it
Well it’s Saturday night and the servers alright
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Don’t reboot it just patch
Hey, hey, hey, oh!

Uptime Funk you up, Uptime Funk you up
(say whaa?!)
Uptime Funk you up, Uptime Funk you up
Uptime Funk you up, Uptime Funk you up
(say whaa?!)
Uptime Funk you up, Uptime Funk you up
Uptime Funk you up, Uptime Funk you up
(say whaa?!)
Uptime Funk you up, Uptime Funk you up
Uptime Funk you up, Uptime Funk you up
(say whaa?!)
Uptime Funk you up

The Website is Down transcript

Web Dude: [playing Halo] C'mon you little bitches, let's go... That's right. Oh snap.
[Skype phone rings]
Web Dude: Ulch, not now! [Halo: "Red team is winning."] Oh, you so suck. Ohhh... c'mon. Ohhh..... FUCK. [Picks up the call] Hello? [Alt-tabs back to Halo]
Chip: Web dude it's Chip in sales, what's up man?
Web Dude: Nothing, I'm working. What's... um. What's going on?
Chip: Hey are you ah, you here in Building 3?
Web Dude: Yeah I'm in Building 3.
Chip: Well why do I have to call an outside number to get to your desk?
Web Dude: Wha. Look uhhh, I don't want to get into an IP Telephony conversation with you right now.
Chip: You pee telephony? Haha. I pee *urine*. Heh heh... he totally fell for it.
Nancy and others giggle.
Web Dude: ...that's a... that's a good one.
Chip: Alright so web dude, we got a problem. The website's down.
Web Dude: ...I'm sorry what??
Chip: The Web Site Is Down. It's a black hole, can't get to anything.
Web Dude: [gets killed in Halo] FUCK.
Chip: Yeah.
Web Dude: Hold on. [alt-tabs out of Halo into web browser, showing monster.com, brings up the company website] Looks like it's up to me.
Chip: Wellp... I rebooted my PC and it's still that way.
Web Dude: [alt-tabbing back to Halo] How many times d'you reboot?
Chip: Three man, you always tell me to do three.
Web Dude: Well, uhmmm... hold on. [alt-tabs back to the site] It's up, I mean, I can check to see if Apache's running. [typing commands] Apache is running.
Chip: I don't know what this Patchie is, but ah, either way? I'm still not able to ge-
Web Dude: Oh look, I can telnet to the core, you can get HTML, like, it's running.
Chip: Ok well I'm st- I'm still not able to get what I'm looking for, uh... Nancy said that you guys rebooted last time- I dunno.
Web Dude: Do you want me to reboot... the web server? Even though it's running.
Chip: I'm just saying that's what Nancy said you did last time. Okay?
[long awkward pause]
Web Dude: Well... I can reboot it now? It doesn't make any sense to reboot something that's running-
Chip: Okay well I'm just, I'm just telling you what Nancy said, that y'guys just ah, you know, you guys rebooted last time.
Web Dude: Ummm...
Chip: Y'know I'm not saying anything about YOU guys, you know, I don't, I don't --
Web Dude: Sure. Why not...
Chip: -- I mean, you know, I dunno anything about ah...
Web Dude: ...let's reboot it I mean. It's fun to reboot a web server. I mean that'll take fifteen minutes [alt-tabs back to Halo] so I can get back to what I was d-
Chip: Wait... something just happened. Uhhhhhhhhhhhhhhhhh. I - I can't get to the homepage.
Web Dude: Whaddaya mean you can't get to the homepage? I just took it down.
Chip: I just -- I just tried to get to the homepage and I can't get in-
Web Dude: You could get to the homepage before?
Chip: Yeah I was gettin' to the homepage and now I can't get to the homepage.
Web Dude: You told me the website was down. ....gehhh FUCK. So the website WASN'T down.
Chip: Well... eh. Well maybe that's not what I meant okay, uh...
Web Dude: Well it's down *now*.
Chip: Well, what. Whatever it's called. Uh, the world wide web, was dow-
Web Dude: The *internet*????
Chip: It's slow, everything is just slow-
Web Dude: You don't know the difference between the internet and our web site?
Chip: Hey Nancy, is your, is your, is your web working?
Nancy: I told you it wasn-
Chip: Nonono, I know, I know. He rebooted the website.
Nancy: What!?
[incoming call]
Chip: He rebooted it.
Nancy: Waaaaaaaat.
Web Dude: Hold on. [transfers to Line 2] Hello?
Trevor: Uhh yeah, this is Trevor... I work for the city of Arvada, population ten thousand... and I was just looking at our website -- www.arvada.org/arvadaharvestfestival -- and. Ah. I get this error message, page cannot be displayed.
Web Dude: Well it's because the web site's down.
Trevor: Hunhhh?
Web Dude: Oh my god. Look, the sales guys upstairs took down the website so we're waiting for it to come back. [Shooting teammate in the balls in Halo]
Trevor: Whooo?
Web Dude: I guess it was Trevor.
Trevor: And then I tried Arvadaharvestfestival/pumpkinpatch and that wasn't on there and then I tried harvestfestival/beanbagrace and nothing's coming up and I LITERALLY... have the Mayor breathing down my neck right now so we need to get this back up, uh --
Web Dude: Well it should be up by now honestly -- [continues to shoot teammate in the elbow in Halo]
Trevor: They call it On Line. We gotta get this page online.
Web Dude: Uh, alright Trevor, well let me, you know, can I call you back when it's up? [Halo: "Blue team has the lead"]
Trevor: You know what, call me back, at this number... LITERALLY. Have the Mayor. Breathing down my neck. Arvadapumpkinpatch.org.
Web Dude: Mkay. Check.
Trevor: Hunhhh?
Web Dude: See you later. [Hangs up on Trevor, transfers back to Chip] Okay --
Chip: ...down because he rebooted it. I--
Nancy: What an idiot.
Chip: I dunno why he did it -- ahhmmm, say that again?
Web Dude: Listen -- oh. What was your name again? Chip?
Chip: Chip-hhh.
[incoming call]
Chip: I didn't ask for it to go down...
Web Dude: Can you hold on a second? [transfers to Line 2] Hello?
Boss: D'you take down the website?
web Dude: ...no...
Boss: Well Nancy says ya did.
Web Dude: Oh I mean. Yeah!
Boss: Well why the hell didja do that???
Web Dude: Well the sales guys... were...
Boss: Didn't you get my email about not taking down the web server?
Web Dude: Uhhmm... nnn... [alt-tabs to Outlook, showing an email: DO NOT REBOOT THE WEB SERVER!!!!!!!!!!!] ...no?
Boss: Well I sent it to you.
Web Dude: ... ... ... ... [click, click, click] well... [click]... [removes all traces of the email from Exchange Server] Hold on. Cuz I don't see it.
Boss: Well... ahh, this is weird. I don't see it here. Okay. Well maybe I didn't send it to you.
Web Dude: Well yeah cuz uh seriously, you know, I didn't get it.
Boss: Well the email said don't take it down because it won't come back up without being powered off.
Web Dude: Oh. Crap.
Boss: Yeah. Thanks a lot.
Web Dude: Uhh -- [Boss hangs up] -- I'm sorry? *sigh* Fucking... look. [transfers back to Chip] Chip?
Chip: Yeap.
Web Dude: Look, okwebserversnotcomingupnowbecauseyoumademetakeitdowninthe- in the wrong way.
Chip: Ahh, okay?
Web Dude: I'm gonna have to get Lazlo to power it off. C- ...can you hold on a minute?
Chip: Alright.
[Puts chip on hold, dials Lazlo's cellphone... rings, rings, rings...]
Chip: Fuckin' Lazlo, c'mon.
Lazlo: Hello Derek, you fucking idiot. [loud hiss of servers in the background] What rack is this in?
Web Dude: I'm sorry what?
Lazlo: What rack is the system in?
Web Dude: It's in Rack Five.
Lazlo: [distant, over the din] Five?
Web Dude: Yes.
Lazlo: Rack Five?
Web Dude: Rack Five.
Lazlo: ...told me that you took down the system.
Web Dude: Yes. It was an accident.
Lazlo: What'd he tell me?
Web Dude: Just reboot it.
Lazlo: You need the system rebooted?
Web Dude: Yes.
Lazlo: Which one is it?
Web Dude: It's gray, it's on the, it's like third down.
Lazlo: The one... they- they're all gray.
Web Dude: It's third down. You can see the gray on the bottom.
Lazlo: You mean which... from the top or the bottom?
Web Dude: From the top...
Lazlo: ...you tell me...
Web Dude: ...it's. Jesus-
Lazlo: You tell me. I can't...
Web Dude: It's gray.
Lazlo: I can't hear anything.
Web Dude: I know -- shut up! It's gray on the bottom!
Lazlo: From the bottom.
Web Dude: It's GRAY on the bottom. It's not in the bottom of the rack? [computer dings]
Lazlo: From the top?
Web Dude: YES!
Lazlo: Ah.
Web Dude: You just powered off the Exchange server!
Lazlo: I'll do the top one now.
Web Dude: Oh my fucking god. [computer dings]
Lazlo: 'Kay, yeah, I did both of them so you should be good.
Web Dude: No!
Lazlo: Mkay, later.
Lazlo: ...idiot...
[click, call ends]
Web Dude: *sigh*... [alt-tabs back to Halo] Wwwwaaaaaaaaaaau[proceeds to fire at teammate incessantly]uauuauuuuuuuggghhghhhhhhhh-
Msg from Halo: ATTENTION. The Server Operator has kicked you from this server.
Web Dude: Aagghh. [transfers to line 1]
Chip: Yeah I dunno, guess he didn't take it down right.
Web Dude: Chip.
Nancy: ...I swear...
Chip: Hey.
Web Dude: Well, ya managed to take the email system down as well.
Chip: R'heally? the email server?
Web Dude: Well it doesn't-
Chip: He just-
Web Dude: -have anything to do with the web server-
Chip: - shut off all our email.
Nancy: That's what he fucking did last time!
Web Dude: Look -- [reboots Halo]
Chip: Ahh, okay.
Web Dude: Lazlo at the data center rebooted it when he was trying to fix the web server that *you* asked me to take down, so...
Chip: How many times?
Web Dude: ............... how many times *what*?
Chip: How many times did he reboot it?
Web Dude: Once.
Chip: Well I think ya need to try a few more times.
Nancy chortles in the background
Web Dude: Lookit-
Chip: Web dude, we're having a quarterly sales call in two minutes, I need to get on the website, or the internet, or whatever, that's why I called you in the first place. Help a brother out.
Web Dude: What's your asset tag, Chip?
Chip: Ahh, the asset tag is 287jpc, and the number 2.
Web Dude: Is that P as in Paul?
Chip: That's P as in Paul.
Web Dude: Mkay. [Remote Desktops into Chip's computer, where an old Windows 95 screen saver is running] Where'd you get this wh...unnhhh... is this your desktop??? ...is the mouse mo-
Chip: WHHOOAAA my mouse just moved!!!!
Web Dude: Okay. Yeah why d-
Chip: Do that again! Oh my god you're moving my mouse...
Web Dude: It's remote desktop. What is your password?
Chip: It's just the letter A.
Web Dude: Just the letter A. Alright. [opens up a screen with a gajilliondy windows open]
Chip: Like Apple. ...are you looking at my desktop right now?
Web Dude: Dude, how many programs do you have running?
Chip: This is so awesome.
Web Dude: You g- you're totally overloading your box. That's probably part of the reason.
Chip: Well I use all these programs... but -- you know I gotta lotta work to do during the day.
Web Dude: Can I... can I close this [closing Explorer window]
Chip: Whoa whoa hey- [Web Dude closes email draft] -nonono!
Web Dude: ...save this? [Web Dude closes IE browser window showing "Utterpants -- sex with Vegetables"]
Chip: Wait wai-
Web Dude: Chip -
Chip: You cannot, no... I need to save this! This is all my work!
Web Dude: Look, you don't need this stuff.
Chip: I've got some research that I'm doing, okay, you-
Web Dude: [closing a game of Hearts] I mean all these things take up memor-
Chip: You can't close all of my windows! Okay!?!?
Web Dude: [closes a game of Solitaire] Closin' that.
Chip: Web dude, web dude, ya gotta slow down-
Web Dude: [comes to a window of AOL before 3.0] Dude, AOL???? Don't use AOL! It's dial-up networking.
Chip: Well how am I going to get to the internet without AOL?
Web Dude: I... It's... it's broadband.
Chip: But I got like 4000 hours for free.
Web Dude: It's -- ughh. We have a corporate OC3 -- it costs like $1000 a month, so don't use AOL. [closes AOL, only to find...] Whoa.
Chip: Can you carry over my hours?
Web Dude: What -- what is *this*??? [mousing over desktop] "Fuk u..."
Chip: It's... my desktop?
Web Dude: What... there're icons, they spell "Fuk u!" and there's a picture of a penis.
Chip: Ahh, Patricia did that when I took over her computer. She wasn't very happy.
Web Dude: Holy crap. ...how long's it been like that?
Chip: Eight or nine years.
Web Dude: Oh my god.
Chip: You know I just got so used to it. I didn't want to change it.
Web Dude: That's fuckin' awesome... hold on. Alright, I'm taking a picture of this, hold on just a sec.
Chip: Ok, just so you know I got a meeting in like five minutes, so whatever we gotta do to get my PC back.
Web Dude: This is going right onto BoingBoing.
Chip: Uh what's BoingBoing?
Web Dude: Here's the thing. This? Is a problem. You can't have people looking at this, okay? Arrange your icons -- [sorts desktop by Name] -- by Name or something...
Chip: Whoa nonono! I can't find anything!
Web Dude: Whaddaya mean? It's alphabetical!
Chip: Aww man. I -- ugh -- I had everything exactly where I knew where it was. I knew th- that th- that our website? Our website? Wasattheverytipofthe penis!
Chip: And now I don't know where anything is! How am I go- no, it's not that one, it's not that one anymore!
Web Dude: Well... ulch...
Chip: MySalesForce.com was on the right testicle -- I'm not gonna be able to find anything. I gotta meeting in two minutes and I need the icons back the way they were.
Web Dude: Well I can't go back. There's no way to go back. You can't arrange 'em by penis.
Chip: Omigod... I tell ya, every time I've called you tech support people, every fucking time, you guys do something entirely different you know? You don't fix the problem that I call about! You know all I wanted was to get the website back! That's all that, that's all I needed! Can you restore it -- you said you took a picture of it. Restore it.
Web Dude: Well.... yeah, I guess. I mean I can just make that the background for your desktop.
Chip: I don't care what you have to do, whatever you gotta do to get this thing back.
Web Dude: ...honestly that probably won't, won't solve the problem completely but...
Chip: Well if the icons're in the same spot I'll be able to get to them. [Web dude restores penis background; meshing in with the grid of arranged icons, it creates a jumbled mess] ...alright, so this is worse. [Web Dude Selects All icons, drags them completely off the screen, leaving the penis background on display crystal clear] Oh wait-
Web Dude: I mean this is just a picture on the desktop...
Chip: That's great, this is perfect, this is perfect. Hey I gotta get into my meeting, so, you know, I'm, I yeah, this is great.
Web Dude: You good with it? [dragging selection box around, not able to select any actual icons since it's only a background] Because...
Chip: No no, this is, this is fine, I can find everything! I can find everything, this is fine.
Web Dude: Mkay.
Chip: Ok so, I gotta go to the meeting, ahhhhh you know, thanks a lot web dude, I'm outta here!
Web Dude: Mkay.
Chip: Alright, bye.
Web Dude: Jesus. What a fuckin' day. [alt-tabs to Halo, plasma grenades a dude and melee's him out, with the grenade exploding a second after.] Hehehehe...

original post http://vasnake.blogspot.com/2016/01/funny-videos.html


God and Codd

Забавный слайд из курса
Data Manipulation at Scale: Systems and Algorithms
University of Washington

– God made the integers; all else is the work of man.
– Codd made relations; all else is the work of man.

Это про реляционные БД, если что.

original post http://vasnake.blogspot.com/2016/01/god-and-codd.html


Make it work, AngularJS

Всем известна фраза: make it work, make it right, make it fast
но мало кто подозревает, что большинство проектов, дошедших до стадии «work», никогда не достигают стадии «right».
Таковы люди, увы. Нам слишком быстро хочется переключится на что-то новенькое и не хочется заниматься рутиной.

Так вот, кто бы мог подумать, AngularJS это инструмент для «быстро сляпать на коленке». Make it work, показать, получить одобрение/деньги и заняться переделкой в make it right.


original post http://vasnake.blogspot.com/2016/01/make-it-work-angularjs.html


Python / JavaScript modules (import)

Как всем известно, в ES6 появилась поддержка модульности. Export, import – вот это всё.
Интересно сравнить эти нововведения с тем, что есть в Python

Here's a comparison of Python and Javascript (ES6) imports. There are a few differences between the two:
Javascript imports are static; Python's are dynamic.
Javascript items must be explicitly exported. In Python, all items are available for import.
Javascript has a concept of a default export. Python does not.

original post http://vasnake.blogspot.com/2016/01/python-javascript-modules-import.html

Архив блога


linux (241) python (191) citation (186) web-develop (170) gov.ru (159) video (124) бытовуха (114) sysadm (100) GIS (97) Zope(Plone) (88) бурчалки (84) Book (82) programming (82) грабли (77) development (73) Fun (72) windsurfing (72) Microsoft (64) hiload (62) opensource (58) internet provider (57) security (57) опыт (55) movie (52) Wisdom (51) ML (47) language (45) hardware (44) money (42) JS (41) driving (41) curse (40) bigdata (39) DBMS (38) ArcGIS (34) history (31) PDA (30) howto (30) holyday (29) Google (27) Oracle (27) tourism (27) virtbox (27) health (26) vacation (24) AI (23) Autodesk (23) SQL (23) Java (22) humor (22) knowledge (22) translate (20) CSS (19) cheatsheet (19) hack (19) Apache (16) Manager (15) web-browser (15) Никонов (15) functional programming (14) happiness (14) music (14) todo (14) PHP (13) course (13) scala (13) weapon (13) HTTP. Apache (12) SSH (12) frameworks (12) hero (12) im (12) settings (12) HTML (11) SciTE (11) USA (11) crypto (11) game (11) map (11) HTTPD (9) ODF (9) купи/продай (9) Photo (8) benchmark (8) documentation (8) 3D (7) CS (7) DNS (7) NoSQL (7) cloud (7) django (7) gun (7) matroska (7) telephony (7) Microsoft Office (6) VCS (6) bluetooth (6) pidgin (6) proxy (6) Donald Knuth (5) ETL (5) NVIDIA (5) REST (5) bash (5) flash (5) keyboard (5) price (5) samba (5) CGI (4) LISP (4) RoR (4) cache (4) display (4) holywar (4) nginx (4) pistol (4) spark (4) xml (4) Лебедев (4) IDE (3) IE8 (3) J2EE (3) NTFS (3) RDP (3) holiday (3) mount (3) Гоблин (3) кухня (3) урюк (3) AMQP (2) ERP (2) IE7 (2) NAS (2) Naudoc (2) PDF (2) address (2) air (2) british (2) coffee (2) font (2) ftp (2) messaging (2) notify (2) sharepoint (2) ssl/tls (2) stardict (2) tests (2) tunnel (2) udev (2) APT (1) CRUD (1) Canyonlands (1) Cyprus (1) DVDShrink (1) Jabber (1) K9Copy (1) Matlab (1) Palanga (1) Portugal (1) VBA (1) WD My Book (1) autoit (1) bike (1) cannabis (1) chat (1) concurrent (1) dbf (1) ext4 (1) idioten (1) join (1) krusader (1) license (1) mindmap (1) navitel (1) pneumatic weapon (1) quiz (1) regexp (1) robot (1) science (1) serialization (1) spatial (1) tie (1) vim (1) Науру (1) крысы (1) налоги (1) пианино (1)