This is some code I made that creates every possible string from a given grammar and tries to find any that were created in two different ways. It is currently very slow as a result of nested for loops, but my knowledge of Python is too limited to know how to make it better. Currently, I just know that it works. Another possible that might be improved on is making a copy of a list (so that it doesn't edit parts it shouldn't), which for all I know has a vastly superior builtin-function
#🔒 Speed up code for finding ambiguous grammars
primal fable
frank wharfBOT
This is some code I made that creates every possible string from a given grammar...
@primal fable
Python help channel opened
wide moss
wow, the site really messed up the tabs
primal fable
Yeah, I say \t >>> spaces, but other people disagree 😢
primal fable
wow, the site *really* messed up the tabs
If it helps, this is it with spaces https://paste.pythondiscord.com/CMBA
pure hamlet
meCopy is supposed to flatten the lists? So, a list like
[[3, 5], 4]``` will turn into ```[3, 5, 4]``` if so, there's probably a built-in functionThere's something in itertools, but idk if it's faster
wide moss
you're doing a lot of (probably unnecessary) string conversions and evals, honestly i'm unsure what is going on
can you explain what these rules mean?
I'm assuming whatever is happening works
primal fable
meCopy is supposed to flatten the lists? So, a list like
```py
[[3, 5], 4]``` w...
It's supposed to make a deep copy, like .copy() but it makes everything inside the list into a copy
primal fable
can you explain what these rules mean?
I'm assuming whatever is happening works
Grammar rule, "Where you see an S, you can replace it with aS. When you see an S, you can replace it with T......"
wide moss
why is "aS" in a list?
pure hamlet
It's supposed to make a deep copy, like .copy() but it makes everything inside t...
There's a .deepcopy() method too :p
primal fable
💀
primal fable
why is "aS" in a list?
Because that represents a split on the "parse tree". The program is trying to find two separate ways to reach any string using the -> rules. To do that, it compares the parse trees of two identical string (when it finds one). The separate elements in the list are the paths it can go down, with the valid ones being those on the left side of the ->'s (S and T in this case). I believe if I were to do it differently it would not work
primal fable
There's a .deepcopy() method too :p
It gives me back AttributeError: 'list' object has no attribute 'deepcopy', is it not for lists?
This is what it was running
for string in history[-1].deepcopy():
I found a separate thing that's a function, I'll try it
copy.deepcopy() makes it work slightly faster, but it's comparatively a drop in the bucket
elder atlas
are these the same path or different paths?
abc -> abz -> azz
abc -> azc -> azz
primal fable
If b -> z and c -> z, they count as the same path. It's just ordering the moves in different ways
It's like saying "If you grab the flour before the sugar, you're still following the recipe". But if you put, say, brown sugar instead of sugar, it would count it as a different recipe
(Assuming you'd get the same cake/cookie/thing)
primal fable
are these the same path or different paths?
`abc -> abz -> azz`
`abc -> azc -> a...
If you're familiar with grammars from automata theory, it should make sense. The program tries to find if a grammar is ambiguous by finding duplicate string that are created in two different ways
elder atlas
your code is kind of hard to read
one thing that would help with that is improving the typehints, e.g. list isn't descriptive enough, it should be list[str] (or whatever is in the list)
wide moss
what even
elder atlas
someone else mentioned this, but you shouldn't be doing string manipulation on things that shouldnt be strings
elder atlas
what even
like these should be tuples of ints probably, not strings
that would make your code both easier to read and faster
primal fable
The reason it's formatted like [#][#][#] is because I use eval() to get the value at a part of history that I then use for comparing. How else should I do this?
elder atlas
if eval(f"string[1]{route}") == ru[0]:
```what is `string`?oh wow you're doing a really dense version of str.replace(a, b)
elder atlas
str.replace doesnt really work for applying production rules
primal fable
```py
if eval(f"string[1]{route}") == ru[0]:
```what is `string`?
It requires some explanation. history contains every string created by the program (like in your example abc abz azc azz). The most recent iteration is stored in a list at the end of history. for string in history[-1]: takes the most recent iteration and for every string (not the best name now that I think about it, looks like ['azz',['a',['z'],['z']]] for azz, string[0] is the flattened string and string[1] is the parse tree) it does ....
wide moss
ok, i am not very knowledgeable on what is going on. BUT after switching some lists to sets and caching some functions you can get pretty far regarding performance
elder atlas
are you familiar with dicts?
primal fable
Yes, but I thought they wouldn't be a super good fit, are they? (like I can use them but I like lists more so I'm a lot more familiar with them)
wide moss
for starters, you can use it to check if it's inside the list without double checking every single item in the list again. and since the lookup time is O(1) the checking time doesnt scale exponentially i think
(his2ry being a dict[str, list])
elder atlas
yeah the general approach I would use is
produce terminal string:
if terminal string in dict:
check whether paths are the same (if its possible for the production code to produce the same path twice, otherwise checking for a collision alone is sufficient)
else:
dict[terminal_string] = path
```then all that's left is the production code (presumably you already have that) and checking equality between pathslooking up the terminal string in the dict is O(1)
primal fable
for starters, you can use it to check if it's inside the list without double che...
That... would be a good fit. How would I create/add to his2ry?
wide moss
well, during creation. I don't know the name of what you're doing so i just named it term. I also made another variable called all_terms that holds a set[str]```py
if len(yeahlist) != 0:
for route in yeahlist:
for ru in rules:
if eval(f"string[1]{route}") == ru[0]:
thing = meCopy(string[-1])
# print(f"thing: {thing}")
change_value_by_indexes(
thing, changePathFormat(route), meCopy(ru[-1])
)
term = convertParseToString(thing)
thingc = meCopy(thing)
all_terms.add(term) # <--
his2ry[term] = thingc # <--
dummy.append([term, thingc])
thing = []
by the way doing the if len(yeahlist) != 0 is probably a little useless
because if it was empty then no iterations would happen anyways
primal fable
Oh, yeah that would be the case
wide moss
ok well that theory was a little right
elder atlas
can you show how your code would represent this production?
abc -> abz -> azz
primal fable
ambigCheck(('a','z'),('r','b','c'),[('r',['a','b','c']),('b',['z']),('c',['z'])],'r')
From what I know, grammars can only have 1 start character, so r -> abc ...
The parse tree for that would be [['a',['z'],['z']]] at the end
['r']
V
[['a','b','c']]
V
[['a','b',['z']]]
V
[['a',['z'],['z']]]
It seems that I broke something, now my program doesn't detect a duplicate
elder atlas
ok so
[
('r',['a','b','c']),
('b',['z']),
('c',['z'])
]
```is the path takenyou said
[
('r',['a','b','c']),
('c',['z']),
('b',['z']),
]
```should be the same pathYes, those are the rules it would you
Now that I think about it, it does break when you have two equivalent outputs
b's and c's rules would do that
elder atlas
yah, because (if I understand your code correctly) you're doing a simple equality check between these two here
if iteration[1] != itera[1]:
Yeah, I remember because I specifically didn't want it to flag two equivalent rules . Like if there was S -> aS twice I didn't want it to flag it. Is that wrong? If the same grammar rule is stated twice, does that matter?
Now that I think about it, when I learned about parse trees, we never recorded what rule was used, just that a rule was used
elder atlas
so then before you continue, I would take a step back and think about which trees you want to consider equivalent and how you could check
a good approach to this sort of thing is to come up with some sort of normalized form such that two equivalent trees will always be written the same way
if you represent all your trees in this normal form, you can reduce the problem of checking whether two trees are equivalent to checking whether their normal forms are literally equal
this usually involves imposing some sort of order
e.g. checking whether two sets of letters are equivalent is kind of hard because two sets are equivalent no matter their order
but you can make it easier by turning each set into a string of letters in alphabetical order
two sets are equivalent if and only if the resulting strings of letters are equal
the alphabetized string of letters would be called a normal form
primal fable
That sounds like a good idea. I'll need to think about it so I can figure out the best way to go about it. When I do, I should probably make another help request, since it'll likely be in over an hour since I need to eat dinner. Thank you so much for your help!
elder atlas
np
primal fable
well, during creation. I don't know the name of what you're doing so i just name...
Wow, compared to how I was doing it previously, this is lightning fast. Now, instead of the second part being far slower than the first, it's the other way around!
wide moss
i can send you my current version if you want. there's still loads of places to improve but tbh idrk what the heck is going on lol
primal fable
Oh, there are other parts that you improved? It would be great if you could
wide moss
i might have messed some things up in my fiddling but the major milestones seemed consistent so
primal fable
i might have messed some things up in my fiddling but the major milestones seeme...
Hmm, it might be that I have some other part added in, but it's running slightly slower. I'll see what I had changed
The only thing that I can find is that I completely replaced meCopy with copy.deepthink() while you changed the definition, but I doubt that that lead to that much difference. I'll send what I have in my code currently
wide moss
I'll be honest im not sure why you're copying as much as you are
after this line, dummy is not used so that can be just given i think (And i hope stuff in history is not modified after its creation!)
primal fable
Some of them might be unnecessary, I was just dealing with an issue and was just going around with a shotgun
wide moss
oh wow yea that cut of a not-insignificant amount of time
(left: copy, right: no copy)
primal fable
Sheeeesh
Wow
And the output is the same
Shoot, I also realized in my code I forgot to swap some instances of meCopy from the old version
wide moss
i tried switching them, all it did was create slowdowns
probably due to checks copy.deepcopy does or something
primal fable
Oh, by the old meCopy I meant the version I had originally before learning about copy.deepcopy()
wide moss
from what i can tell, the only thing in that first loop that needs to be copied is the thing
everything else is just read, so they don't need to be copied
but im not sure, might wanna verify that
primal fable
It seems like it still does work, but for some reason there is a slight increase to the amount of time it takes
Not much, 5.07 to 5.44, but it adds up
Ah, and now it runs faster, so it was just something that happened then
Now it's overall faster
Yeah, it's just faster period
Thank you very much! It runs sooo much faster now
wide moss
no problem!
primal fable
Lol
wide moss
now that's real
btw maybe use time.perf_counter instead of time.time
it's a little more accurate, but for why i dunno
primal fable
Alright, I'm just always recommend time.time
wide moss
!d time.time
frank wharfBOT
wide moss
!d time.perf_counter
frank wharfBOT
primal fable
Oh, should I use perf_counter_ns instead?
wide moss
eh all three works
frank wharfBOT
wide moss
!e ```py
print("{" + ":".join(map(str, range(1, 10))) + "}")
@wide moss :white_check_mark: Your 3.12 eval job has completed with return code 0.
{1:2:3:4:5:6:7:8:9}
Instead of append?
Wait, does join work for lists?
wide moss
yup
# From
def changePathFormat(index_string):
indexes = [i for i in index_string.split('][')]
indexes[0] = indexes[0][1:]
indexes[-1] = indexes[-1][:-1]
stri = ""
for i in indexes:
stri += i + ','
return stri[:-1]
# To
def changePathFormat(index_string):
indexes = [i for i in index_string[1:-1].split('][')]
return ",".join(indexes)
Geez, that's a whole lot cleaner
wide moss
it works on any kind of iterable, including lists, sets, dict keys
even strings
!e print(":".join("what"))
frank wharfBOT
@wide moss :white_check_mark: Your 3.12 eval job has completed with return code 0.
w:h:a:t
So changePathFormat, is there another place it my code where it'd work?
primal fable
Oh right, I remember you had it in your code
wide moss
!e ```py
def walk(tree: list):
for item in tree:
if isinstance(item, list):
yield from walk(item)
else:
yield item
print(list(walk([1, 2, 3, [2, 4, 5, 6, [7, 8, 9]]])))
@wide moss :white_check_mark: Your 3.12 eval job has completed with return code 0.
[1, 2, 3, 2, 4, 5, 6, 7, 8, 9]
That looks like it flattens the list?
wide moss
yes basically, but with a generator
primal fable
I'm sorry, my teacher hasn't taught me what a generator is
wide moss
ah that's no problem
primal fable
Everything after convertParseToString's first line is dead code, right?
wide moss
yes, everything after the return
oh wait if you havent done generators yet you might want to change walk to return a list
if you're submitting this to your teacher
idk
primal fable
Oh no, this is related to class but something that I'm doing independent of it
wide moss
oh, ok
Converting route to a list, then a string, then back to a list is kind of redundantpy change_value_by_indexes(thing, changePathFormat(route), meCopy(ru[-1])) Try changing changePathFormat to return a list of indexes, then change_value_by_indexes to just accept a list of indexes```py
def changePathFormat(index_string: str) -> list[int]: ...
def change_value_by_indexes(lst: list, indexes: list[int], new_value): ...
Got it, now it's implemented. Now that I think about it, I can just eliminate changePathFormat by putting [int(i) for i in index_string[1:-1].split('][')] in its place
wide moss
yes, true
primal fable
It's likely just some natural variation, but it improved by a bit
wide moss
yea for the most part, without some huge structure changes, i think we're at the micro-optimization scale
have you covered list comprehensions?
primal fable
Maybe? The term isn't familiar but we have done a lot with lists
wide moss
!list-comp
frank wharfBOT
primal fable
Oh yeah, we have
primal fable
Got it, now it's implemented. Now that I think about it, I can just eliminate ch...
That's this, right?
wide moss
yea
there are a couple places where that could be useful
particularly in searchForNterms and sNterms
primal fable
I see how it'd work in sNterms
return [k for k in searchForNterms(parse, ntm) if "Fail" not in k]
But I don't know about searchForNterms
primal fable
I think you can completely remove giveback at this point
wide moss
yea that too
primal fable
Oh, and rest as well
primal fable
At this point, the only thing in that else statement is
lst.extend([f"[{branch}]" + item for item in searchForNterms(parse[branch], nt)])
primal fable
Ah yeah, that's not something I've learn. My teacher is very hesitant to teach us anything he calls "syntactic sugar"
wide moss
then you might as well throw away nearly half of python 😂
primal fable
Surely he's eventually going to teach it, although that might just be a higher level thing that I just haven't needed in my coursework
frank wharfBOT
Python help channel closed