Do you understand what a ring buffer is/how it works?
#algos-and-data-structs
half lotus
Once you do, you'll see that all the operations just involve calculating and changing indices, which are constant time.
And, of course, getting or changing the value of an arbitrary index is already constant time for lists.
fiery cosmos
@half lotus is this correct
class Deque:
def __init__(self,k):
self.items = []
self.k=k
def AddToFront(self, e):
if len(self.items)<self.k:
self.items.insert(0,e)
def AddToBack(self, e):
if len(self.items)<self.k:
self.items.append(e)
def RemoveFromFront(self):
return self.items.pop(0)
def RemoveFromBack(self):
return self.items.pop()
def SetElement(self,i,e):
self.items[i]=e
does this follow constant time complexity
fiery cosmos
Would my algorithm not follow constant time complexity
half lotus
It's not constant for all operations
fiery cosmos
like which one
half lotus
popping from the front is not constant because it will shift all elements in front to the left by 1
inserting in the front has the same problem, except it shifts to the right
fiery cosmos
So how do you suggest i do it I have been stuck on it for hours
half lotus
I've been trying to tell you to use a ring buffer
fiery cosmos
I don't known what a ring buffer is
half lotus
Have you tried looking it up?
fiery cosmos
In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.
But the value of the length of my buffer is variable
@half lotus
half lotus
It's not. It's a constant k.
fiery cosmos
(k is not a constant and should not show
up in your running time).
We want to design a list-like data structure that supports the following operations
on integers.
• addToFront(e): Adds a new element e at the front of the list.
• addToBack(e): Adds a new element e at the end of the list.
• removeFromFront(): Removes the first element from the list and returns it.
• removeFromBack(): Removes the last element from the list and returns it.
• setElement(i, e): Sets the element of the i-th element of the list to e.
Each operation should run in O(1) time. You can assume that we know that the list
will never contain more than k elements (k is not a constant and should not show
up in your running time).
half lotus
But it says "You can assume that we know that the list
will never contain more than k elements"
fiery cosmos
but k is variable depends on the user
half lotus
But the user only specifies it once, right?
Once they create the data structure with size k, then it's locked to size k and cannot later be changed.
Is that a correct understanding of the problem?
half lotus
So what?
The point is that it doesn't change once the class is instantiated
So you can create a ring buffer of the size the user gives
fiery cosmos
could you make changes to my code to make it a ring buffer
or is it completely wrong
half lotus
I'm not going to write code for you. That's your task.
Yes, your current implementation is wrong because it's relying on the list's functions. A ring buffer works by calculating and storing indices, as I said.
Like you store an index to the start/end of the data. If you read more about ring buffers this will be explained.
If you're having trouble finding a good explanation, I can try to find one for you.
fiery cosmos
Have you heard about double implemented qeues
half lotus
You mean a double ended queue? Yes
fiery cosmos
Yes it contains all basic four operations as mentioned in our question and does that in constant time
half lotus
Yeah, I recognise that is what you need to implement.
fiery cosmos
Yup what is the difference between a ring buffer and Double Ended qeue
half lotus
A ring buffer is just one way to implement a double ended queue. A ring buffer would be the underlying data structure in which the data of the deque is stored.
Also, deques can change in size in some implementations, but circular buffers are fixed in size. However, this isn't relevant for your task since it says that the size of the deque will not change.
fiery cosmos
the size of deque will change in all these four operations
addToFront(e): Adds a new element e at the front of the list.
• addToBack(e): Adds a new element e at the end of the list.
• removeFromFront(): Removes the first element from the list and returns it.
• removeFromBack(): Removes the last element from the list and returns it.
half lotus
Well yes. But the maximum size does not change. So you can preallocate the maximum size.
fiery cosmos
oh ok
lean dome
Ring buffers have a fixed capacity. Deques may be able to grow dynamically, in order to accommodate more items than they originally had room for.
fiery cosmos
so i first need to implement a ring buffer using an array and then using that ring buffer I need to implement a deque
half lotus
Yeah but if you implemented the ring buffer then you've basically implemented the deque already.
fiery cosmos
could you please help me implement a circular buffer
lean dome
Some ring buffers are only single ended queues, to be fair.
half lotus
Yeah, you're right. I wasn't sure how to phrase it. I was trying to express that the deque needs raw access to the buffer. If it was abstracted away into a separate interface then it wouldn't be possible to implement the deque.
lean dome
True.
half lotus
So trying to distinctly separate them in mind is maybe helpful, but not in implementation.
half lotus
could you please help me implement a circular buffer
Sure, what part do you need help with?
lean dome
Audio in video games is frequently implemented using a ring buffer - which is why, when games freeze, it is common for them to repeat the same 3 seconds of audio forever
Random trivia 😄
fiery cosmos
self.buffer = [None] * max_size
self.head = 0
self.tail = 0
self.max_size = max_size
so this is how you basically start implementing a buffer
half lotus
Yes
fiery cosmos
• addToFront(e): Adds a new element e at the front of the list.
how do I implement this method in the buffer
@half lotus
half lotus
You need to get the index one before the head
Then store the value at that index
And set the head to be head -1
fiery cosmos
could you please code it I am highly confused
half lotus
Which part do you not understand
fiery cosmos
how will you check the size of th buffer after what you have implemented and a few different questions
and plus if do the same operation thrice if the head is at -1
would it overide the element at -1
lean dome
A circular buffer is a buffer of fixed, finite size into which there are two indices:
(1) A 'head' index - the point at which the producer inserts items into the buffer.
(2) A 'tail' index - the point at which the consumer finds the next item in the buffer.
Typically when the tail pointer is equal to the head pointer, the buffer is empty; and the buffer is full when the head pointer is one less than the tail pointer.
The head index is incremented when items are added, and the tail index when items are removed. The tail index should never jump the head index, and both indices should be wrapped to 0 when they reach the end of the buffer, thus allowing an infinite amount of data to flow through the buffer.
fiery cosmos
so if we do what @half lotus said wouldn't the head be =-1 and tail=0
lean dome
Starting them both at 0 is typical. Then the current size of the buffer is the number of times that the head pointer can be advanced before it touches the tail pointer
With an empty ring buffer, the head pointer is touching the tail pointer after advancing the head pointer 0 times, so the size is 0.
fiery cosmos
We want to design a list-like data structure that supports the following operations
on integers.
• addToFront(e): Adds a new element e at the front of the list.
• addToBack(e): Adds a new element e at the end of the list.
• removeFromFront(): Removes the first element from the list and returns it.
• removeFromBack(): Removes the last element from the list and returns it.
• setElement(i, e): Sets the element of the i-th element of the list to e.
Each operation should run in O(1) time. You can assume that we know that the list
will never contain more than k elements (k is not a constant and should not show
up in your running time).
how do I implement the the first method addToFront(e): Adds a new element e at the front of the list. Using a circular buffer
lean dome
By storing the new item into the buffer at the head pointer, then advancing the head pointer.
fiery cosmos
I just known python I dont known anything about pointers
lean dome
The "pointer" is just an index into the buffer
It's a number that points to a particular element of the buffer.
If the buffer is not full, the head index identifies the next index to write to. If the buffer is not empty, the tail index identifies the next index to read from.
fiery cosmos
Could you please show me the code for the first method I am sort of confused
lean dome
I'm not willing to write this for you.
I don't mind answering questions, but you need to do the work.
fiery cosmos
but I cant comprehend what you are saying
head=0
tail=0
my_list[head]=element
head=head+1
what about the tail?
lean dome
That is how inserting at the front works, as long as you ignore the edge case of what to do when the buffer was already full.
unkempt umbra
head=head+1
i think you have to % by the length of the array too (or an if statement could work)
lean dome
Ah, yes.
lean dome
what about the tail?
The tail only moves when you add or remove from the back end. The head moves when you read or write from the front end.
unkempt umbra
Audio in video games is frequently implemented using a ring buffer - which is wh...
lmao i didn't know that. nice trivia
fiery cosmos
Class Data_Structure():
def __init__(self,k):
self.my_list=[None]*k
self.max_length=k
self.head=0
self.tail=0
def AddtoFront(e):
self.my_list[self.head]=e
self.head=(self.head+1)%self.max_length
how do i check if the buffer is already full @lean dome
lean dome
If the head pointer is one past the tail (modulo the length of the buffer), then there's no room.
fiery cosmos
But would it become full if I implement addtofront(e) one time
because self.head=1
self.tail=0
@lean dome are u there
lean dome
But would it become full if I implement addtofront(e) one time
Ah, sorry. Adding to the back is done at the tail position, and then increments the tail. Adding to the front is done at the head position, and then decrements the head.
fiery cosmos
so I need to do self.head=self.head-1
lean dome
Yeah.
If you start off with head = tail = 0, and you insert twice, once at the beginning and once at the end, head and tail need to be 2 apart (modulo the size of the buffer) because the buffer now contains 2 items.
Which means that head moves in one direction, and tail in the other, so that after one append at each side, tail has moved from 0 to 1, and head has moved from 0 to max size - 1
fiery cosmos
Class Data_Structure( ):
def __init__(self,k):
self.my_list=[None]*k
self.max_length=k
self.head=0
self.tail=0
def AddtoFront(e):
If self.tail==(self.head-1)%self.max_length:
Return “Array is Full"
self.my_list[self.head]=e
self.head=(self.head-1)%self.max_length
is this correct
@lean dome
are u there
lean dome
Yep. I'm reading what you wrote.
Looks right. Though the error case would normally be raising an exception, not returning a string, if you've learned exceptions
fiery cosmos
but now self.head=-1
lean dome
Ah, you missed the self parameter in the argument list for the second function, too.
Needs to be (self, e)
fiery cosmos
which is -1
unkempt umbra
python only gives negative for % if the divisor is negative
euclidean divmod or something i forgot
its neat
lean dome
!e print((-1) % 10)
halcyon plankBOT
@lean dome :white_check_mark: Your eval job has completed with return code 0.
9
cool
unkempt umbra
woah python discord got an eval bot
lean dome
Staff members can use it anywhere, regular users can only use it in help channels or #bot-commands
fiery cosmos
would this operation occur in constant time
unkempt umbra
most math is O(1)
wait nvm i think you're talking about the append
!e -1 or testing_lol
halcyon plankBOT
You are not allowed to use that command here. Please use the #bot-commands channel instead.
unkempt umbra
aw this aint a help channel
lean dome
Both inserting the new element into the buffer and updating the head pointer are constant time operations, yes.
As is checking if the buffer is full.
unkempt umbra
wait im curious about python's deque. it says it's using linked lists of blocks, but are the blocks themselves a circular buffer
or are they small enough that it doesnt matter to shift everythign
lean dome
No, a Python deque is a linked list of fixed size arrays
unkempt umbra
what happens when the len of the deque is smaller than a block?
fiery cosmos
Class Data_Structure( ):
def __init__(self,k):
self.my_list=[None]*k
self.max_length=k
self.head=0
self.tail=0
def AddtoFront(self,e):
If self.tail==(self.head-1)%self.max_length:
Return “Array is Full”
self.my_list[self.head]=e
self.head=(self.head-1)%self.max_length
def AddtoBack(self,e):
If self.tail==(self.head-1)%self.max_length:
Return “Array is Full”
self.my_list[self.tail]=e
self.tail=(self.tail+1)%self.max_length
Yeah, that's the idea. It puts an upper bound on the number of items that may need to shift.
unkempt umbra
ah k that's neat
fiery cosmos
is this code inncorect
lean dome
what happens when the len of the deque is smaller than a block?
Then its linked list contains only one block, and that block is only partially used.
fiery cosmos
because when we do addtofront it will add at self.my_list[0]=e
and when we do add to back it will add at the same position
self.my_list[0]=e
@lean dome
unkempt umbra
Then its linked list contains only one block, and that block is only partially u...
ah so it only needs to keep the index of the two ends instead of having the overhead of a circular boi for each block
damn ds is cool
unkempt umbra
```python
Class Data_Structure( ):
def __init__(self,k):
...
what if u increment tail before you assign
like swap the last 2 lines
wait hmm (i think the condition also changes to just plain equality)
lean dome
This walks through how to build it, better than I'm explaining it.
There's an extra complication for double-ended ring buffers I was forgetting.
fiery cosmos
Class Data_Structure( ):
def __init__(self,k):
self.my_list=[None]*k
self.max_length=k
self.head=0
self.tail=0
def AddtoFront(self,e):
If self.tail==(self.head-1)%self.max_length:
Return “Array is Full”
self.my_list[self.head]=e
self.head=(self.head-1)%self.max_length
def AddtoBack(self,e):
If self.tail==(self.head-1)%self.max_length:
Return “Array is Full”
self.my_list[self.tail]=e
self.tail=(self.tail+1)%self.max_length
I just wanted to known for the self.my_list[0] case when both add to back and addtofront will coincide
lean dome
Yeah. You need to special case the first insert into an empty array, when it's allowed to grow from both sides.
fiery cosmos
okay so how do i do that
lean dome
The YouTube video I linked shows one way to do that.
https://www.geeksforgeeks.org/implementation-deque-using-circular-array/ shows it as well.
fiery cosmos
Class Data_Structure( ):
def __init__(self,k):
self.my_list=[None]*k
self.max_length=k
self.head=0
self.tail=0
def AddtoFront(self,e):
If self.tail==(self.head-1)%self.max_length:
Return “Array is Full”
If self.head==0 and self.my_list[self.head]!=None:
self.head=(self.head-1)%self.max_length
self.my_list[self.head]=e
self.head=(self.head-1)%self.max_length
def AddtoBack(self,e):
If self.tail==(self.head-1)%self.max_length:
Return “Array is Full”
If self.tail==0 and self.my_list[self.tail]!=None:
self.head=(self.tail+1)%self.max_length
self.my_list[self.tail]=e
self.tail=(self.tail+1)%self.max_length
is this correct
lean dome
That would do the wrong thing if they ask you to store a None
You're assuming that the only Nones it ever holds are the ones it was initialized with, but the user can add their own
fiery cosmos
Please help me out I am highly confused I cant understand anything from vedio
Could you please make changes to my code just to implement when the element is zero
lean dome
I'm on a phone keyboard right now, that would take me forever
fiery cosmos
Okay just explain me what do i need to do then
unkempt umbra
the gfg code looks pretty simple to me
it sets the head and tail to -1
and it checks if they're -1 instead of checking the array
fiery cosmos
okay what next
unkempt umbra
ohh whoops
yeah in the method, u just check if head is -1 and if it is, you set head and tail to 0
else just do whatever u had originally
lean dome
I'm sorry. It's 3:30 AM here, and I think I'm too sleepy to think this through properly.
unkempt umbra
lol it's 3:30 am here too
lean dome
I'd just follow along with that geeks for geeks article. It shows code in a few different languages at the bottom.
lean dome
Your special case for an empty buffer is that, whether you insert at the start or the end, the results are the same. That new element is both at the head of the queue and the tall of the queue, and both pointers point to it. After the first element, they grow apart. Once the buffer drops down to only one element again, they're equal again.
So that representation uses a special flag - setting head to -1, a number outside its normal range - to indicate when the array is empty and needs to be handled specially
fiery cosmos
how do I do the set element part
drifting cliff
viral lichen
I hope this is the place to put this! I'm pondering performance enhancements and I got to thinking about the following:
Say I have a class method which gets called frequently. It has iteration to do if an object has any entries in its list_of_values.
if self.list_of_values:
for v in self.list_of_values:
do_something(v)
Would there be any benefit to performance if instead of calling that method constantly and checking the list is populated, I were to remove the 'if' statement and make some variable to hold a reference to the task method if anything gets added to the list_of_values?
EG:
def skip(self):
return
call_this_method = skip
def add_value(self, val):
self.list_of_values.append(val)
self.call_this_method = hypothetical_method
I think it'd use more memory but be quicker overall. Happy to bow to the greater wisdom of someone with more experience though 🙂
I'm open to suggestions for other efficient techniques to do this too
agile sundial
if self.list_of_values is always a list then you don't need that if check at all
old rover
so does this like always apply to trees
yes I know the starting index is at 1
it sure seems like it
spring jasper
indices arent a tree thing
agile sundial
having the start index be 1 makes the math easy
agile sundial
with the first index as 1, it makes finding the children very easy
if your node is i, left is 2i and right is 2i + 1
whereas if your first index is 0
it is more annoying
old rover
oh ok
so a binary tree being full v a binary tree being complete
they are two different things
every binary tree is full as well as complete
agile sundial
hm? a binary tree doesn't have to be full or complete
agile sundial
complete means all the levels are full, or all the levels except the last are full and the nodes are as far left as possible
old rover
a heap is a complete binary tree
so this is a full binary tree
but this is a complete binary tree
I thought F would require another child
for it to be completely filled
"A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. "
oh that makes sense
the last level isn't completely filled
that's why it's complete
I thought last level meant that all the possible children had to be there for each node
but I was wrong
this is stupid
but are there multiple parents?
or is parent just the starting node
what are you supposed to call B?
agile sundial
if you're at index i, then your parent is i//2
scarlet maple
old rover
ok good
I was losing my mind
I thought parent only referred to the starting node for a second
not sure why
old rover
How can I start data structure?
big O
old rover
How can I see information about a pid?
idk what a pid has to do w ds/algos
fiery cosmos
is that I did not find a related channel
old rover
so can you only remove the root of a heap
bc it seems like that's what the video is saying
onyx umbra
yeah thats correct
and after removing, it automatically swaps next smallest/biggest value to root.
weak panther
red is bad, yeah?
vocal gorge
yes
looks like 48% of your time is spent doing json.loads
and 36% going get requests, but that's fine, I believe - they are blocking, so it's probably mostly waiting for the reponse.
it does mean that you may want to use something like aiohttp to eliminate the waiting.
half lotus
Requests are already multithreaded though.
Also, I don't think this channel is appropriate.
vocal gorge
red is bad, yeah?
Also, this is #algos-and-data-structs I just realised. Your question would be more fit for... #weekly-topic-discussion, actually, the current topic is optimization and profiling.
weak panther
I wasn't sure where to ask, I'll try weekly topics
half lotus
Claim a help channel usually. Not all questions are going to fit into a topical channel.
weak panther
I've been in #☕help-coffee but I haven't been able to reduce my speed by very much
sly verge
hi, this line is giving me an error
image = np.reshape(image, (1, image.shape[0]*image.shape[1]))
ValueError: cannot reshape array of size 750000 into shape (1,250000)
not my code, but I'm guessing the idea is converting the 2d pixel array into a 1d array. What could be going wrong?
got it, it is RGB instead of grayscale probably
vocal gorge
yup
fiery cosmos
red is bad, yeah?
Hey, is this some sort of code analyser with time? If so what is it named?
weak panther
part of pycharm
vocal gorge
Hey, is this some sort of code analyser with time? If so what is it named?
That's PyCharm's profiler visualization.
The profiler it uses is just the normal cProfile
fiery cosmos
Great I use PyCharm, didn't know about that
vocal gorge
but the visualisation is part of it, and it's not in the free version
fiery cosmos
but the visualisation is part of it, and it's not in the free version
not in the free version, huh
vocal gorge
But there's https://jiffyclub.github.io/snakeviz/ for a free alternative.
Also, this is still #algos-and-data-structs and still not the right place for this 😅
fiery cosmos
Oh great for the information! I'll read into it tomorrow
fiery cosmos
Also, this is still <#650401909852864553> and still not the right place for this...
😆 😆 Okay we can stop now
coral loom
How would I store the values from variables in: country_lat (containing latitudes) & country_lng (containing longitudes) onto a Pandas dataframe with column headings named separately as: "Latitudes" & "Longitudes" ...? ```py
''' Returns the approximmate latitude & longitude for countries stored inside the dataframe '''
def geolocate(self, df):
try:
countries = df['Countries']
# centrelocation = geolocator.geocode(country)
# return (centrelocation.latitude, centrelocation.longitude)
for country in countries:
# country_latlng = country.latlng()
country_lat = country.latlng[0]
country_lng = country.latlng[1]
return (country_lat, country_lng)
this is better suited for, say, #data-science-and-ml (as it involves pandas). It seems to me you just want
lats = [country.latlng[0] for country in countries]
lngs = [country.latlng[1] for country in countries]
df2 = pd.DataFrame({"Latitudes":lats,"Longitudes":lngs})
Sorry, my bad! And thanks for that 🙂 thank you
coral loom
this is better suited for, say, <#366673247892275221> (as it involves pandas). I...
Ohh so you've created a new dataframe object then?
vocal gorge
yes? Is that not what you wanted?
Oh, you wanted to add them to the original one as columns? That's as simple as:
df["Latitudes"] =lats
df["Longitudes"]=lngs
Yup I wanted them added to the original df, yes
meager jetty
a parent is a parent ... root or Adam and Eve didnt have one ...
agile sundial
huh?
meager jetty
lol look like i scrooled back instead of forward reading message lol
node parent is a node who has a parent who is ...
until you hit the root or God
agile sundial
nil, none, null, etc
meager jetty
nil ,null ... are in fact God others name lol
spring jasper
God metaphors never helped anyone, can we stick to algos and DS please?
meager jetty
lol
im so sorry it is because I played to much with void pointers and function pointers today ...
pure sonnet
Anyone here ever made a trading algorithm?
keen hearth
Anyone here ever made a trading algorithm?
Hey 🙂 This is probably better suited to #data-science-and-ml (different kind of algorithm).
fiery cosmos
anyone used python in blender?
old rover
@fiery cosmos wrong channel for this but I don’t know the right channel either
fiery cosmos
yeah same
icy spruce
What's the best way to familiarize with optimizing algos to prepare for technical interview questions/challenges for dev positions with > 5 yrs exp
old rover
@icy spruce do you know what big O is
icy spruce
More or less
old rover
Idk about optimizing algos
icy spruce
I want to prepare for big O questions. I guess just more practice on leetcode etc? And familiarizing with common questions
Never had to think abt big O in real life until a function runs super slow/taking up too muh memory 
old rover
Yeah unless the input is outrageously large
steady sun
neon sparrow
trail kelp
https://www.youtube.com/watch?v=X-iSQQgOd1A
My mind is blown!
tame dagger
Hi, I have a question around usage of Lists vs deque in everyday functions with regular sized inputs ~ 100 items or less
As per some preliminary search I found that deque's performance might be better for use cases of popleft (Also this link helps - https://stackoverflow.com/questions/23487307/python-deque-vs-list-performance-comparison)
I wanted to get a general opinion around usage of Lists when there is an optional requirement of popleft or appendleft (not always) Would be happy to know your views on deciding when to choose which especially when the use case is not 100% of a deque all the time
vocal gorge
It's not a very good idea to use lists when you do popleft (it's even mentioned in the docs), because it's O(n) and not O(1) like pop, or like pop/popleft on deques
mint jewel
Hi, I have a question around usage of Lists vs deque in everyday functions with regular sized inputs ~ 100 items or less
for that few items either is fine
lists may even be faster depending on what deque python uses
vocal gorge
if you mean "how much it actually matters when n<=100", hmm. One should probably generate a representative set of items and operations and time on them.
tame dagger
Thanks
vocal gorge
for example, each appendleft on a 100-element list is around 600 times slower than on a deque:
%%timeit l1 = [1]*100
l1.insert(0,1)
# 32.9 µs ± 951 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%%timeit l2 = collections.deque([1]*100)
l2.appendleft(1)
# 58.1 ns ± 1.61 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
@vocal gorge that includes creation of the dequw though right?
vocal gorge
nope, line of the %%timeit is executed but not timed
agile sundial
oh I didn't know that
void kiln
Can anyone review my program for an algorithmic coding problem. It can run within the given time limits but it gets the answers wrong except the sample case for some reason. Would really appreciate it, but it requires someone who is very skilled at python and an understanding of time complexities to help me
agile sundial
i'm not very skilled, but i may be able to help
old rover
is a binary heap also just a heap
like is there anything special about it being binary
it only has two children per parent? that's what binary means
a heap is just a binary tree
and there's two options a max heap or a min heap
spring jasper
Heaps dont need to be binary heaps, but its a common implementation
old rover
is the time complexity for heap sort on a binary heap any different from the time complexity of heap sort on a standard heap
is that a dumb question
agile sundial
suppose it is the same, can you prove it?
old rover
no
agile sundial
did you try
old rover
it's based on the height of the tree
or the heap
heap sort is O log N and N is the height of the tree
agile sundial
heap sort is O(N log N)
onyx umbra
heap sort is O log N and N is the height of the tree
i think n is number of nodes not height because h=log n
agile sundial
oh i didn't catch that you said "N is the height of the tree"
it's not O(N log N) in that case
spring jasper
You shouldnt expect to understand a 51min video just by glancing at it once
Watch it again, take notes
old rover
I did take notes
agile sundial
most importantly, write code
old rover
ok
so
I have to know how to implement min and max heaps in code
something like this
but also be able to write heapsort and heapify?
old rover
!pastebin
halcyon plankBOT
agile sundial
that's a heap?
agile sundial
yes it is
old rover
so am I supposed to know how to make it that way too?
agile sundial
not necessarily
old rover
so I'm ok with just knowing heapify and heap sort
I have the main idea with heaps down
agile sundial
knowing heapify means you know how to sift nodes
heap sort is just making a heap then popping nodes
old rover
so then what is the point of their code
agile sundial
to make the heap?
old rover
so you still need to know how to make the heap right
old rover
so the code is still important
agile sundial
the code itself is not important
old rover
the concept is important
agile sundial
exactly
well sorry, let me be more clear
the heap implementation that they are showing you is not that important
what's important is that you know what things do, and you can implement it on your own
what they've coded doesn't matter
old rover
well I still need to be able to code it
and the fact that I had to search it up on how to code it
is pretty alarming
it's the whole linked list conundrum again
agile sundial
not really
that's just how learning works
it's a complicated topic, can't be expected to know it first try
old rover
bc linked lists were simple
and this stuff is actually difficult
what's an abstract data type
what does that even mean
abstract is like simple
agile sundial
in this context it means like, an idea
kinda like an interface
maybe idea is a bad way to put it
it's like, a blueprint, kinda
lean dome
It's the interface of a generic type, as opposed to its implementation.
lean dome
"stack" is an abstract data type that supports the push and pop operations. A common implementation way of implementing the stack concept is a dynamic array.
"queue" is an ADT that supports the enqueue and dequeue operations. A common implementation of queue is a linked list of fixed size arrays.
old rover
oh no
idk what happened to my udacity
but it turns out I missed an entire chapter
sets, maps, hashing, collisions, hash maps, string keys
lean dome
"mapping" is an ADT that supports insert value by key, delete by key, lookup by key, and iteration over all keys. A hash table is a common implementation of the mapping ADT.
old rover
should I go back and learn all of that stuff
and then come back to heaps?
do I have to know "sets, maps, hashing, collisions, hash maps, string keys" for heaps?
lean dome
you can learn heaps without those. But, hash tables and hash sets are more useful in the real world than heaps, so definitely go back and learn it.
old rover
so can I just finish off heaps and then come back to it
I'll do that
what does a priority queue mean again
you can enqueue and dequeu from both sides?
agile sundial
it means the highest priority items are dequeued first
agile sundial
you can enqueue and dequeu from both sides?
you're thinking of a deque
agile sundial
not necessarily, it just means to take something off a queue
althoughoh i guess
you would just call it popping if it's from the end
onyx umbra
i think when people say dequeue they mean taking off from head
wet urchin
I need help with this
wet urchin
Node of a Single Linked List
class Node:
# Constructor
def __init__(self):
self.data = None
self.next = None
# Method for setting the data
def setData(self, data):
self.data = data
# Method for getting the data
def getData(self):
return self.data
# Method for setting the pointer
def setNext(self, next):
self.next = next
# Method for getting the pointer
def getNext(self):
return self.next
# return true if the node point to another node
def hasNext(self):
return self.next != None
node1 = Node()
node1.setData(10)
node2 = Node()
node2.setData(20)
node1.setNext(node2)
print("node1 -->",node1.getNext())
print("node2 -->",node2.getNext())
old rover
but he actually deprecated the repo just so that people would spend money to see his code in his course
🙂
wet urchin
I don't understand why in the first print the result is node1 --> <main.Node object at 0x0000026AF0553F10>
And the second print is node2 --> None
agile sundial
you don't have a repr or str
wet urchin
Can someone explain me this?
dapper sapphire
because th value you insert becomes the head that's why you see that memory address
wet urchin
Ok but why in the second node it shows me None?
@agile sundial Sir, May you help me please?
agile sundial
sure
onyx umbra
you did not set node 2's next, thats why it shows null
agile sundial
node2.next is None
wet urchin
Maybe If I can explain you showing my screen it going to be better to me. I have some doubts about that.
wet urchin
`node2.next` is None
Could it be possible?
old rover
getters and setters are pretty unpythonic I heard
Idk if you wrote this implementation or you got it from somewhere else
but whatever way makes sense
wet urchin
That is the point, it is a kind of example that my institute give us to understand linked lists but I don't understand why it is important.
old rover
what does "remove" mean?
remove a node?
remove all the nodes?
yeah remove the smallest node
dude did it so quickly I didn't even realize
agile sundial
for a heap you can only remove the smallest or biggest, depending on if it's a min or max heap. you don't know where any other nodes are
old rover
right
would a function that just looks at the head of a linked list be considered a peek function
lean dome
dequeue means taken off the head
dequeue and deque are different.
dequeue is pronounced "dee-cue" - it's the operation of removing the least most recently inserted item from a queue and returning it to you.
deque is pronounced "deck". It is an abstract data type representing a double-ended queue, supporting push and pop at both the left and right side.
old rover
`dequeue` and `deque` are different.
`dequeue` is pronounced "dee-cue" - it's th...
oh yeah
my bad
idk how I forgot
I knew I'd confuse them someday
lean dome
it's usually pretty obvious from context which one is being talked about, but they're spelled very similarly. "deque" is a class or a type, "dequeue" is a method or an operation.
old rover
yeah
lean dome
and, I should have said this earlier about ADTs: the sense in which an abstract data type is "abstract" is that it specifies what operations must be supported, but not how they're implemented.
wet urchin
and, I should have said this earlier about ADTs: the sense in which an abstract ...
Sir, How do I get the power to speak within a voice channel?
lean dome
wet urchin
<#764802555427029012>
Sir
I have a question with my code.
Node of a Single Linked List
class Node:
# Constructor
def __init__(self):
self.data = None
self.next = None
# Method for setting the data
def setData(self, data):
self.data = data
# Method for getting the data
def getData(self):
return self.data
# Method for setting the pointer
def setNext(self, next):
self.next = next
# Method for getting the pointer
def getNext(self):
return self.next
# return true if the node point to another node
def hasNext(self):
return self.next != None
node1 = Node()
node1.setData(10)
node2 = Node()
node2.setData(20)
node1.setNext(node2)
print("node1 -->", node1.getNext())
print("node2 -->", node2.getNext())
The second print shows me None
I was analyzing the code and I need to know if i understood this in the right way.
The reason of None in the second print I think its because It puts noder1.setNext(node2) so it doesn't have any value in that node2.
Is It right?
old rover
you can have negative values in a heap?
actually you can have negative values in any data structure
wet urchin
The first print shows me <main.Node object at 0x0000026AF0553F10>
old rover
nothing very ground breaking there
wet urchin
So am i right?
lean dome
So am i right?
the reason that node1.getNext() is not None is that you've called node1.setNext(node2), so now node1.getNext() returns node2
the reason that node2.getNext() is None is that you've never called node2.setNext(), so it's getting the value that was set in __init__, which was None.
old rover
the joys of linked lists 🙂
lean dome
you can have negative values in a heap?
you can have any orderable value.
old rover
don't worry you aren't the only one who struggled with linked lists
lean dome
you can have any orderable value.
it doesn't even need to be a number - it could be a letter, for instance, and you could order it alphabetically.
old rover
oh cool
class AbstractHeap(metaclass=ABCMeta):
"""Abstract Class for Binary Heap."""
def __init__(self):
pass
@abstractmethod
def perc_up(self, i):
pass
@abstractmethod
def insert(self, val):
pass
@abstractmethod
def perc_down(self,i):
pass
@abstractmethod
def min_child(self,i):
pass
@abstractmethod
def remove_min(self,i):
pass
what in tarnation is this
oblique panther
```python
class AbstractHeap(metaclass=ABCMeta):
"""Abstract Class for Binar...
it's an abstract class. it's a software design thing.
they want you to implement all those methods
old rover
ohhh
yeah I wouldn't know
class BinaryHeap(AbstractHeap):
def __init__(self):
self.currentSize = 0
self.heap = [(0)]
also this
I thought classes took paramaters in python 2?
jolly mortar
No
BinaryHeap(AbstractHeap) signifies that BinaryHeap inherits from AbstractHeap
old rover
oh
jolly mortar
You're thinking of class A(object)
which signifies A inherits from the class object
this used to be required in python2
old rover
so do I need abstract heap?
I watched another 20 minute video and I couldn't figure out the implementation on my own
jolly mortar
Having BinaryHeap inherit from AbstractHeap forces you to implement all methods in AbstractHeap
jolly mortar
Yes
jolly mortar
But this forces you to do it
jolly mortar
But this *forces* you to do it
it's a contract if you will
old rover
I see
wet urchin
the reason that `node1.getNext()` is not `None` is that you've called `node1.set...
I finally understand that
Thanks a lot :,,)
lean dome
an AbstractHeap can't be instantiated, because it has abstract methods that have not been overridden. If you inherit from AbstractHeap, then your subclass will not be able to be instantiated unless you override all of those abstract methods.
The special behavior of the ABCMeta metaclass is that it checks, at instantiation time, whether the class has any abstract methods that have not been overridden, and if so it causes instantiation to fail.
fiery cosmos
Hi guys I'm a beginner in python.
ripe quest
anyone like writing prime number generators?
print(2, 3, end=' ')
primes = [3]
x = 5
try:
while True:
for p in primes:
if not x % p: break
else:
primes.append(x)
print(x, end=' ')
x += 2
except KeyboardInterrupt:
print('\nKeyboardInterrupt')
it generates prime numbers until you CTRL+C (windows, IDLE)
dapper sapphire
Hi, can someone share resources they used to learn Trees/Tries.
fiery cosmos
import math
def prime(n):
prior = prime(n-1) if n >= 2 else 2.920050977316
floor = math.floor(prior)
result = floor * (prior - floor +1)
print(f"{n}: {int(result)}")
return result
prime(11)
Prime number with recursion and the formula in the picture @ripe quest
ripe quest
wow!
fiery cosmos
Practising recursion 😄
def nums_tail(n: int):
if n >= 1:
nums_tail(n-1)
print(n)
def nums_head(n: int, c: int = 1):
if c <= n:
print(c)
nums_head(n, c+1)
nums_tail(10)
nums_head(10)
This is printing natural numbers till n. Any way to get nums_head (head recursion) with one parameter or more efficient? Tails recursion was my initial thought but I've been told head recursion would be more efficient?
ripe quest
I'm working on another one right now. Every time a prime number is not divisible by the number being tested: the set can be reduced.
fiery cosmos
I'm working on another one right now. Every time a prime number is not divisibl...
I see, feel free to show the code when it works 😄
I've been looking at this wiki page https://en.wikipedia.org/wiki/Formula_for_primes and picked a formula to write the code
fossil lotus
guys i need help
fiery cosmos
guys i need help
Don't we all?
fiery cosmos
can i send a code here?
Sure
fossil lotus
p2=int(input("mantepse arithmo")
counter=0
while p1!=p2:
if p1>p2:
print("o arithmos poy edwses einai mikroteros")
else if p1<p2:
print("o arithmos poy edwses einai megaluteros ")
p2=int(input("ksanamantepse arithmo")
counter=counter+1
if p1==p2:
print("brhkes ton arithmo")
print counter
it says syntax error on line 2
the variables name
ripe quest
missing parantheses
ripe quest
line 1 and 2
fossil lotus
again another error
ripe quest
line 9
fiery cosmos
yeah it's wrong, while needs to be on the same line as counter
tardy pilot
after the else if
Missing parentheses again?
fossil lotus
where?
fossil lotus
fixed it
tardy pilot
After the else where you set p2.
fiery cosmos
indentation is important in python, code gets interpreted differently depending on indentation, bro
fossil lotus
line 7
fiery cosmos
oh well
fossil lotus
does the p1<p2: need parenthesis?
fiery cosmos
No, you can post your code again to keep us up to date. Also next time get a help channel please #❓｜how-to-get-help
fossil lotus
oh ok
p2=int(input("mantepse arithmo"))
counter=0
while p1!=p2:
if p1>p2:
print("o arithmos poy edwses einai mikroteros")
else if p1<p2:
print("o arithmos poy edwses einai megaluteros ")
p2=int(input("ksanamantepse arithmo"))
counter=counter+1
if p1==p2:
print("brhkes ton arithmo")
print counter
can u try running it?
fiery cosmos
yee
yeah there is a space to much in the else if p1<p2: line
No
A space to little in the if p1>p2: line
also else if is elif in python
fossil lotus
do i need : after printing?
fiery cosmos
nO
fiery cosmos
ayy I'm learning c too, but you gotta be more careful of syntax in c than in python no?
p1=int(input("dwse arithmo"))
p2=int(input("mantepse arithmo"))
counter=0
while p1!=p2:
if p1>p2:
print("o arithmos poy edwses einai mikroteros")
elif p1<p2:
print("o arithmos poy edwses einai megaluteros ")
p2=int(input("ksanamantepse arithmo"))
counter=counter+1
if p1==p2:
print("brhkes ton arithmo")
print(counter)
fixed code (syntax error fixed)
dapper sapphire
Hi, can someone please share resources they used to learn Trees/Tries.
And do people use the word Trees and Binary Tree interchangeably?
fiery cosmos
Nope there are different, Binary has only two "children" at most
fiery cosmos
Hi, can someone please share resources they used to learn Trees/Tries.
I have no good resources to share, sorry
fiery cosmos
```py
def nums_tail(n: int):
if n >= 1:
nums_tail(n-1)
print...
Anyone?
ripe quest
print(2, end=' ')
primes = [2]
x = 3
try:
while True:
for p in primes:
if not x % p: break
if p >= primes[len(primes) // p]:
primes.append(x)
print(x, end=' ')
break
x += 2
except KeyboardInterrupt:
print('\nKeyboardInterrupt')
^ only tests divisibility by prime numbers less than half of x then less than a third of x, < 1/5 x, etc
still slow though
fiery cosmos
I tested it 🙂 but I'm going now
ripe quest
ok 👋
old rover
def perc_up(self, i):
while i//2 > 0:
if self.heap[i] < self.heap[i//2]:
is i supposed to represent the index in a list
I think so
that would align w what I saw in the 50 minute video
self.heap = [(0)]
this is what self.heap is for context
not really sure what self.heap[i] does
today I learned perc is short for percolate
so perc up just swaps the child and the parent so the child percolates
but I still don't know what self.heap[i] is when it says that self.heap is equal to the 0th index
vocal gorge
```python
self.heap = [(0)]
```
that's what it is initialized to, not what it is in general
old rover
"You will notice that an empty binary heap has a single zero as the first element of self.heap and that this zero is not used, but is there so that simple integer division can be used in later methods."
so it's supposed to represent the index of the first element
lean dome
is i supposed to represent the index in a list
Whenever you see a variable named i, either a) it's short for "index", or b) someone is terrible at conveying their intent.
old rover
ah
ok
I will keep that in mind from now on
also
what's the point of [0] v [(0)]
is that a tuple in a list in the second one
yeah I don't think there is a point
def perc_up(self, i):
#i means index
while i//2 > 0:
if self.heap[i] < self.heap[i//2]:
self.heap[i], self.heap[i//2] = self.heap[i//2], self.heap[i]
i = i//2
what's the point of floor division on i at the end
I think perc up is O log n
dependent on the height of the tree
lean dome
is that a tuple in a list in the second one
No, non-empty tuples need a comma. (0) is 0.
lean dome
what's the point of floor division on i at the end
it cuts i in half, flooring down to an int
old rover
you can't have a tuple with just one element?
old rover
it cuts `i` in half, flooring down to an int
yeah but why do that
why can't you just leave i as it is
am I not making sense
lean dome
because then the loop would never end
old rover
oh
ok
while i//2 > 0:
they're doing i = i//2
so they can exit out of this while loop?
why am I confused
lean dome
the loop stops when i drops to 0. The i = i // 2 is the thing that changes i
lean dome
!e ```py
i = 20
while i // 2 > 0:
print(i)
i = i // 2
@lean dome :white_check_mark: Your eval job has completed with return code 0.
001 | 20
002 | 10
003 | 5
004 | 2
if you keep floor-dividing any positive integer by another positive integer greater than 1, eventually it will reach 0
meager jetty
just in case somebody need this ... https://wiki.python.org/moin/TimeComplexity
brave oak
Whenever you see a variable named `i`, either a) it's short for "index", or b) s...
i can refer to the first axis
like i, j, k
that's the other legitimate use I can think of
meager jetty
i,j,k are index and x,y,z the values :O)
meager jetty
but with 2 +3i i is the imaginary part of a complexe number lol
meager jetty
I tought AVL tree implemented in array, hum maybe fast search and acces time easy level traversing ..., but rebalancing is ugly ... and yes look here https://stackoverflow.com/questions/16414429/implementing-an-avl-tree-using-a-list
so I will forget about it and open a beer instead lol
glad urchin
how do I type code?
meager jetty
!code
halcyon plankBOT
echo spear
Hello I'm just gonna ask if do you guys know and can explain c programming because I'm having difficulties understanding it?
dapper sapphire
Hello I'm just gonna ask if do you guys know and can explain c programming becau...
I can give it a try. I have done a bit of C.
echo spear
thank you sir i dont know if how can we talk about it since i have a lot of assignments to do ill message you when im free if thats okay with you
dapper sapphire
If you dont have a specific question at the moment, maybe try posting your question in c-extension channel
echo spear
aight thank ill post it there
thin roost
I did operating systems in C so hopefully I can try to answer some 🙂 although C is my nightmare lmao
stoic oracle
I have a data structure problem over at #help-cupcake if anyone has a moment... thanks!
ripe quest
I have improved and fixed my prime number generator
def nthPrime(n):
primes = [2]
x = 3
try:
print(f'Generating the first {n} prime numbers...')
while len(primes) < n:
for p in primes:
if not x % p:
break
elif p >= x // p: # if divisor set is empty or {p}
primes.append(x)
break
x += 2
else:
print(f'{n}th prime is {primes[-1]}')
except KeyboardInterrupt:
print('\nKeyboardInterrupt')
clear tiger
How can I use indexing to grab the word 'hello'
[9:19 AM]
lst = [1,2,[3,4],[5,[100,200,['hello']],23,11],1,7]
[9:20 AM]
How does this work?
fiery cosmos
lst[3][1][2][0]
rugged quiver
you can't have a tuple with just one element?
yes you can: (0,) is a one-element tuple
ripe quest
the comma makes it a tuple so 0, is just as well
fiery cosmos
I need to list all the files in a directory and its subfolders and print the files creation date, but I always get the error "file not found ._." can someone help?
import os
from datetime import datetime
root = r"C:\Users\user\Documents"
for path, subdirs, files in os.walk(root):
for name in files:
try:
position = path.replace(root, "").replace("\\", "/") + name
print(position)
date_raw = os.path.getmtime(position)
date_formated = datetime.fromtimestamp(date_raw).strftime('%Y-%m-%d')
print(date_formated)
print(position + date_formated)
except:
print("file not found ._.")```what exception are you getting
fiery cosmos
FileNotFoundError: [WinError 2] The system cannot find the file specified:
so does anyone know?
thin roost
FileNotFoundError: [WinError 2] The system cannot find the file specified:
I am not using Window but does it have to be C:\ \ instead?
meager jetty
Hello I'm just gonna ask if do you guys know and can explain c programming becau...
Get K&R The C Programming Language 2nd Edition ! https://en.wikipedia.org/wiki/The_C_Programming_Language
mint jewel
is the 2nd edition more up to date?
fiery cosmos
I've been going through this to learn C https://beej.us/guide/bgc/pdf/bgc_a4_c_1.pdf
meager jetty
2nd edition is THE ansii standard definition of the language
fiery cosmos
Beejs guide to c
fiery cosmos
! Code
old rover
?
spring jasper
So i was doing codejam
Is there a fancy fast way of generating permutations for a string thats partially filled?
eg i have a string "CJ?CC?" and i want all permutations of the string where "?" is replaced with either "C" or "J"
So i'd get back four strings
"CJCCCC"
"CJJCCC"
"CJCCCJ"
"CJJCCJ"
What i tried was
from itertools import product
for prod in product("CJ", repeat=string.count("?")):
generated = list(string)
for char in prod:
generated[generated.index("?")] = char
generated = "".join(generated)
But this times out so i had to scrap it
agile sundial
you can replace the "?" with "{}", and use .format
spring jasper
string2 = string.replace("?", "{}")
for prod in product("CJ", repeat=string.count("?")):
print(string2.format(*prod))
Like so?
God this works, frick
spring jasper
Dangit thats so much prettier than what i used to complete the challenge
lean dome
Beejs guide to c
Ooh, I learned networking from Beej's Guide to Network Programming. Good stuff. I didn't know there were others.
cloud plover
Does someone have tips on how to learn algorithms I finished data structures in python and understood fluently until I got to graphs where I don't understand shit and pathfinding algorithms are even worse I looked into someone's Dijkstra's algorithm code and it just was so kuch functions and stuff and I just got lost with all pf those edges and connections that were implemented with dictionaries, can someone who learned it give tips on how to understand algorithms
spring jasper
God this codejam is a shitshow in any case
old rover
Does someone have tips on how to learn algorithms I finished data structures in ...
this is very good for a basic understanding
I myself haven't gotten up to graphs yet
still doing heaps
fiery cosmos
Ooh, I learned networking from Beej's Guide to Network Programming. Good stuff. ...
Yup he has a few more. A apha version book about Python aswell. Though I just read this about his C book on his website: This is a bit of a practice book for later when I write a real book. [...] Keep in mind that this is completely incomplete right now, and I haven't even read most of what I've written. Some of it is Just Plain Wrong. [...] Opps. I might want to find another book source..
old rover
def min_child(self, i):
if 2 * i + 1 > self.current_size: #No right child
return 2 * i
I'm a little bit confused by this
I know the right child is 2i + 1
but why say if it's bigger than the current size
how does that mean there's no right child
lean dome
The list isn't infinitely large.
old rover
if the right child is bigger than the current size
the current size of the heap?
is that what self.current_size means?
or are they saying current_size is the size of the list
lean dome
those are the same thing
old rover
I still don't understand what the point is of comparing the right child to the current size
if the index of the right child is bigger than the current size of the list
lean dome
you've got a list that's 3 elements long. The 0th element is the root, the 1th (2*0+1) is its left child, the 2th (2*0+2) is its right child.
If the left child of the root had a left child, it would be at 2*1+1, or index 3. But there is no index 3, the list is only 3 elements long, and the only indices are 0, 1, and 2.
lean dome
in a binary heap represented as an array, you can figure out what indices into that array the children of a particular index will be at, just by doing math on the index. If the array isn't that long, then that child doesn't exist.
old rover
why is that so hard to understand
lean dome
I don't know. The rule is "if the node at index i has a left child, it will be at index 2*i+1, and if it has a right child it will be at index 2*i+2"
if index 2*i+1 doesn't exist, then it doesn't have a left child. If index 2*i+2 doesn't exist, then it doesn't have a right child.
If you've got a list that's only 2 elements long, you have a root, and the root has a left child. It does not have a right child.
old rover
the youtube tutorial I watched had the left child be 2 * i and the right child be 2 * i +1
but that is probably bc he used indexes starting from 1
lean dome
right. That automatically adds 1 to every index.
In Python, if you did 2*i as the left child, then the left child of 0 would be 0, which is obviously wrong.
lean dome
so that they return None when asked for the index of the min child of the node with value 3
old rover
bc there is no index 3
lean dome
bc there is no index 7
old rover
oh bc 2 * 3 + 1
lean dome
the node with value 3 is index 2, its min child would be 2*3+1, yeah.
lean dome
er, yeah, oops
that should be 2 * 2 +1 == 5
we are. The node with value 3 is at index 2, so index 2 times constant 2 + 1 is index 5.
and because the list has no index 5, the node with value 3 has no min child, so the function to find the min child's index returns None.
old rover
def min_child(self, i):
if 2 * i + 1 > self.current_size: #No right child
return 2 * i
so if the index was 1
it would be 3
if 3 is bigger than the current size
what's 2 * i
the left child is 2i + 1
so what's 2i
lean dome
not specified
lean dome
I mean, you can figure it out
2*i is 2*(i - 1) + 2 - so it's the right child of node i - 1
old rover
what
lean dome
I'm not sure how I can answer that any more clearly. 2*i is not a child of node i; it's the right child of node i-1
you don't have to know what index 2*i is, it isn't important. The only important indices given i are the index of its left child 2*i + 1, the index of its right child 2*i + 2, and the index of its parent (i - 1) // 2
old rover
ok
lean dome
and the special cases for those are "if the index falls outside the array, then the node at that index has no (left child | right child | parent)"
old rover
yes
lean dome
so: The node at index 5 will have its right child at index 5*2+1, or 11. If there is a node at index 11, that's its right child. If index 11 falls outside the array, it has no right child.
The node at index 5 will have its parent at index (5 - 1) // 2, or 2. We know there is an index 2 (there has to be, since there's an index 5), so that's its parent.
The node at index 0 is the root, and doesn't have a parent. If we apply the "find my parent" formula, we do (0 - 1) // 2 and get -1, which is outside the bounds of the array, proving that there is no parent for node 0.
old rover
so I don't have to care what 2 * i is
it's just 2 times the index
I just don't know how 2 * i relates from an array to a heap
lean dome
right. If you did care, you could figure out what node 2*i's parent is, and which child of that parent it is - but you don't need to care.
lean dome
I don't understand what you're asking
old rover
how is 2 * i used in that array
nvm
it doesn't matter
I just don't know why he wrote that in his code
lean dome
I can't really tell without seeing more of the code, but - he's handling that case by returning a child of an entirely different node. 2*i is the index of the right child of node i-1
(because 2*(i-1)+2 is the right child of node i-1, and 2*(i-1)+2 is 2*i)
old rover
def min_child(self, i):
if 2 * i + 1 > self.currentSize: # No right child
return 2 * i
else:
# left child > right child
if self.heap[2 * i] > self.heap[2 * i +1]:
return 2 * i + 1
else:
return 2 * i
does that help
lean dome
not really - I'd need to see where min_child is called, to see how that special case is handled
old rover
def perc_down(self, i):
while 2 * i < self.currentSize:
min_child = self.min_child(i)
if self.heap[min_child] < self.heap[i]:
# Swap min child with parent
self.heap[min_child], self.heap[i] = self.heap[i], self.heap[min_child]
i = min_child
can that branch ever be taken?
old rover
!pastebin
halcyon plankBOT
lean dome
the loop is while 2 * i < self.currentSize, and the condition is if 2 * i + 1 > self.currentSize. If 2 * i < x, then 2 * i + 1 cannot be greater than x, assuming integer i and x
the largest integer smaller than x would be x-1, and if 2 * i == x-1, then 2 * i + 1 == x - it's not > x - so the if won't be taken.
unless I'm misreading something, I don't think that if condition will ever be true.
old rover
then what's the point of it 🥴
lean dome
I don't think there is one, I think he made a mistake.
old rover
def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i*2] < self.heapList[i*2+1]:
return i * 2
else:
return i * 2 + 1
this is another implementation
it also has the same condition
lean dome
how is minChild used in that implementation?
old rover
def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc
yeah, there's the difference
the loop in that one is while (i * 2) <= self.currentSize - in that case, (i * 2) + 1 can be greater, so there needs to be a check in minChild.
The loop in the first one you pasted is while i * 2 < self.currentSize - in that one, i * 2 + 1 can never be greater than self.currentSize, it is at most equal.
lean dome
I don't think it's just the unnecessary if statement - I think they may get the behavior wrong in the case where i * 2 == self.currentSize, though I haven't trace through to be positive of that.
actually, I'm not positive.
frozen smelt
howdy all,
I am new to Python and keep messing up a basic recursive algo and cant figure out why I get a None type as answer
def digital_root(n):
number = [int(x) for x in str(n)]
if len(number) > 1 :
number = sum(number)
return digital_root(number)
print(digital_root(16))
any help for a scrub would be helpful!
sorry, I know this isnt any of the help rooms but they all occupied!
thin roost
howdy all,
I am new to Python and keep messing up a basic recursive algo and ca...
Because after several recursions the len(number) will only be 1 left
old rover
def remove_min(self):
ret = self.heap[1] # the smallest value at beginning
self.heap[1] = self.heap[self.currentSize] # Repalce it by the last value
self.currentSize = self.currentSize - 1
self.heap.pop()
self.perc_down(1)
return ret
I thought the smallest value at the beginning would be self.heap[0]
thin roost
So at that time your function does not return anything
When you print it out it will just be just None
frozen smelt
I am trying to add all numbers in a list down to 1 number
so thought len(number) = 1 would be what I need?
so 16 would become 1 + 6 and = 7 ,
ooooh hang on, thats not returned into a list
old rover
also I don't approve of them using camelcase
it shouldn't be currentSize
it should be current_size
thin roost
ooooh hang on, thats not returned into a list
yeah and also your number is a list not an integer
frozen smelt
yea I was using number as a list for the sum function to add all the numbers up
agile sundial
they may be using a dummy value as the first index to make math easierr
old rover
so they're just saying that the index is 1
like udacity does
what's a dummy value again
agile sundial
value that doesn't do anything
sly verge
hi all, I have a matrix that shows the rate of agreement between different participants in a survey based on how many times they voted the same in some questions. What would be a good algorithm to cluster them based on similarity?
old rover
I don't get this psuedocode
I think heapsort would take self as a parameter
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < n and arr[largest] < arr[l]:
largest = l
# See if right child of root exists and is
# greater than root
if r < n and arr[largest] < arr[r]:
largest = r
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root.
heapify(arr, n, largest)
# The main function to sort an array of given size
def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
# One by one extract elements
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
this is how G4G does it
for i in range(n//2 - 1, -1, -1): what does that even mean
smh
no one is a big fan of G4G and I think I see why
!pastebin
halcyon plankBOT
old rover
this is some random guy's implementation
but he does the same thing
for i in range(n, -1, -1):
heapify(arr, n, i)
idk what that means
n is just a number
and then the first -1 is what it should be incremented to
and then the last -1 is what it should be incremented by
yeah I don't really know
it just seems like this guy copy pasted code from G4G
old rover
if l < n and self[largest] < self[1]:
largest = 1
how is comparing the left child to the size of the heap going to do anything
serene oracle
for i in range(n//2 - 1, -1, -1): what does that even mean
"start 1 slot short of half way up the array, and descend to zero"
agile sundial
all heapsort is, is just building a heap, and just popping nodes
old rover
yes
agile sundial
that's it
old rover
is heapify when you turn an array into a heap?
agile sundial
yeah
agile sundial
more precisely, you swap elements around to maintain the heap invariant
old rover
heap invariant... like the condition of being a max heap v a min heap?
solar timber
I just started using leetcode, and I don't understand how we need to write the code, I don't understand why there's a class mentioned in the beginning. Thanks for the help!
serene oracle
an invariant is a contract. i this case the contract is the heap property.
old rover
oh ok so what I said
solar timber
I do know how to solve the problem, I just don't know ho to write it in the class thing
old rover
do you know what a class is
solar timber
Yes
old rover
what's the problem?
# See if left child of root exists and is
# greater than root
if l < n and arr[largest] < arr[l]:
largest = l
I just don't get it wouldn't the size of a heap always be larger than an index?
agile sundial
if it exists, it would be smaller than the size
solar timber
what's the problem?
I need to check if a number is palindrome or not, I know how I will check it
class Solution:
def isPalindrome(self, x: int) -> bool:
old rover
if it exists, it would be smaller than the size
what is "it"?
agile sundial
the left child
solar timber
class Solution:
def isPalindrome(self, x: int) -> bool:
But this is already written, what do I do?
vocal gorge
But this is already written, what do I do?
This is the function declaration with a typehinted signature. Just write your code in the body.
solar timber
And do I need to return a value?
vocal gorge
(the type hints here just mean x is an int and the function must return a bool).
yup
serene oracle
l<n is checking that the array indexes are legal, arr[largest] < arr[l] is checking if the elements at those indexes need to be swapped
keen hearth
is heapify when you turn an array into a heap?
One of the surprising things about the heapify operation is that it's O(n). If you inserted each element into the heap one-by-one, that would be O(n log n) (as there are n elements and insertion is an O(log n) operation).
old rover
oh
keen hearth
So a heap is quite useful if you want to get the k smallest elements from a list with n elements, and k is much less than n.
You can heapify the list, then heappop k times.
vocal gorge
huh, would that be O(n)?
keen hearth
That would be O(n + k log n) I think.
agile sundial
^
vocal gorge
oh, that's very nice. I should remember that the next time I need k-lowest elements; I usually do that by sorting unless I only need k=2 or so (in which case it can be done in one loop)
agile sundial
heapq.nlargest 😔
vocal gulch
hi
where should i go for 3d modelling?
like i'm trying to work on a program about modelling lidar images
and i have something where i can create really nice looking 3d models based off of points
but i'm hoping to be able to put them into cad files
old rover
if l < n and self[largest] < self[1]:
largest = 1
what does largest = 1
mean?
the largest is the 1st index?
wrong channel, but try #data-science-and-ml
orchid otter
ok, sorry
old rover
the largest is the 1st index?
that is all I can think of
vocal gorge
```python
if l < n and self[largest] < self[1]:
largest = 1
```
well, if self[1] > self[largest], then largest should be changed to 1, since the current value is clearly not the index of the largest value
old rover
if the left child is bigger than the size of the heap
what is largest
largest = i # Initialize largest as root
largest is the root
and the root is smaller than the 1st index
make the largest the 1st index
instead of the root
wait
I'm actually stupid
it looks to me like they're saying that largest isn't being assigned to 1
it's being assigned to L
or am I wrong?
agile sundial
syntax highlighting ftw
old rover
yeah now I see why it exists
I think it is l
it would make the most sense
especially since there's another if statement which ends with the largest being the right child
lean dome
That's l and not 1
lean dome
You can see that the top of the number 1 is slanted, and the top of a lowercase l is straight.
old rover
I am tired 🙂
agile sundial
numbers are green,too
thin roost
lean dome
That's not a great font, honestly. They're much too similar, but you can see the difference.
misty plume
hello everyone, can anyone help me with some graphs algorithms problems? I'm having trouble with them. Already asked for help a few days ago but couldn't connect
misty plume
so basically, the problem is a depth first algorithm
I have the algorithm that checks every node
and the nodes that it points to
and in order to complete the problem, it has to print Yes on the screen, only if starting from one node(doesn't matter which one) you can get to all of the rest
and that's what I don't know how to do, the implementation of the depth algorithm is given to us, but I don't really understand it 100% to be fair
lean dome
So you're supposed to find if the graph is connected or disconnected
misty plume
yes
as you can see, dfsRec and dfs is a recursive way of implementing the depth algorithm
I thought about checking if the visited array that you create on dfs has the same length of true (visited) nodes as the original g[]
but I'm a bit lost on python and lost in graphs overall
lean dome
I'm not understanding that for v in range(1, n) line... Seems like it ought to be range(0, n) instead... I don't see why you'd start at 1 instead of 0...
misty plume
I had that question too, I leaved it like that because that's the original algorithm that they gave me
because leaving the 1 means that you go from 1 to n right?
misty plume
ow I see