Reverse string, can I make it faster?












8












$begingroup$


This code will take as output any string (long, empty, with spaces...) and will return its reverse. Can I improve this algorithm so that it can be faster?



Right now its complexity is $O(n)$.



def reverse(stri):

    output = ''

    length = len(stri)

    while length > 0:

        output += stri[-1]

        stri, length = (stri[0:length - 1], length - 1)

    return output





python performance







share|improve this question









New contributor




Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 2




    $begingroup$
    I'd say your code is O(n**2) because it creates at least n strings with length between 1 and n.
    $endgroup$
    – Eric Duminil
    4 hours ago








  • 1




    $begingroup$
    I think you're right, since I didn't take into account the immutability of strings in python, but the graph of @Graipher shows something similar to O(nlgn) complexity for my code, I don't know I'm a bit confused...
    $endgroup$
    – Midos
    3 hours ago






  • 1




    $begingroup$
    Depending on how large the string is and what you want to do with it, it might be a good idea to create a lazy ReverseString class, which only accesses the data when needed.
    $endgroup$
    – Eric Duminil
    3 hours ago






  • 1




    $begingroup$
    @Midos That might be due to the Python implementation used. AFAIK, cPython does sometimes manage to reuse one of the two strings (i.e. it tries to reserve enough space after/before one of the two strings and needs to copy only one string, but don't quote me on that). However, that is both implementation dependent and potentially dependent on the available memory, which is why Python's official style-guide recommends not relying on it.
    $endgroup$
    – Graipher
    2 hours ago
















8












$begingroup$


This code will take as output any string (long, empty, with spaces...) and will return its reverse. Can I improve this algorithm so that it can be faster?



Right now its complexity is $O(n)$.



def reverse(stri):

    output = ''

    length = len(stri)

    while length > 0:

        output += stri[-1]

        stri, length = (stri[0:length - 1], length - 1)

    return output





python performance







share|improve this question









New contributor




Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$








  • 2




    $begingroup$
    I'd say your code is O(n**2) because it creates at least n strings with length between 1 and n.
    $endgroup$
    – Eric Duminil
    4 hours ago








  • 1




    $begingroup$
    I think you're right, since I didn't take into account the immutability of strings in python, but the graph of @Graipher shows something similar to O(nlgn) complexity for my code, I don't know I'm a bit confused...
    $endgroup$
    – Midos
    3 hours ago






  • 1




    $begingroup$
    Depending on how large the string is and what you want to do with it, it might be a good idea to create a lazy ReverseString class, which only accesses the data when needed.
    $endgroup$
    – Eric Duminil
    3 hours ago






  • 1




    $begingroup$
    @Midos That might be due to the Python implementation used. AFAIK, cPython does sometimes manage to reuse one of the two strings (i.e. it tries to reserve enough space after/before one of the two strings and needs to copy only one string, but don't quote me on that). However, that is both implementation dependent and potentially dependent on the available memory, which is why Python's official style-guide recommends not relying on it.
    $endgroup$
    – Graipher
    2 hours ago














8












8








8





$begingroup$


This code will take as output any string (long, empty, with spaces...) and will return its reverse. Can I improve this algorithm so that it can be faster?



Right now its complexity is $O(n)$.



def reverse(stri):

    output = ''

    length = len(stri)

    while length > 0:

        output += stri[-1]

        stri, length = (stri[0:length - 1], length - 1)

    return output





python performance







share|improve this question









New contributor




Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




This code will take as output any string (long, empty, with spaces...) and will return its reverse. Can I improve this algorithm so that it can be faster?



Right now its complexity is $O(n)$.



def reverse(stri):

    output = ''

    length = len(stri)

    while length > 0:

        output += stri[-1]

        stri, length = (stri[0:length - 1], length - 1)

    return output





python performance




python performance






share|improve this question









New contributor




Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 3 hours ago









esote

2,7561937




2,7561937






New contributor




Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 7 hours ago









MidosMidos

465




465




New contributor




Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Midos is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 2




    $begingroup$
    I'd say your code is O(n**2) because it creates at least n strings with length between 1 and n.
    $endgroup$
    – Eric Duminil
    4 hours ago








  • 1




    $begingroup$
    I think you're right, since I didn't take into account the immutability of strings in python, but the graph of @Graipher shows something similar to O(nlgn) complexity for my code, I don't know I'm a bit confused...
    $endgroup$
    – Midos
    3 hours ago






  • 1




    $begingroup$
    Depending on how large the string is and what you want to do with it, it might be a good idea to create a lazy ReverseString class, which only accesses the data when needed.
    $endgroup$
    – Eric Duminil
    3 hours ago






  • 1




    $begingroup$
    @Midos That might be due to the Python implementation used. AFAIK, cPython does sometimes manage to reuse one of the two strings (i.e. it tries to reserve enough space after/before one of the two strings and needs to copy only one string, but don't quote me on that). However, that is both implementation dependent and potentially dependent on the available memory, which is why Python's official style-guide recommends not relying on it.
    $endgroup$
    – Graipher
    2 hours ago














  • 2




    $begingroup$
    I'd say your code is O(n**2) because it creates at least n strings with length between 1 and n.
    $endgroup$
    – Eric Duminil
    4 hours ago








  • 1




    $begingroup$
    I think you're right, since I didn't take into account the immutability of strings in python, but the graph of @Graipher shows something similar to O(nlgn) complexity for my code, I don't know I'm a bit confused...
    $endgroup$
    – Midos
    3 hours ago






  • 1




    $begingroup$
    Depending on how large the string is and what you want to do with it, it might be a good idea to create a lazy ReverseString class, which only accesses the data when needed.
    $endgroup$
    – Eric Duminil
    3 hours ago






  • 1




    $begingroup$
    @Midos That might be due to the Python implementation used. AFAIK, cPython does sometimes manage to reuse one of the two strings (i.e. it tries to reserve enough space after/before one of the two strings and needs to copy only one string, but don't quote me on that). However, that is both implementation dependent and potentially dependent on the available memory, which is why Python's official style-guide recommends not relying on it.
    $endgroup$
    – Graipher
    2 hours ago








2




2




$begingroup$
I'd say your code is O(n**2) because it creates at least n strings with length between 1 and n.
$endgroup$
– Eric Duminil
4 hours ago






$begingroup$
I'd say your code is O(n**2) because it creates at least n strings with length between 1 and n.
$endgroup$
– Eric Duminil
4 hours ago






1




1




$begingroup$
I think you're right, since I didn't take into account the immutability of strings in python, but the graph of @Graipher shows something similar to O(nlgn) complexity for my code, I don't know I'm a bit confused...
$endgroup$
– Midos
3 hours ago




$begingroup$
I think you're right, since I didn't take into account the immutability of strings in python, but the graph of @Graipher shows something similar to O(nlgn) complexity for my code, I don't know I'm a bit confused...
$endgroup$
– Midos
3 hours ago




1




1




$begingroup$
Depending on how large the string is and what you want to do with it, it might be a good idea to create a lazy ReverseString class, which only accesses the data when needed.
$endgroup$
– Eric Duminil
3 hours ago




$begingroup$
Depending on how large the string is and what you want to do with it, it might be a good idea to create a lazy ReverseString class, which only accesses the data when needed.
$endgroup$
– Eric Duminil
3 hours ago




1




1




$begingroup$
@Midos That might be due to the Python implementation used. AFAIK, cPython does sometimes manage to reuse one of the two strings (i.e. it tries to reserve enough space after/before one of the two strings and needs to copy only one string, but don't quote me on that). However, that is both implementation dependent and potentially dependent on the available memory, which is why Python's official style-guide recommends not relying on it.
$endgroup$
– Graipher
2 hours ago




$begingroup$
@Midos That might be due to the Python implementation used. AFAIK, cPython does sometimes manage to reuse one of the two strings (i.e. it tries to reserve enough space after/before one of the two strings and needs to copy only one string, but don't quote me on that). However, that is both implementation dependent and potentially dependent on the available memory, which is why Python's official style-guide recommends not relying on it.
$endgroup$
– Graipher
2 hours ago










1 Answer
1






active

oldest

votes


















22












$begingroup$

Yes, this can be faster. Adding strings using + is usually a bad idea in Python, since strings are immutable. This means that whenever you add two strings, a new string needs to be allocated with the size of the resulting strings and then both string contents need to be copied there. Instead you usually want to build a list of strings and ''.join them at the end (where you pay this cost only once).



But here you can just use the fact that strings can be sliced and you can specify a negative step:



def reverse(s):

    return s[::-1]


Here is a timing comparison for random strings of length up to 100k characters, where reverse is your function and reverse_g is this one using slicing. Note the double-log scale, for the largest string your function is more than a thousand times slower.



enter image description here






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 for reverse_g significant and if so why?
    $endgroup$
    – gerrit
    3 hours ago










  • $begingroup$
    @gerrit: The uncertainty bars come from the fact that each timing measurement is performed three times, so the value is the mean and the uncertainty the uncertainty of the mean (i.e. standard deviation / sqrt(n)). So I would doubt that the drop is significant. Sometimes you get large increases due to some other activity on the machine, so that is what could have happened in the first case.
    $endgroup$
    – Graipher
    3 hours ago











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});






Midos is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215179%2freverse-string-can-i-make-it-faster%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









22












$begingroup$

Yes, this can be faster. Adding strings using + is usually a bad idea in Python, since strings are immutable. This means that whenever you add two strings, a new string needs to be allocated with the size of the resulting strings and then both string contents need to be copied there. Instead you usually want to build a list of strings and ''.join them at the end (where you pay this cost only once).



But here you can just use the fact that strings can be sliced and you can specify a negative step:



def reverse(s):

    return s[::-1]


Here is a timing comparison for random strings of length up to 100k characters, where reverse is your function and reverse_g is this one using slicing. Note the double-log scale, for the largest string your function is more than a thousand times slower.



enter image description here






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 for reverse_g significant and if so why?
    $endgroup$
    – gerrit
    3 hours ago










  • $begingroup$
    @gerrit: The uncertainty bars come from the fact that each timing measurement is performed three times, so the value is the mean and the uncertainty the uncertainty of the mean (i.e. standard deviation / sqrt(n)). So I would doubt that the drop is significant. Sometimes you get large increases due to some other activity on the machine, so that is what could have happened in the first case.
    $endgroup$
    – Graipher
    3 hours ago
















22












$begingroup$

Yes, this can be faster. Adding strings using + is usually a bad idea in Python, since strings are immutable. This means that whenever you add two strings, a new string needs to be allocated with the size of the resulting strings and then both string contents need to be copied there. Instead you usually want to build a list of strings and ''.join them at the end (where you pay this cost only once).



But here you can just use the fact that strings can be sliced and you can specify a negative step:



def reverse(s):

    return s[::-1]


Here is a timing comparison for random strings of length up to 100k characters, where reverse is your function and reverse_g is this one using slicing. Note the double-log scale, for the largest string your function is more than a thousand times slower.



enter image description here






share|improve this answer











$endgroup$









  • 1




    $begingroup$
    How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 for reverse_g significant and if so why?
    $endgroup$
    – gerrit
    3 hours ago










  • $begingroup$
    @gerrit: The uncertainty bars come from the fact that each timing measurement is performed three times, so the value is the mean and the uncertainty the uncertainty of the mean (i.e. standard deviation / sqrt(n)). So I would doubt that the drop is significant. Sometimes you get large increases due to some other activity on the machine, so that is what could have happened in the first case.
    $endgroup$
    – Graipher
    3 hours ago














22












22








22





$begingroup$

Yes, this can be faster. Adding strings using + is usually a bad idea in Python, since strings are immutable. This means that whenever you add two strings, a new string needs to be allocated with the size of the resulting strings and then both string contents need to be copied there. Instead you usually want to build a list of strings and ''.join them at the end (where you pay this cost only once).



But here you can just use the fact that strings can be sliced and you can specify a negative step:



def reverse(s):

    return s[::-1]


Here is a timing comparison for random strings of length up to 100k characters, where reverse is your function and reverse_g is this one using slicing. Note the double-log scale, for the largest string your function is more than a thousand times slower.



enter image description here






share|improve this answer











$endgroup$



Yes, this can be faster. Adding strings using + is usually a bad idea in Python, since strings are immutable. This means that whenever you add two strings, a new string needs to be allocated with the size of the resulting strings and then both string contents need to be copied there. Instead you usually want to build a list of strings and ''.join them at the end (where you pay this cost only once).



But here you can just use the fact that strings can be sliced and you can specify a negative step:



def reverse(s):

    return s[::-1]


Here is a timing comparison for random strings of length up to 100k characters, where reverse is your function and reverse_g is this one using slicing. Note the double-log scale, for the largest string your function is more than a thousand times slower.



enter image description here







share|improve this answer














share|improve this answer



share|improve this answer








edited 6 hours ago

























answered 6 hours ago









GraipherGraipher

25.7k53789




25.7k53789








  • 1




    $begingroup$
    How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 for reverse_g significant and if so why?
    $endgroup$
    – gerrit
    3 hours ago










  • $begingroup$
    @gerrit: The uncertainty bars come from the fact that each timing measurement is performed three times, so the value is the mean and the uncertainty the uncertainty of the mean (i.e. standard deviation / sqrt(n)). So I would doubt that the drop is significant. Sometimes you get large increases due to some other activity on the machine, so that is what could have happened in the first case.
    $endgroup$
    – Graipher
    3 hours ago














  • 1




    $begingroup$
    How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 for reverse_g significant and if so why?
    $endgroup$
    – gerrit
    3 hours ago










  • $begingroup$
    @gerrit: The uncertainty bars come from the fact that each timing measurement is performed three times, so the value is the mean and the uncertainty the uncertainty of the mean (i.e. standard deviation / sqrt(n)). So I would doubt that the drop is significant. Sometimes you get large increases due to some other activity on the machine, so that is what could have happened in the first case.
    $endgroup$
    – Graipher
    3 hours ago








1




1




$begingroup$
How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 for reverse_g significant and if so why?
$endgroup$
– gerrit
3 hours ago




$begingroup$
How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 for reverse_g significant and if so why?
$endgroup$
– gerrit
3 hours ago












$begingroup$
@gerrit: The uncertainty bars come from the fact that each timing measurement is performed three times, so the value is the mean and the uncertainty the uncertainty of the mean (i.e. standard deviation / sqrt(n)). So I would doubt that the drop is significant. Sometimes you get large increases due to some other activity on the machine, so that is what could have happened in the first case.
$endgroup$
– Graipher
3 hours ago




$begingroup$
@gerrit: The uncertainty bars come from the fact that each timing measurement is performed three times, so the value is the mean and the uncertainty the uncertainty of the mean (i.e. standard deviation / sqrt(n)). So I would doubt that the drop is significant. Sometimes you get large increases due to some other activity on the machine, so that is what could have happened in the first case.
$endgroup$
– Graipher
3 hours ago










Midos is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















Midos is a new contributor. Be nice, and check out our Code of Conduct.













Midos is a new contributor. Be nice, and check out our Code of Conduct.












Midos is a new contributor. Be nice, and check out our Code of Conduct.
















Thanks for contributing an answer to Code Review Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f215179%2freverse-string-can-i-make-it-faster%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Plaza Victoria

Image
Plaza Victoria Plaza Victoria en 2017 Otros nombres Plaza de La Victoria Localización El Almendral, Valparaíso, Chile Vías adyacentes Chacabuco, Molina, Plaza Victoria y Edwards Creación 1841 Metro Bellavista Ubicación 33°02′46″S 71°37′11″O  /  -33.04624167, -71.61980833 Coordenadas: 33°02′46″S 71°37′11″O  /  -33.04624167, -71.61980833 [editar datos en Wikidata] La Plaza Victoria , también llamada Plaza de la Victoria , [ 1 ] ​ es una plaza ubicada en el sector El Almendral del plan de la ciudad de Valparaíso, Chile, de importancia patrimonial, que incluye valiosas estatuas y especies vegetales. [ 2 ] ​ La plaza se creó como tal en la primera mitad del siglo XIX, tomando previamente los nombres de Plaza Nueva y Plaza de Orrego . Si bien desde sus inicios tuvo relevancia histórica, no fue sino a partir de fines de los años 1860 cuando comenzó a cobrar mayor importancia y se convirtió en uno de los principales centros sociales de l...
Read more

Brian Clough

Image
Brian Clough Datos personales Nombre completo Brian Howard Clough Apodo(s) Old Big 'Ead, Cloughie [ 1 ] ​ Nacimiento Middlesbrough, Inglaterra, Reino Unido 21 de marzo de 1935 Nacionalidad(es) Fallecimiento Derby, Reino Unido 20 de septiembre de 2004 (69 años) Altura 1,78 [ 1 ] ​ metros Carrera Deporte Fútbol Debut deportivo 1955 (Como jugador) 1965 (Como entrenador) (Middlesbrough F. C. (Como jugador) Hartlepool United F. C. (Como entrenador) ) Posición Delantero Goles en clubes 269 [ 2 ] ​ Retirada deportiva 1964 (Como jugador) 1993 (Como entrenador) (Sunderland A. F. C. (Como jugador) Nottingham Forest (Como entrenador) ) Carrera internacional Part. 2 [editar datos en Wikidata] Brian Howard Clough , OBE [ 3 ] ​ (Middlesbrough, Inglaterra, Reino Unido, 21 de marzo de 1935 – Derby, Inglaterra, Reino Unido, 20 de septiembre de 2004) fue un jugador y entrenador británico de fútbol. Es conocido por...
Read more

Cáceres

Image
Para otros usos de este término, véase Cáceres (desambiguación). Cáceres Municipio y ciudad Bandera Escudo Collage de Cáceres Cáceres Ubicación de Cáceres en España. Cáceres Ubicación de Cáceres en la provincia de Cáceres. País  España • Com. autónoma  Extremadura • Provincia  Cáceres • Partido judicial Cáceres Ubicación 39°28′23″N 6°22′16″O  /  39.473055555556, -6.3711111111111 Coordenadas: 39°28′23″N 6°22′16″O  /  39.473055555556, -6.3711111111111 • Altitud 457 [ 1 ] ​ msnm (mín.:211 [ 2 ] ​, máx.:708 [ 2 ] ​) Superficie 1750,33 km² Núcleos de población Cáceres Estación Arroyo-Malpartida Rincón de Ballesteros Valdesalor Fundación 34 a. C. Población 96 068 hab. (2018) • Densidad 54,8 hab./km² Gentilicio Cacereño/a [ 3 ] ​ Código postal 10001-10005, 10195 Alcaldesa (2015) María Elena Nevado del Campo [ 4 ] ​ Presupuesto 69.045.004€ [ 5 ] ​  (año ...
Read more