This weekly roundup thread is intended for all culture war posts. 'Culture war' is vaguely defined, but it basically means controversial issues that fall along set tribal lines. Arguments over culture war issues generate a lot of heat and little light, and few deeply entrenched people ever change their minds. This thread is for voicing opinions and analyzing the state of the discussion while trying to optimize for light over heat.
Optimistically, we think that engaging with people you disagree with is worth your time, and so is being nice! Pessimistically, there are many dynamics that can lead discussions on Culture War topics to become unproductive. There's a human tendency to divide along tribal lines, praising your ingroup and vilifying your outgroup - and if you think you find it easy to criticize your ingroup, then it may be that your outgroup is not who you think it is. Extremists with opposing positions can feed off each other, highlighting each other's worst points to justify their own angry rhetoric, which becomes in turn a new example of bad behavior for the other side to highlight.
We would like to avoid these negative dynamics. Accordingly, we ask that you do not use this thread for waging the Culture War. Examples of waging the Culture War:
-
Shaming.
-
Attempting to 'build consensus' or enforce ideological conformity.
-
Making sweeping generalizations to vilify a group you dislike.
-
Recruiting for a cause.
-
Posting links that could be summarized as 'Boo outgroup!' Basically, if your content is 'Can you believe what Those People did this week?' then you should either refrain from posting, or do some very patient work to contextualize and/or steel-man the relevant viewpoint.
In general, you should argue to understand, not to win. This thread is not territory to be claimed by one group or another; indeed, the aim is to have many different viewpoints represented here. Thus, we also ask that you follow some guidelines:
-
Speak plainly. Avoid sarcasm and mockery. When disagreeing with someone, state your objections explicitly.
-
Be as precise and charitable as you can. Don't paraphrase unflatteringly.
-
Don't imply that someone said something they did not say, even if you think it follows from what they said.
-
Write like everyone is reading and you want them to be included in the discussion.
On an ad hoc basis, the mods will try to compile a list of the best posts/comments from the previous week, posted in Quality Contribution threads and archived at /r/TheThread. You may nominate a comment for this list by clicking on 'report' at the bottom of the post and typing 'Actually a quality contribution' as the report reason.
Jump in the discussion.
No email address required.
Notes -
verify() only really exists as an O(n) operation unless someone is trying to be dumb.
sort() can be done inefficiently if someone does not know much about sorting, but there is an O(n) solution waiting to be found; it can even be done in-place.
Sort is just pull off one side, compare to other side, put the smaller on stack, check next on that side compare to other side put smaller on stack repeat right? Probably a way to do less compares. For in place I'm not sure on the cost of shifts for just comparing the next element you're iterating through from left to opposite end.
Yes, if you have two sorted lists, you can combine them into one sorted list just by comparing the next element in both and putting the smaller in the list. (Merge Sort implementations rely on this.)
I thought through my in-place implementation some more and I am becoming skeptical of it. It might be possible in place but I think it means having three lists to compare (the two original and a third you build up as you march along the line). Same big-O technically but might require twice as many compares.
It's definitely possible to do in O(n) in-place, but I don't think there's a workable solution that involves only processing each element once (but I think there is one that involves processing each element at most twice).
That said I expect
return sorted(nums)
is probably as fast as or maybe even faster than the clever solution in practice.More options
Context Copy link
More options
Context Copy link
More options
Context Copy link
More options
Context Copy link