Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a CSV file users.csv with a list of userNames, userIDs, and other data:

username, userid, sidebar_side, sidebar_colour
"John Lennon", 90123412, "left", "blue"
"Paul McCartny", 30923833, "left", "black"
"Ringo Starr", 77392318, "right", "blue"
"George Harrison", 72349482, "left", "green"

In another file toremove.txt I have a list of userIDs:

30923833
77392318

Is there a clever, efficient way to remove all the rows from the users.csv file which contain the IDs in toremove.txt? I have written a simple Python app to parse the two files and write to a new file only those lines that are not found in toremove.txt, but it is extraordinarily slow. Perhaps some sed or awk magic can help here?

This is the desired result, considering the examples above:

username, userid, sidebar_side, sidebar_colour
"John Lennon", 90123412, "left", "blue"
"George Harrison", 72349482, "left", "green"
share|improve this question
    
Maybe you should share your python script. I suspect there's something wrong there, like being O(N²) Although if you are keeping and removing millions of records magic won't help too much. – Ángel Jul 17 '14 at 18:28
    
The script is in fact O(n<sup>2</sup>): n for the users.csv file's lines, and n for the lines of toremove.txt. I'm not really sure how to do it with lower complexity. The gist of it is: for u in users: if not any(toremove in u): outputfile.write(u). I can post it to Code Review. – dotancohen Jul 17 '14 at 19:21
1  
I would read toremove.txt, saving the entries as keys. Iterate users.csv, printing those where the id is not in the dict. You get O(n) processing for both toremove.txt and users.csv, and O(n) memory usage for toremove.txt (which is probably relatively small) – Ángel Jul 17 '14 at 19:28
    
@Ángel: Yes, that is exactly how the script works! – dotancohen Jul 17 '14 at 19:32
1  
Checking if a key exists in a dictionary, equals to a hash table check, which is (almost) O(1). On the other hand, if it needs to iterate the items to remove, that's O(m) – Ángel Jul 17 '14 at 22:25
up vote 9 down vote accepted

With grep, you can do:

$ grep -vwF -f toremove.txt users.txt 
username, userid, sidebar_side, sidebar_colour
"John Lennon", 90123412, "left", "blue"
"George Harrison", 72349482, "left", "green"

With awk:

$ awk -F'[ ,]' 'FNR==NR{a[$1];next} !($4 in a)' toremove.txt users.txt 
username, userid, sidebar_side, sidebar_colour
"John Lennon", 90123412, "left", "blue"
"George Harrison", 72349482, "left", "green"
share|improve this answer
    
Perfect, thank you! – dotancohen Jul 17 '14 at 12:43
    
@terdon: Dang! I was going to say that. Note, though, that Gnouc’s answer (arguably) does what the question asks for, but it might not be what the user wants. – Scott Jul 17 '14 at 15:59
    
The awk solution is highly sensitive to the files’ being formatted exactly as shown in the question. Most glaringly, if a name is just one word/token (i.e., it contains no spaces; e.g., "Bono") or is more than two tokens (i.e., it contains more than one space; e.g., "Sir Paul McCartney"), it will go through even if the userid matches. Less obviously, the same thing happens if there is no space between the first comma and the userid, or if there is more than one space (e.g., "John Lennon", 90123412, …). – Scott Jul 17 '14 at 16:00
    
@Scott: Yes, it's the reason I put awk solution behind grep – cuonglm Jul 17 '14 at 16:14

Here’s Gnouc’s awk answer, modified to be space-blind:

awk -F, 'FNR==NR{a[$1];next} !(gensub("^ *","",1,$2) in a)' toremove.txt users.csv

Since it uses only commas (and not spaces) as delimiters, $1 is "John Lennon", $2 is  90123412 (with a leading space), etc.  So we use gensub to remove any number of leading spaces from $2 before we check whether it (the userid) was in the toremove.txt file.

share|improve this answer
    
You might be able to do some other clever stuff here (just thinking out loud) like parsing out the "exact piece" of the string that shouldn't match, and comparing that with the associative array, or what not. – rogerdpack Oct 16 '15 at 17:47
    
I believe that's what I'm doing.  What did you have in mind? – Scott Oct 16 '15 at 17:51
    
Yes you are. I was just referring to if you needed to do something more funky like removing the first half of a line or anything like that (downcasing, etc. stackoverflow.com/a/4784647/32453) just specialized parsing – rogerdpack Oct 16 '15 at 17:54

OK a ruby way: if you have a list of strings in a file, and you want to remove all lines from another file that even contain any string in the first file (in this case removing "file2" from "file1") ruby file:

b=File.read("file2").split # subtract this one out
remove_regex = Regexp.new(b.join('|'))
File.open("file1", "r").each_line do |line|
  if line !~ remove_regex
    puts line
  end
end

unfortunately with a large "to remove" file this seems to degrade complexity-wise to O(N^2) (my assumption is the regexp has a lot of work to do), but still might be useful to someone out there (if you want more than removing full lines). It might be faster in certain cases.

Another option if you're going for speed is to use the same hash checking mechanism, but to carefully "parse" the line for strings that might match, then comparing them with your hash.

In ruby, might look like this:

b=File.read("file2").split # subtract this one out
hash={}
for line in b
  hash[line] = 1
end

ARGF.each_line do |line|
  ok = true
  for number in line.scan(/\d{9}/)
    if hash.key? number
      ok=false
    end
  end
  if (ok)
    puts line
  end
end

See also Scott's answer, its similar to the awk answers proposed hither thither, and avoids O(N^2) complexity (phew).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.