finished Josephus-Problem in C#, how to make this more efficient?

Question

using System; using System.Collections.Generic; namespace Function_JosephusSurvivor { class Program { static void Main(string[] args) { //Debug purposes Console.WriteLine(JosSurvivor(7, 3)); Console.ReadKey(); } //Actual function: public static int JosSurvivor(int n, int k) { // n = amount of people(array size) // k = every k'th index will be yeeted List<int> list = new List<int>(); int iCounter = 1; //always count till the size of the list int iWatcher = 1; //always count till the size of k for (int i = 1; i <= n; i++) { list.Add(i); } do { if (iWatcher+1 == k) { list.RemoveAt(iCounter); iWatcher = 0; } iWatcher++; iCounter++; if (iCounter == list.Count) // -1 because index { iCounter = 0; } else if (iCounter > list.Count) { iCounter = 1; //if one is jumped due to deleteting } } while (list.Count != 1); return list[0]; //winner } } }

My question is:

how could you make this more efficient? What could I do better?

I'm trying to submit this as my solution on a practicing page. Unfortunately, it always times out. Therefore I need to make this more efficient I believe.

Thanks in advance :)!

Also feel free to add fitting Tags :)!

From what aspect are you looking for a more efficient solution? It was executed less than a sec on dotnetfiddle. — Peter Csala
– Peter Csala, Commented May 20, 2020 at 12:26
@PeterCsala Maybe something that is better practice, or just any hints on what I could do better :). Also, could it be then, that the website could just have problems at the moment? — Jeremias T.
– Jeremias T., Commented May 20, 2020 at 12:29
Sorry but I still don't get it. From what perspective are you looking for some better solution? Better for maintainability / portability / readability / robustness / more efficient memory usage / ... / ??? — Peter Csala
– Peter Csala, Commented May 20, 2020 at 13:19
@JeremiasT. Generally speaking in order to reduce the memory usage you have several techniques. Here are some well-known: 1) If possible prefer Arrays over Lists, because of double capacity allocation. Or it might be even better to use IEnumerables 2) Try to use structs instead of classes for short-living small data objects. 3) Try to avoid to allocate space more than 85000 bytes for a single object, because they will be allocated on the LargeObjectHeap. 4) Try to use allocation optimised structures like Span, Memory, ArrayPool, StringBuilder, etc. — Peter Csala
– Peter Csala, Commented May 22, 2020 at 6:45

score 3 · Accepted Answer · 2020-05-21 07:36:22Z

 List<int> list = new List<int>(); int iCounter = 1; //always count till the size of the list int iWatcher = 1; //always count till the size of k for (int i = 1; i <= n; i++) { list.Add(i); }

You can initialize list more elegantly:

List<int> list = Enumerable.Range(1, n).ToList();

For n = 2; k = 1 it runs infinitely?

Your counting and indexing seem ok, but are a little difficult to comprehend. It can be done a lot easier using modular operations:

static int JosSurvivor(int n, int k) { List<int> positions = Enumerable.Range(1, n).ToList(); int index = k % n - 1; // %n is important for k > n while (positions.Count > 1) { if (index < 0) index += positions.Count; // when (index + k) % poisitons.Count == 0 then index becomes -1 from the line below positions.RemoveAt(index); index = (index + k) % positions.Count - 1; } return positions[0]; }

Another approach building on the same principle is to maintain a fixed array of indices and then left-shift the reminder of the indices for each found index while decrement n by 1:

static int JosSurvivor(int n, int k) { int[] positions = Enumerable.Range(1, n).ToArray(); int index = k % n - 1; while (n > 1) { if (index < 0) index += n; Array.Copy(positions, index + 1, positions, index, n - index - 1); n--; index = (index + k) % n - 1; } return positions[0]; }

There seems to be a little performance gain - but not significant.

Yet another version that uses a fixed array of flags, that are set for each found index:

static int JosSurvivor(int n, int k) { int counter = 0; int index = -1; int runner = 0; bool[] positions = new bool[n]; while (counter < n - 1) { runner += k; int temp = 0; do { index = (index + 1) % n; } while (positions[index] || ++temp < k); if (runner > 0 && runner % k == 0) { positions[index] = true; counter++; } } for (int i = 0; i < n; i++) { if (!positions[i]) return i + 1; } throw new InvalidOperationException("No last position found"); }

This is very fast for small ks - even for large ns - but becomes slower when k increases.

You may have missed my comment to OP, but there is no to work through an elimination process. A formula may be used instead. See exploringbinary.com/powers-of-two-in-the-josephus-problem — Rick Davin
– Rick Davin, Commented May 21, 2020 at 11:45
@RickDavin: I havn't missed your comment, but as far as I can read, it's about eliminating every other person (k = 2) only - not an arbitrary interval - for instance k = 3, og maybe I have missed something? — user73941
– user73941, Commented May 21, 2020 at 12:46

Jeremias T. · Accepted Answer · 2020-05-21 16:29:02Z

I just found a really clever solution to this (not mine):

All credit goes to ViolaCrellin:

using System; using System.Linq; using System.Collections.Generic; public class JosephusSurvivor { public static int JosSurvivor(int n, int k) { if (n == 1) return 1; else return (JosSurvivor(n - 1, k) + k-1) % n + 1; } }

Very nice solution :)!

Thanks for the answers everyone!

Updated by Henrik Hansen

This is an implementation of the formula on wiki

Recursive functions always has the potential to overflow the stack, so whenever you can, you should convert it to an iterative approach, which is also almost faster than using recursion:

public static int JosSurvivor(int n, int k) { int result = 1; for (int i = 2; i <= n; i++) { result = (result + k - 1) % i + 1; } return result; }

You have presented an alternative solution, but you did not review the original code at all. Reviewing code is all this site is about. — Roland Illig
– Roland Illig, Commented May 21, 2020 at 16:55
The person who replied here with the alternative solution IS the OP. — Rick Davin
– Rick Davin, Commented May 21, 2020 at 17:17

potato · Accepted Answer · 2020-05-21 14:41:40Z

As a beginner you do need to practice the loop-based method, but I'd like to add that when you want to optimize code to the maximum, it's worth looking for mathematical rules that will help you predict things - if something is predictable then there's no need to simulate all the intermediate steps.

For k = 1 the result is always n.

I found a great explanation about the math of this problem for k = 2 (link):

$$(2(n-2^{\lfloor\log_2n\rfloor})+1) \mod n$$

In binary, powers of 2 have only one 1-bit, so the part of the formula that finds the greatest power of 2 that is less than or equal to n can be replaced with code that finds the left most 1-bit of n. It's a micro-optimization but it's related to the point I want to make.

I failed generalizing it to work with any k, but it was still worth a shot, my goal is to illustrate that you can use math can optimize some of your code.

Have you actually tested your formula against different steps (k's) - for instance if n = 7 and k = 3? Be aware, that k in OP's algorithm is not the same as k in this formula. Please show the formula implemented in C# with some working examples :-) — user73941
– user73941, Commented May 21, 2020 at 13:34
Turns out I made a big mistake when trying to generalize it to cases where k ≠ 2, so I replaced it with the cases of k=1 and k=2. — potato
– potato, Commented May 21, 2020 at 14:37
@HenrikHansen haha I'd like to think I'm type 1 but sometimes I slip up and act like type 10 — potato
– potato, Commented May 21, 2020 at 14:43

Stack Exchange Network

finished Josephus-Problem in C#, how to make this more efficient?

how could you make this more efficient? What could I do better?

3 Answers 3

You must log in to answer this question.

Hot Network Questions

finished Josephus-Problem in C#, how to make this more efficient?

how could you make this more efficient? What could I do better?

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions