There may be a caveat here. According to the docs, the time complexity for deque.rotate(k) is O(k). In this case, when k

@kikivoorburg

6 ай бұрын

Unless I’ve missed something, it would be possible to handle k > n/2 by counting n-k items backwards from the end of the list. That would make n/2 the worst-case. I’m not sure if you already realised that, but I thought I’d mention it anyway since your comment didn’t make it explicit. I could also be wrong, please correct me if I am!

@MrAnonEMoss

6 ай бұрын

@@kikivoorburg Yeah, I was kind of thinking along those lines, but I didn't want to put it in my comment because I wasn't 100% sure. But yeah, I think you're correct on that

@MrAnonEMoss

6 ай бұрын

And I ran the code on my computer. In the situation presented in the video, when we have 1,000,000 soldiers and k=3, the amount of time it took on my computer was 0.14 seconds. When I ran it with 1,000,000 soldiers and k=500,000, it took 77.25 seconds

@antonhelsgaun

6 ай бұрын

​@@kikivoorburgO(n/2)=O(n), though

@valdrich472

6 ай бұрын

is there a way to 'pop' multiple items from a list? In R I'd append (of sorts) every k-th element from the array, after accounting for the leftover elements from the previous loop. This would be even faster for k

To be pedantic about it, the pythonic "list" in a dynamic array which is also known as a vector. Whereas the deque is a type of doubly linked list which is called "list" for short, compaired to the vector.

@DeclanMBrennan

6 ай бұрын

Not just pedantry - I think this can be confusing for new developers. Alas the list terminology is misused in some other languages as well, so it's probably too embedded to be changed at this point.

@gangulic

5 ай бұрын

Coming from C language I’ve always thougth python list is same as a linked list just with some additional perks

You have no idea about how helpful and useful you are for people like me. I’m a data analyst who predominantly uses Python and this is super super useful. God bless you ❤

@anuragpant2632

5 ай бұрын

Hey can u tell me what is the use case of this algorithm

@rembautimes8808

4 ай бұрын

I like this content and it’ll be good to see use cases of deque so we know when to apply it

@thebeastsclips

4 ай бұрын

​@@anuragpant2632the deck is faster for larger input/array.

the font is brass mono cozy for those who are wondering

You're one of the few programming KZreadrs I've found that strike the balance of being approachable for beginners and don't gloss over best practices and the relevant CS concepts that people need to grow (time complexity, data structures, etc). Love the content

One of the best videos ever. Instead of a dry approach, you explained Lists, deques AND the Josephus permutation in a fun way where you gradually build upon the solution one step at a time. Seeing the code getting improved was magical and I felt like I learnt something useful that I won't forget. Two thumbs up!

A while back I derived a formula to find the last guy in this problem after watching a numberphile vid about it. the formula is f(x)= 2(x-2^(floor(log'base2'(x)))) +1. I plotted it in desmos and it looked pretty cool.

@b001

6 ай бұрын

I plotted it in desmos and that's really interesting. That's for k=2, right? I wonder if there are formulas for other k-values? Thanks for sharing!

@maxsurman7838

6 ай бұрын

​@@b001perhaps this is too simple, but just replace the 2 values with k?

@machado8127

6 ай бұрын

@@b001Well I tried deriving one but couldn’t, and when I looked online, there were none like f(x)= formula style. So if someone finds it they gonna get famous.

@poki6041

4 ай бұрын

​@@machado8127i used chat gpt i got this x = \frac{k - 1}{2} + 2^n k-1/2+2^n But ithink its shit lol

I've never heard of deques before but as soon as you explained how they work, I knew you were talking about a linked list! Wonderful video

I really enjoy your videos, no useless flashy intro, straight to the point and for me a lot of unique content I didn't see anywhere else. Thank you very much

I've watched a few of your videos, and while they were interesting, they were not quite enough to motivate me to give you a subscribe. This one got it. That's incredible.

Your video is great, as always! I am a huge fan of this type of content.

You’re explaining, voice and teaching are very helpful and informative, you earned a new subscriber and I’m hoping to see more content like this, I’m gonna start learning python soon and I’m gonna need content like this

Hi b001! Your videos are really well made and clear. I wondered what software/tools do you use to create your videos and the animations. Keep up the good work.

Oh wow. Recently discovered your channel through your list comprehension video. Your explanation style amazing! Subbed!

yeah man that presentation is amazing! MANY MANY THANKS

Very clever use of Mod Operation

This video really helped me understand deque. Are you planning to go through the rest of the data structures other than the ones you have covered?

@b001

6 ай бұрын

Potentially, eventually!

I found your channel and it's one of the best I've ever seen , thank you for your videos i hope you can cover more topics and explain them for beginners like me 🎉

It’s wonderful to see the deque or linked list being utilized in python!

Great video as always! Keep them coming please! Just want to add that from some simple tests I've run, if you only require to pop one (or very few?) items, d = deque(array) takes more time than the popping saves. In other words, the conversion to deque outweighs the benefits of deque popping. However, obviously if you have n popping operations to do, then the conversion time becomes negligible in comparison.

Awesome content and explanation! Thanks!

Your videos are very understandable and clear. I suggest you create a full course on Python. Thank you.

I had seen usage of deque in DSA course in the past, but I had trouble understanding why it was used back then. Now it's pretty clear :-) Cheers!

This is beautifully done.

One thing to keep in mind, though, is cache invalidation (which granted, if we're using python, it might be the least of our problems). Depending on the sample size of our data, the deque approach might be less efficient than the array one, or vice versa.

These videos make me so excited to start my career

Yo, i really love this CP contents, thank you so much for this. Hope you can do other video relating to standard libraries such as Pandas or Numpy :DDD

To be honest, I had never considered this Data Structure. Thank you @b001 for the video. Very informative and helpful!

Good stuff! Subbed!

I've used a deque before, but I didn't know about rotate. Looks like the perfect data structure for this problem.

wow such a great video!! could you please tell me which software or where to edit those array animations you're making in your videos. Thanks in advance :))

I'd be curious of the memory implications of this. deque sounds like a doubly linked list so rather than working with an array of primitives there is a large number of objects. Now, granted my background is C++/C#/Java so I'm willing to accept that I'm wrong completely in my assumptions, but I would assume that using the code would result in a large number of objects on the heap. Is there a significant difference in memory allocations?

@the_cheese_cultist

6 ай бұрын

there are multiple implementations of deque. a linked list is one of them, but it's not the most common. most deque implementations used allow constant index access. you can look at the Wikipedia page for more info.

@julsmanbr8152

6 ай бұрын

There are no primitives in Python, even things like integers and strings are all encapsulated by objects. So in the end, regular lists and deques are both objects that store other objects.

Your videos are so good! Are you using a specific textbook to get these information from?

Love your videos! could you do some custom exception errors, or decorators por functions ?

List is more of a generalization of a linear structure (specifically Sequences or Tuples), that allows for appending / removing- Queues do this as well, (and are also generalized: as there are different types of queues), but could be represented by a Tree, rather than a Tuple- The tree is a “Fan of degree-1”, for queues and stacks- and is better for appending / removing elements, but removes random access to those elements. The queue gets a reference to a “Head” and “Tail”: tails can only be added to; whereas, heads technically allow removal and adding (in a ~singly directed graph). The stack gets just a “Head” reference instead to add/ remove. For ~doubly directed graphs (some might consider this “undirected”, but I think there’s a difference), then there is more symmetry, and you can add / remove from either side. Also, you can iterate forwards and backwards (instead of just forwards). It uses quite a bit more memory though PS: (Memory optimization idea) Each directed edge is an Object reference can be replaced with an integer reference to a hash-code that will map to a unique object in an outside list (this is exactly how a hashmap works) Technically a hashmap stores Pairs, in a sublist, to avoid “collision” with the hashes- and we should do the same. Cheers

@tylerbakeman

4 ай бұрын

Also. Lists from Tuples, are great because they allow for random access. So choose your data structure wisely.

As others noted when using the deque hte complexity becomes O(n*k). The same can be achieved by looping over an array with two indexes, compacting the array while searching it. E. g. for k=3 you would do copy, copy, skip, copy, copy, skip. This should be asymptotically the same but have better constants. For large k a red-black-tree, splay-tree or a skip-list would be much, much faster.

Instant subscribed

Amazing.. great job !

It would be great if there was a playlist for all the data structures that is built-in python.

I know it might not fetch as many views as the simpler, common Videos, but please keep posting about these more advaced topics. Theres enough beginner coding, we need some good stuff :) thank you!

Interesting that popping the array correctly models the problem, which is not immediately obvious from the visual representation.

Hey Your videos are amazing. Can you tell me the theme you are using in your IDE?

Ok now I’m pretty sure c++ has a completely different implementation of deque that is far more logical to call it a double ended queue. I’ve always thought that they are the same!

@hotwheelz5686

6 ай бұрын

It is just a Linked List, also I remade the solution in C++, without the Linked Lists though, just to see how much faster C++ was, and it was 26 seconds for 1 million elements (with me removing the element), without removing the element, and just adding the element to the return array, it is 34 milliseconds.

@XirevWoW

6 ай бұрын

@@hotwheelz5686 By not removing the item from the list, did you account for the fact that you're now 1 step behind where you would otherwise be if you had removed the item? Since when you remove an item, what was 1 index ahead of you, is now the index you are currently on. And since you are not removing the item, won't you just rotate around the list to the same positions? And when are you determining that you have "killed" all of the men? Since he's checking for when the list is empty to stop looping.

@hotwheelz5686

6 ай бұрын

@@XirevWoW I indeed did forget about that, although it would not have any implication with the time of soultion, although it would be an incorrect solution, but I was more just looking at the time difference between C++ and Python, and I remade it in like 5 mintues and called it good lol, but not decrementing the index would create an incorrect solution

Nice vid, though I wouldn’t say outright better is correct. Like everything, there is a trade off. Lists: O[n] worst case removal, O[1] lookup. Deques: O[1] removal, O[n] worse case lookup. There is also cache coherence to think about, which lists are very good at thanks to be continuous in memory, while deques are very bad thanks to being spread in memory. As usual, the best thing to do is measure, try something different, measure again.

Hi! I quickly want to ask what vs code theme you're using as I realy like the coloring.

Thanks man

The video is so clean. What do you use to create your animation /illustration?

@user-pu1mf8px5e

5 ай бұрын

Same question. do you know any animation software where we can edit those Array like animations ???

Cool video, bro! What color theme do you use for coding? It looks fire

@xdanic3

6 ай бұрын

Seems like SynthWave '84 to me

@danda_legenda

6 ай бұрын

@@xdanic3 thank you

When you showed the memory operations for deque I realized: Oh thats a doubly linked list, cool

very helpful !

This code is relying upon an implementation detail of deque. Deques only guarantees O(1) for push_front() and push_back()--there's no such guarantee for rotate() or arbitrary deletion. A link-list implementation of deque has fast rotation, but another common implementation of an array of dynamic arrays (aka array deques) has very slow rotations.

What vs code theme are you using? I really love the look of the syntac highlighting and vibrancy. Also, nice video about deque :D

@xdanic3

6 ай бұрын

Looks like SynthWave '84

@b001

6 ай бұрын

SynthWave’84

Good information

Finding about that new form of linked list tingles my brain 😁😁 BTW, if I wanted to learn python on my own through the official docs, how would I do that ? I mean no offense but python's docs is the _most messiest_ docs I've ever seen, just right after Microsoft's VBA docs. (I guess that's why they implemented it to MSExcel lol)

Might be a bit of a meme question but what VSCode theme are you using? It kinda looks like Tomorrow Night Blue

Not sure how. But somehow i found myself here. And now I have my new favourite coding channel.

Thing is that if i m not wrong, each element of the deck will take way more memory as he has an integer (32 bits), and 2 pointers (128 bits) wich give us 160 bits in emory for one element instead of 32 bits for an array. So as my college teacher says, the perfect algorithm doesn't exists, its just a story of memory cost and temporal cost balance.

When seeing the rotation, my first thought is just why is traversing through pointers until the head is at the right one any faster than o(n), making it still overall o(n^2)?

Question about list example, I have 2 lists, arr1 is numbers, arr2 is chars arr1 = [1, 2, 3, 3.14, 4, 5] arr2 = ["a", "b", "c", "d", "e"] I want to combine them, but... Should I user rr3 = arr1 + arr2 or? arr3 = arr1.copy() + arr2.copy() which one is better?

tanks

Nice video, brow!

more videos likes this please

Isn't the time complexity O(N/2) when going through a doubly link list/deque, there by making the time complexity O(N*(N/2)) and not O(n)? And the gains come from not having to shift all the data in memory and instead just having to change a single pointer? Or am I thinking wrong somehow?

@Felle2002

4 ай бұрын

Wait just realised that I'm wrong since we will have rotated the list so you just have to go 3 more spaces in the while loop

So instead of O(n^2) it’s O(n*k), for n rotate operations which take (I think) k time to complete?

Yeah you can't sort deques in O(nlogn). You also can't search a sorted deque in O(logn).The continuous memory list is pretty handy for this. You should add this caution at the end in my opinion.

May I ask how did you do this animation?

What's the name of the monospace font you use? Looks pretty clean.

@saintjonny

5 ай бұрын

if you get to know let me know as well. thanks

@saintjonny

5 ай бұрын

after 8 hours of searching for this font and opening over 100 tabs i found this font, its called brass mono cozy

@d3f3kt57

5 ай бұрын

Thank you! You have the patience of a saint indeed. @@saintjonny

@saintjonny

5 ай бұрын

@@d3f3kt57welcome

I never though yet another data structure existed in python Is there more unknown data structure in python hidden from us like that ?

I just watched class in 1 minute and I like how u explain class function can u do python for beginners

Why is your code terminal so cool ?

Keep up 👏

Josephus : casually takes out his laptop and codes a python program that takes 2 mins to make sure he survives others : what the hell is he doing b001 : hey would you mind if i barrow that idea for a video?

I'm waiting for the person who always comments a one-liner solution.

For the array why not just use the range function?

Rotate the deque like a DJ on the decks, scratchin’ left or right for the choice cuts

What theme and font is this?

Naming this data structure deque is really confusing to me, because it is essentially a double linked list. In C++ for example deque is implemented using a dynamic array and it allows for element access in constant time as well as appending and popping from both sides. So to compare time complexity (C++ vs python): Append/pop (any side): O(1) (amortized I believe) vs O(1) Remove given element: O(n) vs O(1) Access random index: O(1) vs O(n) So it's a completely different structure. Really weird naming decision.

Wouldn't rotate be O(n) now?

why would you need memory structures for this at all? simple iterative function mod highest number and loop highest number times in total

there is a way to crunch this algorithm down to 1 line

Nice vid lol 🎉

which font do you use brother?

@saintjonny

5 ай бұрын

after 8 hours of searching for this font and opening over 100 tabs i found, its called brass mono cozy

Whats the font being used anyone aware.. I find it pretty cool...

@saintjonny

5 ай бұрын

after 8 hours of searching for this font and opening over 100 tabs i found this font, its called brass mono cozy

holllly molly WTF......., this really helped me while True: print("thank you")

I am still confused why you are rotating elements in deque? It is a double ended queue, why bring the element in head to delete it? Just traverse to the element and remove it from there. I am confused, is there a difference in this or something? I haven't used queues and stacks in python, so..

what is the theme you use? it isn't synthwave

I hope one day I’ll be this good in algorithms😢

@ngspace9829

6 ай бұрын

You will!

do more of solving a problem to teach a concept

😮😮😮 👏👏👏👏👏

I hope Josephus knew about deques as well

what is your vscode theme

@Aadoxide

5 ай бұрын

synthwave '84

So why not just use a linked list?

here is my solution using lists :) it is 4x faster from time import perf_counter def solution(array,n): result=[] offset=n-1 while l: offsetneu=(offset-len(l))%n result.extend(l[offset::n]) del l[offset::n] offset=offsetneu return result k=1000000 n=3 l=list(range(1,k+1)) start=perf_counter() sol=solution(l,n) print(perf_counter()-start) print(sol[-100:])

i can do this in O(n*logn) with Fenwick Tree

This "deque" is almost like a doubly linked list!

@b001

6 ай бұрын

Yep, that’s how it’s implemented in Python

@braydenmchan

6 ай бұрын

@@b001 ahhh okay that makes sense. It's cool that Python has an implementation of this. Look at that, learning something new every day!

very cool but list comprehensions are faster: [x * k % soldiers for x in range(1, soldiers)]

it is definately link list in C++, isn't it

It's another year of AOC, the deque is so helpful if you want to get to the leader board

That solution is still really slow. Rotating deque still takes O(n).

why not show how deque performs with a million soldiers compared to lists?