| --- Log opened Thu Dec 01 00:00:31 2016 |
| 00:03 | | Emmy [Emmy@Nightstar-9p7hb1.direct-adsl.nl] has quit [Ping timeout: 121 seconds] |
| 00:10 | | catalyst [catalyst@Nightstar-bt5k4h.81.in-addr.arpa] has quit [[NS] Quit: Leaving] |
| 00:39 | | Reiv [NSwebIRC@Nightstar-ih0uis.global-gateway.net.nz] has joined #code |
| 00:39 | | mode/#code [+o Reiv] by ChanServ |
| 00:46 | <@Reiv> | PinkFreud: Not like we don't have a channel literally dedicated to the concept :p |
| 00:46 | <@PinkFreud> | bah! |
| 00:47 | <@PinkFreud> | so, the table layout is a little weird. I'm working with tables DEVICE, DEV_IP, and VM. DEVICE contains a mix of physical and virtual devices. |
| 00:48 | <@Reiv> | Are they flagged either way? |
| 00:48 | <@PinkFreud> | there's a common field across all three, dev_id, that can be used to link rows in them |
| 00:48 | <@PinkFreud> | wait, it gets better. |
| 00:49 | <@PinkFreud> | one of the fields that VM returns is esxi_id, which itself can be corellated with dev_id back in DEVICE. |
| 00:51 | <@PinkFreud> | so, what I want to do is - select fields from DEVICE, join them (I'm currently using nat join) with VM and DEV_IP, and then pull the corresponding esxi_id from VM back out of the DEVICE table to pull just the hostname, and that same id from the DEV_IP table to pull the 'address' field for it. |
| 00:54 | <@PinkFreud> | my terrible query: https://owncloud.mirkwood.net/owncloud/index.php/s/mDzJ1en7wMWXBJo |
| 00:56 | <@Reiv> | okay, I think I follow |
| 00:57 | <@Reiv> | I think we're hitting wood-for-the-trees though |
| 00:57 | <@PinkFreud> | that's likely. |
| 00:59 | <@celticminstrel> | I'm noticing that, at any given time, the priority queue has at least 10-20 elements with the same priority, for each priority present. |
| 01:00 | <@celticminstrel> | (For my A*) |
| 01:00 | <@Reiv> | For tables, we have DEVICE (dev_id, hostname, other shit); VM(dev_id, esxi_id), dev_ip(dev_id, address) |
| 01:00 | <@Reiv> | Yes? |
| 01:01 | <@Reiv> | (dang, shouda capitalised dev_ip, whoops) |
| 01:02 | <@Reiv> | PinkFreud: And then what you want is, for a given DEVICE row, to also pull back what from each table? |
| 01:02 | <@Reiv> | This sounds like it should be a fairly simple set of joins, unless there's a data quirk I've missed here |
| 01:02 | <@PinkFreud> | Reiv: yep. sorry, saying goodnight to Pinky v2. |
| 01:03 | <@Reiv> | np, take your time |
| 01:03 | <@PinkFreud> | I'm back. :) |
| 01:03 | <@PinkFreud> | the wife is taking him off to bed... where I'm sure he'll scream his head off for a few mins before falling asleep, as usual. :P |
| 01:03 | | * PinkFreud sighs - toddlers. :) |
| 01:03 | <@Reiv> | Yup :P |
| 01:03 | <@Reiv> | Give him a buzzy bee, that always helps! |
| 01:03 | <@PinkFreud> | lol |
| 01:04 | <@PinkFreud> | Reiv: I think the only real quirk is that I'm reading the same table for another piece of information. |
| 01:06 | | * Reiv raises an eyebrow. |
| 01:06 | <@PinkFreud> | so, * from DEVICE, nat join'ed with VM and DEV_IP, then we take esxi_id from VM and read a completely separate entry from DEVICE for *only* the hostname and DEV_IP, for *only* the address. |
| 01:06 | <@Reiv> | So DEVICE should have two rows per record that you're trying to line up with each other to give one row in the output? |
| 01:07 | <@PinkFreud> | my initial read from DEVICE is only for DEV_IP.type = 1, which indicates a VM. |
| 01:07 | <@Reiv> | OK |
| 01:07 | <@PinkFreud> | but the second read from DEVICE will be for the associated physical host. |
| 01:07 | <@Reiv> | Right |
| 01:07 | <@PinkFreud> | (and DEV_IP) |
| 01:07 | <@Reiv> | What you need is a self-join, I think |
| 01:07 | <@PinkFreud> | hmm. |
| 01:07 | | Derakon[AFK] is now known as Derakon |
| 01:07 | <@Reiv> | Know them well, or need a 101? |
| 01:08 | <@PinkFreud> | I'd also like to pull off a column name change as well, for those last two. |
| 01:08 | <@Reiv> | No problem, that's merely aliasing |
| 01:08 | <@PinkFreud> | let's shoot for the 101 |
| 01:08 | <@PinkFreud> | ok |
| 01:08 | <@Reiv> | Okay, so I am /assuming/ MySQL can handle aliases |
| 01:08 | | * PinkFreud nods |
| 01:08 | <@PinkFreud> | it can. I'm using some here |
| 01:08 | <@PinkFreud> | select * from DEVICE AS dev |
| 01:08 | <@Reiv> | good good |
| 01:09 | <@Reiv> | select * from DEVICE as D1 inner join DEVICE D2 on D1.key = D2.otherkey |
| 01:09 | <@PinkFreud> | y'know, I like D1 and D2 here. I'll go with that. |
| 01:09 | <@Reiv> | so, hm |
| 01:10 | <@PinkFreud> | hmmm. one problem here is that I won't get esxi_dev until I join VM |
| 01:10 | <@PinkFreud> | so: |
| 01:10 | <@Reiv> | that's OK, just join all your 'first' tables together |
| 01:10 | <@Reiv> | *then* do your inner join |
| 01:10 | <@Reiv> | And then sort out the restrictions in the where clause. (Could also be on the joins, but let's not complicate life~) |
| 01:10 | <@PinkFreud> | select * from DEVICE as D1 NATURAL JOIN DEV_IP NATURAL JOIN VM INNER JOIN DEVICE D2 on D1.esxi_id = D2.dev_id |
| 01:11 | <@PinkFreud> | that look about right? |
| 01:11 | <@Reiv> | Well, I'm a huge advocate for avoiding natural join, but I think so |
| 01:12 | <@Reiv> | And then run your DEV_IP.type = 1 etc in your where clause |
| 01:12 | <@PinkFreud> | natural join helped avoid one pitfall - having the dev_id field show up multiple times |
| 01:12 | <@Reiv> | While true, this is when I start asking for, eg, D1.* |
| 01:12 | <@Reiv> | plus selected D2 columns etc. |
| 01:14 | <@PinkFreud> | https://owncloud.mirkwood.net/owncloud/index.php/s/mDzJ1en7wMWXBJo |
| 01:14 | <@PinkFreud> | how does that look? |
| 01:15 | <@Reiv> | no where clause? |
| 01:15 | <@PinkFreud> | ah, crud |
| 01:15 | <@PinkFreud> | refresh |
| 01:16 | <@Reiv> | Without being able to run it myself, that looks pretty good, yes |
| 01:16 | <@PinkFreud> | damnit |
| 01:16 | <@PinkFreud> | hmmm. is it possible to do (SELECT * FROM DEVICE NATURAL JOIN DEV_IP NATURAL JOIN VM) AS D1 ... ? |
| 01:16 | <@Reiv> | Column collisions? |
| 01:16 | <@PinkFreud> | er, wrong placement of parens |
| 01:17 | <@PinkFreud> | hmmm. is it possible to do SELECT * FROM (DEVICE NATURAL JOIN DEV_IP NATURAL JOIN VM) AS D1 ... ? |
| 01:17 | <@PinkFreud> | there. |
| 01:17 | <@Reiv> | SELECT * FROM (SELECT * FROM tab1) sub1 INNER JOIN table2 on sub1.etc = table2.etc |
| 01:17 | <@Reiv> | Is a classic subquery, yes |
| 01:18 | <@Reiv> | I remain very leery of your use of stars and natural joins, here, however |
| 01:18 | <@PinkFreud> | yeah, no one said I had the best syntax. |
| 01:18 | <@PinkFreud> | :P |
| 01:18 | <@Reiv> | It's best to restrict down to whatever's sensible, even if you leave entire tables starred, do you need *all* of them starred? |
| 01:18 | <@Reiv> | It'll help cut out duplicate rows, ambiguous columns, etc |
| 01:18 | <@PinkFreud> | it's a little cleaner, syntax-wise, I think |
| 01:19 | <@PinkFreud> | meh, I'll leave it as you see on owncloud |
| 01:19 | <@PinkFreud> | let's try this and see what blows up |
| 01:19 | <@Reiv> | Nah, it's OK, and good luck :) |
| 01:19 | <@Reiv> | Is this porformance limited, btw? |
| 01:19 | <@Reiv> | er, only spelled right |
| 01:20 | <@PinkFreud> | ERROR 1054 (42S22): Unknown column 'dev.status' in 'where clause' |
| 01:20 | <@PinkFreud> | whoops. |
| 01:20 | <@Reiv> | haha yeah, you'll have to keep working on that sort of thing, I can never spot that stuff without the actual tables in front of me ;) |
| 01:20 | <@PinkFreud> | ok, got all the old 'dev' references changed to D1 |
| 01:20 | <@Reiv> | A minor thing that helps to remember is that returning fewer columns will speed up a query, because queries are dumb and will load entire rows unless you tell them not to |
| 01:21 | <@Reiv> | ... if there's actual data on those lines, especially files, this can end up clogging its own bandwidth. >_> |
| 01:21 | <@PinkFreud> | ERROR 1054 (42S22): Unknown column 'DEV_IP.esxi_id' in 'on clause' |
| 01:21 | <@PinkFreud> | gorrammit |
| 01:21 | <@PinkFreud> | mysql> describe VM; |
| 01:21 | <@PinkFreud> | ... |
| 01:21 | <@PinkFreud> | | esxi_id | int(11) | YES | MUL | NULL | | |
| 01:21 | <@PinkFreud> | brilliant one there, PinkFreud |
| 01:21 | | * Reiv laughs |
| 01:23 | <@PinkFreud> | ok, getting there. |
| 01:23 | <@PinkFreud> | that worked, but now I have duplicate fields: |
| 01:23 | <@PinkFreud> | *************************** 842. row *************************** |
| 01:23 | <@PinkFreud> | dev_id: 4043 |
| 01:23 | <@PinkFreud> | hostname: ctxsv-gl33be |
| 01:23 | <@PinkFreud> | ... |
| 01:23 | <@PinkFreud> | esxi_id: 1461 |
| 01:23 | <@PinkFreud> | dev_id: 1461 |
| 01:23 | <@PinkFreud> | hostname: ctxsv-glesxi33 |
| 01:23 | <@PinkFreud> | ... |
| 01:24 | | * Reiv raises an eyebrow. |
| 01:24 | <@Reiv> | Not /quite/ duplicate there, are they |
| 01:24 | <@Reiv> | oh, duplicate *fields* |
| 01:24 | <@Reiv> | Yes, this is why I was cautioning you about playing with your star too much. :P |
| 01:24 | <@PinkFreud> | field names are duplicate, since I'm reaching back into the same tables to pull out different records. |
| 01:24 | <@Reiv> | correct |
| 01:25 | <@Reiv> | What records do you actually need? |
| 01:25 | <@PinkFreud> | hey! what I do with my star is *private*. |
| 01:25 | <@PinkFreud> | sheesh, some people. |
| 01:25 | <@PinkFreud> | :P |
| 01:25 | <@Reiv> | not unless you set it to void() as well, bud |
| 01:25 | <@PinkFreud> | lol |
| 01:25 | <@Reiv> | The entirety of the DEVICE table, plus a couple extra rows yes? |
| 01:25 | <@PinkFreud> | ok, so I just need hostname from D2 |
| 01:26 | <@Reiv> | SELECT D2.Hostname, etc, FROM ... |
| 01:26 | <@PinkFreud> | and I'll need to do another inner join to pull address from VM |
| 01:26 | <@PinkFreud> | er |
| 01:26 | <@PinkFreud> | from DEV_IP |
| 01:26 | <@Reiv> | why? |
| 01:26 | <@PinkFreud> | so I can get that esxi host's IP |
| 01:27 | <@Reiv> | Ah, which is to say you currently have a D1 DEV_IP, but now you need a D2 DEV_IP row as well? |
| 01:27 | <@PinkFreud> | yep |
| 01:27 | <@Reiv> | right, yeah, that's good |
| 01:27 | <@Reiv> | And yeah, at that point you *definitely* need to start restricting your output to avoid chaos |
| 01:27 | <@PinkFreud> | let's see if I can pull this off |
| 01:28 | <@Reiv> | PROTIP: Call them DIP1 and DIP2 |
| 01:28 | <@Reiv> | Or equivalent, just keep the numbering consistent with your respective DEVICE tables. |
| 01:28 | <@PinkFreud> | let's fix the field selection first. |
| 01:28 | <@PinkFreud> | INNER JOIN DEVICE AS D2 ON VM.esxi_id = D2.dev_id |
| 01:28 | <@PinkFreud> | how should I rewrite this line? |
| 01:30 | | * Reiv raises an eyebrow |
| 01:30 | <@Reiv> | Do you need to? |
| 01:31 | <@Reiv> | What you want to do is start getting explicit in calling columns, as far as I understand |
| 01:32 | <@PinkFreud> | hm |
| 01:33 | <@PinkFreud> | how do I work explicit columns for D2 in there? |
| 01:33 | <@PinkFreud> | I *want* all of the columns from D1... I just only need one column from D2. |
| 01:34 | <@Reiv> | SELECT D1.*, D2.column_name, VM.othercolumn FROM |
| 01:35 | <@Reiv> | You *may* need to put D1.* as the last argument in the SELECT statement |
| 01:35 | <@Reiv> | If it can't do single-table-stars at all, then it's pants-on-head stupid |
| 01:35 | | McMartin [mcmartin@Nightstar-rpcdbf.sntcca.sbcglobal.net] has quit [[NS] Quit: leaving] |
| 01:37 | <@PinkFreud> | ah, ok |
| 01:37 | <@PinkFreud> | i think it can |
| 01:38 | <@PinkFreud> | but that tosses the nat joins |
| 01:38 | <@PinkFreud> | ah well |
| 01:40 | <@PinkFreud> | actully, maybe not |
| 01:41 | <@PinkFreud> | ooooooh |
| 01:41 | <@PinkFreud> | me likey |
| 01:43 | <@Reiv> | nope, nat joins don't give a shit about the select |
| 01:43 | <@Reiv> | selects happen *after* natural join logic |
| 01:44 | <@Reiv> | That's actually sometimes really importaint to realise - the order of operations involves doing joins & wheres, then group, then order, then select |
| 01:44 | <@Reiv> | So you can't have select make any damn difference to your query beyond breaking it :p |
| 01:45 | <@PinkFreud> | lol |
| 01:46 | <@Reiv> | You want something in your SELECT statement to change query logic? Subquery it, it's the only way, etc |
| 01:47 | | * PinkFreud nods |
| 01:54 | <@PinkFreud> | hah, that did it! |
| 01:54 | <@PinkFreud> | Reiv: thank'ee! |
| 02:15 | <@Reiv> | PinkFreud: Welcome! |
| 02:15 | <@Reiv> | I literally write SQL for a living, so if you ever need a hand, feel free to prod me :) |
| 02:16 | <@PinkFreud> | will do! |
| 02:19 | | himi [sjjf@Nightstar-v37cpe.internode.on.net] has quit [Ping timeout: 121 seconds] |
| 02:22 | | himi [sjjf@Nightstar-v37cpe.internode.on.net] has joined #code |
| 02:22 | | mode/#code [+o himi] by ChanServ |
| 02:26 | <@Reiv> | PinkFreud: Certainly a little cleaner than the abomination mk1, eh? :p |
| 02:26 | <@Reiv> | ... aw, the file isn't there any more |
| 02:27 | <@Reiv> | I was going to see how it looked in comparison~ |
| 02:28 | <@PinkFreud> | ah |
| 02:28 | <@PinkFreud> | well, ran into another wall |
| 02:28 | <@PinkFreud> | so you'll get a chance to see it |
| 02:30 | <@PinkFreud> | https://owncloud.mirkwood.net/owncloud/index.php/s/BwdKAta0J8XpNGx |
| 02:31 | <@PinkFreud> | the problem I'm running into is in the WHERE clause |
| 02:31 | <@PinkFreud> | WHERE D1.status = 1 AND |
| 02:31 | <@PinkFreud> | DIP1.type = 1 AND |
| 02:31 | <@PinkFreud> | somehow, it's ignoring DIP1.type = 1 |
| 02:33 | <@PinkFreud> | the problem is, our esxi hosts have multiple IPs listed - management IP, BMC IP, ... |
| 02:33 | <@PinkFreud> | so each time it finds a different IP for the host, it lists the same VM again |
| 02:33 | <@PinkFreud> | that's the purpose of limiting it to type = 1, which tells it to only return an IP of a specific type. |
| 02:34 | <@PinkFreud> | It's accepting the syntax, but it's not actually honoring it. |
| 02:39 | | * PinkFreud pokes-a-reiv! |
| 02:43 | <~Vornicus> | step 1, add DIP1.type to the select list to make sure it's actually not doing it |
| 02:43 | | * Reiv raises an eyebrow. Yes, do that. |
| 02:44 | <@PinkFreud> | I know it's not, as I can spot IPs with type 3 showing up |
| 02:44 | <@PinkFreud> | (they're on a specific vlan) |
| 02:44 | <@PinkFreud> | (and I've double-checked the records) |
| 02:45 | <~Vornicus> | still. |
| 02:45 | <@PinkFreud> | ok, done. ... and type 1? wut? |
| 02:46 | <~Vornicus> | Things I saw coming: That. |
| 02:46 | <@PinkFreud> | ESXi_IP: 10.10.24.61 |
| 02:46 | <@PinkFreud> | type: 1 |
| 02:46 | <@PinkFreud> | that is wrong |
| 02:46 | <@PinkFreud> | | dev_id | address | type | |
| 02:46 | <@PinkFreud> | | 1432 | 10.10.24.61 | 3 | |
| 02:46 | <@PinkFreud> | | 1432 | 10.10.27.40 | 1 | |
| 02:47 | <@PinkFreud> | so, it's listed in the table as type 3 |
| 02:47 | <@PinkFreud> | but it matches as type 1? |
| 02:47 | <@PinkFreud> | that makes no sense. |
| 02:48 | <~Vornicus> | oh, that'd do it. |
| 02:48 | <~Vornicus> | no it wouldn't, but |
| 02:48 | <~Vornicus> | WHy are these things both with the same dev_id |
| 02:49 | <@PinkFreud> | same physical device |
| 02:49 | <@PinkFreud> | it has multiple addresses (mgmt ip, bmc ip, ...) |
| 02:49 | <@PinkFreud> | in this case, I just want the management ip, type 1 |
| 02:51 | <~Vornicus> | ah, I see |
| 02:52 | <~Vornicus> | does this table have a primary key |
| 02:52 | <@PinkFreud> | it does not. |
| 02:53 | <@Reiv> | oh dear |
| 02:54 | <@PinkFreud> | actually it does |
| 02:54 | <@PinkFreud> | | Field | Type | Null | Key | Default | Extra | |
| 02:54 | <@PinkFreud> | | dev_id | int(11) | NO | PRI | NULL | auto_increment | |
| 02:54 | <@PinkFreud> | | address | varchar(15) | NO | PRI | | | |
| 02:54 | <@PinkFreud> | | type | int(1) | YES | | NULL | | |
| 02:55 | <~Vornicus> | how are we getting |
| 02:55 | <~Vornicus> | what the hell |
| 02:55 | <~Vornicus> | oh, it's composite, ok |
| 03:04 | <@PinkFreud> | hmmm, any idea? |
| 03:05 | <@celticminstrel> | Ooh, my A* has finally just about reached its destination. |
| 03:06 | <@celticminstrel> | It was like one tile away. |
| 03:06 | <@celticminstrel> | Oh, wait, now a new A* has started. |
| 03:06 | <@celticminstrel> | So I have proof that it terminates eventually. |
| 03:06 | <@celticminstrel> | At least, it did at least once. |
| 03:06 | <@celticminstrel> | Pretty sure it's still much too slow though. |
| 03:07 | <@celticminstrel> | I suppose I could find a way to do it async... |
| 03:08 | <@celticminstrel> | For the one I was stepping through, the discovered queue got to a length of ~1500. |
| 03:08 | <~Vornicus> | um |
| 03:08 | <&Derakon> | How big is your map? |
| 03:08 | <@celticminstrel> | I imagine part of the problem is also the length of the paths... |
| 03:08 | <&Derakon> | And what's the heuristic used to guide the A*? |
| 03:08 | <@celticminstrel> | Taxi-cab distance. |
| 03:08 | <&Derakon> | Not familiar with that term. |
| 03:09 | <&Derakon> | Do you mean sum(X distance + Y distance)? |
| 03:09 | <@celticminstrel> | |dx| + |dy| |
| 03:09 | <@celticminstrel> | So yes |
| 03:09 | <&Derakon> | Hm. And map size? |
| 03:10 | <@celticminstrel> | The total area reachable by the pathfinder here is currently 320x400. |
| 03:10 | <@celticminstrel> | The start and dest are problem no more than ~80-100 tiles apart. |
| 03:11 | <@celticminstrel> | But there's some very expensive barriers to get through between start and dest (usually). |
| 03:11 | <@celticminstrel> | If considering the expensive barriers unreachable, no more than 80x80 tiles would be reachable. |
| 03:12 | <&Derakon> | A queue size of 1500 still seems excessive. |
| 03:12 | <@celticminstrel> | But the point of this is to create connections so that's no longer the case. |
| 03:12 | <@celticminstrel> | It does seem quite large, yes. |
| 03:13 | <@celticminstrel> | There might be a lot of visited tiles queued only to be skipped as soon as they're popped... |
| 03:13 | <~Vornicus> | 320x400 should be like a 1 second job for A* |
| 03:13 | <@celticminstrel> | Maybe I could add a visited check before pusing. |
| 03:13 | <@celticminstrel> | ^pushing |
| 03:13 | <&Derakon> | Yes. |
| 03:13 | <&Derakon> | Don't push things you know you've been to. |
| 03:13 | <@celticminstrel> | Oh, wait, I already am. |
| 03:14 | <@Reiv> | right, sorry |
| 03:14 | <@Reiv> | um |
| 03:14 | <@celticminstrel> | Does that make the visited check after popping redundant? I suppose I could see how it might not be. |
| 03:14 | <@Reiv> | PinkFreud: Are you making sure you join on the composite key if that's actually the key? |
| 03:14 | <&Derakon> | If you're checking visited at time of push, then there's no need to check at time of pop. |
| 03:14 | <&Derakon> | A cell should never be put into the queue twice. |
| 03:14 | <@Reiv> | Else your restrictions may be wiggled around by, uh |
| 03:15 | | * Reiv muses. |
| 03:15 | <@celticminstrel> | ...wait. |
| 03:15 | <@PinkFreud> | Reiv: hm |
| 03:15 | <@celticminstrel> | Oh, there it is. |
| 03:15 | | * celticminstrel lost sight of the place where cells are marked visited. |
| 03:16 | <@celticminstrel> | When you say 320x400 should be 1 second does that account for absurdly high-cost tiles and long twisty paths? |
| 03:16 | <@Reiv> | Yeah, if you don't join on the whole key, you'll get A joining to B, and because B isn't likewise restricted you risk chaos all round. |
| 03:18 | <@PinkFreud> | Reiv: what would you recommend changing on https://owncloud.mirkwood.net/owncloud/index.php/s/BwdKAta0J8XpNGx ? |
| 03:18 | | McMartin [mcmartin@Nightstar-rpcdbf.sntcca.sbcglobal.net] has joined #code |
| 03:18 | | mode/#code [+ao McMartin McMartin] by ChanServ |
| 03:19 | <@celticminstrel> | I could try 2D arrays instead of sets for tracking visited and scores... string conversion is required to use the cell as a key. (But a 2D array requires multiplication, so I dunno.) |
| 03:20 | <@Reiv> | For the sake of convinience, could you make that D to VM join an INNER JOIN so I can see explicitly what relevant columns those two tables share? |
| 03:20 | <&Derakon> | Set lookup is O(1), so I wouldn't bother. |
| 03:20 | <@Reiv> | I get it's technically not that needed, but natural joins don't tell me shit :p |
| 03:20 | <&Derakon> | I also would not stress about multiplication. |
| 03:20 | <@Reiv> | Exponents, that's where the fear lies |
| 03:20 | <&Derakon> | Unless you are running on a SOC that uses like 1W of power. |
| 03:20 | <@PinkFreud> | the one remaining nat join? |
| 03:20 | <@Reiv> | yeah, plz |
| 03:21 | <@celticminstrel> | Well, it's mainly the string conversion I'm wondering about, though that's probably pretty fast too given the coordinate range. |
| 03:21 | <@celticminstrel> | [Nov 30@10:16:25pm] celticminstrel: When you say 320x400 should be 1 second does that account for absurdly high-cost tiles and long twisty paths? |
| 03:21 | <&Derakon> | I don't have a good feel for that. |
| 03:22 | <@PinkFreud> | refresh |
| 03:22 | <@celticminstrel> | Whoa, it finally finished all the A* connections. |
| 03:22 | <~Vornicus> | Tile cost isn't a problem. Long twisty paths "are" but you're looking at the pessimal case, which is still "look at every single cell once" and that's only ... uh... 100k cells. |
| 03:23 | <~Vornicus> | I've done much more complex work in less time. |
| 03:24 | <@Reiv> | so, PF |
| 03:24 | <@Reiv> | The thing I want to check is |
| 03:25 | <@Reiv> | Does the line INNER JOIN DEVICE AS D2 ON VM.esxi_id = D2.dev_id return unique rows? |
| 03:26 | <@Reiv> | I had assumed when I constructed this thing that dev_id was a primary key, if it isn't then I am suddenly less confident it'll join right |
| 03:26 | <@PinkFreud> | it has to - each dev_id only has one entry in the DEVICE (D2) table. |
| 03:26 | <@celticminstrel> | The Wikipedia pseudocode of the algorithm defins fScore as "map with default value of Infinity", but doesn't ever seem to use that default. |
| 03:27 | <&Derakon> | Wikipedia pseudocore is incredibly variable in quality. |
| 03:27 | <&Derakon> | And it often replaces high-quality examples with shitty ones. |
| 03:27 | <@PinkFreud> | some other tables, like DEV_IP, can contain multiple rows for the same dev_id |
| 03:27 | <@celticminstrel> | Probably. |
| 03:27 | <@celticminstrel> | This one looks fairly good, though for some reason it uses a set instead of a priority queue for "discovered nodes". |
| 03:28 | <@celticminstrel> | And then says "current := the node in openSet having the lowest fScore[] value" |
| 03:28 | <@celticminstrel> | As if that were something trivial to calculate. >_> |
| 03:28 | <&Derakon> | Heh. |
| 03:30 | <@Reiv> | So VM also has only one row per dev_id, correct? |
| 03:31 | <@PinkFreud> | yep. in this case, VM will only contain information about devices which are VMs. |
| 03:31 | | macdjord|wurk is now known as macdjord |
| 03:31 | | * celticminstrel finds an interactive demo, wonders what the "octile" heuristic is. |
| 03:32 | <@celticminstrel> | https://qiao.github.io/PathFinding.js/visual/ |
| 03:32 | <@PinkFreud> | the problem appears to be with devices that are ESXi hosts, which have multiple IPs. |
| 03:32 | <@PinkFreud> | these VMs only have a single IP. |
| 03:33 | | * celticminstrel also wonders what "best-first search" is; thought that was just a description of A* |
| 03:36 | <~Vornicus> | yes |
| 03:36 | <@celticminstrel> | But that demo lists it separately. |
| 03:37 | <@celticminstrel> | And it performs better than their A* for the walls I drew. |
| 03:37 | <@Reiv> | Can you join those two together? |
| 03:38 | <@PinkFreud> | Reiv: how so? |
| 03:40 | <@Reiv> | um |
| 03:40 | <~Vornicus> | Octile heuristic: max(dx, dy) + (sqrt(2)-1) * min(dx,dy) -- ...probably don't want it, because you can't actually *move* diagonally |
| 03:40 | <@Reiv> | You currently have D1 linked to VM, D1 linked to DEV_IP |
| 03:41 | <@Reiv> | but not VM linked to DEV_IP |
| 03:41 | <@Reiv> | ... no, never mind, that won't fix it will it |
| 03:41 | <~Vornicus> | the more accurate your cost estimation function to the actual cost, the faster A* will find the path. |
| 03:41 | <@Reiv> | baaaah it is /too hot/ to think about this shit |
| 03:42 | <@PinkFreud> | and getting to be too late here. |
| 03:42 | <@Reiv> | I cannot get the heat pump to bloody well point its fans at me ;_; |
| 03:42 | <@Reiv> | I change the settings, they wave down, then up, then sit in 'up' position |
| 03:42 | <@Reiv> | Not helpful when I am *directly below the heat pump* now is it |
| 03:43 | <@PinkFreud> | I think the core issue is that DIP1.type is being seen as 1, even on rows where it's 3 |
| 03:43 | <@Reiv> | No matter what settings I change them to, they do the same: wave all the way down, then up, then stay up. |
| 03:43 | <@Reiv> | Not helpful! |
| 03:43 | <@PinkFreud> | d'oh |
| 03:43 | <@PinkFreud> | how warm is it? |
| 03:43 | <@Reiv> | The room as a whole? OK, little bit warm. |
| 03:43 | <@Reiv> | My corner? Getting the full glory of circulating air as it all flows back to the heat pump to be cooled off again. |
| 03:44 | <@Reiv> | Heater is on my left, blowing lovely cold air. I'm getting a gentle, warm, moist airflow from my right .>_> |
| 03:44 | <@PinkFreud> | 20:38 @<Reiv> And then sort out the restrictions in the where clause. (Could |
| 03:44 | <@PinkFreud> | also be on the joins, but let's not complicate life~) |
| 03:44 | <@PinkFreud> | hmmm |
| 03:44 | <@Reiv> | anyway, yeah |
| 03:44 | <@celticminstrel> | Vornicus: Couldn't that be part of the problem then? My cost heuristic is the taxi-cab distance, but the actual cost is definitely quite a bit more due to twisty passages and high-cost tiles. |
| 03:44 | <@PinkFreud> | would it be better to move that DIP1.type statement? |
| 03:44 | <@Reiv> | You could try restricting on that join clause just to see, but I dunno |
| 03:44 | <@PinkFreud> | Reiv: ah. :) what's the weather like out there? |
| 03:44 | <@Reiv> | There's a bug that should be obvious if I knew the columns better |
| 03:45 | <@Reiv> | Outside? Pissing with rain, hence the 'damp' in here |
| 03:45 | <~Vornicus> | celmin: no |
| 03:45 | <@PinkFreud> | heh, much the same here |
| 03:45 | <@PinkFreud> | we've had so much rain that I'm floating down the street right now |
| 03:45 | <@PinkFreud> | (no, really, call for help!) |
| 03:45 | <@PinkFreud> | (I'm joking, calm down) |
| 03:45 | | * PinkFreud grins |
| 03:46 | <@celticminstrel> | That said, I think it's about the best I can manage as a heuristic... |
| 03:46 | <@celticminstrel> | Without risking overestimation. |
| 03:46 | <@PinkFreud> | heh, but this area does tend to flood fairly easily. fortunately, it largely means our roads are a bit wetter than usual. no raging rivers for roadways here. |
| 03:47 | <@PinkFreud> | just some pooled water that makes driving fun, and occasionally shuts down stretches of roadway |
| 03:51 | <~Vornicus> | celmin: the amount of time it apparently took to do A* suggests there's something else seriously wrong. |
| 03:51 | <~Vornicus> | I'm not sure whether I should look at the code or cleanroom you my own implementation |
| 03:53 | <@celticminstrel> | I don't have a check for whether a tile is in the discovered queue before pushing it. Maybe that's the problem. Both ROT's implementation and Wikipedia's pseudocode include this. |
| 03:54 | <@celticminstrel> | I don't remember why I missed it. |
| 03:54 | <~Vornicus> | That shouldn't be enough to screw you over though. |
| 03:55 | <@celticminstrel> | (Before you ask, I'm not using ROT's implementation because it assumes all tiles cost 1.) |
| 03:55 | <@PinkFreud> | Reiv: I may have to continue this tomorrow. |
| 03:55 | <@Reiv> | PinkFreud: No problem, and good luck |
| 03:55 | <@Reiv> | There is a bug in that code, and I do not hav eth ebrain to spot it, sorry~ |
| 03:56 | <@PinkFreud> | that makes two of us. :) |
| 03:56 | <@Reiv> | yup :) |
| 03:56 | <@PinkFreud> | blah. I'll run it by some co-workers tomorrow. |
| 03:56 | <@celticminstrel> | http://pastebin.com/NAWmRLSj |
| 03:56 | <@PinkFreud> | thanks! |
| 03:57 | <@celticminstrel> | (Not fully general at this point.) |
| 03:57 | <@celticminstrel> | (For example, it doesn't climb stairs.) |
| 04:07 | <@Reiv> | Good luck! |
| 04:07 | <@Reiv> | I mean, the *structure* of the code there is a lot healthier than what you started with |
| 04:07 | <@Reiv> | You just have to get the joins, y'know, joining right~ |
| 04:13 | <@PinkFreud> | :P |
| 04:28 | | * celticminstrel wonders if Vorn has anything to say about the code. |
| 04:31 | <~Vornicus> | Off the top I can't see anything wrong with it. Where's PriorityQueue? |
| 04:32 | <@celticminstrel> | http://pastebin.com/7KsXbcwD |
| 04:37 | <~Vornicus> | Okay, hm. |
| 04:38 | <~Vornicus> | (odd it uses binary search and insertion here. I don't know what that does to performance but it should be acceptable...) |
| 04:38 | <@celticminstrel> | That's odd? |
| 04:40 | <~Vornicus> | Little bit. Heap tends to be the standard; fewer mass moves. |
| 04:41 | <@celticminstrel> | Well, before that I was using an unsorted array with linear search though. |
| 04:41 | <~Vornicus> | D: |
| 04:41 | <~Vornicus> | That would indeed be worse. |
| 04:42 | <@celticminstrel> | ROT's version actually appears to use linear search too... but it does keep the array sorted. |
| 04:42 | <@celticminstrel> | (So it uses search at insertion time rather than extraction time like I initially did.) |
| 04:59 | | * celticminstrel could mention that I'm calling the A* function several times (~60 or so according to the console log) in a row, but I don't think that's quite the problem here since even just the first call seems to be pretty slow. |
| 05:05 | <@celticminstrel> | So I'm out of ideas. |
| 05:06 | <@celticminstrel> | Unrelatedly, I should really get around to randomizing the player's start position so they don't end up in the middle of a lake. >_>3 |
| 05:07 | | Derakon is now known as Derakon[AFK] |
| 05:16 | <~Vornicus> | Should, but even then. blowing through 100k nodes should *not* be -- how long does this thing take anyway |
| 05:18 | <&McMartin> | https://twitter.com/qrush/status/804133542498287619 |
| 05:34 | <@celticminstrel> | Maybe ~10 minutes or something? I didn't actually time it. |
| 05:36 | <~Vornicus> | just, holy shit |
| 05:37 | <@celticminstrel> | Might've been less. I think I had to click "continue" around 10 or 12 times in Firefox's "this script might be running away" dialog. |
| 05:39 | <@celticminstrel> | This is several A*'s in a row though, but... |
| 05:41 | <@celticminstrel> | Yeah, was probably quite a bit less... |
| 05:42 | <@celticminstrel> | Looks like each one is <15s |
| 05:42 | <@celticminstrel> | Or at least <30s |
| 05:43 | <@celticminstrel> | Some a lot less. |
| 05:43 | <@celticminstrel> | Some of the paths are really short. |
| 05:44 | <@celticminstrel> | I could probably reduce the number of paths actually... pretty sure this is more than needed for a minimally connected map... |
| 05:45 | <@celticminstrel> | Maybe some are >30s... |
| 05:46 | <@celticminstrel> | (Wait, is it s or ms...) |
| 05:46 | <@celticminstrel> | (Definitely s) |
| 05:47 | <@celticminstrel> | (The time between Firefox's infinite loop warnings.) |
| 05:47 | <@celticminstrel> | (I've set it to 15) |
| 05:48 | <@celticminstrel> | Huh, it's been almost 10 minutes now sinced I started it, so maybe that wasn't such a bad estimate. |
| 05:49 | <@celticminstrel> | Admittedly the previous estimate was from after one A* had already completed. |
| 05:49 | <@celticminstrel> | Since I had been running through it in the debugger. |
| 05:50 | <@celticminstrel> | Done in 11 minutes. |
| 05:50 | <@celticminstrel> | Approximately. |
| 05:50 | <@celticminstrel> | I didn't use a stopwatch, just kept an eye on the clock. |
| 05:51 | | Pink [user1@Nightstar-g7hdo5.dyn.optonline.net] has joined #code |
| 05:51 | | Pink is now known as ASCII |
| 05:51 | <@celticminstrel> | And that's from running A* 71 times. |
| 06:03 | <~Vornicus> | what are you doing with A* anyway |
| 06:08 | <@celticminstrel> | Connecting continents via underground passages. |
| 06:13 | <~Vornicus> | Uh huh. |
| 06:16 | <@celticminstrel> | Solid walls have a cost of 100 while floors have a cost of 0 (that's tile.cost in my code, so the value used for the A* is 1 greater). |
| 06:19 | <~Vornicus> | Are solid walls diggable or |
| 06:28 | <@celticminstrel> | They are diggable for this purpose. |
| 06:28 | <@celticminstrel> | The player can't dig them. |
| 06:29 | <@celticminstrel> | (Though I'd considered making some of them diggable, but that's another matter altogether.) |
| 06:55 | | Kindamoody[zZz] is now known as Kindamoody|afk |
| 07:05 | <~Vornicus> | So basically the question is -- making sure this is sane here -- you're seeing if there is a path or, if the path is too expensive, cut through the wall? |
| 07:21 | | Alek [Alek@Nightstar-cltq0r.il.comcast.net] has quit [Connection closed] |
| 07:24 | | macdjord is now known as macdjord|slep |
| 07:26 | | Alek [Alek@Nightstar-cltq0r.il.comcast.net] has joined #code |
| 07:26 | | mode/#code [+o Alek] by ChanServ |
| 07:42 | | Alek [Alek@Nightstar-cltq0r.il.comcast.net] has quit [Ping timeout: 121 seconds] |
| 07:45 | | Alek [Alek@Nightstar-cltq0r.il.comcast.net] has joined #code |
| 07:45 | | mode/#code [+o Alek] by ChanServ |
| 07:59 | <@celticminstrel> | Vornicus: The assumption is that the A* finds some path, possibly through the wall if necessary. |
| 07:59 | <~Vornicus> | Righto. |
| 08:05 | <@celticminstrel> | Sometimes there might already be a path through the previously-generated underground rooms, but that's not guaranteed, which is why I'm doing this. |
| 08:08 | | Derakon[AFK] [chriswei@Nightstar-5mvs4e.ca.comcast.net] has quit [Ping timeout: 121 seconds] |
| 08:09 | <~Vornicus> | I cannot tell why you might be having trouble. It might be the mass-moves required by splice and shift, but I'd need the full code and profiling to say |
| 08:10 | <~Vornicus> | heck I don't know if the mass moves are even expensive, really |
| 08:12 | | Derakon [chriswei@Nightstar-5mvs4e.ca.comcast.net] has joined #code |
| 08:12 | | mode/#code [+ao Derakon Derakon] by ChanServ |
| 08:16 | <@celticminstrel> | I suppose I could try reversing the compare and using pop... |
| 08:16 | <@celticminstrel> | No idea if that would really help though, and of course it wouldn't eliminate the splices. |
| 08:19 | <~Vornicus> | No. If you want to defeat mass moves you use a heap |
| 08:20 | <@celticminstrel> | Heaps are confusing, but sure I could try it. |
| 08:20 | <~Vornicus> | Heaps are *weird* to write though, but we're on the third rule of optimization |
| 08:20 | <~Vornicus> | Profile First |
| 08:20 | <@celticminstrel> | Right. |
| 08:20 | <&McMartin> | So, let's see |
| 08:20 | <&McMartin> | The first rule is Don't |
| 08:20 | <~Vornicus> | This is clearly way too long for what appears to be a simple worldgen task. |
| 08:20 | <&McMartin> | The second is Don't Yet |
| 08:21 | <&McMartin> | So is the third "Profile first" or is this some other third |
| 08:21 | <~Vornicus> | Profile First is the third |
| 08:21 | <@celticminstrel> | So how do I profile in JS... |
| 08:22 | <@celticminstrel> | Date.now()? |
| 08:22 | <~Vornicus> | Crhome and Firefox both have a profiler built in to their dev tools. |
| 08:22 | <@celticminstrel> | Seems suitable. |
| 08:22 | <@celticminstrel> | Oh. |
| 08:22 | <@celticminstrel> | Performance tab? |
| 08:23 | <@celticminstrel> | I seem to recall using this for measuring page load times... |
| 08:23 | <@celticminstrel> | No wait that was the network tab. |
| 08:24 | <~Vornicus> | Performance, in Firefox |
| 08:25 | <@celticminstrel> | 'kay it's going |
| 08:25 | <@celticminstrel> | I guess I have to wait ~10 minutes now. |
| 08:25 | | * celticminstrel disabled timeout temporarily for this. |
| 08:26 | <@celticminstrel> | Would be nice if it locked up just the one tab and not the whole program. Oh well. |
| 08:37 | <@celticminstrel> | So it's been >10 minutes now... |
| 08:37 | <@celticminstrel> | How much longer should I wait before killing it... |
| 08:39 | <@celticminstrel> | It's finished, huh. |
| 08:39 | <@celticminstrel> | It says the buffer is 100% full. |
| 08:39 | <@celticminstrel> | And older stuff was overwritten. |
| 08:43 | <@celticminstrel> | I have no idea what to do with this data. |
| 08:43 | <~Vornicus> | Find a way to send it to me, I can read those entrails |
| 08:43 | <@celticminstrel> | Saves as JSON... fun. |
| 08:44 | <~Vornicus> | ( vorn@nightstar.net ) |
| 08:44 | <@celticminstrel> | Oh, sure, that works too. |
| 08:44 | | * celticminstrel was going to upload it to my VPS. |
| 08:44 | <~Vornicus> | that also works |
| 08:44 | <@celticminstrel> | Any preference? |
| 08:46 | <~Vornicus> | No. |
| 08:47 | <@celticminstrel> | 25MB, wow. |
| 08:47 | <~Vornicus> | ...probably the vps |
| 08:47 | <@celticminstrel> | I think the first 80% of it is probably irrelevant though... at least, most of it is flatlined on the graph at the top, but then there's lots of stuff near the top edge. |
| 08:47 | <@celticminstrel> | I started recording a bit early. |
| 08:49 | <@celticminstrel> | Should be at http://celmin.pwcsite.com/misc/profile.json |
| 08:50 | <~Vornicus> | whatever I looked at last on your vps I zoomed in a whole lot |
| 08:51 | <@celticminstrel> | ? |
| 08:54 | <~Vornicus> | The text was at like 100pt |
| 08:54 | <@celticminstrel> | Was it http://celmin.pwcsite.com/malandread/ ? |
| 08:55 | <@celticminstrel> | Or maybe one of the directory listing pages? |
| 08:59 | <~Vornicus> | Ok, my answer is found |
| 08:59 | <~Vornicus> | You spend fully half your time in PQ.pop |
| 08:59 | <~Vornicus> | And about 20% in PQ.push |
| 09:00 | <@celticminstrel> | I see. Sounds like reversing the compare would help (or doing a heap). |
| 09:24 | <@celticminstrel> | Thanks for your help. |
| 09:27 | <@celticminstrel> | Reversing the comparison seems quite a bit faster, indeed. |
| 09:28 | <@celticminstrel> | Still triggers the timeout though, so I guess I'll try a heap tomorrow. |
| 09:28 | <@celticminstrel> | I'll also try to reduce the total number of paths calculated. |
| 09:30 | <@celticminstrel> | Though I might already be at the minimum for total connectivity... |
| 09:31 | <@celticminstrel> | I think that was closer to ~5 minutes than 10 this time. |
| 09:31 | | * celticminstrel zzzZzzz |
| 09:32 | | celticminstrel [celticminst@Nightstar-h4m24u.dsl.bell.ca] has quit [[NS] Quit: And lo! The computer falls into a deep sleep, to awake again some other day!] |
| 09:54 | | Emmy [Emmy@Nightstar-9p7hb1.direct-adsl.nl] has joined #code |
| 09:54 | | mode/#code [+o Emmy] by ChanServ |
| 12:11 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has quit [Ping timeout: 121 seconds] |
| 12:42 | | Alek [Alek@Nightstar-cltq0r.il.comcast.net] has quit [Ping timeout: 121 seconds] |
| 12:45 | | Emmy-werk [NSkiwiirc@Nightstar-41pbej.static.chello.nl] has joined #code |
| 12:45 | | mode/#code [+o Emmy-werk] by ChanServ |
| 12:45 | | Alek [Alek@Nightstar-cltq0r.il.comcast.net] has joined #code |
| 12:45 | | mode/#code [+o Alek] by ChanServ |
| 13:05 | <@Emmy-werk> | mrgh. once more, concentration is whack |
| 13:12 | <@TheWatcher> | I recommend tea. |
| 13:22 | <@Emmy-werk> | Done and done already. :P |
| 13:23 | <@Emmy-werk> | ...More. |
| 13:24 | <@Emmy-werk> | http://earnestlycontending.com/maranatha/wp-content/uploads/2012/05/fd35df73_359 q.jpeg |
| 13:24 | <@Emmy-werk> | MORE! |
| 13:37 | <@Emmy-werk> | https://www.youtube.com/watch?v=e4w6V-PbPKM |
| 14:27 | | Emmy-werk [NSkiwiirc@Nightstar-41pbej.static.chello.nl] has quit [[NS] Quit: http://www.kiwiirc.com/ - A hand crafted IRC client] |
| 14:40 | | Emmy-werk [NSkiwiirc@Nightstar-41pbej.static.chello.nl] has joined #code |
| 14:40 | | mode/#code [+o Emmy-werk] by ChanServ |
| 15:23 | | celticminstrel [celticminst@Nightstar-h4m24u.dsl.bell.ca] has joined #code |
| 15:23 | | mode/#code [+o celticminstrel] by ChanServ |
| 15:25 | | Emmy-werk [NSkiwiirc@Nightstar-41pbej.static.chello.nl] has quit [[NS] Quit: http://www.kiwiirc.com/ - A hand crafted IRC client] |
| 16:19 | | abudhabi [abudhabi@Nightstar-7nkq9k.de] has quit [Ping timeout: 121 seconds] |
| 16:24 | | catadroid [catalyst@Nightstar-depr0p.dab.02.net] has joined #code |
| 16:31 | | catadroid` [catalyst@Nightstar-4e9m8q.dab.02.net] has joined #code |
| 16:33 | | catadroid` [catalyst@Nightstar-4e9m8q.dab.02.net] has quit [[NS] Quit: Bye] |
| 16:34 | | catadroid [catalyst@Nightstar-depr0p.dab.02.net] has quit [Ping timeout: 121 seconds] |
| 16:46 | | abudhabi [abudhabi@Nightstar-7nkq9k.de] has joined #code |
| 16:46 | | mode/#code [+o abudhabi] by ChanServ |
| 16:56 | | catadroid [catalyst@Nightstar-4e9m8q.dab.02.net] has joined #code |
| 17:24 | | catadroid [catalyst@Nightstar-4e9m8q.dab.02.net] has quit [[NS] Quit: Bye] |
| 17:40 | | macdjord|slep [macdjord@Nightstar-cd2k4t.mc.videotron.ca] has quit [[NS] Quit: We *are* shining examples of humanity. It's just that the light we shine with is generally Oppenheimer's.] |
| 18:52 | | Alek [Alek@Nightstar-cltq0r.il.comcast.net] has quit [Ping timeout: 121 seconds] |
| 18:56 | | Alek [Alek@Nightstar-cltq0r.il.comcast.net] has joined #code |
| 18:56 | | mode/#code [+o Alek] by ChanServ |
| 20:56 | | gnolam [quassel@Nightstar-t2vo1j.tbcn.telia.com] has joined #code |
| 20:56 | | mode/#code [+o gnolam] by ChanServ |
| 21:19 | | Vornicus [Vorn@ServerAdministrator.Nightstar.Net] has joined #code |
| 21:19 | | mode/#code [+qo Vornicus Vornicus] by ChanServ |
| 21:22 | | catalyst [catalyst@Nightstar-bt5k4h.81.in-addr.arpa] has joined #code |
| 21:42 | <@celticminstrel> | I really don't want to have to implement a heap... |
| 21:42 | <@celticminstrel> | Maybe I can find some code on SO or something... |
| 21:42 | <~Vornicus> | I can do that for you |
| 21:43 | <@celticminstrel> | Also, Wikipedia's formulas assume that 0 is the min element, but I think it'd be better for the min element to go at the end. |
| 21:43 | <@celticminstrel> | Uhh, if you want to do it for me, then sure? |
| 21:43 | <@celticminstrel> | I'll probably put an MIT license or similar on this eventually. |
| 21:44 | <@celticminstrel> | (Well, it provides formulas for the min element being at index 1, too.) |
| 21:45 | <@celticminstrel> | Unless removing from a heap doesn't involve removing the first element of the array storage? I don't really get how heaps work. |
| 21:45 | <@celticminstrel> | If it doesn't actually remove the first element then I guess it wouldn't matter whether the min is at the beginning or end of the array. |
| 21:45 | <~Vornicus> | Popping from a heap gives you the first element... and then puts the last element in the first slot and reshuffles. |
| 21:46 | <~Vornicus> | In this way it avoids mass moves. |
| 21:46 | <@celticminstrel> | I see. |
| 21:47 | <~Vornicus> | One moment whilst I put this sucker together |
| 21:49 | <~Vornicus> | (the heap invariant *does* however mean that the first element is the only one you know its magnitude compared to *all* other elements. heapqs are not exactly good for random access...) |
| 21:49 | <@celticminstrel> | Well I don't need random access... |
| 21:49 | <~Vornicus> | Indeed not. |
| 21:49 | <@celticminstrel> | I just need to get one of the elements with minimum priority. |
| 21:49 | <@celticminstrel> | Doesn't even matter which one. |
| 22:12 | | * TheWatcher hrms, wonders why -N $filename is always returning true for him in bash |
| 22:14 | <@TheWatcher> | Oh, wait, I know, because this is mounted with noatime |
| 22:38 | <&[R]> | What's the difference between a heap and a stack anyways? Aren't they both FIFO/LILO? |
| 22:38 | <&McMartin> | No |
| 22:38 | <&[R]> | Err |
| 22:38 | <&[R]> | FILO* |
| 22:39 | <&McMartin> | Even more no. |
| 22:39 | <&McMartin> | Er, wait, no |
| 22:39 | <&McMartin> | Less no |
| 22:39 | <&McMartin> | A stack is FILO/LIFO |
| 22:39 | <&McMartin> | LIFO is more common |
| 22:39 | <&McMartin> | Heaps return their contents in sorted order. |
| 22:39 | <&McMartin> | The two operations on heaps are "insert" and "remove largest" |
| 22:40 | <&McMartin> | This also assumes you refer to the data structures "heap" and "stack", and not the parts of most programming language runtimes "heap" and "stacK'. |
| 22:41 | <&McMartin> | For the latter, the stack is usually but not always a stack, and the heap is never actually a heap. |
| 22:41 | <&[R]> | I was kind of doing the former, with the assumtion the latter meant the same? |
| 22:41 | <&McMartin> | OK, so! |
| 22:41 | <&McMartin> | That's only true for the stack in languages with, uh, "stack discipline". Like C. |
| 22:42 | <&McMartin> | The Stack is where your function's local variables go; those are the things that (if your language has stack discipline) vanish when the function returns. |
| 22:43 | <&McMartin> | The Heap is where stuff that plays with malloc/free, or new/delete, or garbage-collection lives. |
| 22:43 | <&McMartin> | It's just a pile of memory that knows which bits of itself are in use, and can dole out new chunks of memory or reclaim them. |
| 22:43 | <&McMartin> | Simplistic implementations of that kind of heap actually look more like linked lists. |
| 22:44 | <~Vornicus> | Stack collision with a heap! |
| 22:44 | <&McMartin> | It's been awhile since I've looked into state-of-the-art modern allocators for very large address spaces, but I seem to recall those look more like binary decision diagrams. |
| 22:44 | <&McMartin> | The data structure "heap" is the heap used in things like "heap sort" |
| 22:45 | <&McMartin> | which is basically "insert all your items into a heap and then keep taking the largest element until you can't" |
| 22:45 | <&McMartin> | Turns out to be one of the more efficient ones, funnily enough |
| 22:45 | <~Vornicus> | Where it is a mere vector with some instrumentation to maintain a vaguely sorted invariant. |
| 22:45 | <&McMartin> | It's a cool trick people should know, but it's honestly not something that you're going to often explicitly use by name. |
| 22:45 | <&McMartin> | If you're going to name the thing that you implemented with a heap, you probably call it something like "priority queue" |
| 22:47 | <&McMartin> | But they're wicked fast on individual operations, only require memory allocation at the start if you know your maximum size, and the using them as a brute-force sorting solution ends up putting you in the same general class as quicksort, with better worst-case characteristics but worse average-case characteristics. |
| 22:47 | <&McMartin> | s/the using/using/ |
| 22:48 | | * Vornicus is building a priority queue today. |
| 22:52 | | gnolam [quassel@Nightstar-t2vo1j.tbcn.telia.com] has quit [[NS] Quit: Z?] |
| 22:58 | | * abudhabi combines crontab with anki. |
| 23:01 | | * [R] doesn't get why you need flashcards for crontab |
| 23:02 | <@abudhabi> | Other way around. |
| 23:02 | <@abudhabi> | I've set anki to launch every day. |
| 23:02 | <@celticminstrel> | Vornicus: How's it going? |
| 23:15 | <~Vornicus> | Other than fully distracted the code is done but I'm going to run some tests. |
| 23:40 | | catalyst [catalyst@Nightstar-bt5k4h.81.in-addr.arpa] has quit [[NS] Quit: Leaving] |
| 23:42 | | Reiver [quassel@Nightstar-ksqup0.co.uk] has quit [Connection closed] |
| 23:42 | | Orthia [quassel@Nightstar-ksqup0.co.uk] has quit [Connection closed] |
| 23:42 | | Orthia [quassel@Nightstar-ksqup0.co.uk] has joined #code |
| 23:42 | | mode/#code [+o Orthia] by ChanServ |
| 23:42 | | Reiver [quassel@Nightstar-ksqup0.co.uk] has joined #code |
| 23:42 | | mode/#code [+ao Reiver Reiver] by ChanServ |
| --- Log closed Fri Dec 02 00:00:33 2016 |