[HN Gopher] Using Scheme to Find the Median of Two Sorted Intege...
___________________________________________________________________
Using Scheme to Find the Median of Two Sorted Integer Lists
Author : erwald
Score : 37 points
Date : 2021-06-05 10:00 UTC (13 hours ago)
(HTM) web link (www.erichgrunewald.com)
(TXT) w3m dump (www.erichgrunewald.com)
| cousin_it wrote:
| Fun problem, conceptually easy but very prone to off-by-one
| errors. I think it's a bit easier to implement median using kth.
| Also it doesn't need recursion, one loop with fixed space usage
| is enough. Here's my JS code: function
| kth2(a,b,k) { var
| ai=0,aj=a.length,bi=0,bj=b.length,d=1; while (true) {
| if (ai==aj) return b[bi+d*k]; if (bi==bj) return
| a[ai+d*k]; var m=d*(aj-ai),n=d*(bj-bi);
| if (k<(m+n)/2) [ai,aj,bi,bj,d,k] =
| [aj-d,ai-d,bj-d,bi-d,-d,m+n-1-k]; var
| ak=Math.floor((m+1)/2),bk=Math.floor((n+1)/2); if
| (d*a[ai+d*ak-d]<d*b[bi+d*bk-d]) [ai,k] = [ai+d*ak,k-ak];
| else [bi,k] = [bi+d*bk,k-bk]; } }
| function median2(a,b) { var n = a.length+b.length;
| if (n%2 == 1) return kth2(a,b,(n-1)/2); else return
| (kth2(a,b,n/2-1)+kth2(a,b,n/2))/2; }
| prezjordan wrote:
| Found the APL programmer
| mike_kamau wrote:
| Could you please add a description to your solution?
| soegaard wrote:
| Here is a Racket (/Scheme) version of the JavaScript solution
| with a thorough explanation.
|
| http://pasterack.org/pastes/80529
|
| Note that this solution is using a standard imperative style,
| with a loop over that narrows down the location of the sought
| of element in two subvectors of a and b.
| cousin_it wrote:
| Wow! Yes, this is all exactly right.
| qsort wrote:
| "Fun", "conceptually easy" and "very prone to off-by-one or
| other trivial errors" is basically a description of 99% of the
| problems on LeetCode.
|
| The last one is particularly annoying because most problems
| could be easily tweaked with e.g. restrictions on the size of
| input or test cases to avoid those issues.
| rav wrote:
| My favorite problem involving Two Sorted Integer Lists is "Sort
| X+Y": Given sorted lists X and Y, each of length N, produce the
| list of N^2 pair-sums in sorted order. Specifically X+Y is the
| set {a + b for a in X and b in Y}. It seems like you should be
| able to solve it without relying on a sorting algorithm, since
| the input lists are already sorted. However, it's unknown if
| there is a faster algorithm than simply constructing X+Y directly
| and running a sorting algorithm.
| whatshisface wrote:
| Produce N sorted lists by adding each element in X to the
| elements of Y. Then mergesort them. Since the blocks you're
| starting with are runs than one element, you're guaranteed to
| save the last few (log2 N) steps of recursion. That's faster,
| although it only a constant factor.
| [deleted]
| bobthepanda wrote:
| Couldn't you construct a list of lists, where each is the
| output of one entry x + Y, and then just merge those lists like
| one would merge two sorted lists? (Basically just popping off
| the smallest head at any given time)
|
| You need to do the construction anyways (after all you need the
| elements of X+Y and you can't get them without summing)
| bjornsing wrote:
| If the "lists" are not random access, and you know their lengths,
| then why not just traverse them in parallel? I find it hard to
| believe you can do it faster than that, and it's super simple...
| yakubin wrote:
| What do you mean by "traverse them in parallel"? You want to
| find the medians of the two lists independently and then
| somehow combine them? How?
| Jtsummers wrote:
| You have two indices, one for each list, updated separately.
| Iterate through a lost until it's next element is larger than
| the current element in the other list. Iterate through it
| until the same condition. Keep going until your present
| position is at the halfway point, the you've got your median.
|
| They don't mean parallel like two thread, though you could
| use two coroutines or a similar mechanism.
| yakubin wrote:
| Thanks. That makes sense. The "in parallel" certainly threw
| me off.
|
| Although in the article the author at some point switches
| from lists to vectors, which changes the whole task, and
| allows for a more efficient implementation (even if it's an
| answer to a different question).
| erwald wrote:
| traversing them won't get you O(log(m+n)) complexity.
| walshemj wrote:
| Bit surprised that this
|
| "Getting the median of a single sorted list is trivial: it is
| either the central value if the list has an odd-numbered length,
| or the mean of the two central values otherwise."
|
| Is stated with no proof its not something I recall from collage
| IncRnd wrote:
| That is the definition of median. You might be confusing the
| definition of median with mean or mode.
| walshemj wrote:
| Thank you I was
| occamrazor wrote:
| It's the definition of median. It doesn't need a proof.
| zikzak wrote:
| It's been 20+ years but this still sounds familiar. Might just
| be the "that's sounds right so I'll assume I knew it" bias that
| makes educated people susceptible to subtle propaganda, though.
| :)
| qsort wrote:
| _sorted_
| casion wrote:
| That's what the median is! The middle number in a sorted list.
| frumiousirc wrote:
| The proof is by definition.
| true1true1true1 wrote:
| Related comic #3951_(en)_ABOUT TOLERANCE AND UNDERSTANDING...
| okt.16
|
| > //www.bilder-upload.eu/bild-cfb913-1622910941.png.html
|
| (-:
___________________________________________________________________
(page generated 2021-06-05 23:02 UTC)