3
\$\begingroup\$

I've developed a script to randomly select 50 elements from a list of .txt files. This process is repeated 100 times. The script joins the randomly selected text files to one long string and then filters out the longest substring.

I want to run this script on a Droplet on Digital Ocean. The server, however, kills the script. When I randomly select only 3 elements, it works. Am I running out of memory? How can I tackle this problem?

Here are the files I randomly select items from. And this is my code:

# coding: utf-8

import glob
from collections import Counter
import pickle
import random

de_list_soz = pickle.load(open('de_list_soz.p', 'rb'))
str_seq_list = []

for str_seq in range(0,100):  
    #creating random list
    random_list = []
    for item in range(0,50):
       list_item = random.choice(de_list_soz)
       random_list.append(list_item)

    #creating long string
    long_str = ''
    for de in random_list:

        input_file = open('txt_sr_de/txt_sr_de/' + de, 'r')
        text = input_file.read()
        text = text.replace('\n', ' ').replace('\xa0', '').replace('  ', '')
        #Removing these automated notifications
        text = text.replace('Wichtiger Hinweis:Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren.Zurück zur Einstiegsseite Drucken Grössere Schrift', '')
        text = text.replace('Vorwärts ähnliche Leitentscheide suchenähnliche Urteile ab 2000 suchen Drucken nach oben', '')
        text = text.replace('Bundesgericht Tribunal fédéral Tribunale federale Tribunal federal', '')
        text = text.replace('Navigation Neue Suche Zurück zum Suchresultat Rang: Zurück 180', '')
        text = text.replace('Navigation Neue Suche Zurück zum Suchresultat Rang:1 ähnliche Leitentscheide suchenähnliche Urteile ab 2000 suchen Drucken nach oben', '')
        text = text.replace('  ', ' ')

        long_str = long_str + text

    times=3

    for n in range(1,int(len(long_str)/times+1)):
        substrings=[long_str[i:i+n] for i in range(len(long_str)-n+1)]
        freqs=Counter(substrings)
        if freqs.most_common(1)[0][1]<3:
            n-=1
            break
        else:
            seq=freqs.most_common(1)[0][0]


    str_seq_list.append(seq)


pickle.dump(str_seq_list, open('SOZIALRECHT_DE.p', 'wb'))
\$\endgroup\$
  • 1
    \$\begingroup\$ "Am I running out of memory?" How are we supposed to know? \$\endgroup\$ – BCdotWEB Mar 7 '17 at 9:54
  • \$\begingroup\$ I cannot check your files now, but if they are, say, 500k each, that means 500k * 50 = 25MiB. Then you get all sub-strings of every length. I'd say that begs for out-of-memory really quickly. As a side note, try to rename file to something like input_file and it would be nicer to use with on then input file. Last note: you have root access, just use dmesg and see if there's something there. \$\endgroup\$ – ChatterOne Mar 7 '17 at 10:09
  • \$\begingroup\$ More, try to fix your indentation, otherwise you code is double-off-topic for Code Review \$\endgroup\$ – Grajdeanu Alex. Mar 7 '17 at 10:19
  • \$\begingroup\$ Sorry, @Dex'ter I have fixed the indentation. \$\endgroup\$ – BarJacks Mar 7 '17 at 10:34
  • 2
    \$\begingroup\$ I think the question is on-topic for Code Review. The code is claimed to work properly for small cases; the concern is scalability. \$\endgroup\$ – 200_success Mar 7 '17 at 12:27
2
\$\begingroup\$

I just rewrote the way you search for the longest substring, to be honest i did not completly understand what you tried in your code, but from my perspectiv this is where your memory died. I also added some withs, you should see how they work, also follow the link in your questions comments.

In this code, a substring ends with a space " " or an line-break "\n"

import pickle
import random


def longest_substring(s: str) -> str:

    indx = 0
    lngth = 0

    tmpindx = 0
    tmplngth = 0

    for i, c in enumerate(s):

        if c == " " | c == "\n":

            if tmplngth > lngth:
                lngth = tmplngth
                indx = tmpindx

            tmplngth = 0
            tmpindx = i + 1

        else:
            tmplngth += 1

    return s[indx: indx + lngth]


with open('de_list_soz.p', 'rb') as o:
    de_list_soz = pickle.load(o)

str_seq_list = []

for str_seq in range(0, 100):
    # creating random list
    random_list = []
    for item in range(0, 50):
        list_item = random.choice(de_list_soz)
        random_list.append(list_item)

    # creating long string
    long_str = ''

    for de in random_list:

        with open('txt_sr_de/txt_sr_de/' + de, 'r') as input_file:
            text = input_file.read()

        text = text.replace('\n', ' ').replace('\xa0', '').replace('  ', '')
        # Removing these automated notifications
        text = text.replace('Wichtiger Hinweis:Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren.Zurück zur Einstiegsseite Drucken Grössere Schrift', '')
        text = text.replace('Vorwärts ähnliche Leitentscheide suchenähnliche Urteile ab 2000 suchen Drucken nach oben', '')
        text = text.replace('Bundesgericht Tribunal fédéral Tribunale federale Tribunal federal', '')
        text = text.replace('Navigation Neue Suche Zurück zum Suchresultat Rang: Zurück 180', '')
        text = text.replace('Navigation Neue Suche Zurück zum Suchresultat Rang:1 ähnliche Leitentscheide suchenähnliche Urteile ab 2000 suchen Drucken nach oben', '')
        text = text.replace('  ', ' ')

        long_str += text

    # here wo go search longest substring
    long_sub = longest_substring(long_str)

    # here we remove all occurrence of longest substring
    no_long_sub_long_str = long_str.replace(long_sub, "")

with open('SOZIALRECHT_DE.p', 'wb') as o:
    pickle.dump(str_seq_list, o)
\$\endgroup\$
  • \$\begingroup\$ Thanks so much @lex. What my code attempted to do was to pull out the 3 longest substrings in one long string. I don't understand what is going wrong in the code you kindly gave me. But it only every returns one long string. Without repetitions. \$\endgroup\$ – BarJacks Mar 20 '17 at 20:28
  • \$\begingroup\$ I went for your tasks description ` The script joins the randomly selected text files to one long string and then filters out the longest substring.` , seems i got this wrong. So you want to extract the longest substring which comes up a given number of times or you want to extract the given number of longest substrings? \$\endgroup\$ – SchreiberLex Mar 21 '17 at 8:37
  • \$\begingroup\$ I want to extract the longest substring which occurs at least three (or n) times in the long string. Background: I have 14'000 txt files dated from 2007 to 2016. And I want to understand whether there's a correlation between the amount of copy pasted elements and the date. In other words: Do more recents documents have more copy pasted elements. \$\endgroup\$ – BarJacks Mar 21 '17 at 11:13
  • \$\begingroup\$ Well then i have to admit my answer is not serving your question, i did misunderstood you. Anyways: the way you described this now makes me wonder what to concatenate all these files in one string. By kontext, the substring you go for would be maximum sized the Document itself, in case an entire Doc is copy and pasted. So you could reduce your sub-string-search on file basis. Also it might be an approach to search for a medium sized sub-string and check how far it could be extended to become the largest substring occuring in multiple files. Will tackle the coding later, give it a shot yourself \$\endgroup\$ – SchreiberLex Mar 21 '17 at 11:44
2
\$\begingroup\$

Since your code performs multiple things at once, you should split it into functions for readability. A first naive rewrite can yield:

from collections import Counter
import random


def filter_text(text):
    return (text
            .replace('\n', ' ')
            .replace('\xa0', '')
            .replace('  ', '')
            #Removing these automated notifications
            .replace('Wichtiger Hinweis:Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren.Zurück zur Einstiegsseite Drucken Grössere Schrift', '')
            .replace('Vorwärts ähnliche Leitentscheide suchenähnliche Urteile ab 2000 suchen Drucken nach oben', '')
            .replace('Bundesgericht Tribunal fédéral Tribunale federale Tribunal federal', '')
            .replace('Navigation Neue Suche Zurück zum Suchresultat Rang: Zurück 180', '')
            .replace('Navigation Neue Suche Zurück zum Suchresultat Rang:1 ähnliche Leitentscheide suchenähnliche Urteile ab 2000 suchen Drucken nach oben', '')
            .replace('  ', ' '))


def create_string_from_files(files, root='txt_sr_de/txt_sr_de', sample=50):
    #creating random list
    random_list = []
    for item in range(sample):
       list_item = random.choice(files)
       random_list.append(list_item)

    #creating long string
    long_str = ''
    for de in random_list:

        input_file = open(os.path.join(root, de), 'r')
        text = input_file.read()

        long_str = long_str + filter_text(text)
    return long_str


def extract_most_common_sequence(text, minimum_occurences=3, times=3):
    for n in range(1,int(len(text)/times+1)):
        substrings=[text[i:i+n] for i in range(len(text)-n+1)]
        freqs=Counter(substrings)
        if freqs.most_common(1)[0][1] < minimum_occurences:
            n-=1
            return seq
        else:
            seq=freqs.most_common(1)[0][0]


def main(files, repeat=100):
    str_seq_list = []

    for str_seq in range(repeat):  
        long_str = create_string_from_files(files)
        str_seq_list.append(extract_most_common_sequence(long_str))

    return str_seq_list


if __name__ == '__main__':
    import pickle
    de_list_soz = pickle.load(open('de_list_soz.p', 'rb'))
    str_seq_list = main(de_list_soz)
    pickle.dump(str_seq_list, open('SOZIALRECHT_DE.p', 'wb'))

Now we can start cleaning things up.

In create_string_from_files, you are basically reinventing random.sample:

>>> import random
>>> random.sample('abcdefghi', 4)
['h', 'e', 'c', 'f']

You also happen to open files but never close them: use the with statement to automatically handle that.

Lastly, concatenating long sentences manually is not memory efficient. Let's ask str.join to do it for us for now. But in order to do it nicely, we need to split the function further:

def read_and_filter_file(filename):
    with open(filename) as input_file:
        text = input_file.read()
    return filter_text(text)


def create_string_from_files(files, root='txt_sr_de/txt_sr_de', samples=50):
    return ''.join(
        read_and_filter_file(os.path.join(root, de))
        for de in random.sample(files, samples)
    )

The same kind of improvements can be made to the main function by replacing the "create empty list + for loop + append" template by a more efficient list-comprehension:

def main(files, repeat=100):
    return [
        extract_most_common_sequence(create_string_from_files(files))
        for _ in range(repeat)
    ]

The extract_most_common_sequence function can also be optimized by using some itertool recipe. I’m thinking about a variation of the pairwise recipe since your list-comprehension, with n being 2 is pretty much it. i.e. using:

>>> long_str = 'This is a test'
>>> n = 2
>>> [long_str[i:i+n] for i in range(len(long_str)-n+1)]
['Th', 'hi', 'is', 's ', ' i', 'is', 's ', ' a', 'a ', ' t', 'te', 'es', 'st']
>>> n = 4
>>> [long_str[i:i+n] for i in range(len(long_str)-n+1)]
['This', 'his ', 'is i', 's is', ' is ', 'is a', 's a ', ' a t', 'a te', ' tes', 'test']

So using something like:

def tuplewise(iterable, length):
    tees = itertools.tee(iterable, length)
    for i, t in enumerate(tees):
        for _ in xrange(i):
            next(t, None)
    return itertools.izip(*tees)

For Python 2 or:

def tuplewise(iterable, length):
    tees = itertools.tee(iterable, length)
    for i, t in enumerate(tees):
        for _ in range(i):
            next(t, None)
    return zip(*tees)

for Python 3, you can simplify the writting and save a bit on memory usage like so:

def extract_most_common_sequence(text, minimum_occurences=3, times=3):
    sequence = ''
    for n in range(1, int(len(text)/times+1)):
        freqs = Counter(tuplewise(text, n))
        (most_frequent, higher_frequency), = freqs.most_common(1)
        if higher_frequency < minimum_occurences:
            break
        sequence = ''.join(most_frequent)
    return sequence

Now I defined sequence = '' as a security measure in the unlikely event that the text is quite short an no letter appear more than twice. It's just to make the function return something in each and every cases.


Now that the code is more readable, let's tackle that memory issue of yours.

The thing to note is that aggregating the content of 50 files in one single string in memory is likely to blow things up. So instead, let's use some disk storage. We'll use the tempfile module for that. The idea is to store the filtered bits of text into a single file and read that file (over and over again) to get the desired most common sequence. We thus need to adapt our tuplewise a bit to either read one character at a time and yield words of the requested size or, better as I/O is concerned, repeatedly read a block of data of a fixed size and grab caracters out of it one by one to produce words of the desired size:

import os
import random
import itertools
import tempfile
from collections import Counter


def filter_text(text):
    return (text
            .replace('\n', ' ')
            .replace('\xa0', '')
            .replace('  ', '')
            #Removing these automated notifications
            .replace('Wichtiger Hinweis:Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren.Zurück zur Einstiegsseite Drucken Grössere Schrift', '')
            .replace('Vorwärts ähnliche Leitentscheide suchenähnliche Urteile ab 2000 suchen Drucken nach oben', '')
            .replace('Bundesgericht Tribunal fédéral Tribunale federale Tribunal federal', '')
            .replace('Navigation Neue Suche Zurück zum Suchresultat Rang: Zurück 180', '')
            .replace('Navigation Neue Suche Zurück zum Suchresultat Rang:1 ähnliche Leitentscheide suchenähnliche Urteile ab 2000 suchen Drucken nach oben', '')
            .replace('  ', ' '))


def read_and_filter_file(filename):
    with open(filename) as input_file:
        text = input_file.read()
    return filter_text(text)


def create_string_from_files(output, files, root='txt_sr_de/txt_sr_de', samples=50):
    for filename in random.sample(files, samples):
        output.write(read_and_filter_file(os.path.join(root, filename)))


def read_chunks(file_object, chunk_size, block_size=4096):
    word = file_object.read(chunk_size)
    yield word
    while True:
        data = file_object.read(block_size)
        if not data:
            return
        for character in data:
            # Drop first character and append the next one
            word = word[1:] + character
            yield word


def extract_most_common_sequence(input_file, minimum_occurences=3, times=3):
    input_file.seek(0, os.SEEK_END)
    file_size = input_file.tell()
    sequence = ''

    for n in range(1, int(file_size/times+1)):
        input_file.seek(0)  # Be sure to read the whole file each time
        freqs = Counter(read_chunks(input_file, n))
        (most_frequent, higher_frequency), = freqs.most_common(1)
        if higher_frequency < minimum_occurences:
            break
        sequence = most_frequent
    return sequence


def main(files):
    with tempfile.NamedTemporaryFile(mode='w+') as storage:
        create_string_from_files(storage, files)
        return extract_most_common_sequence(storage)


if __name__ == '__main__':
    import pickle
    de_list_soz = pickle.load(open('de_list_soz.p', 'rb'))
    str_seq_list = [main(de_list_soz) for _ in range(100)]
    pickle.dump(str_seq_list, open('SOZIALRECHT_DE.p', 'wb'))

I changed main into returning a single element rather than a whole list as it feels cleaner with this implementation. The whole repetition thing is done in the test code now.

\$\endgroup\$
  • \$\begingroup\$ Thanks @Mathias-Ettinger. This was amazingly helpful. I think I have learned a lot about coding in general going through what you have kindly provided. I'm not sure the 'extract_most_common_sequence' function is correct though. Or maybe the mistake is in the 'read_chunks' function. Basically, I seem to be received much shorting strings than with my clunky code. But thanks again. Your work is amazing! \$\endgroup\$ – BarJacks Mar 20 '17 at 20:31
  • \$\begingroup\$ @BarJacks Oh, right, re-reading your string manipulation thingy, its seems that I got it wrong the first time. I extract sequences like 0..n, n+1..2n, 2n+1..3n where you extract 0..n, 1..n+1, 2..n+2. Will edit something when I have some time. \$\endgroup\$ – Mathias Ettinger Mar 20 '17 at 20:43
  • \$\begingroup\$ Thanks a lot @mathias-ettinger, I have to call you a champion! \$\endgroup\$ – BarJacks Mar 21 '17 at 5:29
  • \$\begingroup\$ I'm truely struggling to understand and correct the 'read_chunks' and 'def extract_most_common_sequence' functions, so that they yield the longest strings and not substrings of the longest strings. \$\endgroup\$ – BarJacks Mar 22 '17 at 15:26
  • \$\begingroup\$ @BarJacks I changed the code to match your existing behaviour, check the edit. \$\endgroup\$ – Mathias Ettinger Mar 23 '17 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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