#🔒 Improving Doubly Linked List
final loom
How can I optimise this implementation: https://paste.pythondiscord.com/FIAQ
fading schooner
Just at a glance, you might want to improve the efficiency of reverse to O(1), by either returning a reverse wrapper on the linked list, or having an attribute that encodes whether we go through the dll flipped
Perhaps also implement an __iter__ for the linked list
As for speed? I suppose you can try search for an index via the closest side, instead of from the left each time (blindness 2: electric boogasoo)
You could also use __slots__ to improve access times
final loom
Perhaps also implement an `__iter__` for the linked list
do i not already have an iter method
fading schooner
oh I'm blind
fading schooner
Just at a glance, you might want to improve the efficiency of `reverse` to O(1)...
Might be nice to use that in the other methods, which would help with doing reversal among other things. But that's up to you
final loom
i've never used slots before, how can i use that
fading schooner
just define __slots__ = ("value", "next", "prev") in the body of listNode, and __slots__ = ("head", "tail", "size") in the body of DoublyLinkedList
That will mark the class as "complete", in the sense that we don't need an extensible dict to store its attrs etc
hence speed++
final loom
oh i think ive seen that before actually
final loom
Might be nice to use that in the other methods, which would help with doing reve...
i was going to do that, but then wasn't sure which was more efficient between iterating through the dll, or creating a generator, and context switching between the method and generator code.
fading schooner
yeah, it would be slower. If we want pure efficiency then you'd just be stuck having to copy reversal logic into every function
If we really wanna be fast it's time for cython
Numba sadly won't cut it since this is a class
final loom
class ThreadSafetyWrapper:
def __init__(self, maxsize=None):
self.count = threading.Semaphore(0)
self.space = threading.Semaphore(maxsize) if maxsize else None
self.mutex = threading.Lock()
@contextmanager
def protect_put(self, block):
if self.space and not self.space.acquire(block):
raise Full
yield
self.count.release()
@contextmanager
def protect_get(self, block):
if not self.count.acquire(block):
raise Empty
yield
if self.space:
self.space.release()```ive used this to make thread safe queues before, can i reuse it to make the dll thread safe, it it isn't already
fading schooner
This looks massively familiar, did I help you with this in the past?
final loom
i don't remember
fading schooner
Anyway, yeah looks thread-safe
final loom
wait is that with or without the wrapper
fading schooner
With the wrapper
You can do fine-grained (i.e. node-by-node, lock 2(or 3? i don't remember) at a time to iterate) locking if you really want to, but I don't think the overhead is worthwhile in most cases
final loom
would i need to add anything to it, or just use protect_put/get
fading schooner
protection is always fine if done on all methods
final loom
are these all the methods i'd need to protect https://paste.pythondiscord.com/5DWA
fading schooner
I'd think the get set and delete at least, no?
final loom
i was thinking both appends, both pops, remove, insert, both extends, setitem and delitem
should it not be everything that actually changes the state of the list, but every that just involves traversing it is fine
fading schooner
Well in theory traversals aren't threadsafe: what if you remove the next node as you're about to iterate onto it?
Actually if you're careful about the order in which you change references I think it's ok?
fading schooner
I have absolutely nothing to show for it but I went down a brief rabbithole of expanding my minimal cython knowledge to try and get an implementation of the dll working
This has unqeuivocally led to failure
ruby fernBOT
Python help channel closed