Потрясающий
факт: добавлением пары строчек в алгоритм,
мы сокращаем время выполнения с 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 posthttp://vasnake.blogspot.com/2016/01/wqupc-reduces-time-from-30-years-to-6.html
переделка
Uptown Funk, на тему живого патчевания ядра
Linux.
Наслаждайтесь
пельмешком.
Uptime Funk Lyrics:
This bit
Uncontrolled
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
Halt
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.
[pause]
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.
Web Dude: THANKS A LOT.
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]
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!
[pause]
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 posthttp://vasnake.blogspot.com/2016/01/funny-videos.html
но мало кто
подозревает, что большинство проектов,
дошедших до стадии «work», никогда не
достигают стадии «right».
Таковы люди,
увы. Нам слишком быстро хочется
переключится на что-то новенькое и не
хочется заниматься рутиной.
Так вот, кто
бы мог подумать, AngularJS это инструмент
для «быстро сляпать на коленке». Make it
work, показать, получить одобрение/деньги
и заняться переделкой в make it right.
