Timeline for Reversing a string
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 3, 2011 at 18:57 | comment | added | Billy ONeal |
@CodexArcanum: The linked list solution is still O(n^2), because to do the append the list must be transversed to find the last element (unless you're keeping around a pointer to the last element, which this implementation doesn't seem to do). Linked list is a horrendously bad data structure in any case -- I still wonder why a better compromise like C++'s deque isn't a common primitive available in more languages..
|
|
| Apr 1, 2011 at 22:19 | comment | added | CodexArcanum | Also, technically, the loop example is still faster because you're performing an in-place swap. So the mutable loop code take n/2 time while the recursion takes n time. There may be a clever way to do it functionally that I'm not aware of that evens it up. | |
| Apr 1, 2011 at 22:14 | comment | added | CodexArcanum |
Such as: reverse first :: rest = (reverse rest) :: first And pretend I added the case for empty list. :: is the "cons" operator. Check out F# for functional programming in .NET.
|
|
| Apr 1, 2011 at 22:12 | comment | added | CodexArcanum | In a functional language, a fold or more explicit recursion, would often replace a loop. Single-Linked-Lists are also very common in functional languages, where a string would be a linked-list of char. And actually, a properly done functional algorithm would still be O(n), since you'd go over the list, building a new list in reverse order as you went. | |
| Apr 1, 2011 at 2:48 | comment | added | Billy ONeal | Err.. where I said "constant time" above I meant "linear time". | |
| Apr 1, 2011 at 2:47 | comment | added | Billy ONeal | More to the point, this doesn't answer my question -- I'm not asking about this specific implementation of reverse, I'm asking about the general case of embedding logic more complicated than "n + 1" in a for loop condition. | |
| Apr 1, 2011 at 2:40 | comment | added | Billy ONeal |
That performs horribly though (in the first case -- you've turned a constant time algorithm into an O(N^2) one, with a memory allocation for the whole string for each character!)). I don't know what fold1 is. (Nor have I ever heard of the concept)
|
|
| Apr 1, 2011 at 1:56 | history | answered | Jörg W Mittag | CC BY-SA 2.5 |