Reversing an Array - Use Cases

  • (2 Pages)
  • +
  • 1
  • 2

24 Replies - 916 Views - Last Post: 24 September 2013 - 02:39 PM Rate Topic: -----

#1 jakobt  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 7
  • Joined: 21-March 11

Reversing an Array - Use Cases

Posted 23 September 2013 - 10:46 AM

Hello D.I.Cers,

I recently read a topic regarding the reversal of an array in place (i.e. no placeholder/new array to contain the reversed data)

What I am particularly curious about is whether or not there are real world use cases for a problem such as this. The first thought I had regarding it is that I would just traverse the array from end to start rather than start to end. Has anyone got insight on this subject?
Is This A Good Question/Topic? 0
  • +

Replies To: Reversing an Array - Use Cases

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10573
  • View blog
  • Posts: 39,145
  • Joined: 27-December 08

Re: Reversing an Array - Use Cases

Posted 23 September 2013 - 10:53 AM

Someone may just want the data printed out in reverse order. If you want to traverse in reverse order, that is sufficient. If you need the data in reverse order for later, you can swap the ith and n-ith elements, where i starts at the beginning of the array and n = array.length-1. So T(n) = 3n/2 for this approach (3 steps per swap * n/2 elements), which is still in the complexity class O(n).
Was This Post Helpful? 0
  • +
  • -

#3 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2263
  • View blog
  • Posts: 9,467
  • Joined: 29-May 08

Re: Reversing an Array - Use Cases

Posted 23 September 2013 - 11:07 AM

Isn't it O(n/2) cos it's sub-linear O(n). Swap is 1 instruction on some chips and languages.
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10573
  • View blog
  • Posts: 39,145
  • Joined: 27-December 08

Re: Reversing an Array - Use Cases

Posted 23 September 2013 - 12:10 PM

Big-O is an upper bound. So n/2 is still O(n), and 3n/2 <= 4|n| (which implies that 3n/2 is in the complexity class O(n)).

More to the point, you can drop constants with Big-O. So 3/2 is a constant in the term 3n/2.
Was This Post Helpful? 0
  • +
  • -

#5 jakobt  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 7
  • Joined: 21-March 11

Re: Reversing an Array - Use Cases

Posted 23 September 2013 - 12:57 PM

Thanks for the replies!

Just to be sure I'm understanding the steps you're talking about while analyzing the efficiency, would it be: step 1 - store the first value in memory, step 2 - store the second value in the first value's old memory location, step 3 - store the first value in the second value's old memory location and free up the intermediary location?
Was This Post Helpful? 0
  • +
  • -

#6 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2263
  • View blog
  • Posts: 9,467
  • Joined: 29-May 08

Re: Reversing an Array - Use Cases

Posted 23 September 2013 - 01:46 PM

Swap can be done without a temporary, using XORs.
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7757
  • View blog
  • Posts: 13,120
  • Joined: 19-March 11

Re: Reversing an Array - Use Cases

Posted 23 September 2013 - 02:51 PM

View Postjakobt, on 23 September 2013 - 12:46 PM, said:

What I am particularly curious about is whether or not there are real world use cases for a problem such as this. The first thought I had regarding it is that I would just traverse the array from end to start rather than start to end. Has anyone got insight on this subject?



For one real-world case, you might want to align pseudo-strings representing, say DNA strings. Since DNA strings are not inherently directed, finding a longest match would require examining both forward and back. A reverse-in-place would be a useful tool for this. For another case, you might want to pass a reversed array to a method. You could give the method a flag to indicate that the array is the wrong way around, but it's probably easier to simply reverse it, particularly if you have an efficient means of doing so.


Why in-place rather than a new copy in reverse order? Because space efficiency sometimes matters, and it's just as well to know how to do something in its own footprint rather than occupying extra memory. Of course, if you don't want a destructive reverse, then making a copy or reading backwards is the only way to go.

It's really just about having more tricks in your bag.
Was This Post Helpful? 0
  • +
  • -

#8 jakobt  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 7
  • Joined: 21-March 11

Re: Reversing an Array - Use Cases

Posted 24 September 2013 - 06:13 AM

AdamSpeight2008 said:

Swap can be done without a temporary, using XORs.


I can't say that XORs are my greatest strength, what is the idea behind being able to use them to swap two values in place? Do you do a comparison at the binary level and change the values of the bits?

View Postjon.kiparsky, on 23 September 2013 - 02:51 PM, said:

For one real-world case, you might want to align pseudo-strings representing, say DNA strings. Since DNA strings are not inherently directed, finding a longest match would require examining both forward and back. A reverse-in-place would be a useful tool for this. For another case, you might want to pass a reversed array to a method. You could give the method a flag to indicate that the array is the wrong way around, but it's probably easier to simply reverse it, particularly if you have an efficient means of doing so.


Why in-place rather than a new copy in reverse order? Because space efficiency sometimes matters, and it's just as well to know how to do something in its own footprint rather than occupying extra memory. Of course, if you don't want a destructive reverse, then making a copy or reading backwards is the only way to go.

It's really just about having more tricks in your bag.


Ahhh, this answers my question perfectly. I hadn't even thought about the application of matching entire ordered sets of data in forward order and reverse order. Thanks!
Was This Post Helpful? 0
  • +
  • -

#9 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2263
  • View blog
  • Posts: 9,467
  • Joined: 29-May 08

Re: Reversing an Array - Use Cases

Posted 24 September 2013 - 06:34 AM

Write down two 8 bit binary numbers, see what the result is of XOR them.
Grab some paper and experiment.

Here is the truth table for XOR, to help you.
 A B | Z
-----+---
 0 0 | 0
 0 1 | 1
 1 0 | 1
 1 1 | 0


Was This Post Helpful? 1
  • +
  • -

#10 Witchking  Icon User is offline

  • D.I.C Head

Reputation: 68
  • View blog
  • Posts: 188
  • Joined: 17-February 13

Re: Reversing an Array - Use Cases

Posted 24 September 2013 - 08:12 AM

View Postjakobt, on 24 September 2013 - 03:13 PM, said:

I can't say that XORs are my greatest strength, what is the idea behind being able to use them to swap two values in place? Do you do a comparison at the binary level and change the values of the bits?


The XOR swap algorithm is
x = x ⊕ y
y = x ⊕ y
x = x ⊕ y
Now to break it down, we start with x0 and y0. Then

x1 = x0 ⊕ y0
y1 = x1 ⊕ y0
x2 = x1 ⊕ y1

Notice that y1 is equal to (x0 ⊕ y0) ⊕ y0, and because of the XOR's associativity we can write this as x0 ⊕ (y0 ⊕ y0). We also know that a ⊕ a = 0 and a ⊕ 0 = a so in fact y1 = x0.

Now x2 is equal to (x0 ⊕ y0) ⊕ x0) because y1 = x0. Using the same associativity as before, we find that x2 can be written as y0 ⊕ (x0 ⊕ x0), which in turn we can see is equal to y0, and so we have swapped x0 and y0.


Now, while this works for any data that you can XOR, i would recommend simply using a temporary variable and doing all your swapping like that, especially if you don't quite understand the XOR swap, in order to improve the readability and maintainability of your code. Historically it was useful to use the XOR swap instead of a temporary variable to conserve memory, but that is no longer needed today.

This post has been edited by Witchking: 24 September 2013 - 08:12 AM

Was This Post Helpful? 1
  • +
  • -

#11 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7757
  • View blog
  • Posts: 13,120
  • Joined: 19-March 11

Re: Reversing an Array - Use Cases

Posted 24 September 2013 - 08:32 AM

View Postjakobt, on 24 September 2013 - 08:13 AM, said:

AdamSpeight2008 said:

Swap can be done without a temporary, using XORs.


I can't say that XORs are my greatest strength, what is the idea behind being able to use them to swap two values in place? Do you do a comparison at the binary level and change the values of the bits?



The swap-in-place with XOR is one of those things that gets some people really, really excited, but I honestly can't see why. It's a neat fact about XOR, and it's cute, but where are you actually going to use it? And when you do, what does it actually buy you? Swapping an array in place can make a major difference to your program's footprint, and it's not hard to imagine a scenario where it coud actually make a difference to whether the program runs or not. I can't really imagine a case where swapping an int in place would make a difference.

Basically, it's a lot like rasdix sort - it's cool, and it's worth working out for the intellectual challenge, but it's far too representation-dependent to be useful in modern languages.

This post has been edited by jon.kiparsky: 24 September 2013 - 08:33 AM

Was This Post Helpful? 0
  • +
  • -

#12 jakobt  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 7
  • Joined: 21-March 11

Re: Reversing an Array - Use Cases

Posted 24 September 2013 - 09:10 AM

This has all been really helpful. I have worked through it on paper and came out with the right results. I think there is one thing that came up in my pen and paper work that confuses me a little bit - if I am to XOR my variable A and B and use that result to swap their values, where do I store the result of the XOR prior to using it against A and B?

Basically what I did was:

Variable A = 10101010, Variable B = 10010110

Variable C = A XOR B = 00111100

A XOR C = B
B XOR C = A

Doing it on paper was easy enough because I just wrote down 00111100 and operated with it again, but in a program wouldn't I have to store this somewhere to use against both A and B? Wouldn't that ultimately be the same footprint as using a temporary storage variable?
Was This Post Helpful? 0
  • +
  • -

#13 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7757
  • View blog
  • Posts: 13,120
  • Joined: 19-March 11

Re: Reversing an Array - Use Cases

Posted 24 September 2013 - 09:14 AM

Subscripts here indicate time, not space: these are successive states of A and B

A0 = 1011
B0 = 1100

A1 = A0 XOR B0 = 0111
B1 = A1 XOR B0 = 1011
A2 = A1 XOR B1 = 1100
Was This Post Helpful? 1
  • +
  • -

#14 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2002
  • View blog
  • Posts: 4,162
  • Joined: 11-December 07

Re: Reversing an Array - Use Cases

Posted 24 September 2013 - 09:47 AM

Quote

Since DNA strings are not inherently directed


I wouldn't be so sure about that...

Jon's example of finding complementary DNA is still a good one, despite that slight inaccuracy.

It's not just the direct application that's important. What if you had to reverse a very large file in place? You'd want to optimise it but the same principles would apply.

And on OO land, we tend to shun arrays in favour of lists. How do you reverse a list? You call Collections.reverse(), or course. But let's say you are helping Jon with his DNA program and he wants syncronised forwards and reverse sequences. One solution is to write a wrapper around a Java list:

public class ReverseList<T> implements List<T> {

  private List<T> source;

  public ReverseList(List<T> source) {
    this.source = source;
  }

  public T get(int i) {
    return source.get(size() - i - 1);
  }

  public void add(T t) {
    source.add(0, t);
  }

  public void size() {
    return source.size();
  }

  // and so on...

}

Was This Post Helpful? 1
  • +
  • -

#15 jakobt  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 7
  • Joined: 21-March 11

Re: Reversing an Array - Use Cases

Posted 24 September 2013 - 10:34 AM

View Postjon.kiparsky, on 24 September 2013 - 09:14 AM, said:

Subscripts here indicate time, not space: these are successive states of A and B

A0 = 1011
B0 = 1100

A1 = A0 XOR B0 = 0111
B1 = A1 XOR B0 = 1011
A2 = A1 XOR B1 = 1100


This really clarified it for me, thank you.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2