-2

This is a fairly straight forward programming problem in Python and I am looking for suggestions for further optimization. I am successfully processing in time except for very large strings. I am not looking for code rather areas that I should research for optimization improvements. I have already identified that I can skip even numbers reducing the loop operation and given the nature of the operations the pattern eventually repeats which is why I track when repeat occurs. This allows me break out if n > repeat. I am not positive if converting the string to a list is the most effective.

Problem:

We have a string s and we have a number n that indicates the number of times to run the function. Here is a function that takes your string, concatenates the even-indexed chars to the front, odd-indexed chars to the back. You perform this operation n times.

Example:

example where s = "qwertyuio" and n = 2: after 1 iteration s = "qetuowryi" after 2 iterations s = "qtorieuwy" return "qtorieuwy"

def jumbled_string(s, n):

sl = list(s)
repeat = 0
for y in range(0,n):
    for i in range(1, (len(sl)//2)+1):
        sl.append(sl.pop(i))
    if repeat == 0 and ''.join(sl) == s:
        repeat = y+1
        break
if repeat != 0:
    afterrepeat = n%repeat
    for y in range(0,afterrepeat):
        for i in range(1, (len(sl)//2)+1):
            sl.append(sl.pop(i))

return ''.join(sl)
Josh
  • 1
  • 1
  • 2
    What's the role of the number `n`? – trincot Jul 26 '22 at 13:11
  • One or more examples of input and expected output would also be helpful. – Thomas Jul 26 '22 at 13:12
  • @trincot: i was going to ask exactly the same. what does `n` do in the question ? – D.L Jul 26 '22 at 13:18
  • 1
    It seems `n` just repeats the operation. So `s = 'abcdefghijklmn'; for _ in range(3): s = s[::2] + s[1::2]` gives the same result as the OP's function (i.e. `jumbled_string(s, 3)` => `'aidlgbjemhckfn'`). – ekhumoro Jul 26 '22 at 13:25
  • I’m voting to close this question because questions about improving working code are a better fit for [codereview.se], but remember to check their [on-topic](https://codereview.stackexchange.com/help/on-topic) page first – Pranav Hosangadi Jul 26 '22 at 13:42
  • my apologies for not including the necessary information. @ekhumoro is correct that you repeat the operation n times. – Josh Jul 26 '22 at 14:14
  • @PranavHosangadi if this is in the wrong section, my apologies. – Josh Jul 26 '22 at 14:19
  • @user19620526 Are there any other conditions related to how you're meant to solve the problem? I assume use of python's extended slice syntax is not in the spirit of the question. If you want to keep your question on topic, you should edit it to include some specific type of optimisation you are trying (and presumably failing) to implement. – ekhumoro Jul 26 '22 at 14:23
  • @ekhumoro slicing is acceptable. I was unaware / lack the knowledge that I could use slicing to extract the even / odd characters within the string. In review, it is apparent that looping through each character, albeit each odd character, is not as efficient as performing the slice operation. I will work on improving the completeness of my submissions – Josh Jul 26 '22 at 14:30
  • `sl.pop(i)` is inefficient. Making your shuffling code polynomial time instead of linear time – juanpa.arrivillaga Jul 26 '22 at 16:36
  • The interesting part of this is calculating how many iterations are required before the original string is repeated (based on the length of the string). For strings of length `2^n`, this is simply `n` iterations; but for intervening values, the pattern is quite hard to discern. If a formula could be worked out, this would obviously lead to a huge optimisation, since it could drastically reduce the total number of string concatenations for large values of `n`. – ekhumoro Jul 26 '22 at 19:50

3 Answers3

0

I don't know what you mean by "pattern repeats". But if we stick to the problem statement, it's a one liner in Python:

s='abecidofug'
from itertools import chain
s2 = ''.join(chain([s[c] for c in range(0, len(s), 2)],[s[c] for c in range(1, len(s), 2)]))
s2
'aeioubcdfg'
gimix
  • 3,431
  • 2
  • 5
  • 21
  • this does it the wrong way around, should be even indices at the front – Nin17 Jul 26 '22 at 13:44
  • i failed to include that the n signifies how many times you execute the even- odd operation. Depending on the string length, over X iterations the string will return to its original form. so even if n is 1000000, if the string is only 10 characters, find when it repeats and just find the mod n/repeat value to reduce the number of times i have to loop. – Josh Jul 26 '22 at 14:18
  • oops, editing the answer - just invert the 0 and the 1 – gimix Jul 26 '22 at 14:34
0

You don't explain what n does. The statement is this:

def jumbled_string(s: str) -> str:
    even = s[::2]
    odd = s[1::2]
    return even+odd

print(jumbled_string("0123456789"))
>>>0246813579
Colim
  • 1,283
  • 3
  • 11
  • my mistake, you repeat the function n times. – Josh Jul 26 '22 at 14:14
  • Thanks Colim, this approached removed the need for my loop through each character, pop, and append. This resulted in the performance increase necessary. I don't have the reputation to vote, but i appreciate your time. – Josh Jul 26 '22 at 14:25
  • the ```.join```s are pointless, and results in a significant speed decrease, a factor of 3 on my machine for ```s = 'abcdefghijklmn'``` – Nin17 Jul 26 '22 at 14:37
  • @Nin17 thank you for the suggestion. It was are remnant of when I was originally converting the string to a list. – Josh Jul 26 '22 at 15:10
  • @Nin17 fixed. I must enter minimum length of characters – Colim Jul 26 '22 at 16:29
0

In python 3.8+ (due to := operator) you could do it like this:

import collections

def jumbled_string(s: str, n: int) -> str:
    generator = (s:=s[::2]+s[1::2] for _ in range(n))
    collections.deque(generator, maxlen=0)
    return s

Using collections.deque as this is the Fastest (most Pythonic) way to consume an iterator. Though, for small n I'm finding it faster to use:

def jumbled_string(s: str, n: int) -> str:
    for _ in (s:=s[::2]+s[1::2] for _ in range(n)):
        pass
    return s

Test:

jumbled_string("qwertyuio", 2)

Output:

'qtorieuwy'
Nin17
  • 2,821
  • 2
  • 4
  • 14
  • thank you for the link, interesting read about collections.deque and something i need to explore more. I appreciate it. – Josh Jul 26 '22 at 15:31
  • this is a terrible use of a generator expression (for side effects) and the walrus operator. A *regular loop* would be faster and more clear. This really adds no advantage – juanpa.arrivillaga Jul 26 '22 at 16:33
  • @juanpa.arrivillaga if the string is large, they are the same speed – Nin17 Jul 26 '22 at 17:54
  • I doubt it, a regular for-loop should be faster than the generator expression because there is no additional overhead of the generator (although very recent python versions have made the overhead of a generator much smaller). But the biggest problem is the style here - generator expressions are for expressing *mapping/filtering operations*, not for side-effects. This is a very convoluted way to do `for _ in range(n): s = s[:] + s[1::2]`, which will be faster than `for _ in (s:=s[::2]+s[1::2] for _ in range(n))` because you have an extra, totally pointless layer of iteration. – juanpa.arrivillaga Jul 26 '22 at 17:58
  • @juanpa.arrivillaga you can doubt it all you like, I've timed it and they're the same in both 3.9.13 and 3.10.5. Yh well tbh just discovered ```:=``` so sticking it in wherever – Nin17 Jul 26 '22 at 18:00
  • @Nin17 you haven't even posted your profiling code, so everyone should doubt it. Using the `timeit` module, I'm getting about a 20% speed penalty for the needless generator version. e.g., `def bar(s, n): for _ in range(n): s = s = s[::2] + s[1::2]` and `def foo(s, n): for _ in (s:=s[::2]+s[1::2] for _ in range(n)): pass` then `import timeit` and `timeit.timeit("foo(s, 10)", setup='from __main__ import foo; s = "a"*100')` vs `timeit.timeit("bar(s, 10)", setup='from __main__ import foo, bar; s = "a"*100')` – juanpa.arrivillaga Jul 26 '22 at 18:06
  • yh well when I say large I don't mean ```'a'*100``` – Nin17 Jul 26 '22 at 18:07