« first day (3799 days earlier)      last day (416 days later) » 

12:05 PM
oh i get it
 
for example, I should be the least faded person right now
 
CMC: Favorite sorting algorithm? Mine's sleepSort
 
mine is mergesort
 
12 messages moved from The Edge of Propinquity
 
slaps face I actually clicked that, nice.
 
12:14 PM
@Ausername random sort
@lyxal ha i clicked that and because of my crappy internet i got saved
 
Ye I closed the tab beforeit loaded
 
TIL propinquity means "Proximity; nearness."
 
I was like "huh? Where are the messages? I'llj ust click the link."
 
GPT-3 really does have a better vocabulary than I thought
 
Show me?
 
12:15 PM
48 secs ago, by lyxal
TIL propinquity means "Proximity; nearness."
"The Edge of Propinquity" was generated from all the room names here
 
Oh yeah
 
Hey if y'all need username ideas:
casper
Jadefalcon501
Hawk
Firefighter0701
tacoslayer
jackassonwheels
Thomas
Some Guy
muhahaha
Stuart Jansen
Jebediah

HouseOfCantor
Ethereal
CoffeeCat
Sci-fi
michael.ottawa

Dylan
Sudoku
Keshawn Meeks
Mariel
Hawk
buzzdave
Ivan Chew
Moggie
tldr
Mike
Hawk
Tuxedo Mask
Hawk
 
@lyxal thank you
muhahaha
 
@Ausername Stalin sort
 
GPT-2
 
12:21 PM
GPT-3
with dark mode too
 
I mean, at least GPT-2 generates english
 
@Ausername that's nothing. the empty set denotes, even though it doesn't denote anything
 
@Neil Ok...
2
 
does anyone know R well enough to tell if codegolf.stackexchange.com/a/230419/7310 is really linear time?
 
e.g. all members of the empty set are odd, even, square, cube, prime and composite
 
12:23 PM
Oh true...
More GPT-2
'night
 
@flawr Feel like convolving stuff?
 
CMQ: Name an O(n) sort algorithm.
 
@Adám count sort, radix sort, just leaving the input as it is :)
depends on what the input looks like
@Adám count sort is linear time if the input is integers in a small range
@Adám radix sort is linear time if the input is integers in the range 0..n^c for a constant c if the input is of length n integers.
curiously you can convert from C doubles to 64 bit integers and back without any loss
 
12:43 PM
@felipa What is count sort?
 
In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of...
 
@felipa Of course, they are all just 64 bits. Doesn't matter what the bits represent.
 
en.wikipedia.org/wiki/…. is also linear time under the right circumstances
specifically if the input is uniformly distributed
@Adám yes but the key point is that the order is preserved
 
@felipa That sounds suspicious. Some 64-bit patterns do not represent orderable floats.
 
@Adám you need them to follow IEEE754
which I think essentially always happens
 
12:49 PM
@felipa I still don't get it. E.g. is qNaN<sNaN?
 
@Adám is that a floating point nan?
 
Yes.
 
if it's nan that I guess there is no defined order so you can do what you like with it
 
5 mins ago, by felipa
@Adám yes but the key point is that the order is preserved
 
how is nan represented in bits in IEEE754?
@Adám that's right. The order of things that had order in the first place
like 7 and 13
 
12:52 PM
@felipa s111 1111 1xxx xxxx xxxx xxxx xxxx xxxx
@felipa But surely, any IEEE754 NaN must correspond to a 64 bit int.
 
@Adám sure. Maybe the range is 63 bits in that case?
We need an expert :)
 
@felipa Well, there are 16777214 IEEE754 NaNs, all the ints they correspond to are problematic.
 
so it could still be 63 bits?
If feel writing some code and trying it out could help here
 
I guess. Since all floats that begin with s0 are normal floats.
 
that sounds good
 
12:58 PM
Not very curiously, you can convert from C doubles to 63 bit integers and back without any loss.
 
and preserve the order!!
 
If that even holds. I'm not so sure this is even true.
 
that's the clever bit
 
It it was true.
However, some floats have multiple valid bit representations. Clearly, these values should be considered equal (even if only one is the normal form), and thus they don't have the same ordering as the integers they correspond to.
 
1:27 PM
can you give examples?
 
@felipa 1×2⁴ and 0.5×2⁵
 
can the mantissa even be 1?
 
@Adám what order do you want those sorted in?
 
@felipa They are both 16.
 
@Adám so what is the concern?
they will be sorted correctly when converted to ints won't they?
 
1:36 PM
oh, wait, sorry, ofc. but i don't think 0.5 can be the mantissa? don't quite remember but i think it requires 1 <= m < 2
 
@felipa No, they will be unequal when converted to ints, and therefore they might switch places.
 
@Adám but that's ok
as long as nothing comes in between them!
 
Lots of things come between them, because they are not consecutive ints.
 
@Adám lots of doubles when converted to ints?
can you show a double that would come in between?
 
Sure.
0.75×2⁵
 
1:39 PM
@Adám can 0.5 be a mantissa?
or 0.75
 
ngn
@Adám i'm not sure you understand how floats work
mantissas almost always have an implicit leading digit of 1
 
@ngn I'm pretty sure I don't.
 
ngn
the exceptions are the two 0s, denormals (if supported), nans and infinities
 
Right, my examples were only for illustration.
 
ngn
so, 16 has a unique representation
 
1:42 PM
Right.
 
currently spending a day looking at the polyglot
it just has everything, including ESCAPE
 
However, very small numbers can have non-unique representation.
 
ngn
@Adám example?
i thought only 0 and nan have non-unique representations
 
@Adám does not exist
best is O(n log log n), from here
 
@ngn Ah, looks like I mixed up things. Decimal floats have this issue.
@StackMeter Stalin sort is O(n)
 
1:47 PM
lol
 
@Adám yes but that doesn't return all n items
whatever's left in the gulag may or may not be unsorted
 
So?
 
here's another O(N) sorting algo (O(1) even!)
x=>[]
 
if it's not sorted, you have to sort it again
 
@StackMeter One doesn't go to Gulag to stay; one goes to die.
 
1:49 PM
@Adám not historically true
many escaped
 
@hyper-neutrino Hitler sort!
 
x=>x[0] \o/
 
@hyper-neutrino what about the ENTIREITY OF THE REST OF THE LIST
 
Gone, reduced to atoms.
 
sorry for shouting, but a sort is not a sort unless it works with 100% accuracy on 100% of the list 100% of the time
 
1:51 PM
@hyper-neutrino Primogeniture sort?
@StackMeter It does, though.
 
ngn
monkey-patch the cmp() function to always return -1 to fool any potential tests. what would this algorithm be called? :)
 
"digging yourself a deeper and deeper hole" sort?
 
@Adám that works on (100/len(x))% of the list, and as we all know, 1/x tends to 0, so 100/x tends to 0
 
yes i have been very busy lately
i would come back, but recently I am busy at school and stuffs
 
Mean sort, O(n): Replace all values with the average of the list.
CMC: Implement mean sort.
 
1:54 PM
@Adám Assuming we're given n as an input, I think Jelly and it outputs n+1
 
@Adám Æmṁ in Jelly
 
ngn
lazy sort - return instantly, and later sort the first i+1 elements when result[i] is accessed
 
Nice sort, O(1): Tell the list that it's beautiful just the way it is and doesn't need to be in any other order.
 
@ngn don't think that would work very well :P
 
@Adám take a look at this
 
ngn
1:56 PM
@hyper-neutrino this sorting algorithm believes that all array elements are born equal :)
 
In, there are two things that you must have to be a sorting algorithm.

1) The output must be in NONDECREASING ORDER - no element x > y if index(x) < index(y)

2) The output must be a PERMUTATION of the input, i.e. NO ELEMENT MUST BE SKIPPED, DUPLICATED OR REPLACED.

therefore your "sorts" are not sorts, but imposter sorts.
 
I hope you do realize we're (at least I'm) joking...
 
ik
just felt the need to say
 
@Adám APL, 8 bytes: (≢⍴+/÷≢)
(are the brackets needed?)
 
ngn
@StackMeter well, at least the small-domain algorithms (counting sort, dutch flag, radix..) are serious
 
2:01 PM
@ngn yes, but those fit the criteria
and radix sort is life
 
wait radix sort is linear? wat
 
@hyper-neutrino if all the numbers fit into a single base-c digit
 
realistically, it's n log n
 
radix is definitely logarithmic from what i remember for avg case
something (n+m)*log b or whatever
 
2:03 PM
however, there are improvements to radix sort that allow you to get n log log n for all numbers b where the word length is > log n
 
ngn
@hyper-neutrino it's linear in n (the length of the array) on the assumption that its elements are below a certain limit
 
hmm okay, I see
 
@hyper-neutrino nope
 
okay. It wasn't working when I just tried ⎕← ≢⍴+/÷≢ 1 2 3 5 probably because then the whole thing becomes a chain of monads but idk what's the requirement when actually submitting as a solution
 
the actual algorithm is a mix of radix sort and merge sort, which, in conjunction, push it down to n log^2 n
at least that's what I think log^2 n is
 
2:06 PM
CMQ: I optimised an algorithm from O(n²) to O(n) and then my colleague argued the commit message was wrong because the array size was constant so both were O(1). Who was right?
 
@pxeger what was the algortihm
because I think it's still O(n)
 
@hyper-neutrino when submitting as a solution you can assign the train to a variable without brackets
 
ngn
@pxeger your boss when he said stop arguing about nonsense and get back to work :)
 
it was a string internment/caching initiialisation routine
 
so you can omit them
 
2:07 PM
@ngn lol
 
ah, okay thanks
 
@pxeger I'm saying O(n)
 
n was like 600
 
so O(600)?
 
even if N is small and fixed the TC of an algorithm is still just based on the size in theory is it not?
 
2:09 PM
yup, O(360000) -> O(600)
 
like, if you nested loop thrice through a list even if it has like 4 elements it's still a cubic-time algorithm
 
Well theoretically any algorithm with limited input size can be O(1)
 
you can say the runtime in practice doesn't make a difference because the array is constant and small, but the compexity doesn't care
 
@hyper-neutrino true
@hyper-neutrino complexity cares not for your mortal, limited size input
I am dropping gems here
 
broke: program doesn't work at all
woke: O(infinity) time complexity
 
2:13 PM
lol
@Razetime infinity is a constant so that's still O(1)
4
 
genius
 
infinity is strictly not a constant
 
you mean O(n^infinity
 
infinity + 1 = infinity
this makes it not a constant
 
2:17 PM
So O(n) then
I see
still better than O(n!)
 
infinity != any n
you can only approach infinity
infinity is an expression that will always be higher than any weight you compare to it
 
well if adding any constant to it returns it
it must be O(n)
you probably meant O(n^n^n^n^n... infinity times)
 
are you reading anything i am saying
 
I am
what is infinity in terms of n then
since n is what we measure time complexity
 
> what is infinity in terms of n
it isn't
that's the point
 
2:23 PM
so if it's not any nc, n^c, or n+c (c is a constant or an expression of one of those types), it's a constant
 
Infinity isn't a proper number that can be manipulated like other numbers
 
and?
 
that makes it not fit in any of your formats
 
JS: const x = Infinity; ergo infinity is a constant
 
@pxeger e x a c t l y
 
2:26 PM
noo mr patrick pls
 
If you have an infinite list, then O(n)=O(infinity)
@Razetime ???
 
@user I presume Razetime was referring to me (my name is Patrick)
 
I would like to make bpa.st/A37Q in-place. Can anyone see how to do it?
 
no his name is the krusty krab
@felipa what does "in-place" mean
 
@felipa what do you mean by in-place? Do you mean non-recursive?
 
2:29 PM
@Razetime Oh, spongebob
 
@felipa copy the list
 
@Razetime I mean that it only uses the list that it is given and doesn't make any new ones
@pxeger ^^^
@StackMeter in-place means no new lists
 
oh partitioning without extra lists
 
why would you want to do that?
 
it needs to reorder profits_weights
 
2:30 PM
maybe use index values instead of lists?
 
I'm pretty sure it would be slower
 
@Razetime yes exactly
 
he wants a quicksort like paritioning thing
which will be faster
 
@pxeger why would it be slower? quicksort is famously done in-place
@Razetime exactly yes
 
why would in-place be faster
 
2:31 PM
@cairdcoinheringaahing I think you meant: "can get away without subjects in English if don't give a shit"
 
ngn
@felipa what is stopping you from making it in-place?
 
creating extra arrays and populating them with values is definitely less efficient than modification
 
unless you're working with log (n) to begin with
which, if you're sorting you can't
@Razetime copying surely is a constant time thing
 
Unless I'm misunderstanding what the algorithm is supposed to do, you would have to insert items in the middle of the list which is probably slower than allocating some new ones
 
or at worst linear
 
2:33 PM
@ngn I think I can do the partitoning with something like bpa.st/MDTQ
 
@StackMeter How?
 
@ngn but I am not sure how to plug it all together
 
It's O(n) because you go through the entire list
 
just add a new pointer to the list
 
That's not copying
 
2:33 PM
@user oh
 
do you know how memory works?
 
evidently lmao
 
You don't need to know how memory works
 
and add extra time because you are adding to a list based on a condition
 
2:33 PM
ok
but conditions are constant
 
ok how do you copy N elements without going through all N of them lol - it has to be linear
 
you check one item
 
maybe I should have asked an in-place challenge
 
ngn
@felipa that looks remarkably similar to the code @Anush posted a couple of days ago
 
If you just make a new pointer, modifying the new list would modify the old one and vice versa
 
2:34 PM
@ngn it's the same code
 
it's like copying your house and giving it to a friend by just cutting a new key
(no it isn't, but i wanted to give a garbage analogy)
 
but I can't see quite how to make it all work
 
oh
ok
 
@hyper-neutrino It's not a bad analogy. I once tried copying my friend's house and burning it down but accidentally just burned his house down instead :/
4
 
ah, yeah, I hate it when that happens
 
ngn
2:36 PM
@felipa first step - simplify :) you don't need 5 cases in that while loop - i think only 2 will do
 
it's not constant, but it's linear, and any sorting algorithm is linear at best
 
@hyper-neutrino When you get 3 stars after posting obvious starbait? Yeah
:P
 
@ngn if you can see how to do it, I would love help
don't make me ask SO :)
 
@user imo, the star comes at the moment you least expect it to
 
not really in this case
 
2:37 PM
@user meh who cares if it's star bait when it's also just funny
 
@ngn at least I have completely working code to start with :)
 
^^^
@Razetime Fair enough :P
 
@felipa then if your code works you'd ask CR not SO i think :P
 
@hyper-neutrino :)
 
idk CR's scope too well though ¯\_(ツ)_/¯
 
2:38 PM
@hyper-neutrino Don't ever suggest using CR, they'll hunt you down and format all your golfed code if you do :P
 
ngn
@felipa you mean the working code is the one that makes new arrays?
 
@felipa creating a new list isn't going to increase the time complexity except by a linear factor, and any sorting algorithm is linear at absolute best, so it's effectively constant
 
@ngn yes
@StackMeter right but I care about constant factors today :)
 
@StackMeter i suggest reading about algorithm design properly before saying things
 
2:41 PM
it's not every day that I care about constant factors but I do care today
 
@Razetime wdym?
@Razetime I've read several different articles trying to find the best sort today
 
@StackMeter it really does depend on the input
data that is almost sorted can be sorted more quickly by timsort for example
 
@felipa how?
 
@StackMeter see above
ints can be sorted very quickly by radix sort but string sorting may be faster by another method
etc.
@user :)
I like running automatic formatters on codegolf answers
 
@felipa really fun on perl
 
2:45 PM
You...what?!?1!
 
@Razetime I didn't even know there were perl formatters!
 
more often than not they do nothing
or they absolutely break the program
 
@Razetime for which language?
 
most languages
 
ngn
@felipa do you really need middlepart? would it ruin the algorithm if it's considered part of largepart (or smallpart)?
 
2:46 PM
js, ruby, perl, so on
even C
 
Ruby too?
 
formatters aren't used to seeing an entire program written in a for loop
 
@ngn You might be able to merge them but it's part of the logic. "while cum_weight < capacity and middlepart:" is an important loop
the key point is that at some point we need to deal with a fractional part of an item
if it's fast and in-place I can be flexible :)
@ngn I can give more test cases if that is helpful
 
ngn
@felipa yes please
@felipa anush's version partitions only into >=pivot and <pivot
 
@ngn they may be cleverer than me :)
 
ngn
2:51 PM
but their code didn't work :)
 
@hyper-neutrino Is JoKing the new hive mind now?
 
@ngn so only cleverer in parts :)
I really like anush's partitioning. It feels they are on the right lines because it looks like quicksort's partitioning in spirit
 
@cairdcoinheringaahing We are all JoKing, just as we are all caird and lyxal and hyper and WW, because we are all one entity controlled by the Supreme Leader Redwolf Programs
 
> We are all joking
 
Except for Tim. Screw Tim.
 
2:54 PM
I think this describes 97% of all conversation here :P
 
lmao
 

« first day (3799 days earlier)      last day (416 days later) »