Algorithms Every Programmer Should Know: Reservoir Sampling

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by eridius on Friday March 06, 2015 @04:31PM (#9159685)

If N is sufficiently larger than k, it might actually be faster to do something like

  let count = query("SELECT COUNT() FROM table")
  let indices = computeIndices(count, k)
  for index in indices {
    results.append(query("SELECT * FROM table LIMIT 1 OFFSET ?", index))
  }

Yeah, you're doing a bunch of queries, but you're removing all of copying all the data from all the rows.

[ Parent | on HN ]

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by dbenhur on Saturday March 07, 2015 @02:36AM (#9161324)

OFFSET j is O(j) in most RDMSes. You made an o(N/2 * k) algorithm given j is a random number in [0,N).

[ Parent | on HN ]

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by eridius on Saturday March 07, 2015 @08:02PM (#9163935)

Depending on the size of k compared to N, and how much data is in each row, it's still probably better than iterating over the entire contents of the table.

Also, do you have any citation for OFFSET j being O(j)? I can believe that's the case, but it also seems fairly obvious to optimize OFFSET for the case of a non-filtered unordered SELECT (or one ordered in a way that matches an index).

[ Parent | on HN ]

Re:Algorithms Every Programmer Should Know: Reservoir Sampling by detrino on Saturday March 07, 2015 @09:06PM (#9164147)

Assuming that the DB is backed by some kind of tree, it would need to maintain extra metadata in the branches in order to achieve even O(log n) offsetting. For this reason I could understand it being a linear operation.

[ Parent | on HN ]