This repository has been archived by the owner on Sep 25, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LinkedList.py
132 lines (122 loc) · 3.29 KB
/
LinkedList.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#!/usr/local/bin/python3.8
# -*- coding: utf-8 -*-
import sys
import os
import re
import time
import random
class Node(object):
def __init__(self, word, line):
self.word = word
self.line = [line]
self.right = None
class LinkedList(object):
def insert(self, root, word, line):
if root == None:
return Node(word,line)
elif root.word < word:
root.right = self.insert(root.right,word,line)
elif root.word > word:
aux = root
root = Node(word,line)
root.right = aux
else:
if line not in root.line:
root.line.append(line)
return root
def search(self,root,word):
if root == None:
return None
elif root.word < word:
return self.search(root.right,word)
elif root.word > word:
return None
else:
return root
def readText(src,LL,root):
with open(src,'r',encoding="utf-8") as f:
i=0
for line in f:
newLine = re.sub('[(),;.""'']','',line)
for word in newLine.upper().split():
root=LL.insert(root,word,i)
i+=1
return LL,root
def showLines(instructions,LL,root):
if len(instructions)==2:
r = LL.search(root,instructions[1])
if r == None:
sys.stdout.write("-1\n")
else:
i=0
for l in r.line:
if instructions[0] != None:
i+=1
if i < len(r.line):
sys.stdout.write(str(l)+" ")
else:
sys.stdout.write(str(l)+"\n")
def showAssoc(instructions,LL,root):
if root != None and len(instructions)==3 and instructions[2].isnumeric():
target = instructions[1]
lineNumber = int(instructions[2])
r = LL.search(root,target)
if r != None and lineNumber in r.line:
if instructions[0] != None:
sys.stdout.write("ENCONTRADA.\n")
else:
if instructions[0] != None:
sys.stdout.write("NAO ENCONTRADA.\n")
def selectRandomWords(src,n):
words = list()
line = list()
with open(src,'r',encoding="utf-8") as f:
lines = f.readlines()
for i in range(n):
k = str()
while k == '\n' or k == '':
k = random.choice(lines)
line = re.sub('[(),;.""'']','',k).upper().split()
word = random.choice(line)
words.append(word)
return words,random.randint(0,len(lines))
def stats_LinkedList(PATH,textName,iterLINHAS,iterASSOC,iterations):
print(" ▶︎ LinkedList:")
null = None
instructions = list()
root = None
LL = LinkedList()
instructions.append(None)
for i in range(iterations):
root = None
LL = LinkedList()
times = list()
t = time.process_time()
LL,root = readText(PATH+textName,LL,root)
times.append(time.process_time()-t)
print("\tAVERAGE INSERT TIME: {}".format(sum(times)*1000/len(times)))
for i in range(iterations):
words,null = selectRandomWords(PATH+textName,iterLINHAS)
times = list()
t = time.process_time()
for word in words:
if len(instructions) == 1:
instructions.append(word)
else:
instructions[1] = word
showLines(instructions, LL, root)
times.append(time.process_time()-t)
print("\tAVERAGE LINHAS TIME: {}".format(sum(times)*1000/len(times)))
for i in range(iterations):
words,line = selectRandomWords(PATH+textName,iterASSOC)
times = list()
t = time.process_time()
for word in words:
if len(instructions) == 2:
instructions[1] = word
instructions.append(str(line))
else:
instructions[1] = word
showAssoc(instructions, LL, root)
times.append(time.process_time()-t)
print("\tAVERAGE ASSOC TIME: {}\n".format(sum(times)*1000/len(times)))