Question

Hey I have a task which consists of two part. Part A asks for writing a program of WORD & LINE CONCORDANCE APPLICATION in python which I have completed it.

Now the second part has given 5 dictionary implementation codes namely as: (ChainingDict, OpenAddrHashDict with linear probing, OpenAddrHashDict with quadratic probing, and 2 tree-based dictionaries from lab 12 (BST-based dictionary implementation) and asks for my above program WORD & LINE CONCORDANCE APPLICATION  to use these implemented code and show the time taken by each dictionary implemented code.

Here is the image of second part:

Part B. DICTIONARY COMPARISON We have 5 dictionary implementations from lab 10: ChainingDiet, OpenAddr HashDict with linear probing, OpenAddr HashDict with quadratic probing, and 2 tree-based dictionaries from lab 12 (BST-based dictionary implementation) and lab 13 (AVL-based dictionary implementation) None of these should need to be modified much. You just use their dictionary operations. Time your word-concordance application using all five dictionary implementations to complete the following table: (FYI, for WarAndPeace.txt there are about 2,700 stop words and less than 20,000 non-stop words). Both the stop words and non-stop words should use the same type of dictionary (e.g., both are different ChainingDict's). Have just one word-concordance program with 5 pairs of dictionaries with all but one pair commented out, i.e., the dictionary pair you are timing is the only pair uncommented. Dictionary ADT Implementation Used Word-concordance Program Execution Time (seconds) ChainingDict (hash table sizes 2**15= 32768) OpenAddrHashDict with linear probing (hash table sizes 2**15= 32768) OpenAddrHashDict with quadratic probing (hash table sizes 2**15= 32768) Dictionaries implemented using BSTS Dictionaries implemented using AVL trees

Now I need help to how to use the implemented code in my WORD & LINE CONCORDANCE APPLICATION in order to time the 5 dictionary implemented code separately.

Please it would be better if you show me the code of one dictionary implementation (open_addr_hash_Dictionary) with my WORD & LINE CONCORDANCE APPLICATION and show me that how much time it took.

I will attach all the necessary files here.

Here is my Word & Line Concordance Application which was asked in first part which I implemented it:

import re
from collections import defaultdict
def concordance():
    wordConcordanceDict = defaultdict(list)

    with open('stop_words_small.txt') as sw:
        words = (line.strip() for line in sw)
        stop_words = set(words)

    with open('small_file.txt') as f:
        for line_number, line in enumerate(f, 1):
            words = (re.sub(r'[^\w\s]','',word).lower() for word in line.split())
            good_words = (word for word in words if word not in stop_words)
            for word in good_words:
                wordConcordanceDict[word].append(line_number)

    for word in sorted(wordConcordanceDict):
        print('{}: {}'.format(word, ' '.join(map(str, wordConcordanceDict[word]))))

concordance()

Here is the python open_addr_hash_Dictionary python file which should be used with my word & line concordance code to show it's time execution:

from entry import Entry

class OpenAddrHashDict(object):

EMPTY = None
DELETED = True

def __init__(self, capacity = 8,
hashFunction = hash,
linear = True):
self._table = [OpenAddrHashDict.EMPTY] * capacity
self._size = 0
self._hash = hashFunction
self._homeIndex = -1
self._actualIndex = -1
self._linear = linear
self._probeCount = 0

def __getitem__(self, key):
"""Returns the value associated with key or
returns None if key does not exist."""
if key in self:
return self._table[self._actualIndex].getValue()
else:
return None

def __delitem__(self, key):
"""Removes the entry associated with key."""
if key in self:
self._table[self._actualIndex] = OpenAddrHashDict.DELETED
self._size -= 1

def __setitem__(self, key, value):
"""Inserts an entry with key/value if key
does not exist or replaces the existing value
with value if key exists."""
entry = Entry(key, value)
if key in self:
self._table[self._actualIndex] = entry
else:
self._table[self._actualIndex] = entry
self._size += 1
  
def __contains__(self, key):
"""Return True if key is in the dictionary; return
False otherwise"""
entry = Entry(key, None)
self._probeCount = 0
# Get the home index
self._homeIndex = abs(self._hash(key)) % len(self._table)
rehashAttempt = 0
index = self._homeIndex

# Stop searching when an empty cell is encountered
while rehashAttempt < len(self._table):
self._probeCount += 1
if self._table[index] == OpenAddrHashDict.EMPTY:
self._actualIndex = index
return False
elif self._table[index] == entry:
self._actualIndex = index
return True
  
# Increment the index and wrap around to first
# position if necessary
rehashAttempt += 1
if self._linear:
index = (self._homeIndex + rehashAttempt) % len(self._table)
else:
# Quadratic probing
index = (self._homeIndex + (rehashAttempt ** 2+ rehashAttempt) // 2) % len(self._table)

# An empty cell is found, so store the item
return False

def __len__(self):
return self._size

def __str__(self):
resultStr = "{"
for item in self._table:
if not item in (OpenAddrHashDict.EMPTY,OpenAddrHashDict.DELETED):
resultStr = resultStr + " " + str(item)
return resultStr + " }"

def __iter__(self):
"""Iterates over the keys of the dictionary"""
pass

def homeIndex(self):
return self._homeIndex

def probeCount(self):
return self._probeCount

def loadFactor(self):
return len(self._table)/self._size
  
  
def main():
"""Uses an example data set from Chapter 19."""
table = OpenAddrHashDict(8, lambda x : x)
for item in (range(10, 71, 10)):
table[item] = ""
print( "item:", item, "Home:", table.homeIndex(), "Probes:", table.probeCount(), \
"Load factor:", table.loadFactor())
print( table)
table[2] = ""
print( "item:", item, "Home:", table.homeIndex(), "Probes:", table.probeCount(), \
"Load factor:", table.loadFactor())
print( table)
return table

if __name__ == "__main__": t = main()

  

Here is the entry python file which is imported in Open_addr_hash_Dictionary file above.

class Entry(object):
def __init__(self, key, value):
self._key = key
self._value = value

def getKey(self):
return self._key

def getValue(self):
return self._value

def setValue(self, newValue):
self._value = newValue
  
def __eq__(self, other):
if not isinstance(other, Entry):
return False
return self._key == other._key

def __str__(self):
return str(self._key) + ":" + str(self._value)

Here is the stop_words_small text which is used in my word & line concordance application as stopping word:

a
about
be
by
can
do
i
in
is
it
of
on
the
this
to
was

Here is the proj7small text which is also used in my word & line concordance application to find the main words and their line number:

This is a sample data (text) file to
be processed by your word concordance program.

The real data file is much bigger

Please I repeat I need a code that uses my WORD & LINE CONCORDANCE APPLICATION and open_addr_hash_Dictionary to show me the execution time of open_addr_hash_Dictionary.

Thanks,

  

Answer 1

Part 2 of the given question says to measure time taken by various dictionary implementations. Basically, it means you need to replace the defaultdict used in your WORD & LINE CONCORDANCE APPLICATION with all these given dictionary implementations, one by one.

As you have asked to explain with open_addr_hash_Dictionary, I've used it in the code below.

def concordance():
    wordConcordanceDict = OpenAddrHashDict(100000)

    with open('stop_words_small.txt') as sw:
        words = (line.strip() for line in sw)
        stop_words = set(words)

    with open('small_file.txt') as f:    
        for line_number, line in enumerate(f, 1):
            words = (re.sub(r'[^\w\s]','',word).lower() for word in line.split())
            good_words = (word for word in words if word not in stop_words)
            for word in good_words:
                # it doesn't work as defaultdict. So we have to check
                # if key is present in dictionary or not
                try:
                    # key is present
                    wordConcordanceDict[word].append(line_number)
                except:
                    # key is not present, so we create a new key
                    wordConcordanceDict[word] = [line_number]
    
    # the given implementation of dictionary don't have a method to get all keys/ items as there in python dictionaries.
    # instead, there's a function to get all key, value pairs as a string
    # we call that method and convert it to a dictionary
    wordConcordanceDict = re.sub(r', ',',',wordConcordanceDict.__str__()).split()[1:-1]
    wordConcordanceDict = dict(x.split(":") for x in wordConcordanceDict)

    for word in sorted(wordConcordanceDict):
        print('{}: {}'.format(word, wordConcordanceDict[word].strip('[]')))


# import regex
import re

import OpenAddrHashDict
from open_addr_hash_dictionary import OpenAddrHashDict

# import time module
import time

# start time
start = time.time()

# given function call
concordance()

# end time
end = time.time()

# display time taken
print(end - start)

Comments have been added, wherever I made some edits.

What you have to do for remaining dictionary implementations?

Import all those dictionaries to word concordance program. Replace current dictionary with all the dictionary implementations that you need to time one by one.You might need to change the last line in concordance() function based on the implementation of the corresponding dictionary that you are using.