Don't be so abrasive without linking to proof. I looked at a couple files and they looked fine.
Then there's the bug that you can't delete the first node in a list.
And then there's the fact that double linked list doesn't have a tail pointer.
And then there's the fact that they use the same node class in double linked as single, but the previous member is set by the list, but isn't always set so you might get an exception some times.
Then there's the fact that search is only implemented for single linked .. Oh and its RECURSIVE!
It'd be one thing if this was just them showing how they learned something in a blog post... But this was meant for teaching.... And yet there's no description and clearly obvious bugs.
Could someone please tell me why his code is considered 'non-pythonic'? This statement worries me a little, because his code looks pretty similar to what I write.
- Getters and setters are used all over the place (setData, getData etc)
- Strangely named variables - eg List = [] and newNode = Node(data)
- Non-pythonic conditionals eg I'd expect while(temp.next != None): to read while temp.next:
- functions are commented outside the function instead of in docstrings, which, ironically would have made it much better for learning the algorithms :-)
Not that it's bad code, it's just not very pythonic.
# breadth first search algorithm
def search(graph, startVertex):
# Take a list for stoting already visited vertexes
if startVertex not in graph or graph[startVertex] is None or graph[startVertex] == []:
return None
# create a list to store all the vertexes for BFS and a set to store the visited vertices
visited, queue = set(), [startVertex]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
The initial guard also checks whether graph[startNode] is None, but this is never checked when looking up other nodes in the graph. Whether you check this should be consistent.
The loop pops the zeroth element from the queue. As the queue is a list, this is a linear time operation. This makes the bfs implementation have quadratic worst-case complexity rather than the linear complexity it should have. The Python standard library has a deque class that can be used to fix this, and it would be more instructive and more correct to use that. This also means the time complexity function is wrong.
So 2 clear bugs and 1 weird and probably unnecessary check in the bfs implementation. Also, the implementation has no comments to explain how it works, why it has the time complexity it does, or how you might tweak it to accomplish different goals.
I don't see how someone who didn't already know BFS could learn from this. There's nothing here that teaches the algorithm, and the implementation is weirdly flawed.
On top of all this, the package claims to teach all major algorithms but only contains a handful of sorting and searching algorithms. It doesn't even have a UI to help people discover and learn about the algorithms it does teach. You just have to know which ones are there and import them, then run a bunch of commands to print out the source code. This UI is worse than just browsing the source on GitHub, and that's much worse than just looking the algorithms up on Wikipedia or reading a textbook.
I really don't get why someone would share this on HN in its current state. It looks like what you'd throw together for sample data before you started working on your algorithm teaching package.
That's somewhat surprising. The documentation at https://wiki.python.org/moin/TimeComplexity says that the time complexity of pop(k) on a list of size of n is O(k). Since k is constant in this program, that time complexity should be constant, not linear.
However, a quick little test program:
import sys
import time
n = int(sys.argv[1])
l = list(range(n))
print("list ready")
start = time.time()
for i in range(1000):
l.pop(0)
took = time.time() - start;
print(n, took)
10000 0.00488591194152832
100000 0.06201004981994629
1000000 0.7796049118041992
10000000 12.354434967041016
I tried it in Perl, too:
use Time::HiRes qw(gettimeofday tv_interval);
my $n = shift;
my @list = (1 .. $n);
my $start = [gettimeofday];
for ($i = 0; $i < 1000; ++$i)
{
shift @list;
}
my $elapsed = tv_interval($start, [gettimeofday]);
print "$n $elapsed\n";
10000 0.000135
100000 0.000142
1000000 0.000178
10000000 0.000163
100000000 0.000176
10000 0.00017404556274414062
100000 0.00018596649169921875
1000000 0.0001850128173828125
10000000 0.0001819133758544922
100000000 0.00019288063049316406
Out of curiosity I then changed the Python program to pop the last item of the list instead of the first, and got this:
10000 0.00025200843811035156
100000 0.00026297569274902344
1000000 0.0002658367156982422
10000000 0.0002770423889160156
100000000 0.0002639293670654297
I was then curious to compare list and deque for accessing interior elements. I changed the programs from poping item to adding 1000 items from the list or deque spaced evenly throughout.
List:
10000 0.0002741813659667969
100000 0.0003039836883544922
1000000 0.0004611015319824219
10000000 0.0005731582641601562
100000000 0.0006010532379150391
10000 0.00033092498779296875
100000 0.0014951229095458984
1000000 0.03908801078796387
10000000 0.45997095108032227
100000000 16.526084899902344
I did the same thing with my Perl program:
10000 0.000301
100000 0.000375
1000000 0.000511
10000000 0.000624
100000000 0.000638
The CPython list implementation does indeed sacrifice performance to use less size. It uses a pre-allocated array for the list and when the list gets too large, it needs to allocate a new array to hold the list and re-insert all the items into the new array.
You may have done this in an intro CS class and doubled the array size to get an amortized O(1) append time, but you only need to increase the size by at least a constant fraction of the current size. Python increases by 1/8 of the current size, plus 6. This means more reallocations over a large number of operations, but less memory overhead at any given time.
Because of this implementation, you can pop from the right by just changing the size of the array, but to pop from the left requires shifting the entire array. You can pop the kth element from the right in O(k) time by just shifting those elements, which may be what the wiki means. I didn't read the code thoroughly enough to verify that it actually does this, but it seems reasonable.
Popping from the right is still slower than a deque because in order to save memory, the list gets resized whenever it falls below half of its maximum allocated size. A deque is always O(1) for every push/pop operation, but lists have occasional expensive operations that bump up the runtime a bit. Deques require linear time to access elements due to being implemented as doubly-linked lists. They're really only meant for accessing the elements on the ends.
You can get fast popleft on a list if you also keep a left pointer, but this complicates the implementation and has a corresponding performance penalty. You can even do a fast appendleft on a list if you allocate the elements so they start with empty cells on both the left and the right, but this makes the tradeoff between memory and performance even worse.
# to check if stack is empty
def isEmpty(self):
return self.stack == []
# for checking the size of stack
def size(self):
return len(self.stack)