Are THESE Better Than Lists?? - The Josephus Permutation

[@MrAnonEMoss]

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]

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]

@@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]

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]

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

[@valdrich472]

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

[@austinnar4494]

You're one of the few programming KZbinrs 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

[@Thekingslayer-ig5se]

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]

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

[@rembautimes8808]

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

[@thebeastsclips]

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

[@mithilbhoras5951]

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!

[@yuu-kun3461]

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]

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]

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

[@AG-ur1lj]

@@DeclanMBrennanthe irony kills me. I’ve listened to engineers drone on for hours about the importance of “good names,” yet the industry as a whole is addicted to the foot-gun. And it just keeps going. Google finds some peculiar characteristic of LLMs? “Hey guys, let’s call them ‘hallucinations’! That sounds really clever and creative. It couldn’t possibly create problems and confusion in the future.” Nice job! Good thing a company that specializes in word search was on that one👍🏻

[@saintjonny]

the font is brass mono cozy for those who are wondering

[@BeriBGood]

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

[@Haagimus]

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

[@machado8127]

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]

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]

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

[@machado8127]

@@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]

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

[@tylerbakeman]

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]

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

[@DrummingDivingPythonProgrammer]

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.

[@ksulimma]

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.

[@johnmurphy9727]

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

[@dogslife4831]

Very clever use of Mod Operation

[@GetPsyched6]

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]

Potentially, eventually!

[@soyitiel]

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.

[@yannisbekiaris]

yeah man that presentation is amazing! MANY MANY THANKS

[@HarryC4615]

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.

[@FriendlyCodeBuddy]

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

[@devonharvey8414]

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

[@ladyravendale1]

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.

[@compucademy]

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

[@xXYourShadowDaniXx]

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

[@pranavakailash8751]

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

[@Jelqmaxxer-f5b]

These videos make me so excited to start my career

[@oro5421]

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]

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]

@@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]

@@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

[@RAyLV17]

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

[@MiguelRojas-ud5cm]

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 🎉

[@AnubhavSharma-e6r]

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

[@GenarDarwish]

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

[@kenhaley4]

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

[@Spamuse-w3i]

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 :))

[@temptedtrevor8498]

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

[@CaptMirage]

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?

[@longbranchgooberdapple2238]

tldr: proper data structure for your problem is very important. It could make a 100x difference in calculation time and/or complexity.

[@goforit2085]

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.

[@GfoxSim]

I really enjoy your videos.

[@eldaiblol1492]

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!

[@FormatException]

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]

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]

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.

[@remipelletier5117]

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.

[@hifive5067]

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!

[@plekkchand]

This is beautifully done.

[@kvetter]

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.

[@karreevn9085]

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

[@Aborrajardo]

Awesome content and explanation! Thanks!

[@stacksmasherninja7266]

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.

[@chri_pierma]

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

[@danda_legenda]

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

[@xdanic3]

Seems like SynthWave '84 to me

[@danda_legenda]

@@xdanic3 thank you

[@filipkrawczyk9630]

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.

[@Felle2002]

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]

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

[@nits_koh]

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

[@Spamuse-w3i]

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

[@Malsavahara]

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

[@Miryxem]

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

[@varshard0]

Instant subscribed

[@thefanboy3285]

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)

[@sohailraufi1630]

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

[@CoderIQBE]

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

[@gentlemanbirdlake]

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

[@joshuat6124]

Good stuff! Subbed!

[@m7b774]

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

[@Idan_Nesimov]

Amazing.. great job !

[@dawidsz56]

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?

[@ajflink]

Whenever working with strictly a list of numbers, I always use the array module, especially with integers. deque seems more inviting to me now as the docs made me think: In what scenario would I ever use this? Also, if you are just going to pop the last element of a list (i.e. the rightmost) throughout a process if at all, it seems like deque may be a bit redundant. However, most other scenarios, deque seems like the better option unless memory is a huge thing you need to consider.

[@hk254lyt8]

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

[@ngspace9829]

You will!

[@nubbieeee]

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]

Looks like SynthWave '84

[@b001]

SynthWave’84

[@d3f3kt57]

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

[@saintjonny]

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

[@saintjonny]

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

[@d3f3kt57]

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

[@saintjonny]

@@d3f3kt57welcome

[@konstantinbachem9800]

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:])

[@rami5801]

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

[@shakils1921]

Thanks man

[@hamzahakoun1072]

more videos likes this please

[@igris_tec]

Yeah, but how do I make normal permutations? (ABC)!

[@NStripleseven]

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

[@malchemis]

Why is your code terminal so cool ?

[@OmegaMetorOutside]

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)?

[@antonhelsgaun]

So why not just use a linked list?

[@AilentRed]

very helpful !

[@digitalmachine0101]

Good information

[@braydenmchan]

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

[@b001]

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

[@braydenmchan]

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

[@Chris-op7yt]

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

[@rohullahalavi]

tanks

[@delofj]

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

[@maniagames94]

Nice video, brow!

[@sabrysm]

May I ask how did you do this animation?

[@Cookie-mv2hg]

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

[@ike__]

For the array why not just use the range function?

[@nickburggraaf3977]

I hope Josephus knew about deques as well

[@coopernik]

do more of solving a problem to teach a concept

[@toanvong3825]

Cool but that actually leads to the complexity of O(n * k) which is terrible when k = n. There actually is a data structure that can solve the problem in O(n * log(n)) which is Binary Indexed Tree or Fenwick Tree. I wish you could make a video on solving this problem using those proposed data structure, that would be super cool 😎😎.

[@antonhelsgaun]

Binary index tree sounds oof, though

[@rkdeshdeepak4131]

Wouldn't rotate be O(n) now?

[@makedits]

which font do you use brother?

[@saintjonny]

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

[@reeti5958]

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..

[@taejimcap]

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

[@Tyrant369]

What theme and font is this?

[@thelavagod]

what is your vscode theme

[@Aadoxide]

synthwave '84

[@sudhenduahir802]

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

[@saintjonny]

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

[@chaitanyakrishna6964]

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

[@babanesma]

Keep up 👏

[@bridgeboo3031]

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

[@Артем-у8и1щ]

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

[@Chillymosh]

Even though this video's intention is to show deques, it is definitely not the most efficient / optimised way to solve this problem :)