Open jerome-benoit opened 5 months ago
LinkedList in javascript is not really performant. Not sure it's worth the effort in the end at implementing them via a clean API making node or link a first class citizen
I agree with you. I have never seen the point of a dynamically sized Linked List in JavaScript and never had a use-case for it as it is never performant enough.
Personally I am pondering to drop it altogether from the library. However, I would like to introduce fixed size singly & doubly linked lists like those used internally in some other structures of the library such as the lru cache because those are efficient and can be useful. I will personally need one soon to properly implement a Chiba-Nishizeki routine to count triangles in a graph.
LinkedList in javascript is not really performant. Not sure it's worth the effort in the end at implementing them via a clean API making node or link a first class citizen
I agree with you. I have never seen the point of a dynamically sized Linked List in JavaScript and never had a use-case for it as it is never performant enough.
Happy to see you back. I hope it was because of holidays, not work :D
Personally I am pondering to drop it altogether from the library. However, I would like to introduce fixed size singly & doubly linked lists like those used internally in some other structures of the library such as the lru cache because those are efficient and can be useful. I will personally need one soon to properly implement a Chiba-Nishizeki routine to count triangles in a graph.
So, a roadmap:
sounds reasonable?
Happy to see you back. I hope it was because of holidays, not work :D
Unfortunately it's work. This and I maintain a lot of Open Source libraries.
deprecating the current LL API in favor of an unbounded Deque API
Why not, but I am not sure an actual linked list is the best implementation for a true unbounded Deque in JS. If I remember correctly the Queue
of this library, for instance, has some linear array, amortized constant time implementation or such and does not rely on a Linked List (I think python and Rust deques also use some trick of the kind). In my mind the only fitting use (in higher level languages) of a doubly linked list is to move an item around in constant time and the only fitting use of a singly linked list is to have efficient multimaps or collision handling when you don't know in advance the order of insertion.
(I am only noticing now that you spoke about this in your comment here: "Optimize Deque implementation by using an array with two indexes start and end, or two arrays: benchmarks them")
What I mean, in the end, is that I am not sure a lot of people are using mnemonist for the Linked List anyway and that it would probably not be very costly to trash it, even without a transition phase. I see the value in adding an unbounded Deque class in the library though.
reintroduce fixed singly LL with an API making linked list node a first class citizen
I don't think we need a node class at all, because we can rely on representing them by numerical ids if the list is bounded. This is lighter and does not require allocation of node objects etc. It has some drawbacks because those ids are basically pointers that you can use to hurt yourself if you are not careful.
deprecating the current LL API in favor of an unbounded Deque API
Why not, but I am not sure an actual linked list is the best implementation for a true unbounded Deque in JS.
It's not, but it's an intermediate step for introducing a fast unbounded Deque implementation.
(I am only noticing now that you spoke about this in your comment here: "Optimize Deque implementation by using an array with two indexes start and end, or two arrays: benchmarks them")
The subsequent steps are indeed targeted at making the Deque implementation lean and fast using JS.
reintroduce fixed singly LL with an API making linked list node a first class citizen
I don't think we need a node class at all, because we can rely on representing them by numerical ids if the list is bounded. This is lighter and does not require allocation of node objects etc. It has some drawbacks because those ids are basically pointers that you can use to hurt yourself if you are not careful.
Do you have an example code of using such an optimisation? What will be the exact underlying storage data structure?
I do not understand the trick here.
Rationales:
LinkedList
is not what is expected for an API dedicated at manipulating linked list node or link data structure:{ data, prev, next }
LinkedList
API is what is expected for an API dedicated to non boundedDeque
, except the missingpop()
opLinkedList
in javascript is not really performant. Not sure it's worth the effort in the end at implementing them via a clean API making node or link a first class citizenDeque
implementation backward compatible withLinkedList
is likely more useful to mnemonist usersChangelog:
LinkedList
related files toDeque
related filesLinkedList
importationDeque
API to theFixedDeque
API: deprecatefirst()
,last()
,peek()
ops, addpeekFirst()
,peekLast()
pop()
op by using a doubly linked listTodo:
Deque
implementation by using an array with two indexes start and end, or two arrays: benchmarks themDeque
andFixedDeque