Are THESE Better Than Lists?? - The Josephus Permutation
Vložit
- čas přidán 29. 11. 2023
- ⭐ Join my Patreon: / b001io
💬 Discord: / discord
🐦 Follow me on Twitter: / b001io
🔗 More links: linktr.ee/b001io
Background Music:
Mood by Alex-Productions | onsound.eu/
Music promoted by www.free-stock-music.com
Creative Commons / Attribution 3.0 Unported License (CC BY 3.0)
creativecommons.org/licenses/...
Slowly by Tokyo Music Walker | / user-356546060
Music promoted by www.free-stock-music.com
Creative Commons / Attribution 3.0 Unported License (CC BY 3.0)
creativecommons.org/licenses/...
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.
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.
Coming from C language I’ve always thougth python list is same as a linked list just with some additional perks
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
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!
@@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
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
@@kikivoorburgO(n/2)=O(n), though
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
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 ❤
Hey can u tell me what is the use case of this algorithm
I like this content and it’ll be good to see use cases of deque so we know when to apply it
@@anuragpant2632the deck is faster for larger input/array.
You're one of the few programming CZcamsrs 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
the font is brass mono cozy for those who are wondering
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!
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.
Oh wow. Recently discovered your channel through your list comprehension video.
Your explanation style amazing! Subbed!
Your video is great, as always! I am a huge fan of this type of content.
yeah man that presentation is amazing! MANY MANY THANKS
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.
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 🎉
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.
It’s wonderful to see the deque or linked list being utilized in python!
Awesome content and explanation! Thanks!
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 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?
Potentially, eventually!
Your videos are very understandable and clear. I suggest you create a full course on Python. Thank you.
This is beautifully done.
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
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.
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!
@@b001perhaps this is too simple, but just replace the 2 values with k?
@@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.
@@machado8127i used chat gpt i got this
x = \frac{k - 1}{2} + 2^n
k-1/2+2^n
But ithink its shit lol
To be honest, I had never considered this Data Structure. Thank you @b001 for the video. Very informative and helpful!
Good stuff! Subbed!
These videos make me so excited to start my career
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 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!
Instant subscribed
Amazing.. great job !
Your videos are so good! Are you using a specific textbook to get these information from?
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.
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.
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
Also. Lists from Tuples, are great because they allow for random access. So choose your data structure wisely.
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?
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.
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.
Love your videos! could you do some custom exception errors, or decorators por functions ?
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.
Cool video, bro!
What color theme do you use for coding? It looks fire
Seems like SynthWave '84 to me
@@xdanic3 thank you
The video is so clean. What do you use to create your animation /illustration?
Same question. do you know any animation software where we can edit those Array like animations ???
Hey
Your videos are amazing.
Can you tell me the theme you are using in your IDE?
What vs code theme are you using? I really love the look of the syntac highlighting and vibrancy. Also, nice video about deque :D
Looks like SynthWave '84
SynthWave’84
very helpful !
Nice video, brow!
It would be great if there was a playlist for all the data structures that is built-in python.
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.
Thanks man
Good information
very useful!
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)?
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!
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.
@@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.
@@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
Interesting that popping the array correctly models the problem, which is not immediately obvious from the visual representation.
When you showed the memory operations for deque I realized: Oh thats a doubly linked list, cool
Hi! I quickly want to ask what vs code theme you're using as I realy like the coloring.
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)
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?
Might be a bit of a meme question but what VSCode theme are you using? It kinda looks like Tomorrow Night Blue
more videos likes this please
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.
Not sure how. But somehow i found myself here. And now I have my new favourite coding channel.
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?
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
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.
I never though yet another data structure existed in python
Is there more unknown data structure in python hidden from us like that ?
So instead of O(n^2) it’s O(n*k), for n rotate operations which take (I think) k time to complete?
Keep up 👏
What's the name of the monospace font you use? Looks pretty clean.
if you get to know let me know as well. thanks
after 8 hours of searching for this font and opening over 100 tabs i found this font, its called brass mono cozy
Thank you! You have the patience of a saint indeed. @@saintjonny
@@d3f3kt57welcome
May I ask how did you do this animation?
Nice vid lol 🎉
I just watched class in 1 minute and I like how u explain class function can u do python for beginners
tanks
Rotate the deque like a DJ on the decks, scratchin’ left or right for the choice cuts
Why is your code terminal so cool ?
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?
For the array why not just use the range function?
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.
I'm waiting for the person who always comments a one-liner solution.
Whats the font being used anyone aware.. I find it pretty cool...
after 8 hours of searching for this font and opening over 100 tabs i found this font, its called brass mono cozy
why would you need memory structures for this at all?
simple iterative function mod highest number and loop highest number times in total
Wouldn't rotate be O(n) now?
holllly molly WTF......., this really helped me
while True:
print("thank you")
which font do you use brother?
after 8 hours of searching for this font and opening over 100 tabs i found, its called brass mono cozy
What theme and font is this?
there is a way to crunch this algorithm down to 1 line
do more of solving a problem to teach a concept
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:])
what is your vscode theme
synthwave '84
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..
I hope one day I’ll be this good in algorithms😢
You will!
I hope Josephus knew about deques as well
what is the theme you use? it isn't synthwave
This "deque" is almost like a doubly linked list!
Yep, that’s how it’s implemented in Python
@@b001 ahhh okay that makes sense. It's cool that Python has an implementation of this. Look at that, learning something new every day!
It's another year of AOC, the deque is so helpful if you want to get to the leader board
😮😮😮 👏👏👏👏👏
So why not just use a linked list?
very cool but list comprehensions are faster: [x * k % soldiers for x in range(1, soldiers)]
i can do this in O(n*logn) with Fenwick Tree
it is definately link list in C++, isn't it
That solution is still really slow. Rotating deque still takes O(n).
hi
hi
@@b001 what font is that