2

I have a text file that contains thousands of words, e.g:

laban
labrador
labradors
lacey
lachesis
lacy
ladoga
ladonna
lafayette
lafitte
lagos
lagrange
lagrangian
lahore
laius
lajos
lakeisha
lakewood

I want to iterate every word over itself so i get:

labanlaban
labanlabrador
labanlabradors
labanlacey
labanlachesis
etc...

In bash i can do the following, but it is extremely slow:

#!/bin/bash
( cat words.txt | while read word1; do
  cat words.txt | while read word2; do
    echo "$word1$word2" >> doublewords.txt
 done; done )

Is there a faster and more efficient way to do this? Also, how would i iterate two different text files in this manner?

1
  • Can you fit the list into memory?
    – Thanatos
    Jul 24, 2015 at 5:49

5 Answers 5

2

If you can fit the list into memory:

import itertools

with open(words_filename, 'r') as words_file:
    words = [word.strip() for word in words_file]

for words in itertools.product(words, repeat=2):
    print(''.join(words))

(You can also do a double-for loop, but I was feeling itertools tonight.)

I suspect the win here is that we can avoid re-reading the file over and over again; the inner loop in your bash example will cat the file one for each iteration of the outer loop. Also, I think Python just tends to execute faster than bash, IIRC.

You could certainly pull this trick with bash (read the file into an array, write a double-for loop), it's just more painful.

4
  • Thanks. That worked pretty well. What if i wanted to iterate two different text files instead of the same text file?
    – user3552978
    Jul 24, 2015 at 9:17
  • Load both files with the with… lines and use itertools.product(words1, words2) instead of itertools.product(words, repeat=2). (see ["docs.python.org/2/library/itertools.html"][here] )
    – styko
    Jul 24, 2015 at 9:35
  • Thanks for your help but i couldn't quite get this going. i tried loading both files using the same "with" but it didn't quite work (e.g. with open('a', 'w') as a, open('b', 'w') as b:). Tried 2 separate "with" loops and no luck either.
    – user3552978
    Jul 24, 2015 at 10:29
  • If you want to open two files for reading, you'll want 'r' as the second argument to open. ('w' is "write", and will delete the file!)
    – Thanatos
    Jul 24, 2015 at 14:13
1

It looks like sed is pretty efficient to append a text to each line. I propose:

#!/bin/bash

for word in $(< words.txt)
do 
    sed "s/$/$word/" words.txt;
done > doublewords.txt

(Do you confuse $ which means end of line for sed and $word which is a bash variable).

For a 2000 line file, this runs in about 20 s on my computer, compared to ~2 min for you solution.


Remark: it also looks like you are slightly better off redirecting the standard output of the whole program instead of forcing writes at each loop.


(Warning, this is a bit off topic and personal opinion!)

If you are really going for speed, you should consider using a compiled language such as C++. For example:

vector<string> words;
ifstream infile("words.dat");
for(string line ; std::getline(infile,line) ; )
    words.push_back(line);
infile.close();

ofstream outfile("doublewords.dat");
for(auto word1 : data)
    for(auto word2 : data)
        outfile << word1 << word2 << "\n";
outfile.close();

You need to understand that both bash and python are bad at double for loops: that's why you use tricks (@Thanatos) or predefined commands (sed). Recently, I came across a double for loop problem (given a set of 10000 points in 3d, compute all the distances between pairs) and I successful solved it using C++ instead of python or Matlab.

4
  • Thanks. I'll give your solution a go. Also, how would i iterate two different text files instead of the same text file over itself?
    – user3552978
    Jul 24, 2015 at 9:34
  • The two occurences of words.txt are independant. Just replace the first one by words1.txt and the second one by words2.txt.
    – styko
    Jul 24, 2015 at 9:37
  • I think i'm doing something wrong here. Is this correct? #!/bin/bash for word in $(< doublewords.txt) do sed "s/$/$word/" numbers.txt; done > words-numbers.txt
    – user3552978
    Jul 24, 2015 at 11:00
  • @user3552978 Did you mean to put (< doublewords.txt) instead of (< words.txt). Other than that, it looks correct (except lack of line breaks, which I assume are just from the comment).
    – Qualia
    Jul 24, 2015 at 23:11
0

If you have GHC available, Cartesian products are a synch!

Q1: One file

-- words.hs
import Control.Applicative
main = interact f
    where f = unlines . g . words
          g x = map (++) x <*> x

This splits the file into a list of words, and then appends each word to each other word with the applicative <*>.

Compile with GHC,

ghc words.hs

and then run with IO redirection:

./words <words.txt >out

Q2: Two files

-- words2.hs
import Control.Applicative
import Control.Monad
import System.Environment
main = do
    ws <- mapM ((liftM words) . readFile) =<< getArgs
    putStrLn $ unlines $ g ws
    where g (x:y:_) = map (++) x <*> y

Compile as before and run with the two files as arguments:

./words2 words1.txt words2.txt > out

Bleh, compiling?

Want the convenience of a shell script and the performance of a compiled executable? Why not do both?

Simply wrap the Haskell program you want in a wrapper script which compiles it in /var/tmp, and then replaces itself with the resulting executable:

#!/bin/bash
# wrapper.sh

cd /var/tmp
cat > c.hs <<CODE
# replace this comment with haskell code
CODE
ghc c.hs >/dev/null
cd - >/dev/null
exec /var/tmp/c "$@"

This handles arguments and IO redirection as though the wrapper didn't exist.

Results

Timing against some of the other answers with two 2000 word files:

$ time ./words2 words1.txt words2.txt >out
3.75s user 0.20s system 98% cpu 4.026 total

$ time ./wrapper.sh words1.txt words2.txt > words2
4.12s user 0.26s system 97% cpu 4.485 total

$ time ./thanatos.py > out
4.93s user 0.11s system 98% cpu 5.124 total

$ time ./styko.sh
7.91s user 0.96s system 74% cpu 11.883 total

$ time ./user3552978.sh
57.16s user 29.17s system 93% cpu 1:31.97 total
2
  • awesome! how about 2 different text files?
    – user3552978
    Jul 24, 2015 at 10:08
  • @user3552978 I've now improved the Haskell script for two different text files and updated the results.
    – Qualia
    Jul 24, 2015 at 23:02
0

You can do this in pythonic way by creating a tempfile and write data to it while reading the existing file and finally remove the original file and move the new file to original file.

import sys
from os import remove
from shutil import move
from tempfile import mkstemp


def data_redundent(source_file_path):
    fh, target_file_path = mkstemp()
    with open(target_file_path, 'w') as target_file:
        with open(source_file_path, 'r') as source_file:
            for line in source_file:
                target_file.write(line.replace('\n', '')+line)
    remove(source_file_path)
    move(target_file_path, source_file_path)

data_redundent('test_data.txt')
0

I'm not sure how efficient this is, but a very simple way, using the Unix tool specifically designed for this sort of thing, would be

paste -d'\0' <file> <file>

The -d option specifies the delimiter to be used between the concatenated parts, and \0 indicates a NULL character (i.e. no delimiter at all).

1
  • This only outputs the doubles like "labanlaban" but not things like "labanlacey". (It just doubles each line; the OP appears to want a Cartesian product.)
    – Thanatos
    Jul 24, 2015 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.