« first day (1899 days earlier)      last day (3052 days later) » 

7:00 PM
@AngryShoe yeah i know man. But this one will work for the question, as he only wants to load using loops. The questioner is concerned about lines of codes here. — Kishan Kumar 39 secs ago
 
that chess robot is quite intense, I wonder what would happen if you put it in a difficult situation
 
What?
 
.-.
Printing things in neat columns is the hards.
 
You know what else is hard
 
Oh well.
 
7:08 PM
@sehe I've been working on the paper for pdqsort
and after doing some more thinking I've got a decent analysis
 
Oh, so you're finally writing a paper? :)
 
yes
if there's k distinct keys, then pdqsort is O(n * k)
 
@orlp What is the pdq-sort?
 
so, if k is small, pdqsort takes linear time
 
@orlp Difference from radix? Comparisons?
 
7:09 PM
@orlp Wow o_o
 
@CaptainGiraffe pdqsort is strictly a comparison sort
@Morwenn the analysis is pretty simple actually
@Morwenn each distinct element can be a pivot at most twice
 
@orlp It is trivially provable that a comparison based sort is N*logN What do you relax?
 
done
@CaptainGiraffe N log N in the average case
 
@orlp Yes, what do you relax?
 
as I said, when k is small
 
7:11 PM
@orlp Makes sense.
 
no
 
Ok, > if there's k distinct keys, then pdqsort is O(n * k)
k is n for the n log n argument.
 
@CaptainGiraffe well, this is big O
so it's an upper bound
 
Which is why it runs in times comparable to distribution sorts when there aren't many values.
 
7:14 PM
pdqsort is still O(n log n) as well
O(n log n) && O(n * k)
when k < log n the latter bound is more strict
 
What are your test timings?
 
@CaptainGiraffe please elaborate your question?
 
By the way, where does the log n memory come from?
 
@Morwenn recursion stack :)
 
@orlp Where does your implementaion do better than the traditional sorts.
 
7:16 PM
@CaptainGiraffe did you look at the github page?
it has a benchmark chart right there
 
No, sorry.
 
@orlp Didn't know it was taken into account. Didn't you optimize it so that it performed tail recursion?
 
@Morwenn each partition gives two results
you can only tail recurse optimize one
 
I thought that the original quicksort log n memory came from the fact that the pivot was often copied.
 
the other one has to be stored in some way
 
7:17 PM
@orlp Oh right.
 
in my case it's stored implicitly in the call stack
 
user1804599
@AngryShoe Lord
 
Robot vs Robot in chess: A assume B is perfect in its heuristic, A play perfect move by its heuristic, B assume A is perfect in its heuristic, B play perfect move by its heuristic .. repeat
 
@Morwenn A more precise bound is 2 * n * k
 
Heapsort was an unnecessary addition. It is never the best. Never the worst.
 
7:19 PM
.. now what happen if both robots have the same heuristic
 
@CaptainGiraffe heapsort is the algorithm that pdqsort falls back on in the worst case
it's important to illustrate for the worst case
 
@orlp I think he's talking about the benchmarks.
 
(which is exceedingly rare)
 
@orlp Yes, I noticed that a second later.
 
@CaptainGiraffe basically the heapsort graph is important for people interested in real-time processing
since it shows the 'range' of performance pdqsort could potentially have in the absolute worst case
 
7:21 PM
@CaptainGiraffe Also, I overly use this benchmark so you can have a few more graphs and compare for yourself.
Basically, pdqsort is the best generic comparison sort that doesn't eat too much memory.
 
@orlp +1 Interesting.
 
I wonder if I should write this in F# or Haskell
F# would be easier to work with since it has proper tools
Haskell would make me look more hardcore in front of the professors
these are taff decisions
 
@orlp Please include a radix sort in your test data. ints are easy to take advantage of.
 
@CaptainGiraffe that'd be unfair
 
@AlexM. can you write Haskell in a F# application ?
 
7:25 PM
I'm testing comparison sorts here
 
Why so?
 
@KhaledAKhunaifer meaning?
 
radix sort has a different interface
 
@CaptainGiraffe Just look at what I linked. spreadsort is an optimized distribution sort for integers, so basically an improved radix sort.
 
you can probably map any haskell concept to an F# equivalent
 
7:25 PM
@AlexM. I was just going with "Why not both"
 
user1804599
Are there libraries that can nicely deal with infinite sets?
 
@Elyse what language?
 
@Morwenn Thanks. I was not aware of spreadsort. Where would one expect this algorithm to do well? pdq not spread.
 
user1804599
@KhaledAKhunaifer any
 
Look for lazy evaluating languages.
 
7:32 PM
@CaptainGiraffe I would expect pdqsort to beat almost every everywhere, except maybe some well-crafted algorithms using additional storage, algorithms specialized for some types or algorithms designed to beat some patterns.
 
Has there ever been a game where you can play as the villain?
Not the likeable kind like Overlord
 
@CaptainGiraffe pdqsort is basically an improved std::sort
really efficiently implemented
 
@ElimGarak hmm
let me think
 
with better tricks to avoid worst case, and a nice best case
 
the cringy edgy thing
called Hatred
it's recent
 
7:33 PM
Ah yeah, Hatred
 
So basically, pdqsort would be the best general sort for random-access collections.
 
but fully general, not specialized
 
I'm not sure if you play as the bad guy in Manhunt
 
Ah, there is!
 
probably not
 
7:33 PM
@orlp std::sort is easy to improve for ints
 
In the sense that you were wronged in some way, Arthas for example.
That you have some sympathy points and it isn't all without cause
 
@CaptainGiraffe sure, but that's out of scope for pdqsort
 
you can likely consider yourself the bad guy depending on how you play RPGs like Baldur's Gate
 
@CaptainGiraffe Yeah, that's not the point.
 
pdqsort is strictly a comparison sort to stay general
feel free to combine it with other sorts
@Morwenn if I understand correctly, vergesort is basically merge-pdqsort?
 
7:35 PM
I would love to play a character with the voice of the bad guy in W3
 
The ideas are well worthy of inspection. Would you mind if I discuss this stuff with others? Do you have a paper ready?
 
@orlp Yeah, it just cheks in O(n) time whether some big portions are already sorted or reverse sorted and calls pdqsort to sort the rest, then merges.
 
@ElimGarak man what is the name of the shader thing that you use on single textures like water to make it seem like it "moves"
waving and such
I'm not sure if it's displacement (?)
 
@CaptainGiraffe my paper is not ready, but my repository is stable for a while now
 
In a truly random collection, it's an O(log n) step, almost free.
 
7:36 PM
@Morwenn I think you need a slightly better approach for merging though
you keep merging into the previous sequence
you want to merge sequences of similar sizes
 
@orlp Yeah, the merging step sucks, but I wasn't motivated enough to improve it.
 
@CaptainGiraffe so feel free to discuss whatever you see in the repo
 
On the other hand, when it performs a merge, it means that you're already winning.
 
@CaptainGiraffe I can also strongly suggest you do read the implementation - it's only 300 LOC
 
@orlp It is compact.
 
7:38 PM
@AlexM. I am not sure what you mean :D You could progressively animate UVs with a tiling texture (with wrapping address mode). Personally, I use statistical models to model ocean waves and stuffs, in frequency space, and then generate a mesh on the fly. :D
I think even WoW has upgraded its water rendering, IIRC
Animating the normals in the olden days would change the way light interacts with the "microsurface" and you'd get an idea of changing volume. Max Payne 3 had alternating normal maps for the back of the character to simulate fabric morphing.
 
@CaptainGiraffe for the record, I'm also talking to libstdc++ and libc++ to merge pdqsort as std::sort
 
I think that's more complicated than what I have in mind
here's an example
 
I could simply remember the different "meaningful" iterators in vergesort then decide of the overall merge order. It would take at most O(log n) auxiliary memory to store the iterators.
 
@orlp What is the response?
 
that wave is one big quad-like thing
 
7:41 PM
@CaptainGiraffe they're working on regression benchmarks
@CaptainGiraffe when those are done they'll test it
 
and on the material I can change the offset of the texture (I think that's what it is)
 
@orlp I wish you the best of luck.
 
basically, changing the offset between say 0.0 and 0.1 back and forth
would give the illusion of an animation
I remember (maybe wrong) that there's some kind of really simple shader technique that does this automatically
 
That at the bottom are caustics, refraction caused streaks, which are usually just UV modulated back and forth via the time variable (scaled cos comes to mind). As long as you have a tiled caustics texture, it'll be consistent. (and of course, wrapping address mode)
 
@CaptainGiraffe one of the mailing list people claimed that pdqsort reduced the runtime of one of his programs from 3.46s to 2.85s
 
7:43 PM
wow
 
@orlp It would be neat to have a clause in c++17 that said. The sort is required to be O(n) for this and this input. =)
 
where sorting was 1/3rd of the time taken (although he did not specify whether the above times were only the sorting portion or total runtime)
@CaptainGiraffe I believe that'd be unnecessarily restrictive
 
@orlp If you want additional coolness, spreadsort didn't perform that well in the benchmarks before I changed the fallback calls to std::sort to calls to pdqsort.
 
maybe a sorting algorithm comes along that's 20% better than me in the average case for some reason
 
@orlp If it was possible, you would have a name written in granite.
 
7:44 PM
@Morwenn wait, spreadsort uses pdqsort in your benchmarks
 
Yes.
 
@CaptainGiraffe I don't understand the reference
@Morwenn lol
 
There was a noticeable improvement for some patterns. I don't remember which.
 
by the way I made this visualization of quicksort (not pdqsort)
 
user1804599
WTF
 
user1804599
7:47 PM
rackspace-monitoring-agent uses 105% CPU
 
however, unlike most visualizations, I keep a priority queue
and recurse on the biggest partition
 
ugh VS froze my HDD at 100%
what cancerous overgrowth this IDE is
ah it works now
VS best
 
I see the Lounge is still obsessed with sorting. :D
 
I need to test the sorting algorithms with more types to see how it changes things, but... it's boring .___.
 
7:47 PM
@orlp Not much of a reference. Merge-sort 400 AD, Quicksort(Hoare) 1961 AD. PDQ sort 2015...
 
@ElimGarak Ony a few of us :p
 
@CaptainGiraffe ah
I really like that animation
because it visually shows how quicksort gradually improves
mind you, the only thing I changed was the order in which recursion occurs
 
Next step: find the best sorting algorithm for bidirectional iterators.
 
@Morwenn pdqsort
 
same as forward iterators I'd have to guess
 
7:52 PM
@Puppy nope
only place that requires random access is the median-of-3 calculation
 
@orlp Heapsort doesn't really work.
 
@Morwenn hrm yea
would need a different fallback
 
not sure why a requirement for RA makes a bidi algorithm different from a forward algorithm
 
but for median-of-3 you can take just the first, the last and the second element or smt
 
A pdqmergesort would work if we don't care about memory.
 
7:53 PM
@Puppy partitioning
 
@orlp Uh huh, and how does bidi differ from forward in that respect?
 
@Puppy partitioning is most efficiently done by having two pointers, one from the left, one from the right
 
Partitioning works with forward iterators since C++11.
 
you increment the left point and decrement the right pointer while the ordering invariant holds
 
or to put it another way, it's trivial to convert a forward iterator range into a random-access range in O(n), so you can't get complexity changes between forward and RA.
 
7:53 PM
then when both are 'wrong', you swap them
@Puppy that requires O(n) memory, no?
 
probably.
 
@Morwenn not as efficiently
@Puppy pdqsort only requires O(log n)
 
Unfortunately, my vergesort (over an introsort based on a mergesort instead of heapsort) has a constant O(n) additional factor in its bidirectional form. And it simply doesn't work with forward iterators.
 
basically, if you partition with forward iterators you need N extra moves
 
but I got 32 jiggabytes so I officially don't care about memory complexity
 
7:55 PM
@Elyse likely bad measurement (bad translation to virtual CPU time?)
 
user1804599
@sehe I shut down rackspace-monitoring-agent and the server load dropped from over 34 to under 8.
 
@Puppy that makes no sense. You mean you only solve small problems?
> under 8
RIP
 
user1804599
haha wat grappig
 
@sehe Compared to that memory space, yes.
 
Nope. Not an ageist joke.
@Puppy Lucky you
A UNIX system load of 8 is ... bad news
 
user1804599
7:57 PM
also I think setting application thread count higher than PostgreSQL connection limit isn't such a good idea when you don't use connection pools :')
 
user1804599
@sehe CPU load
 
Well. What does it mean? Unless that's the same notion?
 
On the other hand, smoothsort is wonderful when it comes to complexity, but the implementation I have always sucks when it comes to actually sorting stuff.
 
@Borgleader Oooh Agner updates his blog!
 
@R.MartinhoFernandes "Yeah well. The toothpaste isn't going to cut it for me"
 
8:01 PM
Intel has always been turning off the the AVX-256 unit. But it seems that the latency has increased for Skylake.
 
user1804599
@sehe The load indicates how many threads are ready but waiting to be resumed.
 
So that is UNIX system load
 
user1804599
It should be smaller than the number of hardware threads.
 
And 8 is bad.
 
user1804599
Why?
 
8:03 PM
Mmm. I thought 1 meant "1 process per logical CPU". So 2 on a 8-core would mean 16 running processes
 
user1804599
8 is smaller than the number of hardware threads, so it's fine.
 
Maybe I misremember
I Miss Cucumber
 
user1804599
Ah wait, it includes running processes.
 
I Miss Tomato
 
user1804599
So if the load is smaller than the CPU count, then all processes that could run are running.
 
user1804599
8:04 PM
And nobody is waiting for someone else.
 
@Elyse Well, obviously. Running tasks is just "pending tasks" that have been scheduled. But god knows how long they'll be running, so of course they count
 
hmm
not sure how to structure my CLI driver to permit different input sources.
command-line arguments suck.
 
@Elyse Apparently I missremember. I'll read up again
 
user1804599
@sehe They won't be running very long if the load is higher than the CPU count, due to pre-emption.
 
@Elyse Irrelevant. If they are preempted they're still by definition waiting for CPU. So they still count
 
user1804599
8:05 PM
Waiting, not running.
 
Load factor > hardware threads by definition always waits. That's precisely the bad case
 
user1804599
Yes.
 
Hi all.
 
@CaptainGiraffe just out of interest, who would you be discussing it with?
 
8:09 PM
@orlp I guess rumtscho
 
I don't know who/what that is
but ok
 
@orlp No sorry, that was a joke. My collegues at my uni.
 
user1804599
@KhaledAKhunaifer cool
 
@CaptainGiraffe ah
 
@orlp I have no interest in competing.
 
8:11 PM
@CaptainGiraffe in that case, there's 3.5 things that are to my knowledge truly novel about my design
1. my partitioning scheme that gives O(n * k) for many equal elements
2. detecting the worst case through 'bad' partitions (which has some really interesting and complicated analysis behind it)
3. deterministically breaking worst case patterns by swapping a couple elements on a bad partition
3.5 (minor optimization compared to libc++), detecting perfect partitions simply using one comparison at one point, rather than counting comparisons
 
@Elyse the first link shows how you can play around with infinite sets in matlab, you can do stuff like: Dom::Interval([1], infinity)
 
user1804599
eww proprietary software
 
isn't any lazy set an infinite set
 
@AlexM. no
you can have a lazy finite set
 
user1804599
@sehe I've been having a lot of fun with SQL recently.
 
8:15 PM
ah thank you
 
(i for i in range(10)) in Python for example
 
user1804599
range(10) is already lazy.
 
@Elyse IMPOSSIBRU GROUP BY ANAL HAVING FUN > 0
 
fair enough, in py3
 
Lazy just means it's producing values on demand rather than precomputing them
 
user1804599
8:16 PM
@sehe I wrote a voorraad forecast application in it.
 
@orlp 3 I'm not sure this is true. Still I'd like to investigate.
 
user1804599
Client said it was incredibly helpful.
 
@CaptainGiraffe what part of it aren't you sure that's true?
 
@Elyse Heyhey. I wrote a voorraad forecast in Turbo Pascal in 1992. It was previously done in Lotus 1-2-3
 
@CaptainGiraffe on the average case it does nothing, just to clarify
 
8:17 PM
@Elyse Let's check it's not the same client :) (I bet it's about firework again)
 
it's just a shuffle to change the worst case from one permutation to another
 
user1804599
@sehe Eww languages that aren't declarative and super high level.
 
user1804599
@sehe Why else would server load by unusually high at this time of the year? :P
 
however, I'd argue that the permutation with a pattern is much more common in real-world data than just a random permutation
 
Turbo Pascal was Ok as languages go
 
8:18 PM
@CaptainGiraffe I can perhaps make a visualization
 
I wrote a budget proposal in Enable in 1988 =)
 
@Elyse Because you suck at auto-scaling out :)
@CaptainGiraffe you win
 
user1804599
Yeah we'll probably be looking into horizontal scaling next year.
 
@CaptainGiraffe But I earned an EGA adaptor and a colour CRT monitor (so I could make the UI in colour)
 
Time to cook pasta.
With vegetables and chili.
 
8:20 PM
@Morwenn About 12 minutes - depending
 
And stuff.
 
@sehe I learned the English language from the BYTE magazine.
 
@Elyse you can run matlab script on octave, which is free. stackoverflow.com/a/13937191/2128327
 
user1804599
coolio
 
@KhaledAKhunaifer scilab seemed neat the 10 mins I tried it
it also provides something that looked like an alternative to Simulink
 
8:23 PM
@AlexM. I dunno how it was allowed, but there seem to be a real online matlab compiler online
 
user1804599
@sehe It was really easy.
 
user1804599
UNION ALL is the awesomest.
 
@sehe compared to most of the alternatives at the time, it w as s really pretty cool.
 
I briefly entertained a job offer with Delphi (and C++). Didn't make the cut
 
user1804599
This still irks me: coalesce(sum(...), 0).
 
user1804599
8:27 PM
All over the fucking place.
 
user1804599
Also PostgreSQL is finally getting upsert (INSERT ... ON CONFLICT (id) DO UPDATE ...) in 9.5.
 
omg, there is an online matlab compiler .. but it requires using a vpn, it worked on Tor
 
@sehe When was this?
 
user1804599
So I can eliminate a lot of stored procedures when 9.5 is released.
 
lol .. anycodes.cn
that's enough internet for a day to me, I'm out
 
8:37 PM
@CaptainGiraffe imgur.com/a/deYMp
top one is pdqsort
bottom one is std::sort
 
Guise, I'm hungry, I should feast
 
you'll get le fat
 
I've got two DDR-400 sticks, glorious 256 MB each.
 
@orlp Would you mind doing an x² distribution or an 2^x distribution?
 
@CaptainGiraffe what are you looking for?
 
8:44 PM
@orlp the droids
 
(mind you, creating the distribution in this visualization program takes no effort)
but capturing the gifs hnng
 
@orlp I'm looking for where it assumes a bad position.
 
@CaptainGiraffe what is 'it'
 
@CaptainGiraffe last month(s)
 
@sehe In my mind you had a senior position of master Yoda at craftsmen.com
Are you seriously looking for work?
 
user1804599
8:50 PM
Relational databases have instantsort.
 
user1804599
They just call it "index scan".
 
@Elyse hash lookup.
 
user1804599
No.
 
Dec 23 at 0:13, by sehe
I'm signing with a startup tomorrow.
 
user1804599
Hash indices aren't good for retrieving records in some order.
 
8:51 PM
hmm
Rapptz's jsonpp thing could use some work.
I might just fork it and fix it
 
Plink him
He's not around. Gasp
 
@sehe The Yoda position? Live well and prosper =).
 
Cheers. Will do
 
@Elyse So? Use a tree then. log N is basically O(1)
 
user1804599
8:54 PM
B-tree.
 
user1804599
Allows efficient iteration in order.
 
Looks like I found an error in Agner's Skylake benchmarks...
 
@Mysticial blasphemy!
 
Nah. He's probably using the same benchmark scripts he wrote for older processors, but didn't update them for Skylake.
He has all the integer SIMD multiplications at 1.0 inst/cycle. But others are reporting closer to 2.0. My own results are also showing 2.0-ish.
But you need 10 independent chains to get that. He's probably only using 5 chains.
 

« first day (1899 days earlier)      last day (3052 days later) »