3 ms·

That K solution is O(n^2) complexity, vs O(n*log(n)) for Lisp. I kinda hate it how all the K advocacy always uses old-style languages with small stdlibs, _and_

• rak1507 3y ago
  I'm pretty sure the K solution is O(n)? Both group and unique should be O(n).
  • theamk 3y ago
    Pretty sure it's impossible to calculate unique/group in O(n), unless either the data is pre-sorted, or your range is extremely limited (and problem says nothing about this), so it has to be at least O(nlog(n)) For K, I think the solution is to find unique first (nlog(n)), the for each unique value go over the list and find how many input values match (multiply by n). That's O(n^2 * log(n)), even worse than I wrote initially.
    • mlochbaum 3y ago
      No, the k solution computes the unique elements and group independently. #:'=v[;1] uses group for the first column, and ?v[;1] uses unique for the second. (;) is list notation. Your analysis of the algorithm you've described is also wrong: it would be O(n*log(n) + n^2), or O(n^2), because the second part loops over unique elements and not operations performed by unique. In the random-access model, hash table construction/lookup is O(n) average case for n elements, if the elements have bounded size. More generally, it's linear in the total size of the input. If the strings are very long it can take a while to hash and compare them, but there's never a log(n) factor. Maybe you're confusing this with results from comparison sorting? Both solutions are O(n) with the assumptions of random-access memory and bounded string size (or hash/comparison time), which I consider to be pretty standard.
• adw 3y ago
  Python has https://docs.python.org/3/library/collections.html#collections.Counter https://docs.python.org/3/library/collections.html#collectio... (which I'm sure would raise objections over the volume of code – https://github.com/python/cpython/blob/main/Lib/collections/__init__.py#L545 https://github.com/python/cpython/blob/main/Lib/collections/... – but a lot of it is providing syntactic sugar).
• foomanmanfoo 3y ago
  Unsure of performance but using R's `data.table`(which has uses beyond this example so installing this library shouldn't be a one off) library(data.table) v <- rbindlist(list( data.table(e1=1, string='one'), data.table(e1=1, string='two'), data.table(e1=1, string='three'), data.table(e1=1, string='one'), data.table(e1=1, string='four'), data.table(e1=1, string='two')) ) v[, list(counter= sum(e1)),by= string]
• dreamcompiler 3y ago
  Lisp solution looks like O[n] to me. Where does the log[n] factor come from?