Reverse string, can I make it faster?
$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
edited 15 hours ago
esote
2,7561937
asked 18 hours ago
MidosMidos
515
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$
add a comment |
$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
edited 15 hours ago
esote
2,7561937
asked 18 hours ago
MidosMidos
515
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$
4
$begingroup$
I'd say your code isO(n**2)because it creates at least n strings with length between1andn.
$endgroup$
– Eric Duminil
15 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
15 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 lazyReverseStringclass, which only accesses the data when needed.
$endgroup$
– Eric Duminil
15 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
14 hours ago
add a comment |
$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
edited 15 hours ago
esote
2,7561937
asked 18 hours ago
MidosMidos
515
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
edited 15 hours ago
esote
2,7561937
asked 18 hours ago
MidosMidos
515
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.
edited 15 hours ago
esote
2,7561937
asked 18 hours ago
MidosMidos
515
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.
edited 15 hours ago
esote
2,7561937
edited 15 hours ago
esote
2,7561937
edited 15 hours ago
esote
2,7561937
2,7561937
asked 18 hours ago
MidosMidos
515
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 18 hours ago
MidosMidos
515
asked 18 hours ago
MidosMidos
515
515
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.
4
$begingroup$
I'd say your code isO(n**2)because it creates at least n strings with length between1andn.
$endgroup$
– Eric Duminil
15 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
15 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 lazyReverseStringclass, which only accesses the data when needed.
$endgroup$
– Eric Duminil
15 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
14 hours ago
add a comment |
4
$begingroup$
I'd say your code isO(n**2)because it creates at least n strings with length between1andn.
$endgroup$
– Eric Duminil
15 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
15 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 lazyReverseStringclass, which only accesses the data when needed.
$endgroup$
– Eric Duminil
15 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
14 hours ago
4
4
$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
15 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
15 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
15 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
15 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
15 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
15 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
14 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
14 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$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.
answered 18 hours ago
GraipherGraipher
25.7k53989
$endgroup$
2
$begingroup$
How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 forreverse_gsignificant and if so why?
$endgroup$
– gerrit
15 hours ago
1
$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
14 hours ago
$begingroup$
Data is code and code is data. Ponder why you might want to reverse the string, and consider instead to use an iterator that simply reads the string backwards. This is essentially what this answer is, while the actual implementation the iterator is buried inside CPython's internals. Nice answer
$endgroup$
– sleblanc
2 hours ago
$begingroup$
Adding strings using + is usually a bad idea in Python, since strings are immutable. Immutability (and the use of Python) isn't what matters here; in nearly every case, string addition requires iterating over at least one of the strings. A pre-allocated, mutable C-string concatenation still requires linear time to copy the contents of the second string into the tail of the first.
$endgroup$
– Schism
1 hour ago
add a comment |
$begingroup$
After searching a bit, it turns out that builtins.reversed is actually a type that represents a reverse iterator into a sequence, making it very space-efficient. Therefore, the most efficient implementation of reverse() is:
reverse = reversed
answered 2 hours ago
sleblancsleblanc
1013
$endgroup$
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered 18 hours ago
GraipherGraipher
25.7k53989
$endgroup$
2
$begingroup$
How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 forreverse_gsignificant and if so why?
$endgroup$
– gerrit
15 hours ago
1
$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
14 hours ago
$begingroup$
Data is code and code is data. Ponder why you might want to reverse the string, and consider instead to use an iterator that simply reads the string backwards. This is essentially what this answer is, while the actual implementation the iterator is buried inside CPython's internals. Nice answer
$endgroup$
– sleblanc
2 hours ago
$begingroup$
Adding strings using + is usually a bad idea in Python, since strings are immutable. Immutability (and the use of Python) isn't what matters here; in nearly every case, string addition requires iterating over at least one of the strings. A pre-allocated, mutable C-string concatenation still requires linear time to copy the contents of the second string into the tail of the first.
$endgroup$
– Schism
1 hour ago
add a comment |
$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.
answered 18 hours ago
GraipherGraipher
25.7k53989
$endgroup$
2
$begingroup$
How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 forreverse_gsignificant and if so why?
$endgroup$
– gerrit
15 hours ago
1
$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
14 hours ago
$begingroup$
Data is code and code is data. Ponder why you might want to reverse the string, and consider instead to use an iterator that simply reads the string backwards. This is essentially what this answer is, while the actual implementation the iterator is buried inside CPython's internals. Nice answer
$endgroup$
– sleblanc
2 hours ago
$begingroup$
Adding strings using + is usually a bad idea in Python, since strings are immutable. Immutability (and the use of Python) isn't what matters here; in nearly every case, string addition requires iterating over at least one of the strings. A pre-allocated, mutable C-string concatenation still requires linear time to copy the contents of the second string into the tail of the first.
$endgroup$
– Schism
1 hour ago
add a comment |
$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.
answered 18 hours ago
GraipherGraipher
25.7k53989
$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.
answered 18 hours ago
GraipherGraipher
25.7k53989
edited 18 hours ago
answered 18 hours ago
GraipherGraipher
25.7k53989
answered 18 hours ago
GraipherGraipher
25.7k53989
answered 18 hours ago
GraipherGraipher
25.7k53989
25.7k53989
2
$begingroup$
How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 forreverse_gsignificant and if so why?
$endgroup$
– gerrit
15 hours ago
1
$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
14 hours ago
$begingroup$
Data is code and code is data. Ponder why you might want to reverse the string, and consider instead to use an iterator that simply reads the string backwards. This is essentially what this answer is, while the actual implementation the iterator is buried inside CPython's internals. Nice answer
$endgroup$
– sleblanc
2 hours ago
$begingroup$
Adding strings using + is usually a bad idea in Python, since strings are immutable. Immutability (and the use of Python) isn't what matters here; in nearly every case, string addition requires iterating over at least one of the strings. A pre-allocated, mutable C-string concatenation still requires linear time to copy the contents of the second string into the tail of the first.
$endgroup$
– Schism
1 hour ago
add a comment |
2
$begingroup$
How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 forreverse_gsignificant and if so why?
$endgroup$
– gerrit
15 hours ago
1
$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
14 hours ago
$begingroup$
Data is code and code is data. Ponder why you might want to reverse the string, and consider instead to use an iterator that simply reads the string backwards. This is essentially what this answer is, while the actual implementation the iterator is buried inside CPython's internals. Nice answer
$endgroup$
– sleblanc
2 hours ago
$begingroup$
Adding strings using + is usually a bad idea in Python, since strings are immutable. Immutability (and the use of Python) isn't what matters here; in nearly every case, string addition requires iterating over at least one of the strings. A pre-allocated, mutable C-string concatenation still requires linear time to copy the contents of the second string into the tail of the first.
$endgroup$
– Schism
1 hour ago
2
2
$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
15 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
15 hours ago
1
1
$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
14 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
14 hours ago
$begingroup$
Data is code and code is data. Ponder why you might want to reverse the string, and consider instead to use an iterator that simply reads the string backwards. This is essentially what this answer is, while the actual implementation the iterator is buried inside CPython's internals. Nice answer
$endgroup$
– sleblanc
2 hours ago
$begingroup$
Data is code and code is data. Ponder why you might want to reverse the string, and consider instead to use an iterator that simply reads the string backwards. This is essentially what this answer is, while the actual implementation the iterator is buried inside CPython's internals. Nice answer
$endgroup$
– sleblanc
2 hours ago
$begingroup$
Adding strings using + is usually a bad idea in Python, since strings are immutable. Immutability (and the use of Python) isn't what matters here; in nearly every case, string addition requires iterating over at least one of the strings. A pre-allocated, mutable C-string concatenation still requires linear time to copy the contents of the second string into the tail of the first.
$endgroup$
– Schism
1 hour ago
$begingroup$
Adding strings using + is usually a bad idea in Python, since strings are immutable. Immutability (and the use of Python) isn't what matters here; in nearly every case, string addition requires iterating over at least one of the strings. A pre-allocated, mutable C-string concatenation still requires linear time to copy the contents of the second string into the tail of the first.
$endgroup$
– Schism
1 hour ago
add a comment |
$begingroup$
After searching a bit, it turns out that builtins.reversed is actually a type that represents a reverse iterator into a sequence, making it very space-efficient. Therefore, the most efficient implementation of reverse() is:
reverse = reversed
answered 2 hours ago
sleblancsleblanc
1013
$endgroup$
add a comment |
$begingroup$
After searching a bit, it turns out that builtins.reversed is actually a type that represents a reverse iterator into a sequence, making it very space-efficient. Therefore, the most efficient implementation of reverse() is:
reverse = reversed
answered 2 hours ago
sleblancsleblanc
1013
$endgroup$
add a comment |
$begingroup$
After searching a bit, it turns out that builtins.reversed is actually a type that represents a reverse iterator into a sequence, making it very space-efficient. Therefore, the most efficient implementation of reverse() is:
reverse = reversed
answered 2 hours ago
sleblancsleblanc
1013
$endgroup$
After searching a bit, it turns out that builtins.reversed is actually a type that represents a reverse iterator into a sequence, making it very space-efficient. Therefore, the most efficient implementation of reverse() is:
reverse = reversed
answered 2 hours ago
sleblancsleblanc
1013
answered 2 hours ago
sleblancsleblanc
1013
answered 2 hours ago
sleblancsleblanc
1013
answered 2 hours ago
sleblancsleblanc
1013
1013
add a comment |
add a comment |
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.
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
4
$begingroup$
I'd say your code is
O(n**2)because it creates at least n strings with length between1andn.$endgroup$
– Eric Duminil
15 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
15 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
ReverseStringclass, which only accesses the data when needed.$endgroup$
– Eric Duminil
15 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
14 hours ago