News for hackers. Stuff that matters.
Re:F (2006) by 1vuio0pswjnm7 on Friday August 21, 2020 @07:26PM (#24239965)
It is often said that K can beat the speed of C for some tasks.

The name of this site is "nsl" for No Stinking Loops.

Here is an array programming challenge for the K programmers reading this thread.

There are two large files A and B.

   File A
   AAAbjhOJxxxWXrCHt
   AAAsofxxxLqKbYOAwLMHG
   AAACgxxxOea
   AAAwfHjDtoJc
   AAAiCfYnbVXWhuvtEx
   AAAkzzQwvf
   AAAdjLalKFapoYAcGE
   AAAthGazmnfK
   etc.

   File B
   AAAwfHjDtoJc
   AAAbjhOJxxxWXrCHt
   AAAiCfYnbVXWhuvtEx
   AAACgxxxOea
   AAAkzzQwvf
   etc.
The task is:

What are the lines in B that are not in A?

Something like

   grep -vf B A
But without the stinking loops!

EDIT: File A,B formatting

Re:F (2006) by xashor on Friday August 21, 2020 @08:15PM (#24240345)
In J (which might be slower than K) with excessive comments for a one-liner:

    echo@> (2{ARGV) -.&([: <;._1 LF, 1!:1) (3{ARGV)
    NB.    2nd arg                          3rd arg
    NB.              g&f execute f for each, then g on both
    NB.                              1!:1 read file
    NB.                          LF, prepend newline
    NB.                 [: <;._1 split based on first char
    NB.             -.  remove right elements from left array
    NB. echo@> echo each line
    exit 0
On two ~1.6MB files with ~15k lines (both the same except 3) I had lying around:

    $ time j9 -c ./pseudo_grep.ijs test_b test_a
    …
    real   0m0.064s
    user   0m0.032s
    sys    0m0.017s
    $ time grep -vf test_b test_a
    …
    real   0m5.815s
    user   0m5.234s
    sys    0m0.576s
Note that most of the script is for loading each file into an array of lines. Most work is done by -. on the two arrays, which is exactly what you asked for, e.g. 0 1 2 3 4 -. 2 4 is 0 1 3. https://code.jsoftware.com/wiki/Vocabulary/minusdot#dyadic
Re:F (2006) by DylanDmitri on Friday August 21, 2020 @08:43PM (#24240539)
In loopless Python:

    set(open('file_b')) - set(open('file_a'))
Slower than J by a factor of 2-3, but still 10x faster than grep:

    real    0m0.128s
    user    0m0.078s
    sys     0m0.063s
This would make a good Rosetta Code prompt.
Re:F (2006) by throwaway_pdp09 on Saturday August 22, 2020 @04:02AM (#24242541)
I didn't know you could simply open a file and setify it. Interesting. & neat.
Re:F (2006) by fennecfoxen on Saturday August 22, 2020 @08:06AM (#24243566)
You can setify any iterable. File handles are iterables that return a line at a time. Tada!
Re:F (2006) by throwaway_pdp09 on Saturday August 22, 2020 @08:58AM (#24243818)
> File handles are iterables...

I did not know that. Assumed you had to somehow wrap them first. Very useful, thanks!

Re:F (2006) by qmmmur on Friday August 21, 2020 @09:31PM (#24240814)
this is cheeky, I like it
Re:F (2006) by dunefox on Saturday August 22, 2020 @06:20AM (#24243116)
This is only fast because it hits C underneath, isn't it?
Re:F (2006) by kbenson on Friday August 21, 2020 @10:12PM (#24240993)
That grep is not doing the same thing as the code, nor necessarily what the exercise requires. By default, grep tests patterns, so it's turning all those entries into individual regular expressions. You want to use fgrep, or the -F flag to make it treat all the source matches as fixes strings.

In my simple test, that resulting in grep running in 44% of the prior amount of time it required (still more than python though).

Re:F (2006) by 1vuio0pswjnm7 on Saturday August 22, 2020 @12:16AM (#24241506)
Apologies for the careless omission. I tested the difference on a larger job; with grep 28s, with fgrep 22s.
Re:F (2006) by kbenson on Saturday August 22, 2020 @02:49PM (#24246278)
I think theres probably a sweet spot in how large the files are compared to the method used, because eventually disk access may dominate the running time. Putting files on a ram disk (/dev/shm on some distros) would help.

I tested with files just over 2 MB on a small Digital Ocean VM. Depending on disk speed, based on running time I suspect you ran on files at least an order of magnitude larger. What time did python run in for those? Seeing memory usage from time might be illuminating for these tasks too. Using 4x the disk size in memory is fine for a couple MB file, but less so for a couple GB file (in which case creating a bloom filter or trie might be better, but I really have no idea if Pythons set functions do that already).

Re:F (2006) by jodrellblank on Friday August 21, 2020 @08:57PM (#24240643)
In Dyalog APL, which isn't K:

          A←⊃⎕nget 'C:\test\a.txt' 1
          B←⊃⎕nget 'C:\test\b.txt' 1
          A~B
    ┌─────────────────────┬──────────────────┬────────────┐
    │AAAsofxxxLqKbYOAwLMHG│AAAdjLalKFapoYAcGE│AAAthGazmnfK│
    └─────────────────────┴──────────────────┴────────────┘
Read each file as a nested vector of lines. A without B, like set operations.
Re:F (2006) by waynesonfire on Friday August 21, 2020 @08:18PM (#24240368)
i'm not drinking this kool-aid. you're in a strange place if you think it's loops that are the cause of software complexity.
Re:F (2006) by smabie on Friday August 21, 2020 @10:15PM (#24241006)
Loops are 100% the worst offenders of software complexity. Loops and tail recursion are the most powerful constructs we have, and are too powerful for the vast majority of problems. When using the principle of least power you find that a loop or tail recursive function is exceptionally rare.
Re:F (2006) by lultimouomo on Saturday August 22, 2020 @02:38AM (#24242189)
They might be a great source of algorithmic complexity, but I would argue that by far the most part of software complexity is architectural, not algorithmic.
Re:F (2006) by smabie on Saturday August 22, 2020 @03:36AM (#24242435)
When you can reduce the amount of code you have to write by 100x, architecture no longer becomes important. When all programs are so short, they become very cheap. And when they become cheap, they are easy to replace and rewrite. At this point, architecture becomes irrelevant because you've removed all abstractions in the first place.

If the components of your company's system never are longer than a page or two of code, rewrites become trivial, making planning for the future unnecessary. This is the real promise and value of array languages.

Or put more simply, the size of a code base is the dominant factor in its complexity. Less code is less complex code, is better code.

Also, loops imply mutation, which is the second biggest indicator of complexity. Mutation kills code bases and kills projects. When you decide to never use a loop and to never mutate, you're on the right path. Now the next step is to try and remove as many lines of code as humanly possible.

A good way to measure how you're doing is by comparing the size of your gzipped (or zipped or whatever) codebase to its uncompressed form. If they are close in size, you know you are on the right track. Or in other words, you want the size of your code base to be close to its Kolmogorov complexity.

Re:F (2006) by jodrellblank on Saturday August 22, 2020 @09:58AM (#24244179)
Less code to write, less code to read, less code to maintain, executes faster[1]. What's not to like?

What about someone who thinks "if" is a big source of software complexity? https://www.youtube.com/watch?v=z43bmaMwagI - talk is "If considered harmful: How to eradicate 95% of all your bugs in one simple step - Jules May".

[1] in interpreted languages, anything you can push down for the runtime to do instead of writing that same code in the interpreted language, tends to execute faster. e.g. my_string.count('c') in Python compared to a `for` loop over the characters written in Python.

Re:F (2006) by shrubble on Friday August 21, 2020 @11:29PM (#24241275)
The traditional unix command for this is 'comm' and it is usually installed by default.
Re:F (2006) by 1vuio0pswjnm7 on Saturday August 22, 2020 @12:06AM (#24241459)
How would you solve this task with comm?

For that sort of comparison I usually use

   diff -y A B
Re:F (2006) by drran on Saturday August 22, 2020 @02:42AM (#24242206)

    comm -13 A B
Re:F (2006) by 1vuio0pswjnm7 on Saturday August 22, 2020 @03:07AM (#24242316)
I totally screwed up the example. I wanted list B to have some items not in A, e.g.,

   echo AAA_not_in_A_xxx >> B

   fgrep -vf A B
Result should be

    AAA_not_in_B_xxx
Re:F (2006) by chrispsn on Friday August 21, 2020 @09:45PM (#24240881)
In k9 it should be:

    A_B
Re:F (2006) by chrispsn on Saturday August 22, 2020 @12:46AM (#24241617)

     `A 0: ("some";"lines";"are";"here");     / write to file A
     `B 0: ("more";"lines";"follow";"here");  / write to file B
     _/ 0:' `A`B                              / read files A, B and find lines of B that are not in A
    more  
    follow