Python optimization: Choosing between dictionary or list of list

user_7271239 0
Viewed 260

I'm new to python3, and I got a question about different approaches to solve this problem. question about using different data structure. My question is how to compare tradeoff with different sampling techniques

I used a dictionary data structure in my program to first solve this problem. Then I tried to rewrite it using only the list data structures. I tried to consider the benefits of sorting, and I cannot tell what's the difference between the two approaches. It does not seem to make that much difference between the two approaches.

Method 1. I use dictionary to create my histogram key and value pairs inside my histogram

Method 2 takes in a source text in string format and returns a list of lists in which the first element in each sublist is the word and the second element is its frequency in the source texts

# This program Analyze word frequency in a histogram
# sample words according to their observed frequencies
# takes in a source text in string format and returns a dictionary
# in which each key is a unique word and its value is that word's
# frequency in the source text
import sys
import re
import random
import time

def histogram(source_text):
    histogram = {}
    # removing any sort of string, removing any other special character
    for word in source_text.split():
        word = re.sub('[.,:;!-[]?', '', word)

        if word in histogram:
            histogram[word] += 1
        else:
            histogram[word] = 1
    return histogram

def random_word(histogram):
    probability = 0
    rand_index = random.randint(1, sum(histogram.values()))
    # Algorithm 1
    for (key, value) in histogram.items():
        for num in range(1, value + 1):
            if probability == rand_index:
                if key in outcome_gram:
                    outcome_gram[key] += 1
                else:
                    outcome_gram[key] = 1
                # return outcome_gram
                return key
            else:
                probability += 1

#    Method 2 takes in a source text in string format and returns a list #of lists
#    in which the first element in each sublist is the word and the #second element is its frequency in the source texts

  # Algorithm 2
    # for word in histogram:
    #     probability += histogram[word]
    #     if probability >= rand_index:
    #         if word in outcome_gram:
    #             outcome_gram[word] += 1
    #         else:
    #             outcome_gram[word] = 1
            # return word


if __name__ == "__main__":
    outcome_gram = {}
    dict = open('./fish.txt', 'r')
    text = dict.read()
    dict.close()

    hist_dict = histogram(text)
    for number in range(1, 100000):
        random_word(hist_dict)
python-3.x list dictionary python
2 Answers

Which is more readable? I would think that the dictionary version is easier to understand. Also, note that you could pass the list of 2-tuples from your second method to the dict constructor to reproduce the output from the first method. This should give you an idea of how these two implementations are roughly equivalent at least in some respect. Unless this is causing a performance issue, I wouldn't worry too much about it.

The strength of Python is that you can write the same code, in a readable fashion, in five lines. 

import re, random
from collections import Counter

def histogram(text):
    clean_text = re.sub('[.,:;!-[]?', '', text)
    words = clean_text.split()
    return Counter(words)

def random_word(histogram):
    words, frequencies = zip(*histogram.items())
    return random.choices(words, frequencies, k=1)
user_22475500

I would generally agree with Joran Beasley's comment above, it is often better to solve your problem, and then go back and refactor for efficiency later.

When working with histograms I would recommend checking out Counter inside the collections module. The collections module as a whole is really great, and has a lot of useful containers.

Another cool module is the Timeit module, which allows you to run small timing experiments on code snippets. Keep in mind execution speed is dependent on a lot of factors that are not necessarily in your program's control.

user_54315540
Related